2024知到答案 算法设计与分析（天津大学） 完整智慧树网课章节测试答案
第一章 单元测试
1、多选题：
下列关于效率的说法正确的是（ ）。
选项：
A:提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法
B:效率是一个性能要求，其目标应该在需求分析时给出
C:效率主要指处理机时间和存储器容量两个方面
D:程序的效率与程序的长度强相关
答案: 【提高程序效率的根本途径在于选择良好的设计方法，数据结构与算法;
效率是一个性能要求，其目标应该在需求分析时给出;
效率主要指处理机时间和存储器容量两个方面】
2、多选题：
算法的时间复杂度取决于（ ）。
选项：
A:待处理数据的初态
B:计算机性能
C:问题的规模
D:硬盘容量
答案: 【待处理数据的初态;
问题的规模】
3、单选题：
计算机算法指的是（ ）。
选项：
A:排序方法
B:计算方法
C:解决问题的有限运算序列
D:调度方法
答案: 【解决问题的有限运算序列】
4、多选题：
归并排序法的时间复杂度和空间复杂度分别是（ ）。
选项：
A:O(n)
B:O(nlog2n)
C:O(1)
D:O(n2)
答案: 【O(n);
O(nlog2n)】
5、判断题：
将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。（ ）
选项：
A:对
B:错
答案: 【错】
6、判断题：
用渐进表示法分析算法复杂度的增长趋势。（ ）
选项：
A:对
B:错
答案: 【对】
7、判断题：
算法分析的两个主要方面是时间复杂度和空间复杂度的分析。（ ）
选项：
A:错
B:对
答案: 【对】
8、单选题：
某算法所需时间由以下方程表示，求出该算法时间复杂度（ ）。
选项：
A:O(n)
B:O(nlog2n)
C:O(log2n)
D:O(n2)
答案: 【O(nlog2n)】
9、单选题：
下列代码的时间复杂度是（ ）。
选项：
A:O(1)
B:O(log3N)
C:O(log2N)
D:O(N)
答案: 【O(log2N)】
10、单选题：
下列算法为在数组A[0,...,n-1]中找出最大值和最小值的元素，其平均比较次数为（ ）。
选项：
A:n-3/2
B:3n/2-3/2
C:2n-1
D:3n/2
答案: 【3n/2-3/2】
第二章 单元测试
1、单选题：
可用Master方法求解的递归方程的形式为（ ）。
选项：
A:T(n)= T(n-a) +T(n-b) +f(n)， a≥1, b＞1
B:T(n)= T(n/a) +T(n/b) +f(n)， a≥1, b＞1
C:T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.
D:T(n)= T(n-a) +T(a) +f(n)， a≥1
答案: 【T(n)=aT(n/b)+f(n) , a≥1, b＞1, 为整数, f(n)＞0.】
2、判断题：
选项：
A:对
B:错
答案: 【对】
3、判断题：
假定
，
, 递归方程
的解是
. ( )
选项：
A:错
B:对
答案: 【对】
4、判断题：
假设数组A包含n个不同的元素，需要从数组A中找出n/2个元素，要求所找的n/2个元素的中点元素也是数组A的中点元素。针对该问题的任何算法需要的时间复杂度的下限必为
。 ( )
选项：
A:对
B:错
答案: 【错】
5、单选题：
使用Master方法求解递归方程
的解为（ ）.
选项：
A:
B:
C:
D:
答案: 【
】
6、判断题：
考虑包含n个二维坐标点
的集合S，其中n为偶数，且所有坐标点中的
均不相同。一条竖直的直线若能把S集合分成左右两部分坐标点个数相同的子集合，则称直线L为集合S的一条分界线。若给定集合S，则可在
时间内找到这条分界线L。 ( )
选项：
A:错
B:对
答案: 【对】
7、单选题：
选项：
A:
B:
C:
D:
答案: 【
】
8、判断题：
从n个数中找出前k个最小的元素并对所选择的前k个最小的元素进行排序。使用归并排序算法将这n个数进行排序的时间复杂度为
，从排好序的数组中提取有序的k个最小数的时间复杂度为
，因此总的运行时间复杂度为
. ( )
选项：
A:错
B:对
答案: 【对】
9、判断题：
假定问题对于规模为n的所有不同输入，存在一个分治算法其平均时间复杂度为
，则算法在最坏情形下的时间复杂度可能为
（ ）
选项：
A:错
B:对
答案: 【对】
10、单选题：
使用分治算法求解最大最小问题。假定问题的规模
, 每次将问题分成规模接近的两个子问题，递归地对子问题求解并将子问题的解合并得到大问题的解，该分治算法的复杂度函数可写为 ( )
选项：
A:
B:
,
C:
D:
答案: 【
】