算法设计与分析考试题目及答案(DOC 17页).docx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《算法设计与分析考试题目及答案(DOC 17页).docx》由用户(2023DOC)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析考试题目及答案DOC 17页 算法 设计 分析 考试 题目 答案 DOC 17
- 资源描述:
-
1、Newly compiled on November 23, 2020算法设计与分析考试题目及答案算法分析与设计期末复习题一、 选择题1.应用Johnson法则的流水作业调度采用的算法是(D)A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上,并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为:(B)A. void hanoi(int n, int A, int C, int B) if (n 0) hanoi(n-1,A,C, B); move(n,a,b); h
2、anoi(n-1, C, B, A); Hanoi塔B. void hanoi(int n, int A, int B, int C) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); C. void hanoi(int n, int C, int B, int A) if (n 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); D. void hanoi(int n, int C, int A, int B) if (n 0) hanoi(n-1,
3、A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 3. 动态规划算法的基本要素为(C)A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用4. 算法分析中,记号O表示(B), 记号表示(A), 记号表示(D)。A.渐进下界B.渐进上界C.非紧上界D.紧渐进界E.非紧下界5. 以下关于渐进记号的性质是正确的有:(A)A.B. C. O(f(n)+O(g(n) = O(minf(n),g(n) D. 6. 能采用贪心算法求最优解的问题,一般具有的重要性质为:(A)A. 最优子结构性质与贪心选择性
4、质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中,按(A)策略,从根结点出发搜索解空间树。 A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先9. 程序块(A)是回溯法中遍历排列树的算法框架程序。void backtrack (int t) if (tn) output(x); else for (int i=t;in) output(x); else for (int i=
5、0;in) output(x); else for (int i=0;in) output(x); else for (int i=t;i0,存在正数和n0 0使得对所有nn0有:0 f(n)0,存在正数和n0 0使得对所有nn0有:0 cg(n) 0,存在正数和n0 0使得对所有nn0有:0 f(n)0,存在正数和n0 0使得对所有nn0有:0 cg(n) f(n) ;二、 填空题1. 下面程序段的所需要的计算时间为( )。int MaxSum(int n, int *a, int &besti, int &bestj)int sum=0;for(int i=1;i=n;i+) int th
6、issum=0;for(int j=i;jsum)sum=thissum;besti=i;bestj=j;return sum;2. 有11个待安排的活动,它们具有下表所示的开始时间与结束时间,如果以贪心算法求解这些活动的最优安排(即为活动安排问题:在所给的活动集合中选出最大的相容活动子集合),得到的最大相容活动子集合为活动( 1,4,8,11 )。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指(所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到)。4. 所谓最优子结构性质是指(问题的最优解包含了其子问题的
7、最优解)。5. 回溯法是指(具有限界函数的深度优先生成法)。6. 用回溯法解题的一个显着特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为(O(h(n))。7. 回溯法的算法框架按照问题的解空间一般分为(子集树)算法框架与(排列树)算法框架。8. 用回溯法解0/1背包问题时,该问题的解空间结构为(子集树)结构。9.用回溯法解批处理作业调度问题时,该问题的解空间结构为(排列树)结构。10.用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内
8、容:Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) (b += pi/wi * cleft); return b;11. 用回溯法解布线问题时,求最优解的主要程序段如下。如果布线区域划分为的方格阵列,扩展每个结点需O(1)的时间,L为最短布线路径的长度,则算法共耗时 ( O(mn) ),构造相应的最短距离
9、需要(O(L))时间。for (int i = 0; i NumOfNbrs; i+) = + offseti.row; = + offseti.col; if (grid = 0) / 该方格未标记 grid = grid + 1; if ( = & = ) break; / 完成布线 (nbr); 12. 用回溯法解图的m着色问题时,使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性,则需耗时(渐进时间上限)(O(mn)。Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;r
10、eturn true;13. 旅行售货员问题的解空间树是(排列树)。6.7.三、 证明题1. 一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1,且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间,则有:通过迭代法求得T(n)的显式表达式为:试证明T(n)的显式表达式的正确性。2. 举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品,即只要正在被考虑的物品装得进就装入背包,则此方法不一定
11、能得到最优解(此题说明0/1背包问题与背包问题的不同)。证明:举例如:p=7,4,4,w=3,2,2,c=4时,由于7/3最大,若按题目要求的方法,只能取第一个,收益是7。而此实例的最大的收益应该是8,取第2,3 个。3. 求证:O(f(n)+O(g(n) = O(maxf(n),g(n) 。证明:对于任意f1(n) O(f(n) ,存在正常数c1和自然数n1,使得对所有nn1,有f1(n) c1f(n) 。类似地,对于任意g1(n) O(g(n) ,存在正常数c2和自然数n2,使得对所有nn2,有g1(n) c2g(n) 。令c3=maxc1, c2, n3 =maxn1, n2,h(n)=
12、 maxf(n),g(n) 。则对所有的 n n3,有f1(n) +g1(n) c1f(n) + c2g(n) c3f(n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n) = 2c3h(n) = O(maxf(n),g(n) .4. 求证最优装载问题具有贪心选择性质。(最优装载问题:有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。设集装箱已依其重量从小到大排序,(x1,x2,xn)是最优装载问题的一个最优解。又设 。如果给定的最优装载问题有解,则有。) 证明:四、
13、 解答题1. 机器调度问题。问题描述:现在有n件任务和无限多台的机器,任务可以在机器上得到处理。每件任务的开始时间为si,完成时间为fi,sifi 。si,fi为处理任务i的时间范围。两个任务i,j重叠指两个任务的时间范围区间有重叠,而并非指i,j的起点或终点重合。例如:区间1,4与区间2,4重叠,而与4,7不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此,在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。问题实例:若任务占用的时间范围是1,4,2,5,4,5,2,6,4,7,则按时完成所有任务最少需要几台机器(提示:使
14、用贪心算法)画出工作在对应的机器上的分配情况。2. 已知非齐次递归方程: ,其中,b、c是常数,g(n)是n的某一个函数。则f(n)的非递归表达式为:。现有Hanoi塔问题的递归方程为: ,求h(n)的非递归表达式。解:利用给出的关系式,此时有:b=2, c=1, g(n)=1, 从n递推到1,有:3. 单源最短路径的求解。问题的描述:给定带权有向图(如下图所示)G =(V,E),其中每条边的权是非负实数。另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法:现采用Dijkstra算法计算从源顶点
15、1到其它顶点间最短路径。请将此过程填入下表中。432110030maxint10-1初始dist5dist4dist3dist2uS迭代4. 请写出用回溯法解装载问题的函数。装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi,且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。解:void backtrack (int i) 用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分;试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同。/ 检查左儿子结
16、点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0 故Ew+rbestw总是成立。也就是说,此时右子树测试不起作用。为了使上述右子树测试尽早生效,应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加,因此,可以在算法每一次进入左子树时更新bestw的值。7. 最长公共子序列问题:给定2个序列X=x1,x2,xm和Y=y1,y2,yn,找出X和Y的最长公共子序列。 由最长公共子序列问题的最优子
展开阅读全文