济南大学成人教育《算法分析与设计(144401)》期末考试复习题及参考答案

一、 单选题1.下列算法中通常以自底向上的方式求解最优解的是（）。

A、备忘录法B、动态规划法C、贪心法D、回溯法答案： B

2.下面哪种函数是回溯法中为避免无效搜索采取的策略（）

A、递归函数B、剪枝函数C、随机数函数D、搜索函数答案： B

3.下面是贪心算法的基本要素的是（）。

A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解答案： C

4.衡量一个算法好坏的标准是（）。

A、运行速度快B、占用空间少C、时间复杂度低D、代码短答案： C

5.回溯法的效率不依赖于下列哪些因素（）

A、满足显约束的值的个数B、计算限界函数的时间C、计算约束函数的时间D、确定解空间的时间答案： D

6.基于比较的排序算法的算法复杂度的下界为（A、O(1)B、(n )C、O(nlogn)D、O(n2)答案： C

7.动态规划算法的基本要素为（ ）

）

A、最优子结构性质与贪心选择性质B、重叠子问题性质与贪心选择性质C、最优子结构性质与重叠子问题性质D、预排序与递归调用答案： C

8.实现最大子段和利用的算法是（）。

A、分治策略B、动态规划法C、贪心法D、回溯法答案： B

9.实现循环赛日程表利用的算法是（）。

A、分治策略B、动态规划法C、贪心法D、回溯法答案： A

10.在顺序存储的数据表中的第i个位置插入一个元素，算法的渐进时A、O( log n)B、O(1 )C、O( n)D、O(n log n )答案： C

11.根据执行算法的计算机指令体系结构，算法可以分为（ ）

A、精确算法与近似算法B、串行算法与并行算法C、稳定算法与不稳定算法D、32位算法与64位算法答案： B

12.4个盘子的汉诺塔，至少要执行移动操作的次数为 ( ?)。

A、11次B、13次C、15次D、17次答案： C

13.NP类语言在图灵机下的定义为（ ）

A、NP={L|L是一个能在非多项式时间内被一台NDTM所接受的语言}；B、NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；C、NP={L|L是一个能在多项式时间内被一台DTM所接受的语言}；D、NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}；

的复杂度( ?)

间为