大学MOOC 数据结构与算法(云南大学)1454748161 最新慕课完整章节测试答案
一、概述
第一周测验
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: C. Antony R. Hoare
B: Niklaus Wirth
C: Edsger Dijkstra
D: Donald E. Knuth
E: John Hopcroft
答案: 【 Niklaus Wirth】
7、多选题：
一个图灵机应该由以下哪些部分组成？
选项：
A: 无限长的分格纸带
B: 读写头
C: 状态寄存器
D: 有限的控制规则
E: 字符
答案: 【 无限长的分格纸带;
读写头;
状态寄存器;
有限的控制规则】
8、多选题：
一般来说我们可以把生活中常见的问题分为哪几类？
选项：
A: 分类问题
B: 证明问题
C: 过程问题
D: 计算问题
答案: 【 分类问题;
证明问题;
过程问题】
9、多选题：
以下哪些方法不是以算法的概念来解决问题？
选项：
A: 超大规模分布式计算
B: 光子计算
C: DNA计算
D: 量子计算
E: 智慧众包
F: 星象占卜
答案: 【 智慧众包;
星象占卜】
10、多选题：
Python程序设计语言是
选项：
A: 高级语言
B: 动态类型语言
C: 过程式语言
D: 面向对象语言
E: 函数式语言
答案: 【 高级语言;
动态类型语言;
过程式语言;
面向对象语言;
函数式语言】
三、基本结构上
第五周2测验
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 + * -
C: 5 3 2 * - 4 +
D: 5 3 2 * 4 + -
答案: 【 5 3 - 2 4 + *】
3、单选题：
给定后缀表达式3 6 + 5 2 - /求值结果为？
选项：
A: 3
B: 4
C: 6
D: 10
答案: 【 3】
4、单选题：
使用括号匹配算法判断以下表达式：([()[]{]}<>)结果是否匹配？匹配过程中栈内元素最多有多少个？
选项：
A: 否，3
B: 是，3
C: 是，4
D: 否，4
答案: 【 否，3】
5、单选题：
判断以下函数的功能def func(str1):
s = Stack()
for char in str1:
s.push(char)
str2 = ''
while not s.isEmpty():
str2 += s.pop()
return str2
选项：
A: 将给定的字符串反转输出
B: 判断给定字符串长度
C: 将给定字符串复制并输出
D: 包含错误，无法运行
答案: 【 将给定的字符串反转输出】
6、多选题：
以下哪些关于栈的说法是正确的？
选项：
A: 栈的pop操作时间复杂度是O(n)
B: 栈的pop操作时间复杂度是O(1)
C: 栈的特性是先进先出(FIFO)
D: 栈的特性是后进先出(LIFO)
E: 括号匹配算法需要栈结构的参与
F: 在Python中栈结构可以由list来实现
答案: 【 栈的特性是后进先出(LIFO);
括号匹配算法需要栈结构的参与;
在Python中栈结构可以由list来实现】
7、多选题：
以下未完成的函数可实现不同的功能def func(lst1):
s1, s2 = Stack(), Stack()
for item in lst1:
s1.push(item)
lst2 = []
while not s1.isEmpty():
### 在此进行代码填空 ###
return lst2
# 测试
print(func([1, 3, 5, 7, 9]))在下列选项中，填空内容与分别对列表[1, 3, 5, 7, 9]调用结果相对应的选项有？
选项：
A: lst2.append(s1.pop())[9, 7, 5, 3, 1]
B: lst2.append(s1.pop()) [1, 3, 5, 7, 9]
C: while not s1.isEmpty():
s2.push(s1.pop())
lst2.append(s2.pop())
while not s2.isEmpty():
s1.push(s2.pop())[1, 3, 5, 7, 9]
D: while not s1.isEmpty():
&nbs