中国科学院研究生院课程编号： 711008z-1
试题专用纸课程名称：计算机算法设计与分析。
试卷 b任课教师：陈玉福。
姓名学号成绩。
一． (25分)下面是归并排序算法（递归程序）
mergesort(low, high) /a[low: high]是一个全程数组，含high-low+1
/个待排序的元素。
integer low, high;
if low < high then
mid=(low+high)/2 //求当前数组的分割点。
mergesort(low, mid) /将第一子组排序。
mergesort(mid+1, high) /将第二子组排序。
merge (low, mid，high) /合并两个已经排序的子数组。
endifend mergesort
用表示执行该程序所用的时间，并假定，且合并子程序merge所用时间与成正比，即，是正实数。
1． 写出该程序所用时间的递推关系式；
2． 当时，解上述递推关系式得到的表达式；
3． 证明：对于一般的，有。
二． (25分) 按要求解答下列问题。
1． 用动态规划的思想考虑0/1背包问题：证明：0/1背包问题具有最优子结构性质；
2． 考虑如下0/1背包问题：
试用动态规划方法解之（写出步骤和最优解）。
三． (25分) 用动态规划算法解多段图问题，即求从源点s到目标点t的最短路径：
1． 说明多段图问题具有最优子结构性质；
2． 写出多段图问题最优值的递推公式；
3． 给出下图问题的一个最优解并写出基本计算步骤。
共 2 页第 1 页。
一个5阶段的网络图。
四． (25分) 假定已知“无向图的hamilton圈”问题是npc问题，证明“旅行商判定问题”也是npc问题。说明“旅行商最优问题”不是npc问题。回答下列问题。
共 2 页第 2 页。
算法设计与分析试题2019秋
中国科学院研究生院课程编号 711008z 1 试题专用纸课程名称 计算机算法设计与分析。任课教师 陈玉福。姓名学号成绩。一 回答下列问题 每小题5分 1.陈述算法在最坏情况下的时间复杂度和平均时间复杂度 这两种评估算法复杂性的方法各自有什么实际意义？2.阐述动态规划算法与贪心算法的区别，它们都有那...
2019算法设计与分析试题B
山东理工大学 算法设计与分析 试卷纸。b 卷 10 11学年第二学期班级姓名学号 装订线。山东理工大学 算法设计与分析 评分标准。b 卷 10 11学年第二学期班级姓名学号 装订线。简答题 每题5分，共20分 程序的时间复杂性和空间复杂性。算法的复杂性是算法运行所需要的计算机资源的量。需要时间资源的...
算法分析与设计期末
11.用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需o 1 的时间，l为最短布线路径的长度，则算法共耗时 o mn 构造相应的最短距离需要 o l 时间。12.用回溯法解图的m着色问题时，使用下面的函数ok检查当前扩展结点的每一个儿子所相应的颜色的可用性...