《算法分析与设计》作业（二）
本课程作业由两部分组成。第一部分为“客观题部分”，由 15 个选择题组成，每题 1 分，共 15 分。第
二部分为“主观题部分”，由简答题和论述题组成，共 15 分。作业总分 30 分，将作为平时成绩记入课程总
成绩。
客观题部分：
一、 选择题（每题 1 分，共 15 题）
1、动态规划算法解各个子问题的方法是： （ A ）
A、自底向上 B、自顶向下 C、随机选择 D、自底向上或自顶向下
2、回溯法解园排列问题的解空间树是： （ B ）
A、子集树 B、排列树 C、二叉树 D、多叉树
3、用分治法求平面最接近点对问题时采用的著名原理是： （ B ）
A、Johnson 法则 B、鸽舍原理 C、牛顿原理 D、线性规划原理
4、分支限界法搜索解空间的方式是： （ A ）
A、广度优先 B、深度优先 C、随机 D、以上都不是
5、采用如下随机方法计算 值： （ A ）
A、随机投点法 B、舍伍德法 C、拉斯维加斯法 D、单纯形法
6、下面是描述算法复杂度的有： （ A ）
A、时间复杂度 B、鸽舍原理 C、二分法 D、随机化算法
7、下面不属于单纯形法步骤是： （ D ）
A、选入基变量 B、选离基变量 C、做转轴变化 D、动态规划
8、快速排序和线性时间选择的随机化版本是： （ A ）
A、舍伍德算法 B、拉斯维加斯算法 C、蒙特卡罗 D、单纯形法
9、用回溯法解旅行售货员问题时生成的解空间树是： （ B ）
A、子集树 B、排列树 C、二叉树 D、多叉树
10、用回溯法解 0-1 背包问题时生成的解空间树是： （ A ）
A、子集树 B、排列树 C、二叉树 D、多叉树
11、用分支限界法解布线问题时的解空间是： （ C ）
A、子集树 B、排列树 C、图 D、二叉树
12、跳跃表是采用哪种随机化算法设计的： （ A ）
A、舍伍德算法 B、拉斯维加斯算法 C、蒙特卡罗 D、单纯形法
13、合并排序和快速排序都采用的策略是： （ A ）
1
资源评论
