大学MOOC 数据结构与算法（李峙）(南宁师范大学)1454410165 最新慕课完整章节测试答案

第一周测验

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、单选题：
‎以下关于冒泡和选择排序算法的叙述何者正确？‌
选项：
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&