题库试卷

【百年教育职业培训中心】算法与数据结构-章节资料考试资料-天水师范学院 (2)

来源：百年教育职业培训中心　更新时间：2022-06-01 20:25:53

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！答案：微信搜索【渝粤教育】公众号第一周测验1、【单选题】以下关于基于有穷观点的能行方法说法错误的是

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！

答案：微信搜索【渝粤教育】公众号

第一周测验

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，读写头向右(R)、向左(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 n==0:
return 1
elif n==1:
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+24n^2+12n^3B: 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、<img src="http://edu-image.nosdn.127.net/0ECA5712B27254E3B7D8DB0FF86A918C.png?imageView&thumbnail=890x0&quality=100" />

B、<img src="http://edu-image.nosdn.127.net/310F14A8EBD15A392F959A1312EE1521.png?imageView&thumbnail=890x0&quality=100" />

C、<img src="http://edu-image.nosdn.127.net/2474025934569434FACD90EAC268C690.png?imageView&thumbnail=890x0&quality=100" />

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（）平衡二叉树。<img src="http://edu-image.nosdn.127.net/801B8832D8ECFDA633FAA625A70B2A6D.jpg?imageView&thumbnail=890x0&quality=100" />

A、是，是

B、是，不是

C、不是，是

D、不是，不是

4、【单选题】对下面这棵树查找元素77，在查找失败前需要进行几次比对？<img src="http://edu-image.nosdn.127.net/A1598FB80A897782242C65A2A3CCED8E.jpg?imageView&thumbnail=890x0&quality=100" />

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