算法设计与分析智慧树知到答案章节测试2023年山东科技大学.pdfVIP

第一章测试

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

A:错

B:对

答案:A

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

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

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

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

D:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一

样的。

答案:ABC

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

A:使用何种计算机语言设计程序

B:是求精确解还是近似解

C:确定合适的数据结构

D:证明算法的正确性。

答案:BC

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

A:O(nlogn)

B:O(logn3)

C:O(logn)

D:O（logn2）

答案:C

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

A:logn＜n1/2＜2n＜n3＜3n＜n!

B:n1/2＜logn＜2n＜n3＜n!＜3n

C:n1/2＜logn＜2n＜n3＜3n＜n!

D:logn＜n1/2＜2n＜n3＜n!＜3n

答案:A

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

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

A:对

B:错

答案:A

第二章测试

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

A:递归算法

B:迭代算法

C:贪心算法

D:动态规划算法

答案:A

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

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

计出解Hanoi塔问题的递归算法正确的为：（）

A:

B:

C:

D:

答案:A

3.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题

分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题

和子问题（）。

A:问题规模相同，问题性质不同

B:问题规模不同，问题性质不同

C:问题规模相同，问题性质相同

D:问题规模不同，问题性质相同

答案:D

4.利用二分有哪些信誉好的足球投注网站，最坏情况下的计算时间复杂性为（）。

A:O(logn)

B:O(n2)

C:O（n）

D:O(2n)

答案:A

5.二分有哪些信誉好的足球投注网站算法只适用（）存储结构。

A:顺序

B:堆

C:栈

D:任意顺序

答案:A

6.使用二分有哪些信誉好的足球投注网站算法在1000个有序元素表中有哪些信誉好的足球投注网站一个特定元素，在最坏情况

下，有哪些信誉好的足球投注网站总共需要比较的次数为（）。

A:1000

B:10

C:11

D:500

答案:B

7.线性时间选择的时间复杂度为（）。

A:O(n2)

B:O（nlogn）

C:O(n)

D:O(logn)

答案:C

8.利用合并排序，其辅助空间为（）：

A:O(logn)

B:O(nlogn)

C:O（n）

D:O(n2)

答案:C

9.利用快速排序，对数的序列{16,27,13,2,15,38}，选择基准16，进行一次

划分，结果为（）：

A:{13,2,15}16{38,27}

B:{15,13,2}16{27,38}

C:{13,2,15}16{27,38}

D:{2,13,15}16{38,27}

答案:C

10.分治策略解决