MOOC 高级算法分析与数据结构(东北林业大学)1458488172 最新慕课完整章节测试答案
一、概述
文章目录
第一周测验
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、单选题：
下列哪个项目是抽象的逻辑功能？
选项：
A: 电视机使用手册；
B: 宫保鸡丁菜谱；
C: 汽车维修手册；
D: 电视机的电路图；
答案: 【 电视机使用手册；】
5、单选题：
逻辑功能接口和实现方法的关系？
选项：
A: 逻辑功能改变的话，实现方法可以保持不变。
B: 实现方法改变了，逻辑功能也一定会改变；
C: 逻辑功能接口的实现方法只有一种；
D: 逻辑功能接口是稳定的，可以用不同方法来实现；
答案: 【 逻辑功能接口是稳定的，可以用不同方法来实现；】
6、多选题：
一个图灵机应该由以下哪些部分组成？
选项：
A: 无限长的分格纸带
B: 读写头
C: 状态寄存器
D: 有限的控制规则
E: 字符
答案: 【 无限长的分格纸带;
读写头;
状态寄存器;
有限的控制规则】
7、多选题：
一般来说我们可以把生活中常见的问题分为哪几类？
选项：
A: 分类问题
B: 证明问题
C: 过程问题
D: 计算问题
答案: 【 分类问题;
证明问题;
过程问题】
8、多选题：
以下哪些方法不是以算法的概念来解决问题？
选项：
A: 超大规模分布式计算
B: 光子计算
C: DNA计算
D: 量子计算
E: 智慧众包
F: 星象占卜
答案: 【 智慧众包;
星象占卜】
七、排序与查找（上）
第七周测验
1、单选题：
以下关于冒泡和选择排序算法的叙述何者正确？
选项：
A: 平均时间复杂度上，冒泡排序的复杂度较低
B: 平均时间复杂度上，选择排序的复杂度较低
C: 空间复杂度上，冒泡排序的复杂度较低
D: 空间复杂度上，选择排序的复杂度较低
E: 其它选项皆不正确。
答案: 【 其它选项皆不正确。】
2、单选题：
以下关于归并和快速排序算法的叙述何者正确？
选项：
A: 平均时间复杂度上，归并排序的复杂度较低
B: 平均时间复杂度上，快速排序的复杂度较低
C: 空间复杂度上，归并排序的复杂度较低
D: 空间复杂度上，快速排序的复杂度较低
E: 其它选项皆不正确。
答案: 【 空间复杂度上，快速排序的复杂度较低】
3、单选题：
设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，则第一趟冒泡排序的结果为以下何者？
选项：
A: 2，5，3，6，8
B: 2，5，6，3，8
C: 2，3，5，6，8
D: 2，3，6，5，8
答案: 【 2，5，3，6，8】
4、单选题：
设一组初始记录关键字序列(5，2，6，3，8)，利用插入排序进行升序排序，则第二次插入排序的结果为以下何者？
选项：
A: 2，3，5，6，8
B: 2，5，3，6，8
C: 2，5，6，3，8
D: 5，2，3，6，8
答案: 【 2，5，6，3，8】
5、单选题：
给定两个已分别排序好的列表mylst1, mylst2，两者的长度分别为m<n为已知，现要查找其中位数，问最好的查找方式的时间复杂度？（可以理解为，alist=mylst1+mylst2，问查找alist的中位数的时间复杂度）
选项：
A: O(m^2)
B: O(mn)
C: O(m logn)
D: O(logm)
答案: 【 O(logm)】
6、多选题：
所谓排序算法的稳定性是指：排序前2个相等的数，其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。以下哪些排序算法是稳定的？
选项：
A: 冒泡排序
B: 插入排序
C: 归并排序
D: 快速排序
E: 选择排序
F: 希尔排序
答案: 【 冒泡排序;
插入排序;
归并排序】
7、多选题：
现在有一个几乎顺序排列的，非常大的列表。问以下哪些算法有可能得到时间复杂度O(N)?
选项：
A: 冒泡排序
B: 插入排序
C: 选择排序
D: 归并排序
E: 快速排序
答案: 【 冒泡排序;
插入排序;
归并排序】
8、多选题：
以下哪些排序方式，其最坏情况的时间复杂度O(N^2)的？
选项：
A: 快速排序
B: 选择排序
C: 冒泡排序
D: 插入排序
E: 归并排序
答案: 【 快速排序;
选择排序;
冒泡排序;
插入排序】
三、基本结构（上）
第三周测验
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():
s2.push(s1.pop())
lst2.append(s2.pop())
while not s2.isEmpty():
s1.push(s2.pop())[9, 7, 5, 3, 1]
E: lst2.append(s1.peek())死循环，无法运行
F: lst2.append(s1.peek())[9, 9, 9, 9, 9]
G: for i in range(s1.pop()):
s2.push(i)
lst2.append(s2.size())[9, 16, 21, 24, 25]
H: for i in range(s1.pop()):
s2.push(i)
lst2.append(s2.size())[1, 4, 9, 16, 25]
答案: 【 lst2.append(s1.pop())[9, 7, 5, 3, 1];
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];
lst2.append(s1.peek())死循环，无法运行;
for i in range(s1.pop()):
s2.push(i)
lst2.append(s2.size())[9, 16, 21, 24, 25]】
8、多选题：
以下哪些算法可以使用栈来实现？
选项：
A: 实现UNDO和REDO功能的算法
B: HTML标签匹配算法
C: 求列表平均数的算法
D: 1到N的累计求和算法
答案: 【 实现UNDO和REDO功能的算法;
HTML标签匹配算法】
九、树及算法（上）
第九周测验
1、单选题：
按照课件”603 树的嵌套列表实现“的函数定义进行以下操作：x = BinaryTree('a')
insertLeft(x,'b')
insertRight(x,'c')
insertRight(getRightChild(x),'d')
insertLeft(getRightChild(getRightChild(x)),'e')树x的结果是？
选项：
A: ['a', ['b', [], []], ['c', [], ['d', [], []]]]
B: ['a', ['c', [], ['d', ['e', [], []], []]], ['b', [], []]]
C: ['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]
D: ['a', ['b', [], ['d', ['e', [], []], []]], ['c', [], []]]
答案: 【 ['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]]】
2、单选题：
设x是一个完全二叉树，x共有33个节点，并以非嵌套列表的形式给所有节点编号1~33（此部分可参考”608 优先队列和二叉堆“）。选出错误的选项。
选项：
A: 树的高度为5
B: 18号节点的父节点是9号
C: 23号没有子节点
D: 整个树的左子树比右子树多1个节点
答案: 【 整个树的左子树比右子树多1个节点】
3、单选题：
此处规定二叉树中，左子节点与右子节点地位不同（即某个父节点只有一个子节点时，也要区分它是左子节点还是右子节点）。定义一个函数c(n)，按照此方法，构建一个包含n个节点的，符合规则的树的方法数。问c(1), c(2), c(3), c(4)的值。
选项：
A: 1，1，2，3
B: 1，1，2，4
C: 1，2，4，8
D: 1，2，5，14
答案: 【 1，2，5，14】
4、单选题：
以下关于空树说法何者正确？
选项：