資源簡介

第六單元　數(shù)據(jù)結構
信息技術(50分)
一、選擇題(本大題共12小題，每小題2分，共24分。每小題列出的四個備選項中只有一個是符合題目要求的，不選、多選、錯選均不得分)
1.已知一棵完全二叉樹的節(jié)點總數(shù)為10，則有關該二叉樹的說法正確的是(　　)
A.樹的度為10 B.樹的層數(shù)為3
C.最后一層有3個節(jié)點 D.葉子節(jié)點數(shù)為3
2.現(xiàn)有一棵二叉樹的前序遍歷為ABCDEF，中序遍歷為BCADFE，則該二叉樹的后序遍歷為(　　)
A.CBFEDA B.BCFEDA
C.CBDFEA D.BCEFDA
3.用一維數(shù)組表示二叉樹，如下表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有關該二叉樹的說法正確的是(　　)
A.該樹中共有4個葉子節(jié)點
B.該樹是完全二叉樹，其深度為4
C.該樹的中序遍歷為B－F－D－G－A－C－E
D.該二叉樹的結構圖為(如圖所示)
4.某二叉樹的樹形結構如圖所示，其前序遍歷結果為BADCFGE，則字符“G”所在的位置為(　　)
A.① B.②
C.③ D.④
5.創(chuàng)建一個容量為3的隊列，元素2，3，5，1，3，5，2依次等待入隊。入隊規(guī)則為：
①若當前待入隊元素已經(jīng)在隊列中，則跳過該元素，否則轉②
②若當前隊列已滿，將隊首元素出隊列，否則轉③
③將當前待入隊元素入隊列
操作完成后，隊列中的元素為(　　)
A.2，3，5，1 B.1，2，3，5
C.2，3，5 D.5，1，2
6.某種特殊的隊列Q，支持以下3個操作：操作Q1，若隊列非空，隊首元素出隊，并輸出；操作Q2，若隊列非空，隊首元素出隊；操作Q3，一個元素入隊；以上任意一種操作后，若隊列非空，新的隊首元素仍為隊列中所有元素的最小值。若隊列Q初始狀態(tài)為空，依次進行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列說法正確的是(　　)
A.當前隊列中的元素個數(shù)為2
B.輸出的元素個數(shù)為2
C.第一個輸出的元素肯定比當前隊首元素大
D.隊列初始狀態(tài)是否為空對輸出結果有影響
7.用“除二取余”法將十進制轉換為二進制數(shù)，用棧的方法操作，需要把得到的余數(shù)依次入棧，除盡后再把余數(shù)出棧即可。若要將十進制數(shù)n(0≤n<64)轉換為二進制數(shù)，則設置棧的長度至少為(　　)
A.3 B.4
C.5 D.6
8.用I表示進棧操作，O表示出棧操作，若元素進棧的順序為PQRST，為了得到PSRTQ的出棧順序，則由I和O表示的操作串是(　　)
A.IOIIIOOIOO B.IOIIOIOOIO
C.IIIIOOIOOO D.IOIIIIOOOO
9.有一個空棧，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入棧，其中“o”第一個出棧。則當所有元素全部出棧后，下列說法正確的是(　　)
A.出棧的最后一個元素一定為“P”
B.出棧的最后一個元素一定為“n”
C.元素“h”一定比“P”、“y”、“t”先出棧
D.元素“P”、“y”、“t”、“h”、“o”的出棧序列是不確定的
10.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″輸入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
q[tail]＝i
tail＝tail＋1
s＋＝i
if ansans＝s
while ik：
s－＝q[head]
head＝head＋1
執(zhí)行該程序段后，輸入k的值為2，變量ans的值是(　　)
A.18 B.19
C.21 D.22
11.有如下Python程序段：
a＝[2，1，5，7，3]
n＝len(a)
s1＝[－1]*n；top1＝－1
s2＝[－1]*n；top2＝－1
for i in range(n)：
while top1！＝－1 and a[i]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
運行該程序段后，下列表達式不成立的是(　　)
A.top1＝＝5 B.top2＝＝－1
C.s1[0]＝＝1 D.s1[3]＝＝2
12.有如下Python程序段：
sz＝[″94″，″98″，″156″，″80″，″87″，″178″]
dt＝[0，1，0，1，0，0]
st＝[]；top＝0
st.append(top)
for i in range(1，len(sz))：
flag＝False
while len(st)>0 and dt[st[top]]＝＝1 and dt[i]＝＝0：
if sz[st[top]]　　　 　st.pop()
　　　 　top＝top－1
else：
　　　 　flag＝True；break
if not flag：
top＋＝1
st.append(i)
執(zhí)行該程序段后，st中的元素個數(shù)為(　　)
A.6 B.2
C.4 D.3
二、非選擇題(本大題共3小題，其中第13小題7分，第14小題10分，第15小題9分，共26分)
13.給定一個只包括'('，')'，'{'，'}'，'['，']'的字符串s，判斷字符串是否有效。有效字符串需滿足：左括號必須用相同類型的右括號閉合。左括號必須以正確的順序閉合。
程序運行的結果如圖所示：
(1)實現(xiàn)上述功能的Python程序如下，請在劃線處填入合適的代碼。
dic＝{″(″：″)″，″[″：″]″，″{″：″}″}
s＝input(″輸入的字符串是：″)
st＝[″″]*len(s)
top＝－1
dic1＝{}
for i in dic：
dic1[dic[i]]＝i
flag＝True
for i in s：
if ①________：
top＋＝1
st[top]＝i
if i in dic1：
if top＝＝－1 or ②________：
flag＝False
　　　　 break
else：
　　　 　③________
if ：
print(″字符串有效！″)
else：
print(″字符串無效！″)
(2)加框處的代碼有錯，請改正。
14.一批集裝箱陸續(xù)送達碼頭，要求疊放到指定的若干位置，每個位置最多可疊放5個集裝箱，且輕的在上，重的在下。工作人員根據(jù)每個送達的集裝箱的重量，利用臨時位置經(jīng)過最少的移動次數(shù)放到合適的位置，若移動次數(shù)相同，優(yōu)先選擇編號小的位置(臨時位置不考慮集裝箱重量大小關系)。
例如：共有8個集裝箱，要求疊放到2個位置。已依次送達6號、2號、3號、5號，疊放情況如圖a所示。
新送達的集裝箱為7號，重量為28。
·若疊放到位置0，需要移動3次：①2號→臨時位置②7號→位置0③2號→位置0
·若疊放到位置1，需要移動5次：①5號→臨時位置②3號→臨時位置③7號→位置1④3號→位置1⑤5號→位置1
疊放到位置0的移動次數(shù)<疊放到位置1的移動次數(shù)，所以疊放到位置0。
編寫Python程序實現(xiàn)上述功能，請回答下列問題：
已送達集裝箱信息： {6：29，2：18，3：20，5：19} 當前集裝箱疊放情況： 位置0：[6，2] 位置1：[3，5] 請輸入到達的集裝箱編號：7 請輸入到達的集裝箱重量：28 移動過程為： 2→臨時位置 7→位置0 2→位置0 疊放結果： 位置0：[6，7，2] 位置1：[3，5]
圖b
(1)函數(shù)judge(x，st)的功能是：返回x號集裝箱放入某位置時需移動的次數(shù)。列表st存儲了該位置從下到上已疊放的集裝箱編號。請在劃線處填入合適的代碼。
#goods存儲了已送達集裝箱的信息，如：{6：29，2：18，3：20，5：19}。
def judge(x，st)：
if len(st)＝＝5：
return－1
cnt＝0
i＝len(st)－1
while i>＝0 and____________：
cnt＋＝1
i－＝1
return cnt*2＋1
(2)當某個集裝箱送達時，輸入其編號和重量，將該集裝箱放到移動次數(shù)最少的位置，并輸出移動過程。程序執(zhí)行結果的部分截圖如圖b所示。請在劃線處填入合適的代碼。
goods＝{}
n＝8
k＝(n－1)//5＋1
p＝[[]for i in range(k)]
for i in range(n)：
#輸出當前集裝箱疊放情況，代碼略
x＝int(input('請輸入到達的集裝箱編號：'))
weight＝int(input('請輸入到達的集裝箱重量：'))
goods[x]＝weight
min_steps＝999
for j in range(k)：
t＝judge(x，p[j])
if ①________：
　 　　　minp＝j
　　 　　min_steps＝t
print('移動過程為：')
tmp＝[]
for j in range(②________)：
print(p[minp][－1]，'→臨時位置')
tmp.append(p[minp].pop())　#刪除p[minp]的最后一個元素，并追加到tmp
p[minp].append(x)
print(x，'→'，'位置'＋str(minp))
while ③________：
print(tmp[－1]，'→'，'位置'＋str(minp))
p[minp].append(tmp.pop())
#輸出疊放結果，代碼略
(3)若送達的集裝箱編號和重量依次為4：20，2：18，1：23，3：20，7：28，6：29，0：17，5：19，根據(jù)要求疊放到位置0和位置1，則位置1從下往上疊放的集裝箱編號依次為________。
15.某餐廳餐桌設置如下表：
餐桌型號 2人小桌 4人方桌 6人大方桌 12人大圓桌
餐桌數(shù)量 8 15 10 4
平均就餐時間(分鐘) 25 45 60 80
有客人來就餐時其叫號系統(tǒng)會自動生成一個號碼，并根據(jù)人數(shù)安排餐桌型號；當對應餐桌型號有空桌時，按餐桌編號(由小到大)即時分配餐桌安排客人就餐；當對應餐桌型號沒有空桌時，客人按先后順序排隊。程序部分運行界面如下：
(1)定義如下gettype函數(shù)，功能為輸入客人人數(shù)，返回對應桌型，請在程序劃線處填入合適代碼。
def gettype(num)：
type＝－1
for i in range(len(size))：
if num<＝size[i]：
　　　 　type＝i
　　　 　__________
return type
(2)定義如下checktable()函數(shù)，功能為輸入桌型，返回對應桌型空桌的編號，返回值類型為列表，請在程序劃線處填入合適代碼。
def checktable(n)：
ans＝[]
for i in range(nums[n])：
if____________：
　　 　　ans.append(i)
return ans
(3)解決上述問題的主程序如下，請在程序劃線處填入合適代碼。
size＝[2，4，6，12]　#每種桌型最大就餐人數(shù)
nums＝[8，15，10，4]　#每種桌型的餐桌數(shù)量
times＝[25，45，60，80]　#每種桌型平均就餐時間
flags＝[[True]*nums[i] for i in range(4)]　
#標記每張桌子的初始狀態(tài)
s_time＝10*60*60　#開始營業(yè)時間——10點整，轉化為秒
e_time＝14*60*60　#結束營業(yè)時間——14點整，轉化為秒
maxn＝50　#假設隊列已經(jīng)足夠深
qc＝[[0]*maxn for i in range(4)]　#循環(huán)隊列
now_time＝s_time
id＝0
head，tail＝[0]*4，[0]*4
while now_timenumber＝getinfo()　#調(diào)用函數(shù)getinfo()，獲取客人人數(shù)
if number>0：
id＋＝1
type＝gettype(number)#根據(jù)就餐人數(shù)確定餐桌類型
if type！＝－1：
　　　 　qc[type][tail[type]]＝id
　　　 　tail[type]＝(tail[type]＋1)%maxn
　　　 　qc_len＝①________
　　　 　print(id，″號客人，給您安排的是″，size[type]，″人桌，前面還有″，qc_len－1，″人在等位″)
else：
　　 　　print(id，″號客人，非常抱歉，沒有適合您的桌型！″)
for i in range(4)：
tables＝checktable(i)
if ②________：
　　　 　flags[i][tables[0]]＝False　#入座第一個空桌
　　　 　print(qc[i][head[i]]，″號客人請用餐→″，size[i]，″人桌″，tables[0]，″號″)
　　 　　head[i]＝(head[i]＋1)%maxn
now_time＋＝1
#更新每張餐桌的就餐情況，代碼略
第六單元　數(shù)據(jù)結構
1.C　[本題考查樹的性質(zhì)。A選項二叉樹的最大度為2，因此樹的度也是2。B選項總節(jié)點數(shù)10介于7和15之間，因此該樹層數(shù)為4。C選項由于是滿二叉樹，因此前3層為完全二叉樹，前3層共有7節(jié)點，最后一層有3個節(jié)點。D選項由于最后一層有3個節(jié)點，因此該層的父親節(jié)點有2個，第3層共有4個節(jié)點，因此第3層還有2個葉子節(jié)點。]
2.A　[本題考查二叉樹的遍歷。根據(jù)前序遍歷和中序遍歷的規(guī)則畫出二叉樹，前序遍歷的第一個元素“A”為根節(jié)點，樹分為(BC)A(DEF)。“BC”確定節(jié)點B為根節(jié)點，C是右子樹。“DEF”中，節(jié)點D為根節(jié)點，“EF”是節(jié)點“D”的右子樹。“EF”中E為根節(jié)點，F(xiàn)是右子樹。得到后序遍歷結果為CBFEDA。]
3.C　[本題考查二叉樹的基本知識。第3層節(jié)點的索引號為3，4，5，可見B沒有左子樹，但有右子樹，因此不可能是滿二叉樹，B也不是葉子節(jié)點。二叉樹形態(tài)如圖所示。]
4.C　[前序遍歷是根左右，F(xiàn)為根，G在F的后面，因此G為F的右子樹。]
5.D　[本題考查隊列結構及其操作，各數(shù)據(jù)入隊時狀態(tài)如圖所示。]
6.D　[操作Q3、Q2之后，隊列為空。Q3、Q1，隊列為空。因此隊列中元素個數(shù)為1，Q1操作出隊并輸出元素，輸出的元素個數(shù)為1。C選項沒有可比性。D選項若隊列不為空，則Q3、Q2、Q1、Q2輸出的結果不一樣。]
7.D　[十進制數(shù)n(0≤n＜64)轉換為二進制數(shù)，得到最大的是6位二進制數(shù)。]
8.A　[本題考查棧的操作。P入后馬上出，QRS入，SR出，棧中只有Q，T入后馬上出，Q再出。]
9.C　[本題考查棧的性質(zhì)。o出棧時，n還沒有入棧，因此n可能是最后一個出棧，也可能在其他元素出棧過程中，入棧后再出棧。o出棧時，P，y，t，h均已在棧中，故元素出棧序列是確定的。]
10.C　[遍歷數(shù)組a并累加數(shù)組元素值，求隊列的最大值；當遍歷到的當前值小于隊首或是長度大于k，將隊首元素出隊。s的值依次為[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。]
11.A　[本題考查棧的基本應用。遍歷列表a中數(shù)據(jù)，若棧s1不空，且s1棧頂元素大于等于a[i]時，不斷地將s1中元素出棧，并入棧s2中，將a[i]入棧s1。因此棧s1中元素有1，3，棧s2中有元素[2，7，5]，最后將棧s2中元素出棧并加入到棧s1中，因此棧s1中最終結果為[1，3，5，7，2]。]
12.B　[本題考查數(shù)組的索引和棧的算法實現(xiàn)。st.pop()表示出棧，st.append(i)表示元素i入棧，st[top]是棧頂元素。棧中存儲的元素的編號，一開始棧中有一個元素，″94″對應的下標0入棧。對sz的第2個元素開始遍歷。dt[1]＝＝1，沒有出棧動作，″98″下標1入棧；條件滿足，但是″156″不比棧頂元素″98″大，flag＝True，″156″下標2不會入棧；dt[3]＝＝1，沒有出棧動作，″80″下標3入棧；接下來條件滿足，″87″比棧頂元素″80″大，″80″對應的下標3出棧，接下來的棧頂元素是″98″，flag＝True，沒有入棧動作；最后棧中只有[0，5]共2個元素。]
13.(1)①i in dic　②i！＝dic[st[top]]　③top－＝1 (2)flag and top＝＝－1
解析　本題考查棧的操作。(1)①如果是括號的左半部分，則入棧，否則出棧。②出棧前判斷棧是否為空，為空，說明右半部分先出現(xiàn)，順序不對。若不為空，在字典dic中查找棧頂元素對應的右半分部，如果不相等，說明中間的順序不對。③如果相等，出棧。(2)除了flag的值外，還要判斷左半部分是否比右半部分多，即棧是否為空。
14.(1)goods[x]>goods[st[i]]　(2)①t！＝－1 and t0 或 tmp
(3)6，1，3，5
解析　本題考查棧的應用。插入元素后，維護棧底到棧頂?shù)慕敌蚺帕小?1)judge函數(shù)計算將goods[x]插入到棧st需要移動元素的操作次數(shù)。參數(shù)x是集裝箱編號，即字典goods的鍵，因此在訪問棧頂元素時goods[st[i]]與goods[x]比較為非直接與x比較。(2)從k個位置選擇移動次數(shù)最少的棧并插入元素。第①空獲取當前棧p[j]插入編號為x的元素所需的移動次數(shù)與全局最小次數(shù)min_steps比較并更新min_steps。若棧已滿將無法插入數(shù)據(jù)。第②空輸出移動的過程。先將棧p[minp]大于goods[x]的元素暫存到臨時棧中，這里需出棧的元素個數(shù)恰為min_steps//2。第③空將臨時棧中的全部元素重新壓入棧p[minp]中，因此len(tmp)>0時均需要執(zhí)行入棧。(3)編號4、2依次在位置0入棧；3、7依次在位置1入棧；隨后7插入到位置0的棧底、6插入到位置1棧底；最后0入棧位置0，5入棧位置1，從下到上的編號依次為：6 1 3 5。
15.(1)break　(2)flags[n][i]＝＝True　(3)①(tail[type]－h(huán)ead[type]＋maxn)%maxn　②len(tables)>0 and head[i]！＝tail[i]或tables and head[i]！＝tail[i]
解析　本題考查循環(huán)隊列的基本應用。(1)gettype函數(shù)功能為輸入客人人數(shù)，返回對應桌型。size數(shù)組存儲每種桌型最大就餐人數(shù)，從小桌開始枚舉，找到相應的規(guī)格就結束查找。(2)checktable函數(shù)功能找到對應桌型的空桌編號。nums每種桌型的餐桌數(shù)量，flags二維數(shù)組標記每種桌型每張桌子的初始狀態(tài)，n為桌型編號，nums[n]表示該種桌型中最多就餐桌位，在flags[n]列表中從頭開始(循環(huán)變量i從0至nums[n]－1中枚舉)查找值為True(空桌)的編號，并將這些編號添加到列表ans中，因此答案為flag[n][j]＝＝True。(3)①求隊列長度，qc存儲循環(huán)列表的信息，type表示餐桌類型，qc[type]就是存儲該類型的循環(huán)列表，循環(huán)隊列長度公式(tail－h(huán)ead＋maxn)%maxn，因此①答案為(tail[type]－h(huán)ead[type]＋maxn)%maxn。②輸出安排就餐情況。變量i表示每種桌型，安排座位的條件有兩個，一是這種桌型有客人來，即qc[i]隊列不為空；二是這種桌型有空位，tables調(diào)用checktable(i)函數(shù)，獲取空位列表。

展開更多......

收起↑