第一周测验

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、多选题：
‍一个图灵机应该由以下哪些部分组成？‎
选项：
A: 无限长的分格纸带
B: 读写头
C: 状态寄存器
D: 有限的控制规则
E: 字符
答案: 【 无限长的分格纸带;
读写头;
状态寄存器;
有限的控制规则】

6、多选题：
‍一般来说我们可以把生活中常见的问题分为哪几类？‎
选项：
A: 分类问题
B: 证明问题
C: 过程问题
D: 计算问题
答案: 【 分类问题;
证明问题;
过程问题】

7、多选题：
‌以下哪些方法不是以算法的概念来解决问题？‏
选项：
A: 超大规模分布式计算
B: 光子计算
C: DNA计算
D: 量子计算
E: 智慧众包
F: 星象占卜
答案: 【 智慧众包;
星象占卜】

8、多选题：
‎以下关于“抽象”的描述正确的是：​
选项：
A: “抽象”忽略实体或问题中次要的方面，只强调该实体或问题的本质信息。
B: 在利用计算机求解问题时，需要对各个工作步骤进行过程抽象。
C: 对一个对象，不同的用户看到的抽象的层次可能不同。
D: 从客观世界到信息世界不是简单的数据描述，而是从客观世界中抽象出合适的数据结构并进行操作处理的过程。
答案: 【 “抽象”忽略实体或问题中次要的方面，只强调该实体或问题的本质信息。;
在利用计算机求解问题时，需要对各个工作步骤进行过程抽象。;
对一个对象，不同的用户看到的抽象的层次可能不同。;
从客观世界到信息世界不是简单的数据描述，而是从客观世界中抽象出合适的数据结构并进行操作处理的过程。】

第七周测验

1、单选题：
‎下列哪个算法使用到了分治策略？​
选项：
A: 二分查找
B: 单词最短编辑距离
C: 迷宫寻路
D: 博物馆大盗问题
答案: 【 二分查找】

2、单选题：
​函数值缓存最适合使用哪种Python中的数据类型？‍
选项：
A: 列表
B: 字典
C: 集合
D: 栈
答案: 【 字典】

3、单选题：
‎已知数列G(x)满足：‏‎G(1)=G(2)=G(3)=1‏‎G(x)=G(x-1)+G(x-2)+G(x-3) (x≥4)‏‎根据递推式写出求数列值的递归算法，问原始算法与采用函数值缓存的算法时间复杂度分别为多少？‏
选项：
A: O(3^n); O(n)
B: O(2^n); O(n)
C: O(n^3); O(n^2)
D: O(2^n); O(1)
答案: 【 O(3^n); O(n)】

4、单选题：
‌博物馆大盗问题中，若共有10件宝物，背包总重为20单位，使用动态规划算法求解时需要建立多大的数组？‎
选项：
A: 11×21
B: 12×21
C: 10×21
D: 10×20
E: 11×20
F: 12×20
G: 10×22
H: 11×22
I: 12×22
答案: 【 11×21】

5、单选题：
‌以下哪个说法是正确的？‌
选项：
A: 贪心法适用于局部最优等同于总体最优的问题求解
B: “单词最短编辑距离”问题可使用贪心法解决
C: 相比于函数值缓存，动态规划的优势在于不需要额外的存储空间
D: “字符串匹配”问题中不能应用动态规划思想
答案: 【 贪心法适用于局部最优等同于总体最优的问题求解】

6、多选题：
‍以下是使用递归算法对N皇后问题求解的不完整代码：​‍def solveNQueen(N):
    pool = # <A>
    def queen(cur=0):
        if cur == len(pool):
            return # <X>
        res = # <Y>
        for col in range(len(pool)):
            pool[cur], flag = col, True
            for row in range(cur):
                if pool[row] == col or abs(col – pool[row]) == cur – row:
                    flag = False
                    break
            if flag:
                res += queen(cur+1)
        return res
    
    return queen(0)

# test
print(solveNQueen(8))阅读代码，选出正确的选项​
选项：
A: A处可以填“[None]*N”
B: A处可以填“[0]*N”
C: A处可以填“[]”
D: 若X处填"[list(pool)]"，Y处填"[]"，该函数可返回N皇后问题的所有解
E: 若X处填"[list(pool)]"，Y处填"[]"，该函数可返回N皇后问题解的个数
F: 若X处填"1"，Y处填"0"，该函数可返回N皇后问题解的个数
G: 若X处填"1"，Y处填"0"，该函数可返回N皇后问题的所有解
H: 该算法时间复杂度为O(N)
I: 该算法时间复杂度为O(N^2)
答案: 【 A处可以填“[None]*N”;
A处可以填“[0]*N”;
若X处填"[list(pool)]"，Y处填"[]"，该函数可返回N皇后问题的所有解;
若X处填"1"，Y处填"0"，该函数可返回N皇后问题解的个数】

7、多选题：
​以下哪些问题可用动态规划算法解决？‎
选项：
A: 斐波那契数列求值
B: 单词最短编辑距离
C: 列表排序
D: 后缀表达式求值
答案: 【 斐波那契数列求值;
单词最短编辑距离】

8、多选题：
‎以下哪些说法是正确的？‍
选项：
A: 函数值缓存可以减少算法的时间复杂度
B: 函数值缓存不能减少算法的空间复杂度
C: 动态规划可以减少算法的时间复杂度
D: 动态规划不能减少算法的空间复杂度
E: 函数值缓存不能减少算法的时间复杂度
F: 函数值缓存可以减少算法的空间复杂度
G: 动态规划可以减少算法的空间复杂度
H: 动态规划不能减少算法的时间复杂度
答案: 【 函数值缓存可以减少算法的时间复杂度;
函数值缓存不能减少算法的空间复杂度;
动态规划可以减少算法的时间复杂度;
动态规划不能减少算法的空间复杂度】

第三周测验

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、单选题：
‍将以下中缀表达式：‏‍(A+B)*(C-D)/(E-F*G)‏‍转换为后缀表达式，结果为？‏
选项：
A: A+B*C-D/E-F*G
B: AB+CD-*EFG*-/
C: AB+C*D-E/F-G*
D: ABCDEFG+*-/-*
答案: 【 AB+CD-*EFG*-/】

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,