资源简介

数据与数据结构 综合练习2023—2024学年粤教版（2019）高中信息技术选修1
一、选择题
1．______是重复反馈过程的活动，______是重复调用函数自身（ ）
A．递推，递归 B．递归，递推 C．迭代，递归 D．递归，迭代
2．面对一个大规模复杂问题的求解，递归的基本思想是把 的问题层层转换为 的同类问题求解（ ）
A．规模较大，规模较大 B．规模较大，规模较小
C．规模较小，规模较大 D．规模较小，规模较小
3．数据应用影响着我们的生活，下列说法不正确的是（ ）
A．数据在医疗行业的合理利用，使得就医，诊疗更加方便
B．随着数据安全技术的发展，数据变得更加安全，从而不会产生任何负面影响
C．对人们购买记录、浏览信息的数据分析可以进行有针对性的智能推荐
D．企业基于市场数据分析的决策可以更加精准
4．某二叉树的前序遍历序列是Python3,后序遍历序列是tyn3ohP，则根结点的左子树的结点个数可能是（ ）
A．2 B．3 C．4 D．5
5．设栈s的初始状态为空，元素a、b、c、d、e、f、g依次进栈，出栈顺序为cbdaegf，则栈s容量至少应该是（ ）
A．2 B．3 C．4 D．5
6．数据1~1000升序排列，若用二分查找其中的某个数，最多需要查找的次数为（ ）
A．3 B．10 C．100 D．500
7．下列属于数字生活的是（ ）
①网络购物 ②视频通话 ③在线学习 ④书信交流
A．①②④ B．①②③④ C．①②③ D．①③④
8．有如下Python程序段：
from random import randint
key = randint(5,9) *2 + 1
a=[23,21,19,18,16,15,14,11]
i, j, cnt = 0, 7, 0
while i <= j:
m=(i+j+1)//2
if a[m] >= key :
i = m + 1
else:
j = m - 1
cnt += 1
程序执行后，下列说法不正确的是（ ）
A．i一定等于j+1 B．j的值可能是4 C．i的值可能是8 D．cnt的值一定是3
9．有如下Python程序段：
st = [″h″,″a″,″p″,″*″,″p″,″Y″]
que = [0]*20; key = 2
head,tail = 0, 0
for i in range (len(st)):
if ″a″ <= st[i] <= ″z″:
que[tail] = chr((ord(st[i]) - ord(″a″) + key)%26 + ord(″a″))
tail += 1
else:
head += 1
while head != tail:
print (que[head],end =″ ″)
head += 1
程序运行后，输出的结果是（ ）
A．r r B．p p C．c r r a D．c r r A
10．定义如下函数：
def tran(x,y):
if x > 0:
return tran(x//y,y) + str (x%y)
else:
return "0"
执行语句k = tran(14,2)后，k的值为（ ）
A．″1010″ B．″1110″ C．″01010″ D．″01110″
11．设双向链表的某中间节点p由一个一维数组表示，其中k[p][1]和k[p][2]分别是该节点的前驱及后继。现要求从该链表中删除结点p，则下面语句序列中正确的是（ ）
A．k[p][1][2]=k[p][2]；k[p][2][1]=k[p][1] B．k[k[p][1]][2]=k[p][2]；k[k[p][2]][1]=k[p][1]
C．k[p][2][2]=k[p][1]；k[p][1][1]=k[p][2] D．k[k[p][2]][2]=k[p][1]；k[k[p][1]][1]=k[p][2]
12．某二叉树的中序遍历结果为DBEAFGC，后序遍历结果为DEBGFCA，则前序遍历结果为（ ）
A．ABDECFG B．ABCDEFG C．ABEDFCG D．ABDECGF
13．列表a长度为6，a[0]至a[5]值依次为4，2，5，1，9。
que=[0]*7
head,tail=0,0
que[tail]=a[0]
tail+=1
for i in range(1,len(a)):
if a[i]>que[tail-1]:
que[tail]=a[i]
tail+=1; head+=1
elif a[i] < que[head]:
que[tail]=a[i]
tail+=1
print(que[head:tail])
执行以上程序段后，输出结果是（ ）
A．4,7 B．5,1,9 C．2,5,1,9 D．4,7,2,5,1,9
14．用I表示进栈操作，0表示出栈操作，若元素进栈的顺序为ABCDE，为了得到ADCEB的出栈顺序，则由I和0表示的操作串是（ ）
A．I0III00I00 B．I0II0I00I0 C．IIII00I000 D．I0III0000
15．某二叉树的树形结构如图所示，其后序遍历结果为BDEFCA，则中序遍历结果为（ ）
A．EDCFBA B．ECFDAB C．BFDEAC D．BFEDAC
16．有如下Python程序：
s1=[0]*5; s2=[0]*5; top1=-1; top2=-1
a=[9,2,5,6,1]
for i in range(len(a)):
while top1 !=-1 and a[i] < s1[top1]:
top2 += 1
s2[top2] = s1[top1]
top1 -= 1
top1 += 1; s1[top1] = a[i]
while top2 != -1:
top1 += 1
s1[top1] = s2[top2]
top2 -= 1
print(s1[top1])
执行程序后的输出结果是（ ）
A．1 B．5 C．6 D．9
17．有如下Python程序：
def trans(n):
ch=″0123456789ABCDEF″
if n < 16:
return ch[n ％ 16]
else:
digit = trans(n // 16) + ch[n ％ 16]
return digit
n = int(input(″请输入一个正整数:″))
print(trans(n))
执行该程序时，输入“268”(不含引号)，则输出的结果为（ ）
A．C01 B．C010 C．10C D．010
18．某二叉树用一维数组存储结构如下表所示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I
下列有关该二叉树的说法正确的是（ ）
A．该树度为2的节点有4个
B．该树的前序遍历为A-B-D-E-G-H-C-F-I
C．该树是完全二叉树，其深度为4
D．该树中共有3个叶子节点，分别是G、H、I
19．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（ ）
A．2 B．4 C．5 D．6
20．某二叉树的后序遍历结果为DEBFCA，它的树形结构图不可能是（ ）
A． B． C．D．
二、填空题
21．将6名选手的歌唱比赛成绩存放在数组a中，如下表所示：
若按升序排列，采用冒泡排序算法自右向左进行比较和交换，第二轮排序之后a(4)中的值为
22．某书城五种畅销图书的市场价格(单位：元)存放在数组d中，如下表所示。现对这些数据进行升序排列，若采用冒泡排序算法自下而上进行比较和交换，那么在第一遍加工后，d[2]的值是 。
d[1] 26
d[2] 32
d[3] 20
d[4] 29
d[5] 36
23．class UnionFindSet(object):
def __init__(self, data_list):
self.father_dict = {}
self.size_dict = {}
for node in data_list:
self.father_dict[node] = node
self.size_dict[node] = 1
def find(self, node):
father = self.father_dict[node]
if(node != father):
if father != self.father_dict[father]: # 在降低树高优化时，确保父节点大小字典正确
self.size_dict[father] -= 1
father = self.find(father)
self.father_dict[node] = father
return father
def is_same_set(self, node_a, node_b):
return self.find(node_a) == self.find(node_b)
def union(self, node_a, node_b):
if node_a is None or node_b is None:
return
a_head = self.find(node_a)
b_head = self.find(node_b)
if(a_head != b_head):
a_set_size = self.size_dict[a_head]
b_set_size = self.size_dict[b_head]
if(a_set_size >= b_set_size):
self.father_dict[b_head] = a_head
self.size_dict[a_head] = a_set_size + b_set_size
else:
self.father_dict[a_head] = b_head
self.size_dict[b_head] = a_set_size + b_set_size
N = int(input())
for i in range(N):
M = int(input())
nums = []
maxNum = 0
for j in range(M):
tempTwoNum = list(map(int, input().split()))
maxNum = max(maxNum, max(tempTwoNum))
nums.append(tempTwoNum)
union_find_set = UnionFindSet(list(range(maxNum+1)))
for i in range(M):
union_find_set.union(nums[i][0], nums[i][1])
res_dict = {}
for i in union_find_set.father_dict:
rootNode = union_find_set.find(i)
if rootNode in res_dict:
res_dict[rootNode].append(i)
else:
res_dict[rootNode] = [i]
#print(res_dict)
print( len(res_dict.keys()))
输入：
1
10
0 1
2 3
4 6
2 5
5 4
1 6
10 11
7 9
8 10
7 11
输出：
24．有一维数组1、2、3、4、5，依次按照某一线性存储，请回答以下问题：
（1）如果该线性结构是队列，写出出队序列。
（2）如果该线性结构是栈，输出序列可能是4、3、5、1、2吗？为什么？
（3）在一维数组A中有5个元素：8、12、20、25、33，采用二分查找25，请写出每次查找的过程？
25．请填一下以下内容。
结构类型 数据（节点）之间的关系 生活中相应结构应用举例
队列（线性） （1） （2）
树 （3） （4）
图 （5） （6）
三、操作题
26．优惠购物活动
某电商平台正在开展优惠购物活动，小凡同学征得妈妈的同意后，登录该电商平台，采购所需物品。平台制定的优惠活动规则如下：商品总额达到500元，享受9折；商品总额达到1000元，享受8.5折；商品总额达到2000元，享受8折；商品总额达到3000，享受7折（7折封顶）。
（1）根据商品总额及优惠活动规则计算应付款的程序如下，它采用的结构是( )。
money=float(input("请输入商品总额："))
if money<500:
print("金额不达标，没有折扣哟！")
elif money<1000:
money=money*0.9
elif money<2000:
money=money*0.85
elif money<3000:
money=money*0.8
else:
money=money*0.7
money=round(money,2)
print("请您支付："+str(money)+"元")
A、单分支 B、双分支 C、多分支
（2）第1小题程序中第四行代码如果改为“elif 500<=money<1000:”，则( )。
A、程序仍然正确 B、程序报错 C、程序结果错误
（3）收银系统在计算商品总额时，是根据“商品总额=商品单价*商品数量”这个公式计算的，请问商品单价的数据类型是 ，商品数量的数据类型是 。
A、整型 B、浮点型 C、字符串型 D、布尔型
（4）商品付款结束后，就进入了物流环节。在现代信息技术的支持下，人们可以随时关注快递的状态，主要是因为在快递运输的过程中，分拣员会用扫码枪扫描物品的快递单条形码，从而更新物流信息。关于条形码，以下说法正确的是( )。
A、简单、易于制作，可印刷 B、自身包含信息量较少 C、可靠性高 D、灵活、实用
（5）电子支付可以使用扫描二维码的方式付款，也可以使用刷脸支付等方式，给用户带来了便利。下列说法正确的是( )。
A、二维码是一种更先进的编码方式，因此可以舍弃条形码的使用
B、刷脸支付，十分方便，不会出现安全问题
C、扫描二维码付款时，要注意识别二维码的真伪性，以防二维码被不法分子偷换
D、现在是大数据时代，为了个人隐私和资金安全，我们应该拒绝采用手机付款
27．某企业进行社会招聘，已经先进行了笔试，即将进行面试环节，现需要根据规则选出进入面试名单，规则如下：
a．已知需要招聘的岗位名称及计划招聘人数，保存在字典gwinfo中。
格式：如gwinfo={'岗位1':5,'岗位2':3] ...}表示岗位1计划招5人，岗位2计划招3人...
b．参加面试的求职者，有3个志愿可填写，保存在qzinfo列表中。
格式：如qzinfo=[['张三','岗位3';'岗位2','岗位1',90],['李四','岗位4','岗位1','岗位2', 85], ...]表示求职者张三的三个志愿依次是'岗位3';'岗位2','岗位1',他的笔试成绩是90...
c．按照计划，笔试分数高的求职者优先进入面试，若求职者多个志愿得到进入面试机会，那么将按照志愿先后顺序仅安排一个靠前志愿，取消其他志愿；
d．实际进入面试人数设定为计划招聘人数的2倍（求职人数足够）,在确定面试名单时，如果求职者笔试成绩出现压线同分，则此类求职者都可以进入面试名单（即可能出现进入面试人数超出2倍计划数）；
程序运行样例如下：
岗位需求：
{'岗位1':1,'岗位2':1,'岗位3':1}
求职信息：
[[肖青枝,'岗位1','岗位3';'岗位2',85],[李昕泽,'岗位1','岗位3';'岗位2',85],
[田晓宇,'岗位1','岗位3';'岗位2',86],[李昌镐,'岗位1','岗位3';'岗位2',84],
[刘长浩,'岗位1','岗位3';'岗位2',83],[梁文音,'岗位1','岗位3';'岗位2',82],
[李博宇,'岗位1','岗位3';'岗位2',84],[彭靖开,'岗位1','岗位3';'岗位2',82]]
----------------------------
岗位1 需求人数：1，入围人数：3 入围情况：
序号 姓名 笔试成绩 志愿
1 田晓宇 86 第1志愿
2 肖青枝 85 第1志愿
3 李昕泽 85 第1志愿
----------------------------
岗位2 需求人数：1，入围人数：3 入围情况：
序号 姓名 笔试成绩 志愿
1 李博宇 84 第1志愿
2 梁文音 82 第3志愿
3 彭靖开 82 第3志愿
----------------------------
岗位3 需求人数：1，入围人数：2 入围情况：
序号 姓名 笔试成绩 志愿
1 李昌镐 84 第2志愿
2 刘长浩 83 第1志愿
（1）在样例中李听泽笔试成绩有误，实际成绩为86,那么修改后实际进入面试人数将变为 ；
（2）完善程序，请在划线处填入合适代码。
#输入初始化信息n, m, gwinfo, qzinfo分别代表招聘人数、求职人数、岗位需求信息、求职信息，代码略
dic={}
for g in gwinfo:
dic[g]=[0,[],[]]
def insert (id,zy):
gwmc=qzinfo[id][zy] #岗位名称
num=len (dic[gwmc][2]) #该岗位已安排人数
jhnum=gwinfo[gwmc] #该岗位计划数
fs=qzinfo[id][-2]
if ① :
dic[gwmc][0]=fs
dic[gwmc][1]. append (zy)
dic[gwmc][2]. append (id)
return True
else:
return False
head=0
qzinfo[0]. append (-1)
for i in range (1,m):
pre,cur=-1,head
while ②
pre,cur=cur,qzinfo[cur][-1]
qzinfo[i]. append (cur)
if pre==-1:
head=i
else:
qzinfo[pre][-1]=i
cur=head
while cur!=-1:
for i in range (1,4）:
if insert (cur,i):
③
cur=qzinfo[cur][-1]
#输出每个岗位实际进入面试人员名单：
for key in dic:
p=dic[key][1]
q=dic[key][-1]
print（'-------------------------------'）
print (key,'需求人数:',gwinfo[key],',入围人数:',len (q) ,'入围情况:')
print ('序号','姓名','笔试成绩','志愿')
for i in range (len (p)):
print (i+1,qzinfo[q[i]][0],qzinfo[q[i]][-2], 第'+. ④ +'志愿',)
print ()
28．小王同学进行布艺创作，创作的工艺及流程如下：
每次可以涂不同的颜色，但每种颜色只会涂一段连续区间，并且这些区间须分别连续，且两两不能相交；
曾经用过的颜色，在接下来的创作流程中不会再用；
每次涂完，需要等1天时间完全干透以后，才能用新颜料进行覆盖。
小王现在想对一段长度为N的布条进行艺术创作，将其涂成多彩的目标状态。小王想知道他能不能完成这次创作，如果能完成，则计算出最少需要花费的天数，否则输出“无法实现”。例如，某长度为7的布条初始状态及目标分别如图a和图b所示。图中序号0~6分别对应7个数字，每个数字表示一种颜色，其中0表示没有涂色或无需涂色。具体创作的流程如下：
第一天：将序号1~4位置涂上1号颜色，序号5~6位置涂上3号颜色，得到如图c所示状态；
第二天：将序号2位置涂上4号颜色，序号3位置涂上2号颜色，等待一天染色料完全干透，即完成全部的染色工作，总花费的天数为2天。
小王请你帮忙设计如下Python程序，输入布的长度及每个位置的目标颜色，输出采用以上染色工艺，涂色工作是否能够成功完成，如果能够涂色成功，则输出完成涂色的最小天数。请回答下列问题：
（1）采用以上工艺及流程进行染色，若需要将一段长度为8的未涂色布料，每个单位长度涂成“1 2 4 2 1 5 3 5”的目标颜色，则需要的最小涂色天数为 。
（2）请在划线处填入合适的代码。
def paint (tmp) :
head, tail, days = tmp
backcolor =①
i = head + 1
global top#表示top为全局变量，与主程序中的top相同
while i < tail:
if pos[i] == backcolor:#当前颜色与底色相同
i += 1
continue
if cful[pos[i]] > tail:#当前颜色的最后位置超过覆盖区
return True
else:
top += 1
st[top] = [i,cful[pos[i]],days + 1]
i =②
return False
n = int (input(″请输入布的长度: ″))
m = int (input(″请输入颜色的总数量: ″))
cful = [0] * m#cful储存每个颜色最后出现的位置
pos = [0] * (n + 1)# pos储存目标状态的颜色
for i in range (n):
c = int(input(″请输入序号″ + str(i) + ″位置的颜色号: ″))
pos[i] = c
③
pos[n] = 0#设置序号n所在位置的颜色为0
cfu1[0] = n#设置目标状态下，颜色0的最后出现位置为n
st = [0]*n; top = 0
st[top] = [-1,n,0] #用于存储该颜色的开始位置、结束位置和已经经历的天数
ans = 0
while top != -1:
tmp = st[top]
④
if tmp[2] > ans:
ans = tmp[2]
err = paint (tmp)
if err:
break
if not err:
print(″能够实现，最小涂色天数为: ″, ans)
else:
print(″无法实现″)
29．运用辗转相除法求两个正整数的最大公约数。
def f(m, n): # 递归定义函数，求m和n的最大公约数
if == 0: # m可以被n整除
return n # 求得最大公约数
:
q = m % n
return f(n, q)
a = int(input('请输入第一个正整数：'))
b = int(input('请输入第二个正整数：'))
print( )
30．一个正整数的阶乘是所有小于及等于该数的正整数的积，并且0的阶乘为1，即n!=1×2×3×...×(n-1) ×n，现求n!。
def f(n): # 定义递归函数f(n)
if n == 0 or n == 1:
return 1 # 定义当n为0时函数返回值为1
else:
return # 递归定义n≥1时的通项公式
= int(input("请输入n：")) # 从键盘上输入n的值
print("n！的值为：", ) # 输出结果
参考答案：
1．C
2．B
3．B
4．A
5．B
6．B
7．C
8．B
9．A
10．D
11．B
12．A
13．B
14．A
15．C
16．D
17．C
18．B
19．B
20．C
21．82
22．26
23．2
24． 1、2、3、4、5
不可能，因为：4是第一出栈字符，说明1,2已别压入栈内；并且压入栈的次序为12345;由以上得出：12出栈的顺序只能是2、1，而不是1、2。所以，出栈序列4,3,5,1,2是不可能的 第一次查找，找到的元素为20，此时20小于目标数，所以在列表的后半部分查找，第二次查找到的元素为25，此时找到，所以共需要两次找到
25． 一对一 班级座号的编排 一对多 家族成员关系的表达 多对多 城市间的交通
26． C A B B ABCD C
27． 6 num=qzinfo[i][-1]或cur!=-1 and qzinfo[cur][4]>=qzinfo[i][4] （注>也对） break str(p[i])
28． 3 pos[tail] 或 pos[head] cful[pos[i]]+1 cful[c]=i top-=1 或 top=top-1
29． m%n else f(a,b)
30． n*f(n-1) n f(n)

展开更多......

收起↑