《算法设计分析参考资料重庆大学网络教育.docx》由会员分享，可在线阅读，更多相关《算法设计分析参考资料重庆大学网络教育.docx（16页珍藏版）》请在金锄头文库上搜索。
1、算法设计分析参考资料一、单项选择题（本大题共。分，共60小题，每小题0分）C1.算法的时间复杂度是指（）C.算法执行过程中所需要的基本运算次数C2.衡量一个算法好坏的标准是（）。C. 时间复杂度低D3.在最长公共子序列问题中，如果定义ci,j为Xl.Xi和YL.Yj的最长公共子序列的长 度，则长度为m的X序列与长度为n的Y序列的最长公共子序列的长度为（）。D. cm,nD4.以下关于贪心算法，不正确的说法是（）。D.所需求解的问题可以不满足最优子结构性质C5.合并排序法的基本思想是：将待排序元素分成大小大致相同的（）个子集合，分别对 每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好
2、序的集合。C. 2C6.对于n个元素的排序问题，n = 2时,只要作（）次比较即可排好序。C. 1A7.二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取an/2与x进 行比较：如果（），则只要在数组a的左半部继续搜索X。A. xOand.匕=yrmax(c/ - hy.7 H) if /0311(1. = i厂D.同一行的下一列A15.活动选择问题就是在所给的活动集合中，选出（）的相容活动子集。A.当前可选活动中结束时间最早的活动A16. 一个长度为n英寸的钢管的最优切割问题，总共有（）个不同的子问题。A. n+1对于 aeklu 五个字符,及其频度数据：=0.32, =0.25,
3、 =0.20, =0.18, =0.05。请用 Huffmann 算法构造其Huffmann树。11.参考答案：对于aeklu五个字符，及其频度数据：=0.32, =0.25, =0.20, =0.18, =0.05。请 用Huffmann算法构造其Huffmann树。由题可知字符a,e,k,l,u五个字符的权值分别为0.32,0.25,0.20,0.18,0.05。先由两个权值最小的字符作为叶子节点构造二叉树，即l,u。则权值变为 0.32,0.25,0.20,0.23再选择权值最小的节点构造二叉树，即0.20,0.23则权值变为0.32,0.25, 0.43（3）同理选择0.32和0.25
4、对应的节点作为叶子节点,则权值变为0.57,0.43（4）只剩下两个则继续构造，权值变为1,构造结束。结构为：12.有如下四个矩阵：=50 10 & = 1。. 40 C = 40 x 30 D = 30 x 5 请计算（双乂。）所需要的总的数乘次数，并说明计算方法。11. 参考答案： 由题中(A(B(CD)的计算顺序可得: mA,D = mC,D + mB,CD + mA,B(CD) 首先计算CD：mC,D = 40 x 30 X 5 = 6000那么相乘后矩阵大后F： (CD)- 40X5mB,CD = 10 x 40 x 5 = 2000相乘后矩阵f、(B(CD) 10X5mA,B(CD
5、) - 50 X 10 X 5 = 2500因此总的相乘次数为：60。0 + 2000+ 2500 = 1050013.有5个关键字，其搜索概率如下：pl = 0.25, p2 = 0.2, p3 = 0.05, p4 = 0.2, p5 = 0.3. 请计算上述二又搜索树的搜索代价的数学期望。13.参考答案：j度索次数d(i)受索概率Pi1Ip. 2520.2320. 054I0.2520.3搜索期望 = 1 + Sr=1d(i)-P1E=l+(l*0. 25+0*0. 2+2*0. 05+1*0. 2+2*0. 3)14. 对于钢管切割问题的下述价格表：length/ |123456789
6、1()priceyI_589K)1717202430请计算rl. r5o14. 参考答案：由算法自底向上版本BOTTOM-UP-CUT-ROD(p,n)1 let r0.nbe a new arrayr0=02 for j=l to nq=3 for i=l to j6q=max(q,pi+rj-l)7 rj=qreturn rn有以上算法可以解出rUJ(1)当 j=l 时，i=l,则 q=max;所以，rl=l.当j=2时，当i=l时，所以，r2=5.同理 j=3,4,5 时，可计算出 r3=8;r4=10;r5=13.112345148 10 1315. Ford-Fulkerson算法的
7、主要问题是什么？15. 参考答案：当最大流值较大时可能发生的情况是每次寻找出来的增广路径，都只能将流 网络的流量增加很小的值，这样的话，会大大增加循坏的次数。尤其是|f*|=2|E|dri=2! B 时，算法的时间复杂度变成流网络规模O(|V| + |E|)的指数函数0(|E|2|E|)。16. 何谓P、NP、NPC问题。16. 参考答案：P问题也就是多项式复杂度的问题；NP问题就是多项式复杂度非确定性问 题；NPC问题是指只有把解域里面所有可能都穷举了之后才能得到答案，这样的问题是NP 里面最难的问题，这类问题就是NPC问题。17. 有11个待安排的活动，它们具有下表所示的开始时间与结束时间
8、，如果以贪心算法求解这些活动的最优安排(即为活动安排问题：在所给的活动集合中选出最大的相容活动了集 合)，得到的最大相容活动子集合为活动，I1234567891011Si13053568812fi456789101112131418, 描述分治法与动态规划法的的异同。18. 参考答案：分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先 求解子问题，然后从这些子问题的解得到原问题的解；两者的不同点是：适合于用动态规划 法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解 得到的子问题往往是互相独立的。19. 设是一个流网络，f为G的流，(S,T)为G的
9、一个割，证明|f|=f(S,T)o参考答案：Ifl = f(s,V)= f(S,V)-f(S-s,V)= f(S,V) vt S - s = f(S,T) + f(S,S)=f(S,T)|f|=f (s,V) =f (S,V) -f (S-s,V) =f (S,V)tS-s=f (S,T) +f (S,S) =f (S,T)按增长率由小至大的顺序排列下列各函数：20.按增长率由小至大的顺序排列下列各函数：2、(3/2) (2/3) n* ,峪，n! , 2*, Ign. nJ*参考答案(2/3)B 2*00 lgn n05 n,CB (3/2) 2n n! nB五、问答题(本大题共0分，共20
10、小题，每小题0分)1. 什么是最优子结构性质？五、问答题(0分，共20题，每小题0分)参考答案：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策 所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略 总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。1. 什么是算法的数据输入、输出性？2. 参考答案：具有数据输入：一个算法有零个或多个数据输入，它们是在算法开始之前对 算法最初赋予的量，这些输入取自特定的对象集合。具有数据输出：一个算法产生一个或多个输出，它们是同输入有某种特定关系的量。3. 试给出归并排序的复杂度分析。2. 参考答案：合并
11、两个长度为n/2的子序列的时间复杂度为O(n)o比较两个元素大小的时 间为0(1),而每次比较都会从其中一个子序列中取出一个元素放到合并空间中，因此比较 的总次数不会超过n次，时间复杂度为O(n)o同时，其中一个子序列中的元素都被取出为 止，合并的过程不会停止，所以时间复杂度满足O(n)。3. 试叙述流网络的基本性质。4. 参考答案：(1)容量限制；(2)流量守恒阐述动态规划算法与分治法不同之处。4. 参考答案：与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题 往往不是互相独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指 数时间。5.
12、己知变量x和y中分别存放了数据，交换其中的数据。请用自然语言描述算法。5. 参考答案：为了交换，需要引进一个中间变量m,其算法如下： 将x中的数据送给 变量m,即x-m；将y中的数据送给变量x,即y-x；将m中的数据送给变量y, 即 m-*yo请概述最小代价生成树的贪心选择性质，并证明。6. 参考答案：贪心选择的性质指的是局部最优选择可以得到全局最优解决方案，在最小代 价生成树中，其表现为每次选择的为当前可选情况下权值最小的边。证明：(1) 一定有一个最优解包含了当前权值最小的边烦。假设最优解不包含该边，则将e，nin加入其中，会形成一个环，任意去掉环里比emin权值大的一条边，则形成了一 个
13、更优的解，与假设矛盾。(2)选择了Fmm后，子问题为去掉了关联的点的剩余的点为顶点集，剩余的边为 边集的图的最小代价问题，规模变小，性质不变。通过归纳法，其可以通过贪心性质得到最 优解.7. 描述Ford-Fulkerson算法基本步骤。6. 参考答案：(1)开始的时候，所有的节点u,vGV间的流值都为0,即f(u,v)=0。(2)在每一次迭代中，我们将流网络G的流量进行增加，方法就是在一个关联的“剩余网络” Gf中寻找一条“增广路径”。一旦知道Gf中的-条增广路径的边，就可以很容易辨别出G 中的对应的边，我们可以对这些边上的流值进行修改，从而增加流量(3)重复第2的操作， 直到剩余网络中不再
14、存在增广路径为止。7. 用伪代码或程序语言写出二分搜索的算法，并分析其时间复杂度。8. 参考答案：int binary_search( int *a, int nz int key) (int mid, front=0, back=n-l;while (front=back) (mid = (front+back)/2;if (amid=key)return mid;if (amidkey)front = mid+1;elseback = mid-1;)return -1;)时间复杂度O(log(n)9. 简述分治法在每一层递归上的三个步骤的具体内容。8. 参考答案：分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子 问题；
