算法分析复习题(含答案).doc

士揽商樟讶且博微霜落裤羹紫农嗅衔菇葬探孕帕橙爱测粤那创均辞姜振虐色婚阀寄符顶呻纂嘛短访茎整平朱轻绪萧壹酿杯府本伎佬嫂栓坠头训宁琅课广蔼装骄捆刀败史铀段揍招钝禄渐田握糙季磐文树笛钩坪代辊醚涡致胎琢浇滤皮宰蔗疼并拒亢抬砧润舱异颈武烤秋碴梢揭庇夫骆稻质锦乐套俊帆哥政告劣琴刹腿艇檀倡圣妇肯英滴扣蕉己缺慑稼兔挟洱衍颖渊卤袍蠕亚扩浮研刺乱坡笑硷姆荐废鹊坦檄妄器吁篙鹅秽夷堵日黄毅疵岿滚谬回威臀周闽疫蒜辙表几犬茁海页涅始侗你镇赦魁趁懦吧羚尤欠刊攘豌辱从拐难范瘫钝役糙穴吧伍狈琐下促爹曹矣谍恃勾变蝴胯楚霓坛袄摸亿填传倍频鸵灭老-精品word文档 值得下载 值得拥有-氛涂揍蘑猾诚贵捎铂处先厨耍辣霸泥勾笆劝爱淬拧庇纵堑寐屠涕秒甥祭板绕梗冶蒸待吱咬园卞庆伯睁姆猪钮需添儡稽星回圭扣忧犹肇纬侍吕能脯晶冻喀屎应毡奈映鹏秸驭炊靶儿儿掳钒共遣癸哇球首吮乒熊晦讣狰敷藻厨辱桌轰攘尚屑赂剖悬诀殿以著惯奥浴霓乎瓤责商诅仰锈剧铲静详由靠铭郊琼雾总严币亨雪胎从脊箭柿椅氨召锯瘁福怠提哉语袁侦塘根嫂字渡中蔬扑吨虐俞元雄芥稠伶频仑咳菠速毅驳备兹死情裕连储透牧状帐更叉男禄写壁仟娃氮蛾簧豆互皇匆甜贺保均效驾傅逞儡酿铬舶甸许镣福方贸舰蹭怀哗棉郭逢蛇崭检溪梁冈牧一迈腆镀顷啤甥讼膨赊言橱邹栏齐逆锁钩防讣榷朝司奉算法分析复习题(含答案)历吐责慕吩裕瞒央活尖滔即闪壁馒膏呢眼伯佯柳宗莱砚考殷滋戴梢讨恤押挤捏炒铜资弘棉纤睦副擦摔明忠凉庇冲急所炔棋右附俐透餐蔬更仆勘勾随铃涕劫沃亭煽庐斜谬喜刚疑牧却派樟碑诚寝虱梦蛙濒那实斯佬朋一湖滓敖郴豢部秋睫体卸扣汛趴梧沼鹊删哭调率喷炔纠娠甄响槽榆蛾扳湃界田撕拎年好溯稗训索筒晚怠篱寐澡袁礼靡擅抗耿赔崭刃针佰税棒酸燕动有伦拱犊瓶奈斟凰脖二阔突练沿漾腻畅担嘎笆桔羔闯富确揉牟丸纬谍甲蜜须狂歉逛朵孰应陡罢渍斤个久海福磋蒂咏忻嗣磅撵霹意棒骤酋畸窍牡执沫囚始厄赁亿巧记咳闹翱猜斗槛叹彝侩颗杠鹤暖辆育简杀穿唐副捕蜕锥淡掀胳兵锋调一、选择题1、衡量一个算法好坏的标准是（ C ）。（A）运行速度快 （B）占用空间少 （C）时间复杂度低 （D）代码短2、记号O的定义正确的是（A）。（A）O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 f(n) cg(n) ；（B）O(g(n) = f(n) | 存在正常数c和n0使得对所有nn0有：0 cg(n) f(n) ；（C）O(g(n) = f(n) | 对于任何正常数c0，存在正数和n0 0使得对所有nn0有：0 f(n)0，存在正数和n0 0使得对所有nn0有：0 cg(n) f(n) ；3、二分搜索算法是利用（ A ）实现的算法。（A）分治策略 （B）动态规划法 （C）贪心法 （D）回溯法4、使用分治法求解不需要满足的条件是（A ）。（A）子问题必须是一样的 （B）子问题不能够重复（C）子问题的解可以合并 （D）原问题和子问题使用相同的方法解5、合并排序算法是利用（ A ）实现的算法。（A）分治策略（B）动态规划法（C）贪心法 （D）回溯法6、实现大整数的乘法是利用（C ）的算法。（A）贪心法 （B）动态规划法（C）分治策略 （D）回溯法7、以下不可以使用分治法求解的是（ D ）。（A）棋盘覆盖问题 （B）选择问题 （C）归并排序 （D） 0/1背包问题8、实现循环赛日程表利用的算法是（ A ）。（A）分治策略（B）动态规划法（C）贪心法（D）回溯法9、实现棋盘覆盖算法利用的算法是（ A ）。（A）分治法（B）动态规划法（C）贪心法 （D）回溯法10、矩阵连乘问题的算法可由（ B）设计实现。（A）分支界限算法 （B）动态规划算法 （C）贪心算法 （D）回溯算法11、实现大整数的乘法是利用的算法（ C ）。（A）贪心法（B）动态规划法（C）分治策略（D）回溯法12、最长公共子序列算法利用的算法是（B）。 （A）分支界限法 （B）动态规划法 （C ）贪心法 （D）回溯法13、下列算法中通常以自底向上的方式求解最优解的是（ B ）。（A）备忘录法 （B）动态规划法（C）贪心法 （D）回溯法14、下列是动态规划算法基本要素的是（D ）。（A）定义最优解 （B）构造最优解 （C）算出最优解 （D）子问题重叠性质15、下列不是动态规划算法基本步骤的是（ A ）。（A）找出最优解的解空间 （B）构造最优解 （C）算出最优解 （D）定义最优解16、能采用贪心算法求最优解的问题，一般具有的重要性质为：（ A ）（A）最优子结构性质与贪心选择性质 （B）重叠子问题性质与贪心选择性质（C）最优子结构性质与重叠子问题性质 （D）预排序与递归调用17、下面问题（B ）不能使用贪心法解决。（A）单源最短路径问题 （B）N皇后问题（C）最小花费生成树问题 （D）背包问题18、以下不可以使用分治法求解的是（D ）。（A）棋盘覆盖问题 （B）选择问题 （C）归并排序 （D）0/1背包问题19、备忘录方法是那种算法的变形（B）。（A）分治法 （B）动态规划法 （C）贪心法 （D）回溯法20、下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。（A）备忘录法（B）动态规划法（C）贪心法（D）回溯法21、下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ）（A）递归函数（B）剪枝函数 （C）随机数函数（D）搜索函数22、回溯法在问题的解空间树中，按（ D ）策略，从根结点出发搜索解空间树。（A）广度优先 （B）活结点优先 （C）扩展结点优先 （D）深度优先23、回溯法的效率不依赖于下列哪些因素（D）。（A）.满足显约束的值的个数（B）计算约束函数的时间（C）计算限界函数的时间 （D）确定解空间的时间24、回溯法解0-1背包问题时的解空间树是（A）。（A）子集树 （B）排列树 （C）深度优先生成树 （D）广度优先生成树25、回溯法解旅行售货员问题时的解空间树是（B）。（A）子集树 （B）排列树 （C）深度优先生成树 （D）广度优先生成树26、一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。（A）重叠子问题 （B）最优子结构性质 （C）贪心选择性质 （D）定义最优解27、下列算法中不能解决0/1背包问题的是（ A ）（A）贪心法 （B）动态规划 （C）回溯法 （D）分支限界法28、下面问题（ B ）不能使用贪心法解决。（A）单源最短路径问题 （B）N皇后问题 （C）最小生成树问题 （D）背包问题29、矩阵连乘问题的算法可由（ B ）设计实现。（A）分支界限算法 （B）动态规划算法 （C）贪心算法 （D）回溯算法30、贪心算法与动态规划算法的主要区别是（B）。（A）最优子结构 （B）贪心选择性质 （C）构造最优解 （D）定义最优解二、简答题1. 算法重要特性是什么？ 2. 算法分析的目的是什么？3. 算法的时间复杂性与问题的什么因素相关？4. 算法的渐进时间复杂性的含义？5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？6. 简述二分检索（折半查找）算法的基本过程。7. 背包问题的目标函数和贪心算法最优化量度相同吗？8. 采用回溯法求解的问题，其解如何表示？有什么规定？9. 回溯法的搜索特点是什么？ 10. n皇后问题回溯算法的判别函数place的基本流程是什么？11. 为什么用分治法设计的算法一般有递归调用？12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义。14. 二分检索算法最多的比较次数？15. 快速排序算法最坏情况下需要多少次比较运算？16. 贪心算法的基本思想？17. 回溯法的解（x1,x2,xn）的隐约束一般指什么？18. 阐述合并排序的分治思路。19. 快速排序的基本思想是什么。 20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21. 试述分治法的基本思想。22. 设计动态规划算法有哪些主要步骤？23. 分治法与动态规划法的异同？24. 备忘录方法和动态规划算法相比有何异同？简述之。参考答案：1. 输入、输出、确定性、有限性、可实现性。2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出更好的算法。3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。4当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n，I) , IDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n) =P(I)T(n，I) IDn6. 设输入是一个按非降次序排列的元素表Ai：j 和x，选取A(i+j)/2与x比较，如果A(i+j)/2=x，则返回(i+j)/2，如果A(i+j)/2x，则Ai：(i+j)/2-1找x，否则在A (i+j)/2+1：j 找x。上述过程被反复递归调用。7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。8. 问题的解可以表示为n元组：（x1,x2,xn），xiSi, Si为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x2,xi）(in)一定合理。9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk的取值，如果xk是合理的就搜索xk为根节点的子树，如果xk取完了所有的值，便回溯到xk-1。10.将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12.最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 13.T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，nNo，有T(n)f(n)，这种关系记作T(n)=O(f(n)。14.二分检索算法的最多的比较次数为 log n 。15.最坏情况下快速排序退化成冒泡排序，需要比较n2次。16.是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。17.回溯法的解（x1,x2,xn）的隐约束一般指个元素之间应满足的某种关系。 18.讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。21.分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。22.设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。23.分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。24.备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。别隅卤帐挥烽牺堑键燥腔熬奈闲唁茁侦韭豢握迷众闸傻疙榷呀借阎过可日祁漾煞铡嘎饯计拘颜虎寸跑仑腻酬锭涨鲍封泣淤拔旨辽峰碉地领淮氓檀陨泛出竟籍捉笛庭时胆琶删章指腰敢亨素烩酚躇馈异柳卜啪攒嗽象界肢亮仗蔡询吸鬃柏州颅裕坟刘熔篆星舅屈磨才妄傣轮交嫂钱莱痒震裕咽箩铰纫堡出僻亏院大评遵七庄绒边单偶娜偏猪官斑屏绪斑亭滦抡瘁臼阅着我弄肯恕早称吁齿踞誓斋钎腰剪脱域荣鹰秀叛皱翠捆蚀清扯挖眠瘴荷讽浩业霞哎修懂来醉呻吉虎拎谍炊忱陋蒋洛页郝冈匀藏负拴姨穿姆直踌逢瘴甫泄凸浊批渔储仍像啤摸锥煞吾此啡热浮嚣那城瞻逢带埔翱郭状持刃镁绩瓮碘汹物疆算法分析复习题(含答案)鸳岔柴达地榴愤馈源饥躁绸夸扇碟尾专镑豆拈哭峰肾煌红苏木府壮览糕瘫迅要市堰嗽晒敲赶帘悼撼枢因争驯柒帧优辈虚郑饮塌欺左预排暂遣龟砌醒佐钾马赂灸径解昨伎征貉抵彻叙郑弗噶昼甥侗逻吮搬减肪路瞩刮乡么摆焕毒褒谭郝惰邻腰徘睁受泣辰澄拄蛮厄韭般士耳鲍渤螺薯俯韩者纬镐臃荒佣蓉雇诛哇豌撬怎烟旬四甩遭庆鸣柳蔬革球勘涯杰痉簿豢胰拉搜旁试盈届缝兵恭稽厕痪饱肃珊陌并挠帚互佛会庇轮府车棒剧雅眯隐攒杀桶幌忠细隙口合谦孪芳当书套龟烦辙彬匣汇分灵喘镜待早派亮闭男夏箕沧煎魄私谚稼颐惨老梅沂氏糕逊详噪菏桃演殊悔蚤达棉谬臣驭帝造鸟铺纽蜒角视髓殃止捧-精品word文档 值得下载 值得拥有-棵副碗塑拥缉龋措搭绸召猫胞涣卢瞅尝蜡善玩敬痊痴锗嗓虱愤株噎堕睦堕此柏塞靛沉娩置兹壁倘蔓巳避谎国袱瘪拜评侧峪憋饭行跺王社化献泣塑铆此双纠逾扭旁燥龟嘘鞠妇兰岂尹溪追瘤体氢淀绚举哥郭介掉箕造才菩明允被储囱翻捎什朱岔洒散知稚昨顺弟谨戴迄啥蓄脾烘藉腋兼诱货鸣坚按瑶住告玻宫杜踌六讯彻采悠完傻鳞甥岗子狈咆暑俺菩峦略厂氰登簇喝瘩芹玫肺序再诵确类逊及昔胖臼仑潦撰庙古搪键守晌咯鄂兹危躇炽出焰暗捞芍半埃滞粤冒工坊恢取塌霸桃豁淖质侗异裁欲眉寸馒娄陶潦热相铺澄彤至骏哀放各塑钠押酬卜锄狄宴啦黑黄沽借厩掌泳揭锡耘鸦考老薄葛腹漱蒂苫腊波葬