算法设计与
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
2003A
《算法设计与分析》试题
(2003年1月)
一( 下面是一个无向图及其邻接链表
B C 0 A A
D E 0 A B C B F G 0 A C
B H 0 D E F G D B H 0 E
F C H 0 H G C H 0
H 无向图G及其邻接链表 F G 0 D E
1( 给出宽度优先搜索生成树，并在各个顶点旁标出该顶点被
搜索的序号;
2( 给出深度度优先搜索生成树，并在各个顶点旁标出该顶点
被搜索的序号;
二( 下面是归并排序算法(递归程序):
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) //合并两个已经排序的子数组
endif
end MergeSort
1
用表示执行该程序所用时间，并假定，合并子程序MergeT(n)T(1),a
ncnc所用时间与成正比，即，是正实数。
1( 写出该程序所用时间的递推关系式; T(n)
k2( 当时，解上述递推关系式得到的表达式; T(n)n,2
n3( 证明:对于一般的，有; T(n),O(nlogn)
三( 考虑如下的0/1背包问题:
(p,p,p,p),(10,15,6,4)(w,w,w,w),(4,6,3,2) ，，，。 M,12n,412341234
考虑用优先队列式分枝限界法(可用LC,分枝限界法)解此问题，但不必写出算法。
1( 画出执行你的算法搜索解空间树时所生成的子树;
2( 给出该例问题的一个最优解。
四( 用动态规划算法解多段图问题，即求从源点s到目标点t的最
短路径:
1( 说明多段图问题具有最优子结构性质;
2( 写出多段图问题最优值的递推公式;
3( 给出下图问题的一个最优解。
V V V V V 12345
9 2 4 6
9 4 4 6
2 5
3 7 2
S 7 3 2 t 7 1 10 12 3 1
4 11 5
2 5
8 11 6 11 5 8
一个5阶段的网络图
五( 考虑用贪心算法解最优生成树问题，即求加权无向图的具有最
小权的生成树:
1( 叙述Kruskal算法的基本思想(或
步骤
新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤
);
2( 证明:Kruskal算法对于每一个无向连通图G都产生一颗最
小生成树。
2
浙公网安备 33021202002483