05计本算法设计与分析期考试卷(C卷).doc

一．填空题（每空2分，共30分） 1．计算复杂性包括 两个方面。 2．在忽略常数因子的情况下，提供了算法运行时间的一个 界。 ，其中Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示 。 4．从算法时间复杂性的角度看，时间复杂性阶为 的算法是实际可接受的。5．。 6． 7．。贪心法 问题。．PQ式的分支限界法中，活结点表的结构是 。 ．Prim算法 Dijkstra算法算法和Huffman算法中 不是贪心算法。11．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间 。 4. if x=A[mid] then j=mid 5. else if xA[mid] then high=mid-1 考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿ 装 订 线 else low=mid+1 7. end if 8. end if 9. end while 10. return j end BISEARCH 14．下面算法的基本运算是 运算，该算法中第4步执行了 次。 算法 COUNT 输入：正整数n（n=）。 输出：count的值。 1. count=0 2. while n=1 3. for j=1 to n 4. count =count+1 5. end for 6. n=n/2 7. end while end COUNT 二．计算题和简答题（每小题7分，共21分） 1．用表示下列各函数的阶，并按阶从低到高的顺序排列这些函数。 n3/(n+5) , 2n+ 3n/2, 5n2log3n+n3log2n, n!+nn, log(logn)/1000 2．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。 算法 EX2 输入：正整数n，n=2k。 输出：… ex2(1, n) end EX2 过程 ex2(low, high) if low=high then pro1( ) else m= ex2(low, m) ex2(m+1, high) pro2(low, high) end if return end ex2 3．设矩阵M1，M2，M3，M4，M5的阶如下： M1：102 M2：25 M3：52 M4：24 M5：410。 下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果， 考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏 ＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿ 专业 ＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿ 学号＿＿＿＿＿ 装 订 线 C[1,1]=0 C[1,2]=100 C[1,3]=60 C[1,4]= C[1,5]= C[2,2]=0 C[2,3]=20 C[2,4]=36 C[2,5]= C[3,3]=0 C[3,4]=40 C[3,5]=180 C[4,4]=0 C[4,5]=80 C[5,5]=0 表1 S[1,1]=0 S[1,2]=2 S[1,3]=2 S[1,4]= S[1,5]= S[2,2]=0 S[2,3]=3 S[2,4]=4 S[2,5