2024知到网课 算法设计与分析智慧树答案

第一章 单元测试

1、判断题：程序运行结果往往与输入相关，所以程序可以不满足确定性（）
A:错
B:对
正确答案:【错】

2、多选题：有关算法分析的事后统计法正确的是（）。
A:从理论上讲，在各种软硬件环境下进行算法测试，得到的资源耗费都是一样的。

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

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

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

正确答案:【测试的结果与程序的编译和运行环境有关
;结果是面向机器，面向程序员，面向语言的
;结果与测试的样本数据有关
】

3、多选题：下面哪些内容是算法设计之前要完成的内容? ( )
A:证明算法的正确性。

B:确定合适的数据结构

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

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

正确答案:【确定合适的数据结构
;是求精确解还是近似解
】

4、单选题：函数10logn3+5logn2的渐近表达式为（）： A:O(nlogn)
B:O（logn2）
C:O(logn3)
D:O(logn)

正确答案:【O(logn)
】

5、单选题：下列函数根据渐近阶从低到高顺序是（）
A:n1/2 ＜ logn ＜2n ＜n3 ＜3n ＜n!
B:n1/2 ＜ logn ＜2n ＜n3 ＜ n! ＜ 3n

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

D:logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!
正确答案:【logn ＜ n1/2 ＜2n ＜n3 ＜3n ＜n!】

6、判断题：研究NPC 问题的意义: 一旦某个NPC问题找到了多项式时间复杂性的算法，那么所有的NP问题都找到了多项式时间算法。( )
A:对
B:错
正确答案:【对】

第二章 单元测试

1、单选题：直接或间接的调用自身的算法称为（）。
A:贪心算法

B:动态规划算法

C:递归算法

D:迭代算法

正确答案:【递归算法
】

2、单选题：Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）
A:

B:

C:

D:

正确答案:【

】

3、单选题：分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（）。
A:问题规模不同，问题性质不同

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

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

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

正确答案:【问题规模不同，问题性质相同
】

4、单选题：利用二分搜索，最坏情况下的计算时间复杂性为（）。
A:O (n2)
B:O（n）
C:O (logn)
D:O (2n)

正确答案:【O (logn)】

5、单选题：二分搜索算法只适用（）存储结构。
A:堆
B:任意顺序
C:栈

D:顺序
正确答案:【顺序】

6、单选题：使用二分搜索算法在1000个有序元素表中搜索一个特定元素，在最坏情况下，搜索总共需要比较的次数为（）。
A:10
B:1000

C:500
D:11
正确答案:【10】

7、单选题：线性时间选择的时间复杂度为（）。
A:O(n)

B:O （nlogn）
C:O(n2)
D:O(logn)
正确答案:【O(n)
】

8、单选题：利用合并排序，其辅助空间为（）： A:O(logn)
B:O(nlogn)

C:O（n）
D:O(n2)
正确答案:【O（n）】

9、单选题：利用快速排序，对数的序列{16, 27, 13, 2, 15,38}，选择基准16，进行一次划分，结果为（）： A:{2, 13, 15} 16 {38, 27}

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

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

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

正确答案:【{13, 2, 15} 16 {27, 38}
】

10、判断题：分治策略解决棋盘覆盖问题是一个渐近意义下最优的算法.（）
A:对
B:错
正确答案:【对】

第三章 单元测试

1、单选题：设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，若xm=yn则（）。
A:zk≠xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。

B:zk=xm=yn，且zk是Xm-1和Yn-1的最长公共子序列。

C:zk≠xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

D:zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。

正确答案:【zk=xm=yn，且zk-1是Xm-1和Yn-1的最长公共子序列。
】

2、单选题：当(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)=(-1, 5, -2, 1, -7, -4, 2, 3, -1, 2)时，最大子段和为( ).
A:7
B:10
C:6
D:9