資源簡介

數據與數據結構 綜合練習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)

展開更多......

收起↑