資源簡介

(共43張PPT)
第六章　大數據時代數據的組織
驗收卷(六)　綜合練習(B)
(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
1.下列關于數據結構的說法，正確的是(　　)
D
解析　A選項數組中未使用到的空間導致內存浪費。B選項若刪除的是頭節點，只要修改頭指針即可。C選項實現“后退”按鈕的功能是棧的功能。D選項棧是一種受限的數據結構，只能在一端進行操作。
A.數組的最大元素數量在定義時就已確定，因此在操作過程中不會導致內存浪費
B.刪除鏈表節點時，鏈表中必定存在某個節點的指針區域發生變化
C.瀏覽器采用隊列結構組織網頁數據從而實現“后退”按鈕的功能
D.棧結構只有一端開放，數據進、出操作都只能在開放的一端進行
B
2.幼兒園中 8 個小朋友，依次編號(1－8)玩游戲，按編號順序排隊圍成一圈，由編號 1 號的小朋友開始報數，報數報到 3 的小朋友出列，下一個編號的小朋友又從 1 開始報數，一直反復直到剩下最后一人，請問在該問題上采用的適合數據結構和剩下的小朋友的編號是(　　)
A.二叉樹7 B.隊列7 C.棧4 D.鏈表 4
解析　本題考查數據結構的相關知識。適合的數據結構應為隊列，出隊的順序為：3，6，1，5，2，8，4，最后剩下的一人編號為 7。
B
3.在利用棧來判斷一個表達式的括號(只有小括號)是否匹配的過程中，當遇到表達式中的一個左括號時，就讓其進棧，遇到一個右括號時，就對棧進行一次出棧操作；當棧最后為空，表示括號是配對的，否則是不配對的。現有表達式“(a＋b)*c＋((d－e)*f＋g)*h”，針對該表達式設計棧的大小至少為(　　)
A.1 B.2 C.3 D.4
解析　遇到第一個左括號進棧，遇到第一個右括號時，棧中的左括號出棧。遇到第二個和第三個左括號，依次進棧。遇到第二個右括號，依次出棧，遇到第三個右括號，又依次出棧。此時棧為空，表達式中的括號配對成功。整個過程中，棧中最多有2個左括號，所以棧的大小至少為2。
D
4.有一棵樹，節點的度和個數如下表所示。
解析　樹中所有節點的度之和加1為節點總數，因此1*4＋2*3＋3*2＋4*1＝21。節點數為x＋4＋3＋2＋1＝x＋10，因此可以得到葉子節點數為11個。
度 0 1 2 3 4
節點個數 x 4 3 2 1
則葉子節點x的個數為(　　)
A.8 B.9 C.10 D.11
B
5.已知某二叉樹的中序遍歷結果為BFDGAEHC，層序遍歷(從上往下、從左往右)結果為ABCDEFGH，則下列有關該二叉樹的說法，正確的是(　　)
A.該二叉樹是完全二叉樹
B.用數組存儲該二叉樹時，節點F對應的數組下標為9
C.該二叉樹有4個葉子節點
D.該二叉樹的前序遍歷結果為ABDFGCHE
解析　A為整棵樹的根節點，從中序遍歷來看，B和C分別是整棵樹的左右節點。FDG是節點B的右子樹，EH是節點C的左子樹。第3層左邊第1個節點為D，因此F是D的左子樹，G是D的右子樹。第3層左邊第2個節點為E，因此H為E的右子樹。畫出樹的形態如圖所示。該樹只有3個葉子節點，前序遍歷為ABDFGCEH。
6.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　c[tail]＝a[i]
　tail＝tail＋1
　elif a[i]>c[head]：
　 head＝head＋1
print(c[head：tail])
解析　若隊列中數據元素小于2或者t的值為0，則將a[i]入隊，否則當a[i]大于c[head]時出隊，a中元素既可以不入隊，也可以不出隊(t為1，且a[i]小于等于c[head])。A選項8，10入隊，2和7可以不入隊，11讓8出隊，隊列中只剩下1個元素，9入隊，接著t的值為0，16入隊。B選項8，10入隊后，接著t的值依次為1，1，0，0，0。C選項隊首為8，當遍歷到11時，要么讓8出隊，要么產生的t為0，11入隊，因此C不可能。D選項11讓隊首8出隊，當遍歷到16時，產生的t為0，16入隊。
C
7.有如下 Python 程序段：
import random
a＝[23，25，40，16，21，－1，－1，－1，21，－1，－1，－1，－1，－1，－1，－1，－1，－1，－1]
st＝[0]*10
key＝random.randint(10，19)*2＋1
top＝－1
n＝len(a)
i＝0；p＝0
while itop＋＝1；st[top]＝p
　　　if a[st[top]]＝＝－1 or key＝＝a[st[top]]:
　break
　　　elif key>a[st[top]]:
　 p＝p*2＋2
　else：
　p＝p*2＋1
　　i＋＝1
while(top！＝－1):
　　　print(st[top]，end＝″ ″)
　　　top－＝1
B
解析　本題考查棧的算法實現。產生21到39之間的任意奇數key，將列表a中對應數據的索引存放到棧中，若棧頂數據為空或者棧頂對應的值和key相同時，結束循環，若key值大于棧頂數據，將p*2＋2個位置存入棧中。若key小于棧頂數據時，將p*2＋1個位置入棧。A選項Key值大于23且小于等于39時，0，2，5位置數據入棧。C選項key值等于23時，存入數據為0，結束循環。D選項當key小于23時，0，1，3，8位置數據入棧。B選項當key值為21，不會出現0，1，4數據入棧。
B
8.定義如下函數：
def inquire(x，y，key)：
　 m＝(x＋y)∥2
　 if key＝＝a[m]：
　 return ″M″
　　elif key　return ″R″＋inquire(m＋1，y，key)
　　else：
　 return ″L″＋inquire(x，m－1，key)
數組a的元素為[55，49，37，26，24，14，3，3，1]，若執行語句h＝inquire(0，8，14)，則h的值是(　　)
A.LRM B.RLM C.MRL D.MLR
解析　程序的功能采用二分查找法查找14的過程。依次查找的數據為24，3和14，因此先向右查找，再向左查找，最后一次找到。
9.定義如下兩個函數，fac_1和fac_2：
def fac_1(n)：
res＝1
for i in range(1，n＋1):
　　res *＝i
return res
def fac_2(n)：
if n＝＝1：
　　 return 1
else：
　return n * fac_2(n－1)
解析　本題考查迭代與遞歸的算法思想。兩處程序的功能均為求n的階乘。A選項程序fac_1體現迭代算法思想。B選項fac_1(4)只調用1次，而fac_2(4)要調用4次。C選項返回值均為24。D選項均循環了n次，因此算法效率一樣。
B
下列說法正確的是(　　)
A.fac_1和fac_2都采用遞歸算法
B.執行fac_1(4)和fac_2(4)時，兩個函數被調用次數不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函數的算法時間效率遠大于fac_1
C
10.有如下Python程序段：
a＝list(map(int，input().split())) #將輸入的數據轉換成列表
n＝len(a)
for i in range(2)：
　for j in range(n－1，i，－1 )：
　if a[j] % 3>a[j－1] % 3：
　　　a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
解析　本題考查程序冒泡排序。從右往左(從后往前)進行了2趟排序，排序比較是元素%3后，最前面的2個元素除3余數一定是所有元素中最大的。
11.小明為英文字母A～Z定義了一套全新的二進制編碼規則，代碼如下：
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　i＝0
　 j＝len(s)－1
　 rt＝″0″
　while i<＝j：
　m＝(i＋j)∥2
　if s[m]＝＝k：
　　　dc[k]＝rt
　　　break
　elif s[m]　 　　　　i＝m＋1
　　 　rt＋＝″1″
　else：
　 　j＝m－1
　　　rt＋＝″0″
inp＝input(″請輸入英文字符串： ″).upper()
#將輸入的英文字母轉為大寫
解析　構建一棵26個節點的升序二叉樹，由于26小于31，因此最多查找4次，用一個4位二進制數存儲訪問的節點(標記為1)。
for c in inp：
　print(dc[c]，end＝″ ″)
當程序運行后，輸入“OK”后，其輸出的二進制編碼為(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
A
12.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
i＋＝1
　　if i＝＝k：
　p＝people[q][1]
　people[q][1]＝people[p][1]
　if p＝＝head：
　　　head＝people[q][1]
　i＝1
　n－＝1
　　q＝people[q][1]
print(people[head][0])
該程序段運行后，若輸入 2，則輸出的結果為(　　)
A.3 B.5 C.6 D.2
B
解析　本題考查循環鏈表的算法實現。每遍歷一次，i增加1，實現計數。第1次刪除節點2，第2次刪除節點4，第3、4、5分別刪除節點6、3、1，鏈表中只剩下節點5。
二、非選擇題(本題共3小題，共26分)
13.(6分)水房里一共有m個水龍頭，每個龍頭每秒鐘的供水量均為1。現有按接水順序從1到n編號的n名同學進行接水。一開始，m位同學同時接水，下一名排隊等候接水的同學，接替接水時間最短同學的水龍頭位置開始接水，以此類推，當其中一個水龍頭完成某個同學的接水任務時，下一位等候的學生自動接上。每個水龍頭的供水時間為在該水龍頭上接水所有學生時間之和，所有同學接水的時間為供水時間最長的水龍頭。第4位學生將在第1個水龍頭接水，該水龍頭放水8秒時，第4位和第5位學生分別接在第1個和第2個水龍頭接水，第6位學生將在第9秒開始在第3個水龍頭進行接水。
(1)7位學生在3個水龍頭中接水時間(單位：秒)分別為“4，5，7，1，6，2，8”(不包括雙引號)，則所有同學接水的總時間為________秒。
(2)編寫程序運行結果如圖所示，代碼如下，請在劃線處填入合適的代碼。
需要取水時間分別為：4，8，9，4，5，6，8，7
籠頭1取水時間：4，4，5，7
籠頭2取水時間：8，6
籠頭3取水時間：9，8
最多取水時間為：20
#讀取n名同學進行接水時間存儲到數組a中，代碼略
m＝3；n＝len(a)
q＝[[0 for j in range(n)]for i in range(m)] #構建三個隊列，用于記錄每個水龍頭接水情況
head＝[0]*3；tail＝[1]*3
q[0][0]＝a[0]；q[1][0]＝a[1]；q[2][0]＝a[2]
h＝3；t＝0 #h表示隊列a中的指針，用于讀取每個人的接水時間。t表示當前時間。
totaltime＝[a[0]，a[1]，a[2]] #存儲每個水龍頭總的接水時間
flag＝False
while ①________：
for i in range(3)：
if ②________：
　　　　if h　　　　　　　q[i][tail[i]]＝a[h]
　　　　　　　totaltime[i]＋＝a[h]
　　　　　　　h＋＝1
　　　　　　　③________
　　　　else：
　　　　　　flag＝True　　　　
t＋＝1
maxx＝max(totaltime)
#輸出每個水龍頭接水時間和最長接水時間，代碼略。
答案　(1)15　(2)①not flag　②totaltime[i]＝＝t ③tail[i]＋＝1
解析　本題考查隊列的基本操作。(1)水龍頭1取水時間為4＋1＋6＝11，水龍頭2取水時間為5＋2＋8＝15，水龍頭3取水時間為7，最大取水時間為15。h表示隊列a中的指針，用于讀取每個人的接水時間。當條件h14.(10分)某停車場分為省內區和省外區，省內客車只能停靠在省內區，省外客車只能停靠在省外區。每輛客車抵達后，如果相應的區(省內區/省外區)還有空閑的近車位，就停靠在近車位，否則停靠在遠車位(假設遠車位的數量充足)。現給定未來一段時間客車的抵達、離開時刻，根據省內區和省外區的停車位數量，使停靠在近車位的客車數量最多，并顯示各個車位停車情況。
車輛班次信息存儲在 bc 列表中，存入順序為先省內再省外，列表中的每個元素包含三個數據項，分別對應每個班次客車的車型(0 代表省內，1 代表省外)、抵達時間、離開時間。將省內班次和省外班次分別按抵達時間做升序排序，并計算停靠在近車位的車輛數量最多的車位分配方案，并顯示各個車位停車情況，代碼運行效果如圖所示。
[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
省內班次：5　省外班次：4
最多停的班次數：7　分配省內車位數2　省外車位數：1
1號車位情況
[0，1，5]
[0，6，10]
[0，13，18]
2號車位情況
[0，3，8]
[0，9，14]
3號車位情況
[1，2，11]
[1，12，16]
(1)上圖所示例子，車位分配方案改為省內 1 個、省外 2 個，則最多停靠班次數為________輛。
(2)實現上述功能的程序如下，請在劃線處填入合適的代碼。
def sort(st，ed): #對區間[st，ed]之間所有的車次按到達時間升序排列。
　for i in range(st，ed)：
　 for j in range(st，①__________):
　　　 　if bc[j][1]>bc[j＋1][1]：
　　　　 bc[j]，bc[j＋1]＝bc[j＋1]，bc[j]
bc＝[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
#[班次類型，抵達時間，離開時間] 0 表示省內 1 表省外 m＝3；x＝0；y＝0 #m 個近車位，x 個省內班次，y 個省外班次
for i in range(len(bc))：
　　　if bc[i][0]＝＝0:
x＋＝1
　　　else：
y＋＝1
print('省內班次數：'，str(x)，'省外班次數：'，str(y))
sort(0，x－1)
sort(x，x＋y－1)
maxstack＝[[0]*100 for i in range(m)]
maxtop＝[－1]*m；maxans＝0；maxi＝0；maxj＝0 #存儲停車最多時的方案
def check(st，ed，j，stack，top):
　num＝－1
　for i in range(st，ed＋1)：
　if top[i]＝＝－1 or ②__________：
　 　　num＝i
　　 　break
　return num
for i in range(0，m＋1)：
　stack＝[[0]*100 for i in range(m)]
　 top＝[－1]*m；ans＝0
　for j in range(x＋y)：
if j　　　　k＝check(0，i－1，j，stack，top)
else：
　　　　k＝③________
if k！＝－1：
　　　　ans＋＝1；top[k]＋＝1
　　　　④__________
if ans>maxans:
maxans＝ans；maxstack＝stack；maxtop＝top
maxi＝i；maxj＝m－i
print('最多停的班次數：'，maxans，'分配省內車位數：'，maxi，'省外車位數：'，maxj)
for i in range(m)：
　print(i＋1，'號車位情況')
　 for j in range(maxtop[i]＋1):
print(bc[maxstack[i][j]])
答案　(1)6
(2)①ed－i＋st
②bc[stack[i][top[i]]][2]③check(i，m－1，j，stack，top)
④stack[k][top[k]]＝j
解析　(1)省內 1 個車位，分別停[0，1，5]、[0，6，10]、[0，13，18]共3個班次。省外2個車位，一個車位停[1，2，11]、[1，12，16]，另一個車位停[1，4，15] 共3個班次。(2)①內循環決定每趟排序的次數和起址位置。開始位置為st，因此實現從前往后冒泡，第一趟排序變量j的的終值為ed，此時變量i的值為st，隨著i的增加，內循環終值將不斷地減小，因此終值的值為ed＋st－i。②check函數判斷某個班次是否可以停放到某個車位上。st表示起始車位編號，ed 表示結束車位編號，j 表示班次編號，stack 表示停車場的車位停放車輛信息，top 表示每個車位上停車數量的列表(即棧頂)。循環遍歷起始車位到結束車位的車位列表，判斷當前車位是否可以停放該班次，如果可以停放，則返回該
車位的編號；否則返回－1。停放的條件：該車位沒有車輛停放或者該班次編號和前面已經停放的車輛班次再停放時間上沒有重疊。bc[stack[i][top[i]]][2]表示標號為 i 的停車位最后停放車輛的離開時間。③枚舉停車場中省內和省外車位的數量，計算出停車場中停放班次最多的方案。外循環枚舉停車場中省內車位的數量，內循環枚舉班次列表中的所有班次。當 j15.(10分)有60個人要組建一個聚會，每人的喜好是一個數值，為提升聚會效果，會務組要把參會人員進行分組，分組原則是：
1)每組不超過8人
2)組內新增人員的喜好值必須與現有組內人員的平均喜好值相差在5以內
3)若新增人員無法加入現有小組，則被分入新組建小組
采用Python編寫了程序，運行結果如圖所示：
第1組：4，6，8，2，2，7，2，8
第2組：50，45，43，48，48，43，43，42
第3組：14，11，13，16，17，18，17，13
第4組：21，26，19，23，23，18，23，22
第5組：37，35，38，34，33，35，33，33
第6組：16，13，10
第7組：43，45，47，40，45，44，44
第8組：28，28，33，29，34，32，27，33
第9組：37，38
(1)如圖所示，當前數據已被分組，若再新增一個數“47”，會被分在第________組。
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
#讀取n個人的喜好值，存儲到列表a中代碼略。
h＝[－1 for i in range(n)] #創建n個空的鏈表
ave＝[[0 for j in range(2)]for i in range(60)]
#用于存儲每組喜好值的總和和人數
b＝[]
for i in a：
　j＝0 #表示從第0條鏈表開始遍歷
　 p＝h[j]
　 while p！＝－1：
if abs(i－ave[j][0]/ave[j][1])>5 or ave[j][1]＝＝8：
　　　j＋＝1
　　 　①________
else：
　　　p＝b[p][1]
　b.append([i，－1])
　if h[j]＝＝－1: #每組第一個人，添加到鏈表頭
　②________
　else：　　　　
　p＝h[j]　　　　
　while p！＝－1：
　　　bp＝p
　　　p＝b[p][1]
　 ③________
　　ave[j][0]＋＝i
　　ave[j][1]＋＝1
#輸出各個分組情況，代碼略
答案　(1)7　(2) ①p＝h[j]　 ②h[j]＝len(b)－1 ③b[bp][1]＝len(b)－1
解析　(1)第2至5組人數已經達到8人，第7組目前平均值為44，加入第7組后的平均喜好值相差在5以內。(2)分析程序可得，i表示當前參會人員個人喜好值；j表示當前組(從0開始編號)；p表示遍歷鏈表b 的位置；變量h用于存儲每組的頭結點在鏈表b中的位置；①內層While循環中if語句表示當前的參會人員不能加入到該組，因此需要查看后面組的平均值以及當前總人數看是否能夠加入到這些組中，知道找到第一個能插入的組，因此j＋＝1為往后找能存儲的組，當找到可以加入的組時，需要添加在b中相應鏈表中，因此需要找到當前組的
頭結點位置賦值給p，便于后續插入時查找位置。②該空位于if語句中，每組的第一個人，添加到鏈表頭，h存儲每組頭結點的位置，由于是第一個，因此將該人員在b中的位置值復制給h相應組處，答案為h[j]＝len(b)－1。③非該組第一個人，插入時指針值為－1，單向鏈表因此需要修改前驅節點的指針值為該節點的位置，通過上個while循環可得前驅節點的位置存儲在變量p中，因此答案為b[bp][1]＝len(b)－1。驗收卷(六)　綜合練習(B)
(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
1.下列關于數據結構的說法，正確的是(　　)
A.數組的最大元素數量在定義時就已確定，因此在操作過程中不會導致內存浪費
B.刪除鏈表節點時，鏈表中必定存在某個節點的指針區域發生變化
C.瀏覽器采用隊列結構組織網頁數據從而實現“后退”按鈕的功能
D.棧結構只有一端開放，數據進、出操作都只能在開放的一端進行
2.幼兒園中 8 個小朋友，依次編號(1－8)玩游戲，按編號順序排隊圍成一圈，由編號 1 號的小朋友開始報數，報數報到 3 的小朋友出列，下一個編號的小朋友又從 1 開始報數，一直反復直到剩下最后一人，請問在該問題上采用的適合數據結構和剩下的小朋友的編號是(　　)
A.二叉樹7 B.隊列7 C.棧4 D.鏈表 4
3.在利用棧來判斷一個表達式的括號(只有小括號)是否匹配的過程中，當遇到表達式中的一個左括號時，就讓其進棧，遇到一個右括號時，就對棧進行一次出棧操作；當棧最后為空，表示括號是配對的，否則是不配對的。現有表達式“(a＋b)*c＋((d－e)*f＋g)*h”，針對該表達式設計棧的大小至少為(　　)
A.1 B.2 C.3 D.4
4.有一棵樹，節點的度和個數如下表所示。
度 0 1 2 3 4
節點個數 x 4 3 2 1
則葉子節點x的個數為(　　)
A.8 B.9 C.10 D.11
5.已知某二叉樹的中序遍歷結果為BFDGAEHC，層序遍歷(從上往下、從左往右)結果為ABCDEFGH，則下列有關該二叉樹的說法，正確的是(　　)
A.該二叉樹是完全二叉樹
B.用數組存儲該二叉樹時，節點F對應的數組下標為9
C.該二叉樹有4個葉子節點
D.該二叉樹的前序遍歷結果為ABDFGCHE
6.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　c[tail]＝a[i]
　tail＝tail＋1
　elif a[i]>c[head]：
　 head＝head＋1
print(c[head：tail])
執行該程序段后，輸出的內容不可能是(　　)
A.[10，9，16] B.[8，10，11，9，16]
C.[8，10，2，9] D.[10，7，16]
7.有如下 Python 程序段：
import random
a＝[23，25，40，16，21，－1，－1，－1，21，－1，－1，－1，－1，－1，－1，－1，－1，－1，－1]
st＝[0]*10
key＝random.randint(10，19)*2＋1
top＝－1
n＝len(a)
i＝0；p＝0
while i　　　top＋＝1；st[top]＝p
　　　if a[st[top]]＝＝－1 or key＝＝a[st[top]]:
　break
　　　elif key>a[st[top]]:
　 p＝p*2＋2
　else：
　p＝p*2＋1
　　i＋＝1
while(top！＝－1):
　　　print(st[top]，end＝″ ″)
　　　top－＝1
執行以上程序，不可能得到的輸出結果是(　　)
A.5 2 0 B.10 4 1 0 C.0 D.8 3 1 0
8.定義如下函數：
def inquire(x，y，key)：
　 m＝(x＋y)∥2
　 if key＝＝a[m]：
　 return ″M″
　　elif key　return ″R″＋inquire(m＋1，y，key)
　　else：
　 return ″L″＋inquire(x，m－1，key)
數組a的元素為[55，49，37，26，24，14，3，3，1]，若執行語句h＝inquire(0，8，14)，則h的值是(　　)
A.LRM B.RLM C.MRL D.MLR
9.定義如下兩個函數，fac_1和fac_2：
def fac_1(n)： res＝1 for i in range(1，n＋1): 　　res *＝i return res
def fac_2(n)： if n＝＝1： 　　 return 1 else： 　return n * fac_2(n－1)
下列說法正確的是(　　)
A.fac_1和fac_2都采用遞歸算法
B.執行fac_1(4)和fac_2(4)時，兩個函數被調用次數不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函數的算法時間效率遠大于fac_1
10.有如下Python程序段：
a＝list(map(int，input().split())) #將輸入的數據轉換成列表
n＝len(a)
for i in range(2)：
　for j in range(n－1，i，－1 )：
　if a[j] % 3>a[j－1] % 3：
　　　a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
以下運行結果不可能的是(　　)
A.[20，50，10，40，30，60]　　B.[5，8，1，3，4，6]
C.[9，17，16，4，12，5] D.[17，11，1，4，9，6]
11.小明為英文字母A～Z定義了一套全新的二進制編碼規則，代碼如下：
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　i＝0
　 j＝len(s)－1
　 rt＝″0″
　while i<＝j：
　m＝(i＋j)∥2
　if s[m]＝＝k：
　　　dc[k]＝rt
　　　break
　elif s[m]　 　　　　i＝m＋1
　　 　rt＋＝″1″
　else：
　 　j＝m－1
　　　rt＋＝″0″
inp＝input(″請輸入英文字符串： ″).upper()
#將輸入的英文字母轉為大寫
for c in inp：
　print(dc[c]，end＝″ ″)
當程序運行后，輸入“OK”后，其輸出的二進制編碼為(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
12.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
i＋＝1
　　if i＝＝k：
　p＝people[q][1]
　people[q][1]＝people[p][1]
　if p＝＝head：
　　　head＝people[q][1]
　i＝1
　n－＝1
　　q＝people[q][1]
print(people[head][0])
該程序段運行后，若輸入 2，則輸出的結果為(　　)
A.3 B.5 C.6 D.2
二、非選擇題(本題共3小題，共26分)
13.(6分)水房里一共有m個水龍頭，每個龍頭每秒鐘的供水量均為1。現有按接水順序從1到n編號的n名同學進行接水。一開始，m位同學同時接水，下一名排隊等候接水的同學，接替接水時間最短同學的水龍頭位置開始接水，以此類推，當其中一個水龍頭完成某個同學的接水任務時，下一位等候的學生自動接上。每個水龍頭的供水時間為在該水龍頭上接水所有學生時間之和，所有同學接水的時間為供水時間最長的水龍頭。第4位學生將在第1個水龍頭接水，該水龍頭放水8秒時，第4位和第5位學生分別接在第1個和第2個水龍頭接水，第6位學生將在第9秒開始在第3個水龍頭進行接水。
(1)7位學生在3個水龍頭中接水時間(單位：秒)分別為“4，5，7，1，6，2，8”(不包括雙引號)，則所有同學接水的總時間為________秒。
(2)編寫程序運行結果如圖所示，代碼如下，請在劃線處填入合適的代碼。
需要取水時間分別為：4，8，9，4，5，6，8，7 籠頭1取水時間：4，4，5，7 籠頭2取水時間：8，6 籠頭3取水時間：9，8 最多取水時間為：20
#讀取n名同學進行接水時間存儲到數組a中，代碼略
m＝3；n＝len(a)
q＝[[0 for j in range(n)]for i in range(m)] #構建三個隊列，用于記錄每個水龍頭接水情況
head＝[0]*3；tail＝[1]*3
q[0][0]＝a[0]；q[1][0]＝a[1]；q[2][0]＝a[2]
h＝3；t＝0 #h表示隊列a中的指針，用于讀取每個人的接水時間。t表示當前時間。
totaltime＝[a[0]，a[1]，a[2]] #存儲每個水龍頭總的接水時間
flag＝False
while ①________：
for i in range(3)：
if ②________：
　　　　if h　　　　　　　q[i][tail[i]]＝a[h]
　　　　　　　totaltime[i]＋＝a[h]
　　　　　　　h＋＝1
　　　　　　　③________
　　　　else：
　　　　　　flag＝True　　　　
t＋＝1
maxx＝max(totaltime)
#輸出每個水龍頭接水時間和最長接水時間，代碼略。
14.(10分)某停車場分為省內區和省外區，省內客車只能停靠在省內區，省外客車只能停靠在省外區。每輛客車抵達后，如果相應的區(省內區/省外區)還有空閑的近車位，就停靠在近車位，否則停靠在遠車位(假設遠車位的數量充足)。現給定未來一段時間客車的抵達、離開時刻，根據省內區和省外區的停車位數量，使停靠在近車位的客車數量最多，并顯示各個車位停車情況。
車輛班次信息存儲在 bc 列表中，存入順序為先省內再省外，列表中的每個元素包含三個數據項，分別對應每個班次客車的車型(0 代表省內，1 代表省外)、抵達時間、離開時間。將省內班次和省外班次分別按抵達時間做升序排序，并計算停靠在近車位的車輛數量最多的車位分配方案，并顯示各個車位停車情況，代碼運行效果如圖所示。
[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]] 省內班次：5　省外班次：4 最多停的班次數：7　分配省內車位數2　省外車位數：1 1號車位情況 [0，1，5] [0，6，10] [0，13，18] 2號車位情況 [0，3，8] [0，9，14] 3號車位情況 [1，2，11] [1，12，16]
(1)上圖所示例子，車位分配方案改為省內 1 個、省外 2 個，則最多停靠班次數為________輛。
(2)實現上述功能的程序如下，請在劃線處填入合適的代碼。
def sort(st，ed): #對區間[st，ed]之間所有的車次按到達時間升序排列。
　for i in range(st，ed)：
　 for j in range(st，①__________):
　　　 　if bc[j][1]>bc[j＋1][1]：
　　　　 bc[j]，bc[j＋1]＝bc[j＋1]，bc[j]
bc＝[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
#[班次類型，抵達時間，離開時間] 0 表示省內 1 表省外 m＝3；x＝0；y＝0 #m 個近車位，x 個省內班次，y 個省外班次
for i in range(len(bc))：
　　　if bc[i][0]＝＝0:
x＋＝1
　　　else：
y＋＝1
print('省內班次數：'，str(x)，'省外班次數：'，str(y))
sort(0，x－1)
sort(x，x＋y－1)
maxstack＝[[0]*100 for i in range(m)]
maxtop＝[－1]*m；maxans＝0；maxi＝0；maxj＝0 #存儲停車最多時的方案
def check(st，ed，j，stack，top):
　num＝－1
　for i in range(st，ed＋1)：
　if top[i]＝＝－1 or ②__________：
　 　　num＝i
　　 　break
　return num
for i in range(0，m＋1)：
　stack＝[[0]*100 for i in range(m)]
　 top＝[－1]*m；ans＝0
　for j in range(x＋y)：
if j　　　　k＝check(0，i－1，j，stack，top)
else：
　　　　k＝③________
if k！＝－1：
　　　　ans＋＝1；top[k]＋＝1
　　　　④__________
if ans>maxans:
maxans＝ans；maxstack＝stack；maxtop＝top
maxi＝i；maxj＝m－i
print('最多停的班次數：'，maxans，'分配省內車位數：'，maxi，'省外車位數：'，maxj)
for i in range(m)：
　print(i＋1，'號車位情況')
　 for j in range(maxtop[i]＋1):
print(bc[maxstack[i][j]])
15.(10分)有60個人要組建一個聚會，每人的喜好是一個數值，為提升聚會效果，會務組要把參會人員進行分組，分組原則是：
1)每組不超過8人
2)組內新增人員的喜好值必須與現有組內人員的平均喜好值相差在5以內
3)若新增人員無法加入現有小組，則被分入新組建小組
采用Python編寫了程序，運行結果如圖所示：
第1組：4，6，8，2，2，7，2，8 第2組：50，45，43，48，48，43，43，42 第3組：14，11，13，16，17，18，17，13 第4組：21，26，19，23，23，18，23，22 第5組：37，35，38，34，33，35，33，33 第6組：16，13，10 第7組：43，45，47，40，45，44，44 第8組：28，28，33，29，34，32，27，33 第9組：37，38
(1)如圖所示，當前數據已被分組，若再新增一個數“47”，會被分在第________組。
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
#讀取n個人的喜好值，存儲到列表a中代碼略。
h＝[－1 for i in range(n)] #創建n個空的鏈表
ave＝[[0 for j in range(2)]for i in range(60)]
#用于存儲每組喜好值的總和和人數
b＝[]
for i in a：
　j＝0 #表示從第0條鏈表開始遍歷
　 p＝h[j]
　 while p！＝－1：
if abs(i－ave[j][0]/ave[j][1])>5 or ave[j][1]＝＝8：
　　　j＋＝1
　　 　①________
else：
　　　p＝b[p][1]
　b.append([i，－1])
　if h[j]＝＝－1: #每組第一個人，添加到鏈表頭
　②________
　else：　　　　
　p＝h[j]　　　　
　while p！＝－1：
　　　bp＝p
　　　p＝b[p][1]
　 ③________
　　ave[j][0]＋＝i
　　ave[j][1]＋＝1
#輸出各個分組情況，代碼略
驗收卷(六)　綜合練習(B)
1.D　[A選項數組中未使用到的空間導致內存浪費。B選項若刪除的是頭節點，只要修改頭指針即可。C選項實現“后退”按鈕的功能是棧的功能。D選項棧是一種受限的數據結構，只能在一端進行操作。]
2.B　[本題考查數據結構的相關知識。適合的數據結構應為隊列，出隊的順序為：3，6，1，5，2，8，4，最后剩下的一人編號為 7。]
3.B　[遇到第一個左括號進棧，遇到第一個右括號時，棧中的左括號出棧。遇到第二個和第三個左括號，依次進棧。遇到第二個右括號，依次出棧，遇到第三個右括號，又依次出棧。此時棧為空，表達式中的括號配對成功。整個過程中，棧中最多有2個左括號，所以棧的大小至少為2。]
4.D　[樹中所有節點的度之和加1為節點總數，因此1*4＋2*3＋3*2＋4*1＝21。節點數為x＋4＋3＋2＋1＝x＋10，因此可以得到葉子節點數為11個。]
5.B　[A為整棵樹的根節點，從中序遍歷來看，B和C分別是整棵樹的左右節點。FDG是節點B的右子樹，EH是節點C的左子樹。第3層左邊第1個節點為D，因此F是D的左子樹，G是D的右子樹。第3層左邊第2個節點為E，因此H為E的右子樹。畫出樹的形態如圖所示。該樹只有3個葉子節點，前序遍歷為ABDFGCEH。]
6.C　[若隊列中數據元素小于2或者t的值為0，則將a[i]入隊，否則當a[i]大于c[head]時出隊，a中元素既可以不入隊，也可以不出隊(t為1，且a[i]小于等于c[head])。A選項8，10入隊，2和7可以不入隊，11讓8出隊，隊列中只剩下1個元素，9入隊，接著t的值為0，16入隊。B選項8，10入隊后，接著t的值依次為1，1，0，0，0。C選項隊首為8，當遍歷到11時，要么讓8出隊，要么產生的t為0，11入隊，因此C不可能。D選項11讓隊首8出隊，當遍歷到16時，產生的t為0，16入隊。]
7.B　[本題考查棧的算法實現。產生21到39之間的任意奇數key，將列表a中對應數據的索引存放到棧中，若棧頂數據為空或者棧頂對應的值和key相同時，結束循環，若key值大于棧頂數據，將p*2＋2個位置存入棧中。若key小于棧頂數據時，將p*2＋1個位置入棧。A選項Key值大于23且小于等于39時，0，2，5位置數據入棧。C選項key值等于23時，存入數據為0，結束循環。D選項當key小于23時，0，1，3，8位置數據入棧。B選項當key值為21，不會出現0，1，4數據入棧。]
8.B　[程序的功能采用二分查找法查找14的過程。依次查找的數據為24，3和14，因此先向右查找，再向左查找，最后一次找到。]
9.B　[本題考查迭代與遞歸的算法思想。兩處程序的功能均為求n的階乘。A選項程序fac_1體現迭代算法思想。B選項fac_1(4)只調用1次，而fac_2(4)要調用4次。C選項返回值均為24。D選項均循環了n次，因此算法效率一樣。]
10.C　[本題考查程序冒泡排序。從右往左(從后往前)進行了2趟排序，排序比較是元素%3后，最前面的2個元素除3余數一定是所有元素中最大的。]
11.A　[構建一棵26個節點的升序二叉樹，由于26小于31，因此最多查找4次，用一個4位二進制數存儲訪問的節點(標記為1)。]
12.B　[本題考查循環鏈表的算法實現。每遍歷一次，i增加1，實現計數。第1次刪除節點2，第2次刪除節點4，第3、4、5分別刪除節點6、3、1，鏈表中只剩下節點5。 ]
13.(1)15　(2)①not flag　②totaltime[i]＝＝t　③tail[i]＋＝1
解析　本題考查隊列的基本操作。(1)水龍頭1取水時間為4＋1＋6＝11，水龍頭2取水時間為5＋2＋8＝15，水龍頭3取水時間為7，最大取水時間為15。h表示隊列a中的指針，用于讀取每個人的接水時間。當條件h14.(1)6　(2)①ed－i＋st　②bc[stack[i][top[i]]][2]解析　(1)省內 1 個車位，分別停[0，1，5]、[0，6，10]、[0，13，18]共3個班次。省外2個車位，一個車位停[1，2，11]、[1，12，16]，另一個車位停[1，4，15] 共3個班次。
(2)①內循環決定每趟排序的次數和起址位置。開始位置為st，因此實現從前往后冒泡，第一趟排序變量j的的終值為ed，此時變量i的值為st，隨著i的增加，內循環終值將不斷地減小，因此終值的值為ed＋st－i。②check函數判斷某個班次是否可以停放到某個車位上。st表示起始車位編號，ed 表示結束車位編號，j 表示班次編號，stack 表示停車場的車位停放車輛信息，top 表示每個車位上停車數量的列表(即棧頂)。循環遍歷起始車位到結束車位的車位列表，判斷當前車位是否可以停放該班次，如果可以停放，則返回該車位的編號；否則返回－1。停放的條件：該車位沒有車輛停放或者該班次編號和前面已經停放的車輛班次再停放時間上沒有重疊。bc[stack[i][top[i]]][2]表示標號為 i 的停車位最后停放車輛的離開時間。③枚舉停車場中省內和省外車位的數量，計算出停車場中停放班次最多的方案。外循環枚舉停車場中省內車位的數量，內循環枚舉班次列表中的所有班次。當 j15.(1)7　(2) ①p＝h[j]　 ②h[j]＝len(b)－1
③b[bp][1]＝len(b)－1
解析　(1)第2至5組人數已經達到8人，第7組目前平均值為44，加入第7組后的平均喜好值相差在5以內。(2)分析程序可得，i表示當前參會人員個人喜好值；j表示當前組(從0開始編號)；p表示遍歷鏈表b 的位置；變量h用于存儲每組的頭結點在鏈表b中的位置；①內層While循環中if語句表示當前的參會人員不能加入到該組，因此需要查看后面組的平均值以及當前總人數看是否能夠加入到這些組中，知道找到第一個能插入的組，因此j＋＝1為往后找能存儲的組，當找到可以加入的組時，需要添加在b中相應鏈表中，因此需要找到當前組的頭結點位置賦值給p，便于后續插入時查找位置。②該空位于if語句中，每組的第一個人，添加到鏈表頭，h存儲每組頭結點的位置，由于是第一個，因此將該人員在b中的位置值復制給h相應組處，答案為h[j]＝len(b)－1。③非該組第一個人，插入時指針值為－1，單向鏈表因此需要修改前驅節點的指針值為該節點的位置，通過上個while循環可得前驅節點的位置存儲在變量p中，因此答案為b[bp][1]＝len(b)－1。

展開更多......

收起↑