第一章测试
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. 旅行售货员问题的解空间树是一棵子集树。 ( )
参考答案:
错
