l算法复习题.docVIP

一、选择题 1. 通俗地讲，算法是指解决问题的一种方法或一个过程，描述算法的方式有很多，如（ ）。 A、自然语言方式 B、表格方式 C、程序设计语言 D、程序设计语言与自然语言相结合 算法的描述方式（常用的） 算法描述 自然语言流程图　　特定的表示算法的图形符号　伪语言　　包括程序设计语言的三大基本结构及自然语言的一种语言类语言　　类似高级语言的语言，例如，类PASCAL、类C语言2.算法的复杂性依赖于（ ）。 A、要解决问题的规模 B、算法的输入 C、算法本身的函数 D、设计者的学术水平3. 以下描述是有关算法设计的基本步骤： ①问题的陈述 ②算法分析 ③模型的拟制 ④算法的实现 ⑤算法的详细设计⑥文档的编制，应与其它环节交织在一起 其中正确的顺序是（ ）。 A、①②③④⑤⑥ B、①③⑤②④⑥ C、②④①③⑤⑥ D、⑥①③⑤②④4.对于含n个元素的子集树问题，最坏情况下解空间的叶结点数目为（ ）。 A、n! B、2^n C、2n+1-1 D、 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、3 B、4 C、5 D、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和，使得当 时，有，则称函数当充分大时上有界，且是它的一个上界，记为 。这时还说明的阶不 （高于/低于）的阶。2.在循环赛日程表问题中，若给定的运动员数n=2k-1)，则至少需要_____天完成比赛；n=2k时，则需要_____天。其中，k为正整数。3. 按照符号的定义，如果，则 。4. 算法是由若干条指令组成的有序序列，并且具有输入、 、 和有限性的性质。5.一个直接或间接地调用自身的算法称为________，它有两个条件，一个是要直接或间接地调用自身，另一个是必须有__。6. 一个问题能够用分治法求解，说明该问题：①可以分解为规模比较小的问题且容易解决，②该问题具有 性质，③分解后的子问题的解可以合并为原问题的解，④分解后的各个子问题是相互 的。 7. 运用动态规划法的一般步骤是：①分析最优解，②定义 ，③求最优值，④构造最优解。 8. 四个物品的0-1背包问题的解空间层数为 ，共有 个叶结点。共有 个结点9. 对解空间的有哪些信誉好的足球投注网站过程中如果运用回溯法一个中间结点有 （一次/多次）机会称为扩展