- 1 - 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 算法分析考试试卷（A 卷） 课程名称 算法分析 编号 题号 一 二 三 四 总分 得分 评阅人 一、填空题（每小题3 分，共30 分） 1、一个算法的优劣可以用 与 与来衡量。 2、这种不断回头寻找目标的方法称为 。 3、直接或间接地调用自身的算法称为 。 4、 记号在算法复杂性的表示法中表示 。 5、由分治法产生的子问题往往是 ，这就为使用 提供了方便。 6、建立计算模型的目的是为了使 。 7、下列各步骤的先后顺序是 。①调试程序 ②分析问题 ③设计算法 ④编写程序。 8、最优子结构性质的含义是 。 9、贪心算法从初始阶段开始，每一个阶段总是作一个使 的贪心选择。 10、拉斯维加斯算法找到的解一定是 。 二、选择题（每小题2 分，共20 分） 1、哈夫曼编码可利用（ ）算法实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是基本计算模型的是（ ）。 A、RAM B、ROM C、RASP D、TM 3、下列算法中通常以自顶向下的方式求解最优解的是（ ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 - 2 - 4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( ) A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、动态规划 5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ A、 递归；B、分治；C、迭代；D、模拟。 6、FIFO 是（ ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 7、投点法是（ ）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 8、若线性规划问题存在最优解，它一定不在（ ） A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对 9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ ）对输入进行预处理。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 10、若 L 是一个 NP 完全问题，L 经过多项式时间变换后得到问题 l，则l 是( ). A、P 类问题 B、NP 难问题 C、NP 完全问题 D...
