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

福建师范大学数学与计算机科学学院2006 2007学年第二学期考试 C 卷考生信息栏学院系 专业 年级姓名 学号装 订 线 专 业：计算机科学与技术 年 级： 2005级 课程名称: 算法设计与分析 任课教师： 潘日晶 试卷类别：开卷（ ）闭卷（） 考试用时： 120 分钟考试时间: 年 月 日 午 点 分题号一二三四五总得分评卷人得分题号六七八九十得分一填空题（每空2分，共30分）1计算复杂性包括 两个方面。2在忽略常数因子的情况下，提供了算法运行时间的一个 界。3算法的平均情况下时间复杂性A(n)=，其中Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间, p(I)表示 。4从算法时间复杂性的角度看，时间复杂性阶为 的算法是实际可接受的。5用动态规划算法解题时， ，算法的效率越高。6分治算法的基本步骤包括 。7回溯算法的搜索顺序是 。8贪心法通常用于求解 问题。9PQ式的分支限界法中，活结点表的结构是 。10Prim算法、 Dijkstra算法、快速排序算法和Huffman算法中 不是贪心算法。11一个问题满足递归关系是指 。12随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间 。13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤 ，就可得到一个随机化查找算法。 算法 BISEARCH 输入：正整数n，n个元素的升序数组A1.n和元素x。输出：如果存在j，1=j=n使得x=Aj，则输出j，否则输出0。1. low=1; high=n ; j=02. while (low=high) and (j=0)3. mid= 4. if x=Amid then j=mid5. else if x=1 3. for j=1 to n 4. count =count+1 5. end for6. n=n/27. 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 ex23设矩阵M1，M2，M3，M4，M5的阶如下：M1：102 M2：25 M3：52 M4：24 M5：410。 下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果， 考生信息栏学院系 专业 年级姓名 学号装 订 线C1,1=0 C1,2=100 C1,3=60 C1,4= C1,5= C2,2=0 C2,3=20 C2,4=36 C2,5= C3,3=0 C3,4=40 C3,5=180 C4,4=0 C4,5=80 C5,5=0 表1 S1,1=0 S1,2=2 S1,3=2 S1,4= S1,5= S2,2=0 S2,3=3 S2,4=4 S2,5= S3,3=0 S3,4=4 S3,5=4 S4,4=0 S4,5=5 S5,5=0 表2其中，Ci, j表示求MiMi+1Mj所需的最少数量乘法次数，Si, j表示相应的最优解信息。填充表1和表2中空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。三算法填空题（共34分）1 （10分）下面是快速排序算法。算法 QUICKSORT 输入：正整数n，n个元素的数组A1.n。 输出：按非降序排列的数组A中的元素。 quicksort(A,1,n) end QUICKSORT 过程 quicksort(A, low, high) / 将Alow.high中的元素按非降序快速排序。 if lowhigh then w=SPLIT( A, low, high) quichsort( (1) ) quichsort( (2) ) end ifend quicksort过程 SPLIT ( A, low, high)/以Alow为主元划分Alow.high, 返回主元的新位置。 i=low; x=Alow for j=low+1 to high if Aj=x then i= (3) if ij then (4) end if end for (5) w=i return wend SPLIT2. (10分)下面是用回溯法解n皇后问题的算法（求出所有解）。n皇后问题：在n x n棋盘上放置n个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。）算法 NQUEENS输入：正整数n。输出：n皇后问题的一个解x1.n,若无解，则输出No solution。flag=false k=1 ; x1=0考生信息栏学院系 专业 年级姓名 学号装 订 线while (1) while xkmax then max=a (3) end ifend forfi, j= (4) (5) end ifend ifreturn fi, jend knapsack算法 KNAPSACK_SOLUTION输入：物品种数n , 背包容量C, n种物品的体积数组s1.n, 相应的可复选的背包问题的最优解信息数组H0.n, 0.C。输出：相应的可复选的背包问题的最优解x1.n。y=C; xn=Hn, Cfor i=n-1 to 1y= (6) xi= (7) end forreturn x1.nend KNAPSACK_SOLUTION四算法设计题（15分）1. 设有n种不同面值的硬币，面值分别为