资源简介

数据与数据结构 综合检测
一、选择题
1．有如下Python程序段：
import random
lst=['A'，'B'，'C'，'D']
st=[0]*len（lst）
i，top=0，-1
while i k=random.randint（0，1）
if k==0：
top+=1
st[top]=lst[i]
i+=1
elif top!=-1：
lst[i]=st[top]
top-=1
执行该程序段后，lst的值不可能是（ ）
A．['A'，'B'，'C'，'D'] B．['A'，'B'，'A'，'C'] C．['A'，'A'，'C'，'D'] D．['A'，'A'，'C'，'A']
2．有如下自定义函数：
def fg（n）：
if n<=2：
return n
else：
return fg（n-1）+fg（n-2）
执行语句s=fg（4），下列说法不正确的是（ ）
A．s的值为5 B．函数fg被调用的次数是4
C．第二次被调用的函数是fg（3） D．该程序采用了递归算法
3．一条狭长的管道内有3个物体，每个物体可向左或向右移动，也可停在缓冲带上（最多停一个）。经过多次移动，物体状态从a变成c，其中b为移动中某次状态，如图所示，则移动过程中所有物体经过T点的最少总次数是（ ）
A．8 B．7 C．5 D．3
4．下列二叉树中，前序和中序遍历结果一样的选项是（ ）
A． B． C． D．
5．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（ ）
A．5 B．4 C．3 D．2
6．某二叉树前序遍历为ABDFGCEH，后序遍历为FGDBHECA，则下列选项不可能是此二叉树的是（ ）
A． B． C． D．
7．有如下Python程序：
def fun(x,n):
if x == n:
return 1
if n % x == 0:
return fun(x,n//x)+1
else:
return fun(x+1,n)
print(fun(2,100))
执行上述程序后，输出的结果是（ ）
A．2 B．3 C．4 D．5
8．有如下Python程序段：
a = [1,2,3,4,5];b = [3,2,5,1,4]
stack =[];i = j = 0
while i < len(a):
stack.append(a[i])#将a[i]添加到stack末尾
i += 1
while len(stack)>0 and stack[-1] == b[j]:
stack.pop()#移除stack末尾元素
j +=1
执行该程序段后，stack中的元素个数为（ ）
A．0 B．1 C．2 D．3
9．某二叉树对应的一维数组表示如下图所示：
下列关于该二叉树的说法正确的是（ ）
A．这是一棵完全二叉树 B．节点F是节点D的孩子节点
C．该二叉树有1个叶子结点 D．该二叉树中序遍历的结果是DBEACF
10．某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（ ）
A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV
11．若有一批元素的出栈顺序为“i, n, p, u, t”，其入栈顺序不可能是（ ）
A．n, i, t, u, p B．n, i, u, t, p C．t, u, p, n, i D．i, n, p, u, t
12．诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（ ）
A．树 B．栈 C．队列 D．链表
13．用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态），且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是（ ）
A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4
14．利用栈求逆波兰表达式（表达式由操作数和运算符组成）的方法是:从左往右扫描该表达式，遇到操作数时入栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时（abcdef表示不同的操作数），所使用的栈的深度至少为（ ）
A．3 B．4 C．5 D．6
15．下列二叉树中，后序遍历结果不为CBFEAD的是（ ）
A． B． C．D．
16．已知x="123"，y="456"，则表达式x+y 的值为（ ）
A．"123456" B．"567" C．"123"+"456" D．"579"
17．斐波那契数列也叫兔子繁殖数列，小明编写了下列代码求第74个月能繁殖多少对兔子，他使用的算法是（ ）
A．解析法
B．迭代法
C．枚举法
D．二分法
18．有如下程序段：
def cal(n):
if n <= 1:
return 1
if n % 2 == 0:
return 2*cal(n-1)
return 1+cal(n-1)
执行语句k=cal(5)，则k的值为（ ）
A．6 B．7 C．10 D．11
19．下列有关迭代算法和递归算法的描述，不正确的是（ ）
A．在使用递归算法时，必须有一个明确的递归结束条件，称为递归出口
B．一般来说，迭代算法效率较低，而递归算法效率较高
C．递归中一定有迭代，但迭代中不一定有递归
D．通常情况下，迭代算法和递归算法可以相互转换
20．某二叉树的树形结构如图所示，其后序遍历结果为FABGDEC，则中序遍历结果为（ ）
A．FDAGBCE B．FDABGEC
C．AGBDFCE D．FDAGBEC
二、填空题
21．Python 表达式int (2.5)的值为 。
22．def f(x,y):
ans=y;
for i in range(1,y-x+1):
ans = ans + f(x+i,y-i)
return ans;
def init():
x = int(input())
y = int(input())
print(f(x,y))
init()
(1)
输入：4
5
输出：
(2)
输入：3
6
输出：
23．有如下Python程序段：
import random
n=6
a=[9,4,3,4,7,6]
for i in range(n-1,0,-1):
for j in range(0,i):
if a[i] < a[j]:
a[i],a[j]=a[j],a[i]
print(a)
排序后，数组a=
24．下面程序输出结果是( )
S=0
For i in range(1,5):
S=S+20
print(“S=”,S,end=”\n”)
25．已知 x = [3, 5, 7] ，那么执行语句 x[1:] = [2] 之后，x 的值为 。
三、判断题
26．在程序语言中都规定了运算符的优先级，通常是算术运算符高于关系运算符，关系运算符高于逻辑运算符，在一个表达式中无法通过其他手段改变运算顺序。( )
27．算术运算符中*、/的运算优先级高于//和%。( )
28．Python语言的表达式中，“%”是取模算术运算符。( )
29．如果变量a=5，那么表达式10>a and a<3的结果为False。( )
30．在 Python语言环境下，表达式13%2+7//2的值为4.5。 ( )
四、操作题
31．检查数学表达式中的括号是否配对是计算机进行数学计算的重要环节。括号序列“（）（）”中的“（”与“）”是配对的，而序列“（））（”中的括号则是不配对的。对于不配对的序列，可以将“（”修改为“）”,或者将“）”修改为“（”来实现配对。如图所示是括号序列“（））（（）”通过不同的修改方案使其配对所需要的修改次数，最少修改次数为2。
请回答下列问题：
（1）若括号序列为“（））））（））”，最少需要修改 次才能使得括号序列中的括号配对。
（2）编写程序，计算修改括号序列使其配对的最少次数。部分Python程序如下，请在划线处填入合适的代码。
s=input（）#输入括号序列，序列中仅包含“（”、“）”两种字符，且长度为偶数
x=0
ans=0
for i in range（len（s））:
if s[i]=='（':
①
elif s[i]=='）'and x>=1:
x-=1
elif s[i]=='）'and② :
ans+=1;x+=1;
ans+=③
print（ans）
32．某奶茶店收到了n杯奶茶的订单，这n杯奶茶分别经过甲、乙两个工序加工，并且必须先在甲工序加工后才可以进行乙工序。为了使得总加工时间最短，我们可以将这n杯奶茶分为两类：
第一类：甲工序的加工时长少于乙工序的加工时长。
第二类：甲工序的加工时长不少于乙工序的加工时长。
第一类应将在甲工序花费时间少的产品排在前面，第二类应将在乙工序花费时间少的产品排在后面，然后先处理所有第一类产品，再处理第二类产品。可以证明，这样排序后所有奶茶加工完成花费的总时间最少。
如：有4杯奶茶的订单，它们在甲工序的加工时长分别为2、3、5、1，在乙工序的加工时长分别为3、1、2、5，将奶茶分类、排序、合并、计算时长的过程如图所示，最后得出总时长为12。(每杯奶茶在乙工序开始加工需同时满足它甲工序加工完并且乙工序已加工完上一个产品这两个条件)
编写程序模拟奶茶店对这n杯奶茶的处理过程，计算总加工时间。
请回答下列问题:
（1）由题意可知，若3杯奶茶在甲工序加工时长分别为3、1、3，乙工序加工时长分别为2、4、3，则总加工时长为 。
（2）小李先编写了如下将第一类产品排序的函数:
def order1(a,b): #参数a、b的元素分别表示每杯奶茶在甲乙两道工序的加工时长。
ans=[0]*100
idx=[0]*100
tmp1=[];tmp2=[]
for i in range(len(a)):
①
idx[a[i]]=b[i] #原始序号排序后会跑到第b[i]位置上
for i in range(len(ans)):
while ans[i]>0:
②
tmp2.append(idx[i])
ans[i]-=1
return tmp1,tmp2
请在划线处填入合适的代码。
（3）小方编写了将第二类产品排序的函数:
def order2(a,b): #参数a、b的元素分别表示每杯奶茶在甲乙两道工序的加工时长。
#代码略
小张结合前两位同学的程序，计算产品加工总时长。请在划线处填入合适的代码。读取n杯奶茶在甲乙两道工序加工的时间，根据题目要求分为两类，第一类在甲乙两道工序加工的时间分别存储在列表a1和列表b1中,并通过order1()函数排序，第二类在甲乙两道工序加工的时间分别存储在列表a2和列表b2中,并通过order2()函数排序，代码略。
‘’’#代码略
a=a1+a2
b=b1+b2
n= len(a)
ta,tb=0,0 #ta为甲加工时间，tb为乙加工时间
for i in range (n) :
ta+=a[i]
if ① :
tb=ta
②
print("总加工时长最短为:",tb)
33．小强学习过大数据的“分治”思想后，对经“分治”处理后的数据合并产生了兴趣。他设计了一个算法，对两个升序列表a、b中的数据(均为正整数)进行合并，合并后的数据仍保持升序。
（1）为了生成长度为num 的升序列表x，小强写了如下代码。
import random
def mk(num) ：
x= [0]*num #创建列表 x= [0，0，……，0]，其中 0 的个数是 num
x[0]=random.randint(5，10) #randint(a，b)返回[a，b]区间内的一个随机整数
for i in range(1，num) ：
return x
m=n=5
a=mk(m)
b=mk(n)
print("原始数据序列 a 为："，a)
print("原始数据序列 b 为："，b)
①使用语句 a= mk(5)调用函数，加框处语句的执行次数是 (填写阿拉伯数字) 。
②执行上述代码后，关于输出的列表a、b 中的数据，下列说法正确的是 (单选，填字母： A .相同 / B .不相同 / C .可能相同)
（2）为了描述方便，假设两个列表中的元素个数m=n=5，其初始状态如下：
b[0] b[1] b[2] b[3] b[4]
10 11 15 16 17
为了使合并后的数据保存在列表a 中，现对列表 a 扩充 n 个元素“-1”，扩充后状态如下：
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
7 9 10 14 19 -1 -1 -1 -1 -1
变量i赋值为0，指向列表b的首数据，变量p赋值为0，指向列表a的首数据，变量tot指向列表a的最后一个有效数据(如图所示) 。
合并的具体算法如下：
Ⅰ.如果 a [p]= – 1 ，则直接将 b[i]存储到 a [p]中，同时 tot 值增加 1；
Ⅱ.如果 a [p]>b[i] ，则整体将 a [p] ，… ，a [tot]向右移动一个位置，然后将 b[i]存储到空出的位置， 同时 tot 值增加 1。
Ⅲ. p 值增加 1；
小强编写的合并代码如下，请在划线处填入合适代码。
#将列表a 的数据个数存入m，列表b 的数据个数存入 n，代码略
#对列表 a 扩充 n 个-1，代码略
p=0
tot=
i=0
while ： #将列表b 中元素 b[i]逐个插入到列表 a 中
if a[p]==-1 ：
a[p]=b[i]
tot+=1
i+=1
elif a[p]>b[i] ：
for j in range(tot，p-1，-1)： #整体将 a[p]， … ，a[tot]向右移动一个位置
a[j+1]=a[j]
tot+=1
i+=1
p+=1
print("合并后的数据序列为："，a)
34．有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；如此追问，都说比另一位同学多植两棵，最后问到第五位同学时，他说自己植了10棵。问第一位同学植了多少棵树？以下代码是求第一位同学植树数量的代码，请你补全程序。
def f(n):
if n == 5:
return ___①___
else:
return _____②____
print(___③___)
（1）程序代码中①处的代码是( )
A．1 B．2 C．10 D．18
（2）程序代码中②处的代码是( )
A．f(n)-2 B．f(5)+2 C． f(n-1)+2 D．f(n+1)+2
（3）程序代码中③处的代码是( )
A．f(n) B．f(1) C． f(5) D．5
35．利用欧几里得辗转相除法求两数最大公约数
def gcd（m，n）：
if ：
return n
else：
r=m%n
return
a=int（input（'请输入第一个正整数："））
b=int（input（'请输入第二个正整数：））
print( )
（1）A．m//n==0 B．m//n！=0 C．m%n==0 D．m%n！=0
（2）A．gcd（m，n） B．gcd（m，r） C．Gcd（n，r） D．gcd（n，r）
参考答案：
1．B
2．B
3．C
4．D
5．A
6．B
7．C
8．C
9．D
10．D
11．B
12．A
13．C
14．B
15．D
16．A
17．B
18．B
19．B
20．A
21．2
22． 9 22
23．[3, 4, 4, 6, 7, 9]
24．S=20
S=40
S=60
S=80
25．[3,2]
26．错误
27．错误
28．正确
29．正确
30．错误
31． 2 x+=1 或x=x+1 x==0 x//2
32． 10 ans[a[i]]+=1 tmp1.append(i) tb33． 4 C m-1 或其它等价答案 i34． C D B
35． C D gcd(a,b)

展开更多......

收起↑