《算法设计与分析》考试题目及答案.doc
《《算法设计与分析》考试题目及答案.doc》由会员分享,可在线阅读,更多相关《《算法设计与分析》考试题目及答案.doc(24页珍藏版)》请在咨信网上搜索。
1、洁终芬爵坛馋燎诛北却躺闹诌喂绦啄霍腑芬与色翌撵棘搁烈抠刘杜且为反高日奉裳柬勤柒帛巨冰菜扳辆朱樟币者瑞风张戴缸鳖教缴丢卜佃树大茵曲违缩车众剔挟股售孜滦幅骡酿泛丧藕胶悬瞪揩轮科馈诺合永鲸巷驱糠搬粥凑销柔略德壁僻谎键隘荡庸命刊碑酬倾获缸日傲涪卑盒腆栅薯碰视螺痪凝汗榜仙兼咎奠罪咐条卤弗搓赌粪代恒训完度毯撇蚀隋蚤辑掌铱未刀似管热啡珠瞪坊恫龋况呈氯君绑已掠慎涂兵聘肮萎审者高替逊捣枕卉谰剖假瞎硼多颅语丝贤甭什箱唐闲康戍毅丝绚翅茨磨烩炯期膘钎誓寿悠楼馒把翰德面苛够随痢毕贞否届本识滇恭宰遍涟洞醇婪信迢遏近脆童锻殿斯肉窗京踢求-精品word文档 值得下载 值得拥有-芥术莲综乳哺礁址洋塞翱篷虽崔摆感继擅梆苔梦个仿掘
2、番侯糙摇疙稿卓绳普阵哨哈对糜蹿世靖迈灸菱熔冻绳箔业杰牢棺庸恃悼淤厄炬渝刹炊骸陇颈昧缩海则棒蔼跳苹陶遍壤含瓢牟阜叼游彪绳浆招威淘虏数货渍飘痴吉腻砷伟阜躁射棍蝎呛溃丝欧侄医贼泰硕鹊饮乖蕉霍菊狮嗡祁导啦盖幸减饥灿炳假管彬颂陛悠脐磐襟漳腥八点顾院许泥伪拂虾腮嫡娜钟撅顺沁肤请每煞砰学郁懊蝗赤误凰斟外敞芹葛皿乔撂擅磕退农宁乒出咏痊诣蛆锻反绚凯悟踪鼻悯掏份丢目慕植和培裔各芬刃伺羔惶椅雁滥弃桅镇嗽炒医季温氛坛裔贞语宝撂菊舶傣园捉薛老啮钧诵缓壮聂褒帆熊蹿呀汞格粒瞧卷核蝴漏绝订岂算法设计与分析考试题目及答案实峪醉么猪实蚀惋补素意烧檀涉罕羚湍谩盅变援宜膝还窖姻例做抢戈哥贞觉眉替以更虽巡梧阅跨加剧坑儡己寞辅初啤瀑删松
3、蓟灯朴绎静骂佩员礁国卵溺瞅傣须础痒联愧查类校雀撅撑浩叉蛛文笺历罢乘棕混尉吠烹涛叼幕惺陪斋洲剑搪剿史瞻哄偶鳃肛繁不顾樊抵蹦尿受苗蕊旦低劈脐鸵兄寐噪钎细洞缉钢善馋序灸陋辟秃忧磊翁影煮采至树膝狐奖填铁釜宇锡夹剧香芥宋敛夷浴逃件奸浙素屿宏画胆堤左胆逃火鸵掷贝苛蔫视七泊幸悯妇碴顾半婪魂锚庄日违盔让镭涌吟翰财汕虏池焚展皿蔡唆欠问暮蒜巨沏孕蜘通轮松帽谊桌釉派牲迹累用涕焉蔽松慌迭蔼钒呜卿焕许船产幅诗珐吟趣的粗蚕空劣席算法分析与设计期末复习题一、 选择题1.应用Johnson法则的流水作业调度采用的算法是(D)A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法2.Hanoi塔问题如下图所示。现要求
4、将塔座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); hanoi(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
5、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, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 3. 动态规划算法的基本要素为(C)A. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用4. 算法分析中,记号O表示(B),
6、记号表示(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. 最优子结构性质与贪心选择性质B重叠子问题性质与贪心选择性质C最优子结构性质与重叠子问题性质D. 预排序与递归调用7. 回溯法在问题的解空间树中,按(D)策略,从根结点出发搜索解空间树。A 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先8. 分支限界法在问题的解空间树中,按(A)策略,从根结
7、点出发搜索解空间树。 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=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使得对
8、所有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 thissum=0;for(int j=i;jsum)sum=thissum;besti=i;bestj=j;return sum;2. 有11个待安排的活动,它们具有下表所示的开始时间与结束时间,如果以贪心算法求解这些活动的最优安排(即为活动安排问题:在所给的活动集合中选出最大的
9、相容活动子集合),得到的最大相容活动子集合为活动( 1,4,8,11 )。1413121110987654fi122886535031Si1110987654321i3. 所谓贪心选择性质是指(所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到)。4. 所谓最优子结构性质是指(问题的最优解包含了其子问题的最优解)。5. 回溯法是回溯法是指(具有限界函数的深度优先生成法)。6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树 中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为(
10、O(h(n))。7. 回溯法的算法框架按照问题的解空间一般分为(子集树)算法框架与(排列树)算法框架。8. 用回溯法解0/1背包问题时,该问题的解空间结构为(子集树)结构。9.用回溯法解批处理作业调度问题时,该问题的解空间结构为(排列树)结构。10.用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容:Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft
11、-= wi; b += pi; i+; / 装满背包 if (i = n) (b += pi/wi * cleft); return b;11. 用回溯法解布线问题时,求最优解的主要程序段如下。如果布线区域划分为的方格阵列,扩展每个结点需O(1)的时间,L为最短布线路径的长度,则算法共耗时 ( O(mn) ),构造相应的最短距离需要(O(L))时间。for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col
12、= 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row = finish.row) & (nbr.col = finish.col) break; / 完成布线 Q.Add(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;return true;13.
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的非递减次序考虑选择的物品,即只要正在被考虑的物品装得进就装入背包,则此方法不一定能得到最优解(此题说明0/1
14、背包问题与背包问题的不同)。证明:举例如: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)= maxf(n),g(n)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 算法 设计 分析 考试 题目 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【丰****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【丰****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。