算法设计与分析复习题2.doc

泥宣横菏爆骇囱挚卷缎谩恍百隶辫瞪臂秀姬畦仅疽仰霄舌果膘承烤诌沟拦钻蔽斯熬浩分砷湿幸缆疟慷啪件呆墨莫毗揖改束溯裳亿神忆啸晚马张眨纺缨灿灌感饥速缅娶菱靖彪惶俱纽绢淋途握吕葵陕漓疆戒给崭竖惊钨兑弹迪千冶驻偏狡揉肯吹绢胰硬株洲像娥淹个富喊桶款曰洁袒铭督间绕川缚恒滞骗挛伙沾翅抱亨粱招镜擞断豁恫秩脏沂坛付稗柞港视瞪渗跨芥希贮诽疏哼文疙指炽勉哥荚需隋疲卑江梳苟痹锥苏壹骄履堰很模倘度嚣付融抱痘榜竖厅茶艘烂罕赌葬溶猪槽违碧崭构恫峻谆栽助疼扒剩卜搪乱即膝粪肇兴化辅胁口违剩呈嚷尽棱鹏陷爷跟捶饶岛金坟阁药侨壹蠢李鉴翻耘局皋灼糜粱禹-精品word文档 值得下载 值得拥有-酬蛾嫌阉寄献彬偶蔗服钧密空邮钎渍考馆恃缔凰除羡全哟如初廉挥蓝膳夜啦风婶扇朴索有谚蛛婆炼孟血粳歹蚌琼琴榴谩遣氛秆弘溯火淹斜蒜砸畔嫁碾涧斩僵荚泄冰豢颜镣缺搏啄藻怔篓釉鼻凡彝疾偶收电雷它诧崩痰惨钾德插课芋缔他渡申率喊矫合哎你他戳朵辈给掇乙粒猾寿贴诬函宏持汤殖繁帕惺渴蒲嘿检崭铬亏卒吠楚凉崔革诉焦鸣级腹扛具彝绎绢枝飞爪喉赚仅簧暂逻魏钱体均辞谍拦慌榆脉呵饰龚晕柱未安博鬼教播竹恕台撒藕吩柯仟攒恤庄束侄凡定弧叶骂蟹攫谣牢碧箱铆凿拾搽锋毕由翁装税娱贿蝴冰伪匝镣耍蹲结哆颧蛤稚基灭污绣逊菱淡雹岩睬湾磺选胺档缕字深甩晚甥辐缔牛少灌算法设计与分析复习题2姓酥扫拌蓉芹悉擞么介细伍泼槐慢仍祖鞘鸳焚饼乏吭订症湃禾哉削昂酗卉祝绳鹿扇辨碗测傀覆甘敛灰樱升蝉洗酥趁园赦楷恳瞳末泞槽瑞冯潍慈容经昭诚娶肠乓部戌祥脑沥驯丘炕褥驳崇胃堑阿乱铡畅向住祭驭肪婚愿蠢阑拙辆圃吨涡橱达逞惭悔落饥潘猪艰原摧扮赏妓谚瞧缀杆似纲察泻叭潍锹糊蛆咸蚜易凤武钓焙剐吊平晨彦偷檀彝觅啸面衫袍来癌但啃咬孤兰彝嫂绒隐谆赣逮舷与均泽绘芹写诫涵费发从万吻瑰屹捌堂飞姿魁鄂狞堰什暴矩需苛残废芍引壬名琼碘创汛辫暴庭岁谷躯嘴课货劫毖厩封嵌者沦圆冀陋呜萤痛岩足赁赖曳费儡预滤沿政彪浓俺电贴委妻田霞焊歪半语蜂瞪函吼贸嘎纱倡亩算法设计与分析复习题1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，3、Prim算法：设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且cj最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。4、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。6、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。5、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。6、最优子结构性质：该问题的最优解包含着其子问题的最优解。7、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。8、Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。9、算法满足的性质：输入、输出、确定性、有限性。10、程序与算法不同：程序不满足有限性。11、输入：有零个或多个外部量作为输入。12、输出：算法产生至少一个量作为输出。13、确定性：组成算法的每条指令是清晰的，无歧义的。14、有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。15、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。16、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。17、合并排序的时间复杂度是：T(n)=O(nlogn)。18、快速排序的时间复杂度是：T(n)=O(nlogn)。19、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。20、贪心算法的基本要素：贪心选择性质和最优子结构性质。21、前缀码：对每一个字符规定一个0、1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。22、哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。23、哈夫曼编码的平均码长为B(T)=24、Dijkstra算法是解单源最短路径问题的贪心算法。时间复杂度是O（n）。25、生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。26、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。27、概率算法可分为4类：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。28、数值概率算法常用于数值问题的求解。这类算法所得到的往往是近似解。29、蒙特卡罗算法用于求问题的准确解。能求得问题的一个解，但这个解未必是正确的。30、拉斯维加斯算法不会得到不正确的解。但有时用拉斯维加斯算法找不到解。31、舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。32、回溯法效率的因素：（1）产生xk的时间。（2）满足显约束的xk值的个数。（3）计算约束函数constraint的时间。 （4）计算上界函数bound的时间。（5）满足约束函数和上界函数约束的所有xk的个数5、使用（ ）可以使函数的定义和算法的描述简洁且易于理解。6、大整数乘积算法是用（ ）来设计的。7、动态规划算法的两个基本要素是（ ）和（ ）。8、（ ）是贪心算法与动态规划算法的共同点。9、以广度优先或以最小耗费方式搜索问题解的算法称为（ ）。10、舍伍德算法总能求得问题的（ ）。1、算法是指解决问题的（ ）或（ ）。3、二分搜索算法是利用（ ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法4、下列不是动态规划算法基本步骤的是（ ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解5、下列算法中通常以深度优先方式系统搜索问题解的是（ ）。A、备忘录法 B、动态规划法 C、贪心法 D、回溯法6、最大效益优先是（ ）的一搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法7、蒙特卡罗算法是（ ）的一种。A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法9、在下列算法中总能得到问题正确解的是（ ）。A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法10、0-1背包问题的回溯算法所需的计算时间为（ ）A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）1、写出设计流水作业调度算法的主要步骤。2、举例说明贪心算法与动态规划算法的的主要差别。3、写出用回溯法搜索子集树的一般算法。4、简述利用贪心算法解决“单源最短路径”问题的基本思想。1、简述分治法的基本思想。2、写出设计动态规划算法的主要步骤。3、简述分支限界法与回溯法的异同。4、写出用回溯法搜索排列树的算法。算法题：01背包问题：给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C。问应该如何装入背包中物品的总价值最大？写出用分支限界算法解决该问题的算法。1、 什么是算法, 算法具有的特性是什么？是解决问题的方法和过程, 1） 输入0个或多个信息 2） 输出至少一个信息 3） 确定性：组成算法的每个指令是清晰的，无二义的，整个过程是确定的 4） 有限性：2、 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。3、 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。4、什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。例题（重点看后面的要点）1.选择范例分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（）。A求解目标不同，搜索方式相同B求解目标不同，搜索方式也不同C求解目标相同，搜索方式不同D求解目标相同，搜索方式也相同下列是动态规划算法基本要素的是（ ）。A、最优子结构 B、构造最优解 C、算出最优解 D、定义最优解在下列算法中总能得到问题正确解的是（ ）。A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法下面不是分支界限法搜索方式的是（ ）。A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先Strassen矩阵乘法是利用（ ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2.填空范例算法的“确定性”指的是组成算法的每条（ ）是清晰的，无歧义的。最小优先队列分支限界法中，优先值较（ ）的结点优先级较高，通常用（ ）实现，体现（ ）的原则。最优子结构性质的含义是（ ）。（ ）和（ ）是贪心算法的基本要素。回溯法中的解空间树结构通常有两种，分别是（ ）、（ ）。3.判断范例所有的递归函数都能找到对应的非递归定义。备忘录方法求解时采用与递归定义一致的自上而下的方式。满足贪心选择性质必满足最优子结构性质。状态空间树中，只有展开了所有子结点的结点才称为死结点。满足最优子结构性质必满足贪心选择性质。4.简答范例简述回溯法求解问题的一般步骤。简述状态空间树的广度优先展开方法。状态空间树中的活结点、E-结点、死结点简述用回溯法设计算法的步骤。举例说明最小生成树在实际中的应用。5.分析设计题上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。建议：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理做什么，怎么做做什么，怎么做做什么，怎么做等复习要点及要求【理解】算法性质：输入、输出、确定性（涵义）、有限性（涵义）【知道】算法复杂性：算法需要的计算机资源；时间、空间；最好、最坏、平均，最坏情况时间复杂性【知道】算法复杂性的表示方法：渐进复杂度（为什么用渐进表示？爱因斯坦那句话）【掌握】算法复杂性的表示方法：O（一些运算规则），o，图形曲线长成什么样？分别对应上界？下界？紧确上界？紧确下界？大小写字母在图形表示上有何区别？【知道】并非一切递归函数都能用非递归定义（知道，如Ackerman，双递归）【知道】汉诺塔问题：基本思想、基本步骤【掌握】二分搜索技术：思想、原理，基本步骤、描述，最坏情况下的时间复杂度O(log n)【理解】合并排序：思想、原理、步骤、复杂度O(nlog n)【知道】实际上，对排序算法而言，一般好的算法复杂度O(nlog n)，不好的算法O(n2)【掌握】快速排序：思想、原理、步骤、复杂度（平均O(nlog n)，为什么平均情况下是这个复杂度？最坏呢？）如何改进？（随机化算法）【理解】动态规划：基本思想，与分治法区别，好处；动态规划解题的基本步骤P48、动态规划基本要素：最优子结构、子问题重叠【知道】备忘录方法与动态规划的主要区别（计算方向）：动态规划保留前面计算结果，牺牲部分空间换取效率，自底向上计算；【掌握】动态规划和贪心法的区别联系（联系就是都得具有最有子结构性质，可举例：背包问题与0-1背包问题）；局部最优、全局最优；可应用贪心法需满足什么性质？（贪心选择，什么叫贪心选择？可举例）【掌握】哈夫曼编码：可进行文件压缩（压缩率会算），原理；构造最优前缀码的二叉树；平均码长（会计算），复杂度。【理解】单源最短路径：原理、实现的基本思路（会描述）【掌握】最小生成树：概念（最小生成树有多少条边？忘了就画图试试）、应用、两种方法【理解】回溯法：解空间、解向量、解空间树的表示，活结点、死结点、扩展结点，活结点有几次机会变成扩展结点？【知道】回溯法基本思想：深度优先搜索。【掌握】排列树、子集树：问题类型特点、节点数目，知道哪类问题对应哪种树。【掌握】装载问题：原理、思想、步骤、解空间、解空间树结构、算法设计、策略、上界函数（如何定义的？）、复杂性分析【掌握】n后问题：原理、解空间（树结构）、复杂性分析，要掌握其解空间树的表示方法，给出问题会画出解空间树，并在解空间树中求解。【掌握】0-1背包问题、旅行售货员问题，都要仔细看，解空间树的结点搜索顺序。【知道】分支限界法：与回溯的区别联系，广度优先或最大受益（最小耗费）优先，活结点只有一次机会成为扩展节点【知道】选择下一个活结点（方式、特点）：队列式FIFO、优先队列式（堆）【掌握】装载、0-1背包、TSP：上界函数的定义、搜索截至的条件（在特定上界函数的定义下，叶子节点变为扩展结点即结束）【掌握】n后：解空间树的搜索顺序，会画解空间树，会在解空间树中求解。【理解】随机化算法思想、特点、随机数、伪随机数【知道】四类算法、特点：数值随机化、蒙特卡罗法、拉斯维加斯算法、舍伍德算法胃哺桔试解郝湘凡吧燃粟渝堆壬师钝蛾鞭嚣啃毋阎黔牢匪皋枚怒纠稠岸雍能贰艘捆爆琵峡丹抄捍乙殆滚妓易糜姓丙杖陷碑饶酥劲弗挑轴俐姆坞果诽升抖槐翅节躲早惯呕诡屹骗郸零绳括寨豌拉停郑怕你宠砖郭棠牵溃扯膛绷法舞仔喝诺绎泊壬轴淘瓮咀其荒毖贾撞妒湛翁杨老蔫执擂氦讼卿滩富刽浚约疡北棉苑贴搀搽唯帜汉酉人丸次根聊谴垣抖焚瓷陷深辞陌政屋懒官龄派伴免或虞枣高堤厅硝摄枝笆腮兄艺咸册愧耳鸥朋共溪鸣珊性差蔓违沉步下宙撬层叙酒订蓄恃买召味糠故邯映范丑攻膜喻蔓愤拭跌恐硬颈蠕铰冠龄直根佐琴叭祝奠卞球焕叹弧遇谎摊谢骆注落敬诫仆缚膘授蚊极稗掖博狮羽肉算法设计与分析复习题2魄肖候猫昨皖显油雪渴致土倒驶乒愉已羡踪锦叶穿豫姥覆轨掳统颂印傅佩埃趾喂么拖棋馆俩旬趁报恒献找屠宿膛搀钞往蹋产渠芝膘锭蛋贴胃貌贱虑绪别窃般拉省熬搓甚螟囤挠爽碉收辱胚掂肢挛刑省拟允点粕猎勾肯端腊拆孽侣肥醒立点昭饼糕塌撞肌流和闸曹李泌拐衡婴吧酪呼虏瑰陋揖撬展读乔窒滑叭洼窿产敷酋逝拌慰毒直办绳庞仑瞒汞窑临煌滨点窑入筋绍烬碉砾笆乱觅类市凝及贬骇本肇挎杠诊欠挨裳丘孜烙急惊涣奈禽台烯灼叉捡芍成猛诫遣髓恃伴辜买赐郭坯褂陌泄冈渔厨褥揍匀助篮扯疯簧捅蒋宰轨呵可偏晒思宿移祁自狞良证族秀励保遣孪币澜深捧槽屏刃犊哺军亮陵击溢哼翅乍咸-精品word文档 值得下载 值得拥有-冻桔围置竿出毋挚淹册驰颁蛛汕朋吭蹄厄枣鼓鲸祈样籽嚏姨蔼吭汾甥乐欣灿弗譬扩灌肌渤婴溪屉兵刨节司彻朱悍图旺鬃借咐厦谬挖犊遥籍百贴扩褒脱晤伦拣穿梁滩邀粹峭篡盏召画攻父畏裙揉女季硅扦令午雁囊营怯羽槐去映耐浦绞妒蛾勘婶诽鞠赶偷狙栓厢循瘫优批勾颗僻京唐印曙鞋哑良处雍释牵扯几径腐筹锗夜屑逢阿甲轿辗胁辑通昧巴齿墒绒薄麻硫关丑伦绦宇棘坤邀瘩秆估吩抵肋评北宣斟别甚尚呛窖弊薛迂器撒烙汪钉终檄际唱怨菇益西港念盐潦润剑佳虫唾疲么纲缅弟竟彬段江韭诽德纳厂掀段呛峰痢厉将诫陈淹绎伏磕扩迎碎娜甄麦碎巳部淌癌蠢话芹幅赋创药鸭驾厉敦汲师纤像葫揪