算法设计与分析期末复习题

[单选题]

1.可操作性最好且最具有实际价值的是哪种情况下的时间复杂性

A.最好情况

B.最坏情况

C.平均情况

D.以上都不对

答案：B

2.算法分析中，记号表示

A.渐进下界

B.渐进上界

C.非紧上界

D.同阶

答案：D

3.快速排序算法在最坏情况下的时间复杂性为

A.O(n2)

B.O(logn)

C.O(n)

D.O(nlogn)

答案：A

4.使用递归算法时，算法之间信息的传递和控制转移必须通过哪种方式来实现

A.数组

B.链表

C.栈

D.树

答案：C

5.用O（n3）的时间解矩阵连乘问题用的是下列哪种方法

A.随机化算法

B.动态规划法

C.分治法

D.回溯法

答案：B

6.选择排序、舍伍德算法和凸多边形最优三角剖分中，哪个算法可用动态规划算法求解

A.选择排序

B.舍伍德算法

C.凸多边形最优三角剖分

D.都不是

答案：C

7.Dijkstra算法解单源最短路径问题用的是哪种思想

A.分治法

B.动态规划法

C.回溯法

D.贪心算法

答案：D

8.下列算法中通常以深度优先方式系统搜索问题解的是

A.备忘录法

B.动态规划法

C.贪心法

D.回溯法

答案：D

9.下列哪种方法有通用解题法之称，用它可以系统搜索一个问题的所有解或任意解

A.回溯

B.分治法

C.分支限界法

D.动态规划法

答案：A

10.下列哪一种算法不是随机化算法

A.动态规划算法

B.拉斯维加斯算法

C.蒙特卡罗算法

D.舍伍德算法

答案：A

[填空题]

11.排序问题的计算时间下界为()

答案：nlogn

12.遍历子集树需计算时间，()

答案：2ⁿ

13.采用二分搜索技术，从{10,20,30,40,50}中查找元素10需要比较()次。

答案：2

14.回溯法解图的m着色问题时，解空间树是一棵()。

答案：排列树

15.贪心算法总是做出在当前看来的()选择。

答案：最优

16.任何可用计算机求解的问题所需的时间都与其()有关。

答案：规模

17.求解最小生成树利用的算法是()。

答案：贪心算法

18.拉斯维加斯算法找到的解一定是()。

答案：正确解

19.()的种子可以由用户指定也可以由系统时间自动产生。

答案：伪随机数

[简答题]

20.优先队列式分支限界法选取——的结点成为当前的扩展结点。

答案：优先级最高

21.设有以下问题：一辆汽车加满油后可行驶nkm。旅途中有k个加油站，k个加油站之间的距离在数组a中存储，设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。阅读下面的算法回答以下问题： Int greedy(int a[ ],int n,int k){ int sum=0;int x[];//sum为加油的次数，数组x用来存放在哪些站加油 for(int i=1;i