第一章测试

1. 程序运行结果往往与输入相关，所以程序可以不满足确定性( )

参考答案:

错

2. 有关算法分析的事后统计法正确的是( ) 。

参考答案:

结果是面向机器， 面向程序员，面向语言的

;测试的结果与程序的编译和运行环境有关

;结果与测试的样本数据有关

3. 下面哪些内容是算法设计之前要完成的内容? ( )

参考答案:

是求精确解还是近似解

;确定合适的数据结构

4. 函数 10logn3+5logn2 的渐近表达式为( ) ：

参考答案:

O(logn)

5. 下列函数根据渐近阶从低到高顺序是( )

参考答案:

logn < n1/2 <2n

6. 研究 NPC 问题的意义: 一旦某个NPC 问题找到了 多项式时间复杂性的算法，

那么所有的 NP 问题都找到了 多项式时间算法。 ( )

参考答案:

对

第二章测试

1. 直接或间接的调用自身的算法称为( ) 。

参考答案:

递归算法

2. Hanoi 塔问题如下图所示。 现要求将塔座 A 上的的所有圆盘移到塔座 B 上，

并仍按同样顺序叠置。 移动圆盘时遵守 Hanoi 塔问题的移动规则。 由此设

计出解 Hanoi 塔问题的递归算法正确的 ……此处隐藏4518个字……

3. 下面关于用回溯法解题说法， 正确的是( ) .

参考答案:

这种方法适用于解一些组合数相当大的问题。

;解空间树有子集树与排列树两种;

;在搜索过程中动态产生问题的解空间;

4. 回溯法中的剪枝函数包括( ) 。

参考答案:

限界函数

;约束函数

5. 回溯法解题步骤,正确的是( )

参考答案:

针对所给问题， 定义问题的解空间;

;以深度优先方式搜索解空间， 在搜索过程中用剪枝函数避免无效搜索;

;确定易于搜索的解空间结构;

6. 四色定理是第一个主要由计算机证明的理论( )

参考答案:

对

第六章测试

1. 在对问题的解空间树进行搜索的方法中， 一个活结点最多有一次机会成为活

结点的是( ) 。

参考答案:

分支限界法

2. 分支限界法与回溯法的相同点是： 都是一种在问题的( ) 中搜索问题解的

算法。

参考答案:

解空间树 T

3. )。

参考答案:

最大堆 最小堆

4. 具有限界函数的广度优先生成搜索解空间树法称为回溯法。 ( )

参考答案:

错

5. 旅行售货员问题的解空间树是一棵子集树。 ( )

参考答案:

错