密封线
学号：
姓名：
算法分析考试试卷（A卷）
密封线
课程名称算法分析
编号
题号
一二三四总分
得分
评阅人
一、填空题（每小题3分，共30分）
1、一个算法的优劣可以用空间复杂度与时间复杂度
2、这种不断回头寻找目标的方法称为回溯法。
3、直接或间接地调用自身的算法称为
递归算法
。
来衡量。
4、记号在算法复杂性的表示法中表示
紧致界
。
5、由分治法产生的子问题往往是提供了方便。
原问题较小模式
，这就为使用递归技术
6、建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。
7、下列各步骤的先后顺序是序。
②③④①。①调试程序②分析问题③设计算法④编写程
8、最优子结构性质的含义是
问题最优解包含其子问题最优解
。
9、贪心算法从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择。
10、拉斯维加斯算法找到的解一定是
正确的
。
二、选择题（每小题2分，共20分）
1、哈夫曼编码可利用（C）算法实现。A、分治策略B、动态规划法C、贪心法D、回溯法
2、下列不是基本计算模型的是（B）。A、RAMB、ROMC、RASPD、TM
3、下列算法中通常以自顶向下的方式求解最优解的是（C）。A、分治法B、动态规划法C、贪心法D、回溯法
班级：
考试课程：
1
f4、在对问题的解空间树进行搜索的方法中一个活结点有多次机会成为活结点的是A
A、回溯法B、分支限界法C、回溯法和分支限界法D、动态规划
5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？B
A、递归；B、分治；C、迭代；D、模拟。
6、FIFO是（A
）的一搜索方式。
A、分支界限法
B、动态规划法C、贪心法D、回溯法
7、投点法是（B）的一种。
A、分支界限算法
B、概率算法C、贪心算法D、回溯算法
8、若线性规划问题存在最优解，它一定不在（C）
A．可行域的某个顶点上B．可行域的某条边上C．可行域内部D．以上都不对
9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用
（B）对输入进行预处理。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法
10、若L是一个NP完全问题，L经过多项式时间变r