《计算机算法设计与分析》试卷2000(网络)(答案).docVIP

《计算机算法设计与分析》试卷 （计算机学院2000级（网络），2003.12.12） 姓名 学号 班级 成绩 一、简答（20分） 1．简述用贪心策略和动态规划进行问题求解的一般方法。 2．已知G=（V，E）如下所示。 二、化简递推关系式（15分） 三、带权有向图如下图所示。利用算法SHORTEST-PATH（算法3.10）求从结点1到其余各结点的最短路径长度。要求：用结点集S和各结点DIST值的变化情况描述算法的执行轨迹，并画出相应的最短路径生成树。（20分） 迭代 选取的结点 S DIST (1) (2) (3) (4) (5) (6) 置初值 1 2 3 4 － 2 4 3 5 1 1,3 1,3,2 1,3,2,6 1,3,2,6,4 0 20 15 +∞ +∞ +∞ 0 19 15 +∞ +∞ 25 0 19 15 +∞ 29 25 0 19 15 28 29 25 0 19 15 28 29 25 四、求标识符集合(a1,a2,a3,a4)＝(case，for，print，while)的最优二分检索树（标识符大小按字母顺序定义）：已知成功检索概率为P(1)=1/6，P(2)=1/12，P(3)=1/6，P(4)=1/12；不成功检索概率为Q(0)=1/12，Q(1)=1/12，Q(2)=1/8，Q(3)=1/8，Q(4)=1/12。并画出该树的形态。（25分） 五、已知n个整型数的集合A={a1,a2,…,an}和一个整数X。设计一个算法，检 查A中是否存在这样的两个元素ai和aj，使得ai＋aj＝X，1≤i,j≤n。要 求：若存在这种情况，则至少输出一对这样的元素的下标；若不存在，则 输出“not exist.”，并分析你所设计的算法的时间复杂度。（20分） 3 2 1 4 BFS检索到的结点序列是： DFS检索到的结点序列是： D_SEARCH检索到的结点序列是： w(0,1)=w(0,0)+P(1)+Q(1)=1/12+1/6+1/12=1/3 C(0,1)=1/3 R(0,1)=1 w(1,2)=w(1,1)+P(2)+Q(2)=1/12+1/12+1/8=7/24 C(1,2)=7/24 R(1,2)=2 w(2,3)=w(2,2)+P(3)+Q(3)=1/6+1/6+1/8=11/24 C(2,3)=11/24 R(2,3)=3 w(3,4)=w(3,3)+P(4)+Q(4)=1/8+1/12+1/12=7/24 C(3,4)=7/24 R(3,4)=4 w(0,0)=Q(0)=1/12 C(0,0)=0 R(0,0)=0 w(1,1)=Q(1)=1/12 C(1,1)=0 R(1,1)=0 w(2,2)=Q(2)=1/8 C(2,2)=0 R(2,2)=0 w(3,3)=Q(3)=1/8 C(3,3)=0 R(3,3)=0 w(4,4)=Q(4)=1/12 C(4,4)=0 R(4,4)=0 3 w(0,2)=w(0,1)+P(2)+Q(2)=1/3+1/12+1/8=13/24 C(0,2)=13/24 + min(7/24,1/3)=13/24+7/24=20/24 R(0,2)=1 w(1,3)=w(1,2)+P(3)+Q(3)=7/24+1/6+1/8=14/24 C(1,3)=14/24+min{11/24,7/24}=14/24+7/24=21/24 R(1,3)=3 w(2,4)=w(2,3)+P(4)+Q(4)=11/24+1/12+1/12=15/24 C(2,4)=15/24+min{7/24,11/24}=15/24+7/24=22/24 R(2,4)=3 w(0,3)=w(0,2)+P(3)+Q(3)=13/24+1/6+1/8=20/24 C(0,3)=20/24+min{21/24,1/3+11/24,20/24}=20/24+19/24=39/24 R(0,3)=2 w(1,4)=w(1,3)+P(4)+Q(4)=14/24+1/12+1/12=18/24 C(1,4)=18/24+min{22/24,7/24+7/24,21/24}=18/24+14/24=32/24 R(1,4)=3 w(0,4)=w(0,3)+P(4)+Q(4)=20/24+1/12+1/12=24/