2020 数据结构与算法（李峙）(南宁师范大学) 最新满分章节测试答案
本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-03-01到2020-06-30
本篇答案更新状态:已完结
一、概述 第一周测验
1、 问题:以下关于基于有穷观点的能行方法说法错误的是：
选项：
A:由有限数量的任意指令构成
B:指令执行在有限步骤后终止
C:指令每次执行都得到唯一的结果
D:原则上可以由人单独采用纸笔完成
答案: 【由有限数量的任意指令构成】
2、 问题:以下关于ADT抽象数据类型说法错误的是：
选项：
A:ADT是对数据进行处理的一种逻辑描述。
B:ADT建立的封装技术将可能的处理实现细节隐蔽起来。
C:同一ADT只有唯一的数据结构可以实现。
D:采用程序设计语言的控制结构和基本数据类型来实现ADT的所提供的逻辑接口。
答案: 【同一ADT只有唯一的数据结构可以实现。】
3、 问题:关于“图灵机”，下列说法不正确的个数为：1）图灵机给出的是计算机的理论模型；2）图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右(R)、向左(L)移动一格或不动(N)，状态变为p；3）图灵机是一种离散的、有穷的、构造性的问题求解思路；4）凡是能用算法方法解决的问题也一定能用图灵机解决，凡是图灵机解决不了的问题算法也解决不了。
选项：
A:0
B:1
C:2
D:3
答案: 【0】
4、 问题:下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，其上标注的如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。该图灵机能实现的功能是：
选项：
A:将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。
B:将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
C:识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
D:识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同。
答案: 【将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。】
5、 问题:下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5，S6}，其中S1为起始状态，S6为终止状态；箭头表示状态转换，其上标注的如in, out, direction表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。该图灵机能实现的功能是：
选项：
A:识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。
B:识别是否如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同。
C:将形如0101，01010101的0、1串，即一个0接续一个1，且0的个数和1的个数相同， 转换为XYXY， XYXYXYXY的形式。
D:将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式。
答案: 【识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串。】
6、 问题:一个图灵机应该由以下哪些部分组成？
选项：
A:无限长的分格纸带
B:读写头
C:状态寄存器
D:有限的控制规则
E:字符
答案: 【无限长的分格纸带;
读写头;
状态寄存器;
有限的控制规则】
7、 问题:一般来说我们可以把生活中常见的问题分为哪几类？
选项：
A:分类问题
B:证明问题
C:过程问题
D:计算问题
答案: 【分类问题;
证明问题;
过程问题】
8、 问题:以下哪些方法不是以算法的概念来解决问题？
选项：
A:超大规模分布式计算
B:光子计算
C:DNA计算
D:量子计算
E:智慧众包
F:星象占卜
答案: 【智慧众包;
星象占卜】
二、算法分析 第二周测验
1、 问题:判断下列代码段的大O级别：test = 0
for i in range(n):
for j in range(n):
test = test + i * j
选项：
A:O(n)
B:O(n^2)
C:O(n^3)
D:O(n*log(n))
答案: 【O(n^2)】
2、 问题:判断下列代码段的大O级别：test = 0
for i in range(n):
test = test + 1
for j in range(n):
test = test – 1
选项：
A:O(n)
B:O(n^2)
C:O(n^3)
D:O(n*log(n))
答案: 【O(n)】
3、 问题:判断下列代码段的大O级别：for i in range(n):
k = 2 + 2
选项：
A:O(n)
B:O(n^2)
C:O(n^3)
D:O(1)
答案: 【O(n)】
4、 问题:判断下列代码段的大O级别：def function(n):
return n+2
选项：
A:O(n)
B:O(n^2)
C:O(n^3)
D:O(1)
答案: 【O(1)】
5、 问题:以下是一个快速幂算法：def pow(x, n):
if n==0:
return 1
elif n==1:
return x
elif n%2==0:
return pow(xx, n//2)
else:
return pow(xx, n//2)*x问它对于n的大O级别。
选项：
A:O(n)
B:O(log n)
C:O(nlog n)
D:O(1)
答案: 【O(log n)】
6、 问题:下面的列表操作中哪些是O(1)的？
选项：
A:list.pop(0)
B:list.pop()
C: list.append(10)
D:list[10]
答案: 【list.pop();
list.append(10);
list[10]】
7、 问题:下面的字典操作中哪些是O(1)的？
选项：
A:” in my_dict
B:del my_dict[”]
C:my_dict[”] == 10
D:my_dict[”] += 1
答案: 【” in my_dict;
del my_dict[”];
my_dict[”] == 10;
my_dict[”] += 1】
8、 问题:令n为问题规模，其中解决本问题的三个算法称为A,B,C，他们需要的总运算次数分别是：A: 96+108n+24n^2+12n^3B: 16n+48n^3C: 10080+168n+7n^2*log(n)三个算法的时间复杂度的大O级别中，以下表述正确的有：
选项：
A:A算法和B算法的时间复杂度相同
B:B算法比A算法的时间复杂度更大
C:C算法的时间复杂度最大
D:C算法的时间复杂度最小
E:A算法比B算法的时间复杂度更大
答案: 【A算法和B算法的时间复杂度相同;
C算法的时间复杂度最小】
三、基本结构（上） 第三周测验
1、 问题:假设你执行了下列的栈操作：s = Stack()
s.push(1)
s.push(3)
s.pop()
s.push(5)
s.push(7)现在栈内还有哪些元素？
选项：
A:1, 5, 7
B:3, 5, 7
C:1, 3, 7
D:1, 3, 5
答案: 【1, 5, 7】
2、 问题:将以下中缀表达式：( 5 – 3 ) * ( 2 + 4 )转换为后缀表达式，结果为？
选项：
A:5 3 – 2 4 + *
B:5 3 2 4 + * –
本文章不含期末不含主观题！！
本文章不含期末不含主观题！！
支付后可长期查看
有疑问请添加客服QQ 2356025045反馈
如遇卡顿看不了请换个浏览器即可打开
请看清楚了再购买哦，电子资源购买后不支持退款哦
