重庆大学算法设计分析第3次1答案

1、作业 试卷总分:100 得分:100 一、填空题(共 (共 10 道试题,共 30 分) 1.矩阵连乘问题的算法可由_实现。 答案:动态规划2.一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为_。 答案:O(n)3.S(n)=O(f(n)，其中n为_，S(n)表示空间复杂度。 答案:问题的规模4.有如下递归过程： void reverse (int n) printf(“%d”,n%10); if(n/10!=0) reverse(n/10); 如果n是m位十进制的整数，则上述程序的时间复杂度用m可以表示为_。 答案: 5.归并排序算法是用 _

2、 策略实现对n个元素进行排序的算法。 答案:分治6.在JAVA语言中，执行特定认为的任务的函数或过程统称为 _ 。 答案:方法7.O记号在算法复杂性的表示法中表示_ 。 答案:渐进确界或紧致界8.算法的基本操作的重复执行次数与 _ 有关。 答案: 9.直接或间接地调用自身的算法称为 _ 算法。 答案:递归10.Edmonds-Karp算法规定，在剩余网络中采用 _寻找_路径作为增广路径。 答案:软件，最佳二、简答题(共 (共 6 道试题,共 30 分) 1.设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; j=0; while(ij) j+; else

3、i+; (2)x=n;y=0 while (x=(y+1)*(y+1) y+; (3) x=91; y=100; while(y0) if(x100) x=x-10;y-; else x+; 答案:(1) T(n)=O(n) (2) T(n)= O(n 0.5 ) (3) T(n)=O(1)2.三数取中选择中心点所划分成的两子数组其长度比例不低于1:7的概率超过90%。在绝大多数情况下，快速排序的时间不会超过多少？ 答案: 3.设图是一个流网络，f为G的流，(S,T)为G的一个割，证明|f|=f(S,T)。 答案: 4.若n=4，在机器M1和M2上加工作业i所需要的时间分别为ai和bi，且(a

4、1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)。求4个作业的最优调度方案，并给出最优值。 答案: 5.有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动_。图 答案:1，4，8，116.给出将十进制整数表达为二进制整数的标准算法的伪代码描述。 答案: 三、问答题(共 (共 4 道试题,共 40 分) 1.有面值分别为1、5和11单位的硬币，希望找回总额为15单位的硬币，贪心算法的思路和最优解分别是什么？ 答案:假设当前的找回总额为a，贪心算法总是在可行的选择中寻找小于等于a的最大值b，然后改变找回额，即a=a-b，重新上面的过程直到不能继续为止。按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。最优的解应是3个5单位面值的硬币。2.请概述最小代价生成树的贪心选择性质，并证明。 答案: 3.简述贪心算法的基本思想？ 答案:贪心算法是通过做一系列的选择来给出某一问题的最优解的对算法中的每一决策点，做一个当时(看起来像是)最佳的选