算法设计与分析试题2011补考

《算法设计与分析试题2011补考》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国科学院研究生院课程编号：711008Z-1试题专用纸课程名称：计算机算法设计与分析试卷B任课教师：陈玉福———————————————————————————————————————————————姓名学号成绩一．(25分)下面是归并排序算法（递归程序）MergeSort(low,high)//A[low:high]是一个全程数组，含high-low+1//个待排序的元素integerlow,high;iflow

2、t(mid+1,high)//将第二子组排序Merge(low,mid，high)//合并两个已经排序的子数组endifendMergeSort用表示执行该程序所用的时间，并假定，且合并子程序Merge所用时间与成正比，即，是正实数。1．写出该程序所用时间的递推关系式；2．当时，解上述递推关系式得到的表达式；3．证明：对于一般的，有。解：一．(25分)按要求解答下列问题1．用动态规划的思想考虑0/1背包问题：证明：0/1背包问题具有最优子结构性质；2．考虑如下0/1背包问题：试用动态规划方法解之（写出步骤和最优解）。解：二．(25分)用动态规划算法解多段图问题

3、，即求从源点s到目标点t的最短路径：1．说明多段图问题具有最优子结构性质；2．写出多段图问题最优值的递推公式；3．给出下图问题的一个最优解并写出基本计算步骤。4．共2页第1页V1V2V3V4V51ts3729224611781134526554453267891011121一个5阶段的网络图三．(25分)假定已知“无向图的Hamilton圈”问题是NPC问题，证明“旅行商判定问题”也是NPC问题。说明“旅行商最优问题”不是NPC问题。回答下列问题共2页第2页