北师大0512算法分析与设计在线作业.docx

北师大0512算法分析与设计在线作业.docx

《北师大0512算法分析与设计在线作业.docx》由会员分享，可在线阅读，更多相关《北师大0512算法分析与设计在线作业.docx（12页珍藏版）》请在冰点文库上搜索。

北师大0512算法分析与设计在线作业

单选：

第1题（2.5分）

递归算法：

（）

直接调用自身

间接调用自身

直接或间接调用自身

不调用自身

C，

单选：

第2题（2.5分）

在用贪心法解多机调度时的贪心选择策略是：

（）

最优子结构

重叠子问题

Johnson法则

最长处理时间作业优先

D

单选：

第3题（2.5分）

备忘录方法的递归方式是：

（）

自顶向下

自底向上

和动态规划算法相同

非递归的

C

单选：

第4题（2.5分）

回溯法的求解目标是找出解空间中满足约束条件的：

（）

所有解

一些解

极大解

极小解

A

贪心算法和动态规划算法共有特点是：

（）

最优子结构

重叠子问题

贪心选择

形函数

A

哈夫曼编码是：

（）

定长编码

变长编码

随机编码

定长或变长编码

B

单选：

第7题（2.5分）

多机调度的贪心策略是：

（）

最长处理时间作业优先

最短处理时间作业优先

随机调度

最优调度

A

单选：

第8题（2.5分）

程序可以不满足如下性质：

（）

零个或多个外部输入

至少一个输出

指令的确定性

指令的有限性

D

单选：

第9题（2.5分）

用分治法设计出的程序一般是：

（）

递归算法

动态规划算法

贪心算法

回溯法

A

采用动态规划算法分解得到的子问题：

（）

相互独立

与原问题相同

相互依赖

相互独立且与原问题相同

D

单选：

第11题（2.5分）

回溯法搜索解空间的方法是：

（）

深度优先

广度优先

最小耗费优先

随机搜索

A

单选：

第12题（2.5分）

拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：

（）

所需时间变化

一定找到解

找不到所需的解

性能变差

C

贪心算法能得到：

（）

全局最优解

0-1背包问题的解

背包问题的解

无解

C

能求解单源最短路径问题的算法是：

（）

分支限界法

动态规划

线形规划

蒙特卡罗算法

A

单选：

第15题（2.5分）

快速排序算法和线性时间选择算法的随机化版本是：

（）

舍伍德算法

蒙特卡罗算法

拉斯维加斯算法

数值随机化算法

A

单选：

第16题（2.5分）

动态规划算法解各个子问题的方法是:

（）

自底向上

自顶向下

随机选择

自底向上或自顶向下

A

回溯法解园排列问题的解空间树是：

（）

子集树

排列树

二叉树

多叉树

B

用分治法求平面最接近点对问题时采用的著名原理是：

（）

Johnson法则

鸽舍原理

牛顿原理

线性规划原理

B

分支限界法搜索解空间的方式是：

（）

广度优先

深度优先

随机

以上都不是

A

采用如下随机方法计算值：

（）

随机投点法

舍伍德法

拉斯维加斯法

单纯形法

A

下面是描述算法复杂度的有：

（）

时间复杂度

鸽舍原理

二分法

随机化算法

A

下面不属于单纯形法步骤是：

（）

选入基变量

选离基变量

做转轴变化

动态规划

D

单选：

第23题（2.5分）

、快速排序和线性时间选择的随机化版本是：

（）

舍伍德算法

拉斯维加斯算法

蒙特卡罗

单纯形法

A

用回溯法解旅行售货员问题时生成的解空间树是：

（）

子集树

排列树

二叉树

多叉树

B

用回溯法解0-1背包问题时生成的解空间树是：

（）

子集树

排列树

二叉树

多叉树

A

用分支限界法解布线问题时的解空间是：

（）

子集树

排列树

图

二叉树

B

单选：

第27题（2.5分）

跳跃表是采用哪种随机化算法设计的：

（）

舍伍德算法

拉斯维加斯算法

蒙特卡罗

单纯形法

A

单选：

第28题（2.5分）

合并排序和快速排序都采用的策略是：

（）

分治

Johnson法则

鸽舍原理

单纯形法

A

下面不属于单纯形法的步骤的是：

（）

选入基变量

选离基变量

作转轴变化

找最优子结构

D

Kruskal算法能解以下问题：

（）

单源最短路径

n后问题

最小生成树

装载问题

C

单选：

第31题（2.5分）

贪心算法解各个子问题的方法是：

（）

自底向上

自顶向下

随机选择

自底向上或自顶向下

B

单选：

第32题（2.5分）

用回溯法解旅行售货员问题时生成的树是：

（）

子集树

排列树

二叉树

多叉树

B

在n后问题中任意两个皇后能放在：

（）

同一行

同一列

同一斜线

以上都不行

D

单选：

第34题（2.5分）

用回溯法解0-1背包问题时生成的解空间树是：

（）

子集树

排列树

二叉树

多叉树

A

单选：

第35题（2.5分）

用贪心算法解单源最短路径问题时采用的算法是：

（）

Dijkstra算法

Prime算法

Kruskal算法

蒙特卡罗算法

A

在用动态规划解流水作业调度时的最优调度法则是：

（）

最优子结构

重叠子问题

Johnson法则

最长处理时间作业优先

C

算法与程序的区别在于：

（）

输入

输出

指令的确定性

指令的有限性

D

单选：

第38题（2.5分）

从分治法的一般设计模式可以看出，用它设计的程序一般是：

（）

顺序

选择

循环

递归

D

回溯法的解空间是在搜索过程中：

（）

动态产生

静态产生

无解空间

动态或者静态产生

A

单选：

第40题（2.5分）

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：

（）

相互独立

与原问题相同

相互依赖

相互独立且与原问题相同

D