算法复习题.doc

一、选择题1. 通俗地讲，算法是指解决问题的一种方法或一个过程，描述算法的方式有很多，如（ ）。A、自然语言方式B、表格方式C、程序设计语言D、程序设计语言与自然语言相结合算法的描述方式（常用的） 算法描述 自然语言流程图特定的表示算法的图形符号伪语言包括程序设计语言的三大基本结构及自然语言的一种语言类语言类似高级语言的语言，例如，类PASCAL、类C语言2.算法的复杂性依赖于（ ）。A、要解决问题的规模B、算法的输入C、算法本身的函数D、设计者的学术水平3. 以下描述是有关算法设计的基本步骤：问题的陈述算法分析模型的拟制算法的实现算法的详细设计 文档的编制，应与其它环节交织在一起其中正确的顺序是（ ）。A、B、C、D、4.对于含n个元素的子集树问题，最坏情况下解空间的叶结点数目为（ ）。A、n!B、2nC、2n+1-1D、5. 对于给定的问题，考虑算法复杂性的意义在于（ ）。A、设计出复杂性尽可能低的算法B、若该问题已有多种算法时，选择其中复杂性低的求解问题C、提高算法设计的学术水平层次D、判断算法的正确性6.符号在算法复杂度描述中表示（ ）。A、紧渐近上界B、渐近上界C、紧渐近下界D、渐近下界7. 设、是定义在正数集上的正函数，如果存在正的常数C和自然数，使得当时有，则称函数当充分大时有上界，记作，即的阶（ ）的阶。A、不高于B、不低于C、等价于D、逼近8. 回溯法在解空间树T上的搜索方式是（ ）。A、深度优先 B、广度优先C、最小耗费优先 D、活结点优先9. 下面关于动态规划和备忘录方法的叙述中正确的是（ ）。A、备忘录方法是自顶向下的递归方式B、动态规划自底向上的，其最优值的计算不能递归定义C、当一个问题的所有子问题都至少需要求解一次时，用动态规划方法较好D、当子问题空间的部分子问题可不必求解时，用备忘录方法则较有利10.一个四城市的旅行售货员问题，其解空间的深度为（ ）。A、3B、4C、5D、611. 分支限界法与回溯法都是在问题的解空间树上搜索问题的解，二者（ ）。A、求解目标不同，搜索方式相同B、求解目标不同，搜索方式也不同C、求解目标相同，搜索方式不同D、求解目标相同，搜索方式也相同12. 下列哪些问题不可以用贪心算法求得最优解（ ）。A、哈夫曼编码 B、活动安排问题C、0-1背包问题 D、单源最短路径13. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。A、回溯法 B、分支限界法C、回溯法和分支限界法 D、回溯法求解子集树问题14.分支限界法在解空间树T上的一种搜索方式是（ ）。A、深度优先 B、广度优先C、活结点优先D、长度优先15. 以下关于判定问题难易处理的叙述中正确的是（ ）。A、可以由多项式时间算法求解的问题是难处理的B、需要超过多项式时间算法求解的问题是易处理的C、可以由多项式时间算法求解的问题是易处理的D、需要超过多项式时间算法求解的问题是不能处理的二、填空题1. 如果存在正的常数C和，使得当 NN0 时，有，则称函数当充分大时上有界，且是它的一个上界，记为 f(N)=O(g(N) 。这时还说明的阶不 （高于/低于）的阶。2.在循环赛日程表问题中，若给定的运动员数n=2(k-1)，则至少需要_n_天完成比赛；n=2k时，则需要_n-1_天。其中，k为正整数。3. 按照符号的定义，如果，则 O(f) 。4. 算法是由若干条指令组成的有序序列，并且具有输入、 输出 、 确定性 和有限性的性质。5.一个直接或间接地调用自身的算法称为_递归_，它有两个条件，一个是要直接或间接地调用自身，另一个是必须有_初始条件或非递归定义的初始值_。6. 一个问题能够用分治法求解，说明该问题：可以分解为规模比较小的问题且容易解决，该问题具有 最优子结构 性质，分解后的子问题的解可以合并为原问题的解，分解后的各个子问题是相互 独立 的。7. 运用动态规划法的一般步骤是：分析最优解，定义 建立递归关系 ，求最优值，构造最优解。8. 四个物品的0-1背包问题的解空间层数为 5 ，共有 8（2n）个叶结点。 共有 31（2（n+1）-1）个结点9. 对解空间的搜索过程中如果运用回溯法一个中间结点有 （一次/多次）机会称为扩展结点，若使用分支限界法则有 （一次/多次）机会。用分支限界法求解0-1背包问题时，对于每个物品j有重量wj和价值vj，考虑当前物品i，已装入背包中物品的重量和价值分别为cw、cv，剩余物品的价值上界为urv，剩余容量为c，目前已有的最优价值为bestp，则当左儿子满足约束条件 属于可行结点时，就将它加入活结点队列中；当右儿子满足上界条件 时才将它加入活结点队列中。10.在使用回溯法考虑求解一个具体问题时，往往需要设计出约束条件和限界条件。装载问题的约束条件是_；限界条件是bestwcw+r，其中，bestw是当前最优值，cw=_当前最优载重量_，r=_剩余集装箱重量_。三、证明题1.证明哈夫曼编码的贪心选择性质。2.试证明活动安排问题的贪心选择性质。3.试证明最长公共子序列问题具有最优子结构性质。四、求下列各式时间复杂度1.写出函数的渐近表达式。O(n2)2.写出函数的渐近表达式。3.写出函数的渐近表达式。O(2n)4.求的渐近表达式（，为常数）。5.写出函数的渐近表达式。五、应用题1.有0-1背包问题如下：n=4，c=20，P=（11，8，15，18），W=（5，4，4，8）。试画出用回溯法求解时的搜索情况。（本题6分）解： n=4，c=20，P=（11，8，15，18），W=（5，4，4，8） 2.请用快速排序法升序排序下面实例，给出每一趟排序的结果。（3，20，5，9，2，30，25，18，16，3）解： 30 25 18 16 20 30 25 18 16 20 20 25 18 16 30 18 16 20 25 16 18 结果： 16 18 20 25 303.画出下面字符表的哈夫曼编码对应的二叉树。字符abCDef出现频率（%）1245131695哈夫曼编码字符表解：课本P110 至底向上4.印刷电路板将布线区域分为方格阵列，如下图所示。电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案，布线时，电路只能沿直线或直角布线，已经布了线的方格做了封锁标记，其他线路不允许穿过被封锁的方