[渝粤教育] 天水师范学院 算法与数据结构 参考 资料

教育
-算法与数据结构-章节资料考试资料-天水师范学院【】
第一周测验
1、【单选题】以下关于基于有穷观点的能行方法说法错误的是：
A、由有限数量的任意指令构成
B、指令执行在有限步骤后终止
C、指令每次执行都得到唯一的结果
D、原则上可以由人单独采用纸笔完成
参考资料【 】
2、【单选题】以下关于ADT抽象数据类型说法错误的是：
A、ADT是对数据进行处理的一种逻辑描述。
B、ADT建立的封装技术将可能的处理实现细节隐蔽起来。
C、同一ADT只有唯一的数据结构可以实现。
D、采用程序设计语言的控制结构和基本数据类型来实现ADT的所提供的逻辑接口。
参考资料【 】
3、【单选题】关于“图灵机”，下列说法不正确的个数为：1）图灵机给出的是计算机的理论模型；2）图灵机的状态转移函数q, X, Y, R(或L或N), p，其实就是一条指令，即在q状态下，当输入为X时，输出为Y，读写头向右®、向左(L)移动一格或不动(N)，状态变为p；3）图灵机是一种离散的、有穷的、构造性的问题求解思路；4）凡是能用算法方法解决的问题也一定能用图灵机解决，凡是图灵机解决不了的问题算法也解决不了。
A、0
B、1
C、2
D、3
参考资料【 】
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、【单选题】判断下列代码段，关于的大O级别：test = 0
for i in range(n):
for j in range(n):
for k in range(i):
test = test + i * j
A、O(n)
B、O(n^2)
C、O(n^3)
D、O(n _log(n))
参考资料【 】
2、【单选题】判断下列代码段的大O级别：test = 0
for i in range(n):
test = test + 1
for j in range(n):
test = test - 1
for k in range(n):
test = test * 1
A、O(n)
B、O(n^2)
C、O(n^3)
D、O(n_log(n))
参考资料【 】
3、【单选题】判断下列代码段的大O级别：for i in range(n):
for j in range(i):
k = 2 + 2
A、O(n)
B、O(n^2)
C、O(n^3)
D、O(1)
参考资料【 】
4、【单选题】判断下列代码段的大O级别：def function(n):
return 2
A、O(n)
B、O(n^2)
C、O(n^3)
D、O(1)
参考资料【 】
5、【单选题】以下是一个快速幂算法：def pow(x, n):
if n0:
return 1
elif n1:
return x
elif n%2==0:
return pow(x _x, n//2)
else:
return pow(x_x, n//2)_x问它对于n的大O级别。
A、O(n)
B、O(log n)
C、O(nlog n)
D、O(1)
参考资料【 】
6、【多选题】下面的列表操作中哪些是O(1)的？（假设列表alist足够长，不导致任何报错）
A、alist.pop(0)
B、alist.pop()
C、alist.append(10)
D、alist[10:16]
E、alist.sort()
参考资料【 】
7、【多选题】下面的字典操作中哪些是O(1)的？
A、’’ in my_dict
B、del my_dict[’’]
C、my_dict[’’] == 10
D、my_dict[’’] += 1
参考资料【 】
8、【多选题】令n为问题规模，其中解决本问题的三个算法称为A,B,C，他们需要的总运算次数分别是：A: 96+108n+24n2+12n3B: 16+3n^48C: 10080+168n+7n^2_log(n)三个算法的时间复杂度的大O级别中，以下表述正确的有：
A、A算法和B算法的时间复杂度相同
B、B算法比A算法的时间复杂度更大
C、C算法的时间复杂度最大
D、C算法的时间复杂度最小
E、A算法比B算法的时间复杂度更大
参考资料【 】
第三周作业
第三周测验
1、【单选题】假设你执行了下列的栈操作：s = Stack()
s.push(1)
s.push(3)
s.push(5)
s.pop()
s.push(7)现在栈内还有哪些元素？
A、1, 5, 7
B、3, 5, 7
C、1, 3, 7
D、1, 3, 5
参考资料【 】
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 + -
参考资料【 】
3、【单选题】给定后缀表达式3 6 + 5 2 - /求值结果为？
A、3
B、4
C、6
D、10
参考资料【 】
4、【单选题】使用括号匹配算法判断以下表达式：([()[]{]})结果是否匹配？匹配过程中栈内元素最多有多少个？
A、否，3
B、是，3
C、是，4
D、否，4
参考资料【 】
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来实现
参考资料【 】
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]
参考资料【 】
8、【多选题】以下哪些算法适合用栈来实现？
A、实现UNDO和REDO功能的算法
B、HTML标签匹配算法
C、求列表平均数的算法
D、1到N的累计求和算法
参考资料【 】
第四周作业
第四周测验
1、【单选题】下列叙述正确的是？
A、有两个指针域的链表称为二叉链表
B、队列可以用链式存储结构的双向链表实现
C、带链的栈有栈顶指针和栈底指针，因此又称为双重链表
D、节点中具有多个指针域的链表称为多重链表
E、栈可以用链式存储结构的单链表实现
参考资料【 】
2、【单选题】用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时
A、仅修改队头指针
B、仅修改队尾指针
C、队头、队尾指针都必须要修改
D、队头、队尾指针都可能要修改，但不必然都修改
参考资料【 】
3、【单选题】递归过程或函数调用时，处理参数或返回地址，用以下哪种数据结构最合适？
A、栈
B、队列
C、线性表
D、多维数组
参考资料【 】
4、【单选题】设有序单链表的关键字序列为{1,4,6,11,19,35,52,54,57,71,78,86,92,96}，当查找关键字为21的结点时，经( )次比较后查找失败？
A、14
B、6
C、7
D、3
参考资料【 】
5、【单选题】设某顺序表中第一个元素的起始存储地址为a,每个元素的长度为b,则第c个元素的起始地址是？（a,b,c均为非负整数）
A、a+b c
B、a+b+c
C、a+b(c-1)
D、a+(b-1)*c
参考资料【 】
6、【多选题】以下哪些不是单链表的特点？
A、随机存取
B、顺序存取
C、插入删除元素时需要移动表中元素
D、插入删除元素时不必移动表中元素
E、插入删除元素时需要修改指针
参考资料【 】
7、【多选题】以下哪些是顺序表的特点？
A、随机存取
B、顺序存取
C、插入删除元素时需要移动表中元素
D、插入删除元素时不需要移动表中元素
参考资料【 】
8、【多选题】设一个队列的入队顺序是1，2，3，4，5，那下列哪些是不能存在的出队顺序？
A、1，2，3，5，4
B、3，4，5，1，2
C、1，2，3，4，5
D、5，4，3，2，1
E、1，2，5，4，3
F、2，3，4，5，1
参考资料【 】
第五周作业
第五周测验
1、【单选题】以下哪项不是递归的三定律之一？
A、有一个基本结束条件
B、算法调用自身
C、能够不断减小问题规模
D、对函数运行结果进行缓存
参考资料【 】
2、【单选题】递归函数的实现与哪种数据结构直接相关？
A、栈
B、队列
C、堆
D、无序表
参考资料【 】
3、【单选题】使用进制转换函数：def toStr2(n,base):
convertString=‘0123456789ABCDEF’
if n == 0:
return ‘’
return toStr2(n // base, base) + convertString[n % base]将数字135转换为三进制“12000”的过程中，函数共被调用了多少次（包含初始调用）？
A、3
B、4
C、5
D、6
参考资料【 】
4、【单选题】若定义实心等边三角形为0阶谢尔宾斯基三角，现给定一个边长为1的4阶谢尔宾斯基三角，请问它的面积更接近以下哪个数字？
A、0.316
B、0.244
C、0.183
D、0.137
E、0.237
参考资料【 】
5、【单选题】以下是使用递归方式实现的圆括号匹配函数：def match(s, n=0):
if s:
if s[0] == ‘(’:
n += 1
else:
n -= 1
if n 0:
return False
return match(s[1:], n)
else:
return n == 0请问以下哪个输入中可能出现参数为match(((())), 3)的函数调用？
A、"(((()((()))"
B、"()((()))"
C、"((()))((("
D、"((()))"
参考资料【 】
6、【多选题】给定绘制分形树函数：def tree(branch_len):
t.pendown()
t.forward(branch_len)
t.penup()
if branch_len 5:
t.left(20)
tree(branch_len - 5)
t.right(40)
tree(branch_len - 5)
t.left(20)
t.backward(branch_len)其中t为海龟画笔对象。在调用函数tree(50)时，下列哪些说法是正确的？
A、画线的长度总和为10180
B、画线的长度总和为9150
C、组成树的线段共1023条
D、组成树的线段共511条
E、树梢与树根的路径距离为275
F、树梢与树根的路径距离为270
G、树梢共512个
H、树梢共256个
参考资料【 】
7、【多选题】以下函数用于可用于求方程的近似解，其中参数f为一个输入、输出均为数字的函数def solve(f, x1, x2):
mid = (x1 + x2) / 2
if f(mid) == 0 or abs(x1 - x2) 1e-8:
return # A
elif f(mid) * f(x1) 0:
return # B
else:
return # C如何补全该函数使其可以正常使用？
A、A处应填：mid
B、A处应填：solve(f, x1, mid)
C、A处应填：solve(f, mid, x2)
D、B处应填：solve(f, mid, x2)
E、B处应填：mid
F、B处应填：solve(f, x1, mid)
G、C处应填：solve(f, x1, mid)
H、C处应填：mid
I、C处应填：solve(f, mid, x2)
参考资料【 】
8、【多选题】以下哪些问题不能用递归算法求解？
A、图像、语义识别
B、求斐波那契数列第N项的值
C、查找有序列表中某元素是否存在
D、计算两个数的差
参考资料【 】
第六周测验
1、【单选题】下列哪个算法使用到了分治策略？
A、二分查找
B、单词最短编辑距离
C、迷宫寻路
D、博物馆大盗问题
参考资料【 】
2、【单选题】函数值缓存最适合使用哪种Python中的数据类型？
A、列表
B、字典
C、集合
D、栈
参考资料【 】
3、【单选题】已知数列G(x)满足：G(1)=G(2)=G(3)=G(4)=1G(x)=G(x-1)+G(x-2)+G(x-3)+G(x-4) (x≥5)根据递推式写出求数列值的递归算法，问原始算法与采用函数值缓存的算法时间复杂度分别为多少？
A、O(4^n); O(n)
B、O(5^n); O(n^2)
C、O(n^4); O(n^2)
D、O(5^n); O(1)
参考资料【 】
4、【单选题】博物馆大盗问题中，若共有8件宝物，背包总重为25单位，使用动态规划算法求解时需要建立多大的数组？
A、9x26
B、9x25
C、10x25
D、10x26
E、8x25
F、8x26
G、10x27
H、9x27
I、8x27
参考资料【 】
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处可以填“[]_N”
C、A处可以填“[0 for i in range(N)]”
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)
参考资料【 】
7、【多选题】以下哪些问题可用动态规划算法解决？
A、斐波那契数列求值
B、单词最短编辑距离
C、列表排序
D、后缀表达式求值
参考资料【 】
8、【多选题】以下哪些说法是错误的？
A、函数值缓存可以减少算法的时间复杂度
B、函数值缓存不能减少算法的空间复杂度
C、动态规划可以减少算法的时间复杂度
D、动态规划不能减少算法的空间复杂度
E、函数值缓存不能减少算法的时间复杂度
F、函数值缓存可以减少算法的空间复杂度
G、动态规划可以减少算法的空间复杂度
H、动态规划不能减少算法的时间复杂度
参考资料【 】
第七周作业
第七周测验
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
参考资料【 】
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
参考资料【 】
5、【单选题】给定两个已分别排序好的列表mylst1, mylst2，两者的长度分别为mn为已知，现要查找两表合并后的中位数，问最好的查找方式的时间复杂度？（可以理解为，查找 alist=sorted(mylst1+mylst2) 的中位数的时间复杂度）
A、O(m^2)
B、O(mn)
C、O(m logn)
D、O(logm)
E、O(n 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、【单选题】按照课件”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’, [], []]]
参考资料【 】
2、【单选题】设x是一个完全二叉树，x共有33个节点，并以非嵌套列表的形式给所有节点编号1~33（此部分可参考”608 优先队列和二叉堆“）。选出错误的选项。
A、树的高度为5
B、18号节点的父节点是9号
C、23号没有子节点
D、整个树的左子树比右子树多1个节点
E、23号节点的父节点是11号
F、27号节点的父节点是14号
参考资料【 】
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
参考资料【 】
4、【单选题】以下关于空树说法何者正确？
A、是一个树，但不是一个二叉树
B、是一个树，也是一个二叉树
C、不是一个树，而是一个二叉树
D、不是一个树，也不是一个二叉树
参考资料【 】
5、【单选题】四叉树是一种树状结构，常用于图像或空间索引，典型体现为快速加载低清图像或地图，并随着读入数据的量的增加，逐渐提高解析度。四叉树的每个节点，恰有0或4个子节点，且每个子节点的地位也不同（在图像或空间信息处理上，子节点的地位通常表示相对位置）。以下关于非空的四叉树的说法，何者错误？
A、四叉树的节点数量符合4k+1形式，其中k是非负整数
B、若某个四叉树有n个节点，则有ceil(n_3/4)个节点为叶节点
C、若某个四叉树有n个节点，则有n//4个节点不是叶节点
D、若某个四叉树有n个节点，则树的高度有ceil(log_4(n))层
参考资料【 】
6、【多选题】关于树myTree = [‘a’, [‘b’, [‘d’,[],[]], [‘e’,[],[]] ], [‘c’, [‘f’,[],[]], []] ]的说法，何者正确？
A、左子树是[‘b’, [‘d’, [], []], [‘e’, [], []]]
B、左子树的根是’b’
C、右子树是[‘c’, [‘f’, [], []], []]
D、右子树的根是’e’
参考资料【 】
7、【多选题】设x是一个完全二叉树，x共有5个深度为3的节点，并以非嵌套列表的形式给所有节点编号（此部分可参考”608 优先队列和二叉堆“）。选出正确的选项。
A、x共有12个节点
B、x共有13个节点
C、6号节点有子节点12和13
D、6号节点有子节点12
E、7号节点有1个子节点
F、7号节点没有子节点
参考资料【 】
8、【多选题】设一个二叉树有p个出度（此处可以理解为子节点的个数）为0的节点，q个出度为1的节点，r个出度为2的节点，问下列叙述何者正确？
A、此树的总节点数为p+q+r
B、叶节点有p个
C、根节点有r个
D、p=r+1
参考资料【 】
第十周作业
第十周测验
1、【单选题】如下哪个树正确地显示了按顺序插入键值5，30，2，40，25，4后的二叉搜索树？
A、
B、
C、
D、其它选项都不对
参考资料【 】
2、【单选题】对以下这棵树：<img src="http://edu-image.nosdn.127.net/EB3D57D60B3032E23F3E18F3BC6A4DF7.jpg?imageView操作，欲把根节点11删除，remove方法做完后新的根节点是（），其右子树的高度是（）。
A、12，2
B、12，1
C、15，2
D、15，1
参考资料【 】
3、【单选题】下图有两棵树，其中a（）平衡二叉树，b（）平衡二叉树。
A、是，是
B、是，不是
C、不是，是
D、不是，不是
参考资料【 】
4、【单选题】对下面这棵树查找元素77，在查找失败前需要进行几次比对？
A、1
B、2
C、3
D、4
参考资料【 】
5、【单选题】高度为4的平衡二叉树最少有（）个节点。
A、12
B、15
C、7
D、9
参考资料【 】
6、【单选题】考虑规模为n的二叉搜索树中，put, get, del, in 四个方法的时间复杂度数量级。四个方法中，有（）个方法在最差情况下，具有O(n)的时间复杂度
A、1
B、2
C、3
D、4
参考资料【 】
7、【多选题】将键值1，2，3，4，5，6，7，8，9，10的10个元素以某种顺序插入某二叉搜索树后，发现这个树的根是3。问这个树的高度可能为多少？（规定仅有根的树的高度为0）
A、2
B、3
C、4
D、5
E、6
F、7
参考资料【 】
8、【多选题】这是一棵右重树，圈内写出其点的名称和其平衡因子：<img src="http://edu-image.nosdn.127.net/9D6FBE732029387EECD18CA6F85DD677.png?imageView将它进行旋转以后得到的树叫做T，选出错误的选项。
A、T的根是D
B、T的根是C
C、T的根是B
D、根的左子节点是B
E、根的左子节点是A
F、根的右子节点是D
G、根的右子节点是E
参考资料【 】