[北京师范大学]20秋《算法分析与设计》离线作业

skystar

在线作业试卷列表
单选?
1.递归算法：（ ）?分值：2.5
A. 直接调用自身
???B. 间接调用自身
???
C. 直接或间接调用自身
???D. 不调用自身
????

2.分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：( ）?分值：2.5
A. 相互独立
???B. 与原问题相同
???
C. 相互依赖
???D. 相互独立且与原问题相同
????

3.备忘录方法的递归方式是：（ ）?分值：2.5
A. 自顶向下
???B. 自底向上
???
C. 和动态规划算法相同
???D. 非递归的
????

4.回溯法的求解目标是找出解空间中满足约束条件的：（ ）?分值：2.5
A. 所有解
???B. 一些解
???
C. 极大解
???D. 极小解
????

5.贪心算法和动态规划算法共有特点是：（ ）?分值：2.5
A. 最优子结构
???B. 重叠子问题
???
C. 贪心选择
???D. 形函数
????

6.哈夫曼编码是：（ ）?分值：2.5
A. 定长编码
???B. 变长编码
???
C. 随机编码
???D. 定长或变长编码
????

7.多机调度的贪心策略是：（ ）?分值：2.5
A. 最长处理时间作业优先
???B. 最短处理时间作业优先
???
C. 随机调度
???D. 最优调度
????

8.程序可以不满足如下性质： （ ）?分值：2.5
A. 零个或多个外部输入
???B. 至少一个输出
???
C. 指令的确定性
???D. 指令的有限性
????

9.用分治法设计出的程序一般是：（ ）?分值：2.5
A. 递归算法
???B. 动态规划算法
???
C. 贪心算法
???D. 回溯法
????

10.采用动态规划算法分解得到的子问题：（ ）?分值：2.5
A. 相互独立
???B. 与原问题相同
???
C. 相互依赖
???D. 相互独立且与原问题相同
????

11.回溯法搜索解空间的方法是：（ ）?分值：2.5
A. 深度优先
???B. 广度优先
???
C. 最小耗费优先
???D. 随机搜索
????

12.拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法： （ ）?分值：2.5
A. 所需时间变化
???B. 一定找到解
???
C. 找不到所需的解
???D. 性能变差
????

13.贪心算法能得到：（ ）?分值：2.5
A. 全局最优解
???B. 0-1背包问题的解
???
C. 背包问题的解
???D. 无解
????

14.能求解单源最短路径问题的算法是：（ ）?分值：2.5
A. 分支限界法
???B. 动态规划
???
C. 线形规划
???D. 蒙特卡罗算法
????

15.快速排序算法和线性时间选择算法的随机化版本是：（ ）?分值：2.5
A. 舍伍德算法
???B. 蒙特卡罗算法
???
C. 拉斯维加斯算法
???D. 数值随机化算法
????

16.动态规划算法解各个子问题的方法是:（ ）?分值：2.5
A. 自底向上
???B. 自顶向下
???
C. 随机选择
???D. 自底向上或自顶向下
????

17.回溯法解园排列问题的解空间树是： （ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 二叉树
???D. 多叉树
????

18.用分治法求平面最接近点对问题时采用的著名原理是：（ ）?分值：2.5
A. Johnson法则
???B. 鸽舍原理
???
C. 牛顿原理
???D. 线性规划原理
????

19.分支限界法搜索解空间的方式是： （ ）?分值：2.5
A. 广度优先
???B. 深度优先
???
C. 随机
???D. 以上都不是
????

20.采用如下随机方法计算 值：（ ）?分值：2.5
A. 随机投点法
???B. 舍伍德法
???
C. 拉斯维加斯法
???D. 单纯形法
????

21.下面是描述算法复杂度的有：（ ）?分值：2.5
A. 时间复杂度
???B. 鸽舍原理
???
C. 二分法
???D. 随机化算法
????

22.下面不属于单纯形法步骤是：（ ）?分值：2.5
A. 选入基变量
???B. 选离基变量
???
C. 做转轴变化
???D. 动态规划
????

23.、快速排序和线性时间选择的随机化版本是：（ ）?分值：2.5
A. 舍伍德算法
???B. 拉斯维加斯算法
???
C. 蒙特卡罗
???D. 单纯形法
????

24.用回溯法解旅行售货员问题时生成的解空间树是：（ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 二叉树
???D. 多叉树
????

25.用回溯法解0-1背包问题时生成的解空间树是：（ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 二叉树
???D. 多叉树
????

26.用分支限界法解布线问题时的解空间是：（ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 图
???D. 二叉树
????

27.跳跃表是采用哪种随机化算法设计的： （ ）?分值：2.5
A. 舍伍德算法
???B. 拉斯维加斯算法
???
C. 蒙特卡罗
???D. 单纯形法
????

28.合并排序和快速排序都采用的策略是：（ ）?分值：2.5
A. 分治
???B. Johnson法则
???
C. 鸽舍原理
???D. 单纯形法
????

29.下面不属于单纯形法的步骤的是： （ ）?分值：2.5
A. 选入基变量
???B. 选离基变量
???
C. 作转轴变化
???D. 找最优子结构
????

30.Kruskal算法能解以下问题： （ ）?分值：2.5
A. 单源最短路径
???B. n后问题
???
C. 最小生成树
???D. 装载问题
????

31.贪心算法解各个子问题的方法是：（ ）?分值：2.5
A. 自底向上
???B. 自顶向下
???
C. 随机选择
???D. 自底向上或自顶向下
????

32.用回溯法解旅行售货员问题时生成的树是：（ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 二叉树
???D. 多叉树
????

33.在n后问题中任意两个皇后能放在：（ ）?分值：2.5
A. 同一行
???B. 同一列
???
C. 同一斜线
???D. 以上都不行
????

34.用回溯法解0-1背包问题时生成的解空间树是：（ ）?分值：2.5
A. 子集树
???B. 排列树
???
C. 二叉树
???D. 多叉树
????

35.用贪心算法解单源最短路径问题时采用的算法是：（ ）?分值：2.5
A. Dijkstra算法
???B. Prime算法
???
C. Kruskal算法
???D. 蒙特卡罗算法
????

36.在用动态规划解流水作业调度时的最优调度法则是：（ ）?分值：2.5
A. 最优子结构
???B. 重叠子问题
???
C. Johnson法则
???D. 最长处理时间作业优先
????

37.算法与程序的区别在于： （ ）?分值：2.5
A. 输入
???B. 输出
???
C. 指令的确定性
???D. 指令的有限性
????

38.从分治法的一般设计模式可以看出，用它设计的程序一般是：（ ）?分值：2.5
A. 顺序
???B. 选择
???
C. 循环
???D. 递归
????

39.回溯法的解空间是在搜索过程中：（ ）?分值：2.5
A. 动态产生
???B. 静态产生
???
C. 无解空间
???D. 动态或者静态产生
????

40.在用贪心法解多机调度时的贪心选择策略是：（ ）?分值：2.5
A. 最优子结构
???B. 重叠子问题
???
C. Johnson法则
???D. 最长处理时间作业优先