中国科学院研究生院课程编号：711008z－1
试题专用纸课程名称：计算机算法设计与分析。
任课教师： 陈玉福。
姓名学号成绩。
一． 回答下列问题： (每小题5分)
1. 陈述算法在最坏情况下的时间复杂度和平均时间复杂度；这两种评估算法复杂性的方法各自有什么实际意义？
2. 阐述动态规划算法与贪心算法的区别，它们都有那些优势和劣势？
3. 阐述回溯算法与分枝限界算法的共同点和不同点，提高算法效率的关键是什么？
4. 在对算法进行复杂性分析时，强调渐进复杂性的意义是什么？
二． （20分）试用prim算法求解下面无向赋权图的最小生成树，指出最小生成树及该树中各边被选中的先后次序；写出算法的基本步骤。
三． （20分）用lc－分枝限界算法求解0/1背包问题： ，物品重量和价值分别是：
和 1. 画出由算法生成的状态空间树，并标明各节点的优先级的值；
2. 给出各节点被选作当前扩展节点的先后次序；
3. 给出最优解。
四． （20分）已知一组数满足，且被搜索的对象的概。
率分布是：共 2 页第 1 页。
其中表示被搜索对象在区间内的概率，表示被搜索对象为的概率，
使用动态规划算法求该搜索问题的最优二叉搜索树。
五．(20分) 假定已知“无向图的hamilton回路”问题是npc问题，证明“旅行商判定问题”也是npc问题。
共 2 页第 2 页。
算法设计与分析试题2019补考
中国科学院研究生院课程编号 711008z 1 试题专用纸课程名称 计算机算法设计与分析。试卷 b任课教师 陈玉福。姓名学号成绩。一 25分 下面是归并排序算法 递归程序 mergesort low,high a low high 是一个全程数组，含high low 1 个待排序的元素。intege...
2019算法设计与分析试题B
山东理工大学 算法设计与分析 试卷纸。b 卷 10 11学年第二学期班级姓名学号 装订线。山东理工大学 算法设计与分析 评分标准。b 卷 10 11学年第二学期班级姓名学号 装订线。简答题 每题5分，共20分 程序的时间复杂性和空间复杂性。算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的...
算法分析与设计期末
11.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需o 1 的时间，l为最短布线路径的长度，则算法共耗时 o mn 构造相应的最短距离需要 o l 时间。12.用回溯法解图的m着色问题时，使用下面的函数ok检查当前扩展结点的每一个儿子所相应的颜色的可用性...