高品质文库网

算法设计与分析试题2011补考
收录时间:2022-11-25 22:59:54  浏览:0
中国科学院研究生院 课程编号: 711008Z-1 试 题 专 用 纸 课程名称:计算机算法设计与分析试 卷 B 任课教师:陈玉福 姓名 学号 成绩 一 (25分)下面是归并排序算法(递归程序)MergeSort(low/ high) / Alow/ 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 给出下图问题的一个最优解并写出基本计算步骤。4 共 2 页 第 1 页V1 V2 V3 V4 V51ts3729224611781134526554453267891011121一个5阶段的网络图四 (25分) 假定已知“无向图的Hamilton圈”问题是NPC问题,证明“旅行商判定问题”也是NPC问
温馨提示:
1. 高品质文库网仅展示《算法设计与分析试题2011补考》的部分公开内容,版权归原著者或相关公司所有。
2. 文档内容来源于互联网免费公开的渠道,若文档所含内容侵犯了您的版权或隐私,请通知我们立即删除。
3. 当前页面地址:https://www.gpinxiao.vip/doc/9fb219d13bb4c531.html 复制内容请保留相关链接。