一．填空题（每空2分，共30分） 1．计算复杂性包括 两个方面。 2．在忽略常数因子的情况下，?提供了算法运行时间的一个 界。 3．算法的平均情况下时间复杂性A(n)=?p(I)t(I)，其中Dn表示大小为n的输I?Dn入集合，t(I)表示输入为I时算法的运算时间, p(I)表示 。 4．从算法时间复杂性的角度看，时间复杂性阶为 的算法是实际可接受的。 5．用动态规划算法解题时， ，算法的效率越高。 6．分治算法的基本步骤包括 。 7．回溯算法的搜索顺序是 。 8．贪心法通常用于求解 问题。 9．PQ式的分支限界法中，活结点表的结构是 。 10．Prim算法、 Dijkstra算法、快速排序算法和Huffman算法中 不是贪心算法。 11．一个问题满足递归关系是指 。 12．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间 。 13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤 ，就可得到一个随机化查找算法。 算法 BISEARCH 输入：正整数n，n个元素的升序数组A[1..n]和元素x。 输出：如果存在j，1<=j<=n使得x=A[j]，则输出j，否则输出0。 1. low=1; high=n ; j=0 2. while (low<=high) and (j=0) 3. mid=?(low?high)/2? 4. if x=A[mid] then j=mid 5. else if x
6. else low=mid+1 ＿＿＿＿＿号学 ＿＿ 栏＿＿ ＿ ＿ 名 姓 息 级 年 ＿ ＿ 信＿＿ ＿ ＿ 业 专 生＿＿ ＿ ＿ ＿ ＿ 系 考＿＿＿＿＿＿院学＿＿＿＿＿＿ 7. end if 8. end if 9. end while 10. return j end BISEARCH 14．下面算法的基本运算是 运算，该算法中第4步执行了 次。 算法 COUNT 输入：正整数n（n=2k）。 线 输出：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 37
2．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和nlog2n。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用?表示）。 算法 EX2 输入：正整数n，n=2k。 输出：… ex2(1, n) end EX2 过程 ex2(low, high) if low>=high then pro1( ) else m=?(low?high)/2? ex2(low, m) ex2(m+1, high) pro2(low, high) end if return end ex2 3．设矩阵M1，M2，M3，M4，M5的阶如下： M1：10?2 M2：2?5 M3：5?2 M4：2?4 M5：4?10。 下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果，
38
＿＿＿＿＿号学 ＿ 栏＿＿ ＿ ＿ ＿ 名 姓 息 级 年线 ＿ ＿ 信 ＿ ＿ ＿ ＿ 业 专订 生 ＿ ＿ ＿ ＿ ＿ ＿ 考系 ＿装＿＿＿＿＿院学＿＿＿＿＿＿
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]= S[3,3]=0 S[3,4]=4 S[3,5]=4 S[4,4]=0 S[4,5]=5 S[5,5]=0 表2 其中，C[i, j]表示求MiMi+1…Mj所需的最少数量乘法次数，S[i, j]表示相应的最优解信息。填充表1和表2中空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。 三．算法填空题（共34分） 1．（10分）下面是快速排序算法。 算法 QUICKSORT 输入：正整数n，n个元素的数组A[1..n]。 输出：按非降序排列的数组A中的元素。 quicksort(A,1,n) end QUICKSORT 过程 quicksort(A, low, high) // 将A[low..high]中的元素按非降序快速排序。 if low quichsort( (1) ) quichsort( (2) ) end if end quicksort 过程 SPLIT ( A, low, high) //以A[low]为主元划分A[low..high], 返回主元的新位置。 i=low; x=A[low] for j=low+1 to high if A[j]<=x then i= (3) if i≠j then (4) end if end for (5) w=i return w end SPLIT 2. (10分)下面是用回溯法解n皇后问题的算法（求出所有解）。 n皇后问题：在n x n棋盘上放置n个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。） 算法 NQUEENS 输入：正整数n。 输出：n皇后问题的一个解x[1..n], 若无解，则输出No solution。 flag=false k=1 ; x[1]=0 40