資源簡介

(共39張PPT)
第五章　數據結構與算法
驗收卷(四)　數據結構與算法
(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
1.下列有關數據結構的敘述中正確的是(　　)
A
解析　棧是限定在一端進行插入和刪除的線性表，而另一端封閉，隊列是限定僅在一端進行插入，在另一端進行刪除的線性表，因此B選項錯誤；數據結構與算法有著密不可分的關系，數據結構的不同選擇會影響算法的運行效率，因此，在設計算法需要考慮選用何種數據結構，故C選項錯誤；鏈式存儲結構不一定優于線性表的線性存儲結構，例如查找時，鏈式存儲結構需要從頭開始找，而線性表可直接通過下標找到，因此D選項錯誤；算法的設計和選擇總是依賴于數據結構，它們兩者是相輔相成的，因此，答案為A。
A.算法的設計和選擇總是依賴于數據結構
B.棧是限定僅在一端進行插入，在另一端進行刪除的線性表
C.數據結構與算法是相互獨立的，設計算法時不用考慮選用何種數據結構
D.鏈式存儲結構優于線性表的線性存儲結構
D
2.遞歸算法的執行過程，一般來說，可先后分為遞推階段和(　　)
解析　本題主要考查的是遞歸算法的執行過程。遞歸算法的執行過程分為遞推和回歸兩個階段，因此，答案為D。
A.合并階段 B.返回階段
C.回溯階段 D.回歸階段
A
3.定義如下函數：
def fn(n，num1，num2):
　if n＝＝1：
　 return num1
　return fn(n－1，num2，num1＋num2)
下列說法正確的是(　　)
A.該算法的時間復雜度是O(n)
B.fn(10，1，2)的效果等價于1＋2＋3…＋10
C.fn(5，1，1)的結果是22
D.fn(1，1，1)與fn(1，1，2)的返回結果不同
解析　A選項函數將調用n次，因此時間復雜度是O(n)。B選項該函數的功能是實現斐波那契數列效果；C選項，fn(5，1，1)的結果是 5；D選項fn(1，1，1)與fn(1，1，2)的返回結果相同，都是 1。
4.下列有兩段程序：
D
關于兩個程序段的說法，正確的是(　　)
A.程序段 1 和程序段 2 的輸出結果不相同
B.程序段 1 和程序段 2 都采用了遞歸算法
C.若問題規模為 n，程序段 2 的時間復雜度為O(n2)
D.程序段 1 中，①和②兩方框處中的數字 1 同時修改為 0，輸出結果不變
解析　本題考查遞歸和迭代、時間復雜度的計算閱讀程序段 1，可知為遞歸算法實現 10＋9＋…＋1 的和；閱讀程序段 2，可知為迭代算法實現 1＋2＋…＋10。因此兩段程序輸出結果相同，A 錯誤；程序段 2 為迭代算法，B 錯誤；程序段 2 中只有一層循環，時間復雜度為O(n)，C 錯誤；修改程序段 1 代碼，僅僅多遞歸一層函數，但是返回值＋0 并不會影響輸出結果，D 正確。
D
5.下列四段程序中，時間復雜度為O(n)的是(　　)
解析　選項A、B中程序段的時間復雜度均為O(n2)，因此，AB選項錯誤；選項C中程序段的時間復雜度均為O(log2n)，因此C選項錯誤；選項D中程序段，外循環的時間復雜度均為O(log2n)，內循環的執行次數為20＋21＋…＋2k(k＝log2n)，根據等比數據求和公式，其和為n－1，即時間復雜度為O(n)，因此答案為D。
6.有如下Python 程序段：
def fx(x)：
if x>3：
ans＝x*fx(x－1)
elif x>1：
ans＝x＋fx(x－1)
else：
ans＝2
return ans
n＝int(input(″please input n：″))
print(fx(n))
C
程序執行時，輸入n的值為6，則輸出的結果為(　　)
A.127 B.720 C.840 D.1440
解析　本題主要考查的是遞歸算法。n＝6，ans＝6*5*4*f(3)，而f(3)＝3＋2＋f(1)，已知f(1)＝2，因此ans＝840，故答案為C。
D
A.10，5，32，6，7，9，17，24，4
B.10，5，32，6，7，9，4，17，24
C.10，5，32，4，6，7，9，17，24
D.4，10，5，32，17，9，24，6，7
解析　冒泡的方向可以從前往后排序，后面的數據先有序；也可以從后往前排序，前面的數據先有序。第一遍排序后的結果把最小的數排到了最前面，因此可以推斷是升序排列。
A
8.采用冒泡排序算法對某數據序列進行排序，第一輪排序后的結果是“2，8，6，3，5，7，9”，則第二輪排序需要交換的次數為(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
解析　本題考查冒泡排序算法的相關知識。由第一輪數據“2，8，6，3，5，7，9”可知，采用冒泡排序對數據進行升序排序，但有兩種可能，一種是從后往前的冒泡升序，則第二輪排序后的數據為“2，3，8，6，5，7，9”，交換2次，另一種是從前往后的冒泡升序，則第二輪排序后的數據為“2，6，3，5，7，8，9”，交換4次。
9.有如下Python 程序段：
a＝[3，1，9，6]
#將以空格隔開的輸入數以列表的形式存儲
m＝len(a)
while m！＝1：
　　for i in range(m－1):
　if a[i]>a[i＋1]：
　　　　a[i]，a[i＋1]＝a[i＋1]，a[i]
　　　m－＝1
print(a)
A
執行程序后，輸出的結果為(　　)
A.[1，3，6，9] B.[9，6，3，1]
C.[1，6，3，9] D.[9，3，6，1]
解析　本題考查冒泡排序的算法思想。從前往后冒泡實現升序排列，共排了m－1趟。
C
10.互不相等的 10 個列表元素 s[0]、s[1]、s[2]……s[9]，有如下Python 程序段：
n＝10
for i in range( 5 ) ：
　for j in range(1，n－i):
　 if s[j]>s[j－1]：
　　 　s[j]，s[j－1]＝s[j－1]，s[j]
該程序段實現的是(　　)
A.s[0]到 s[5]的降序排列 B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列 D.s[5]到 s[9]的升序排列
解析　本題考查冒泡排序算法思想。分析冒泡排序內循環的代碼，是從左(前)向右(后)冒泡、降序。外循環只進行了5次，所以只有最后5個數(s[5]到 s[9])是有序的。
11.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j：
　　　m＝(i＋j＋1)∥2
　　　n＝n＋1
　　　if key＝＝a[m]：
　　　　　break
　　　if key>a[m]：
　　　　　i＝m＋1
　　　else：
　　　　　j＝m－1
print(n)
A
解析　n的值為查找次數，7查找次數為2，其余查找次數是4。
12.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　ans＝m
　break
　　if a[m]>key：
D
　R＝m－1
　f－＝1
　　else：
　L＝m＋1
　 f＋＝1
運行該程序段后，關于f和ans的結果，下列說法正確的是(　　)
A.f可能的最小值為－3 B.f的值可能為－1
C.ans的值可能為1 D.ans的值不可能為3
解析　查找一個0－18之間的隨機偶數key，畫出相應的二叉樹。A選項查找0，向左查找4次，f的值為－4。B選項向右查找1次，找到的數為3，不是偶數。C選項a[1]的值為3，不是偶數。D選項ans的值若為3，a[3]的值為8，而找到的第1個8的索引位置是4。
二、非選擇題(本題共3小題，共26分)
13.(9分)根據申請人的QA和QB值，從m個申請人中挑選2人組隊參加某挑戰賽。條件一是2人的QA值都必須大于指定參數h；條件二是2人的QA值之差(較大值減較小值)小于h。在滿足上述兩個條件的所有2人組合中，挑選QB值之和最大的一個組合。(QA、QB和h的值均為正整數)
編寫Python程序，實現上述挑選功能。運行程序，輸入參數h后，按QA值降序顯示滿足條件一的申請人信息，最后顯示組隊結果。程序運行界面如下圖所示。
請輸入h的值：60
符合條件一的申請人
編號　QA值　QB值
11 200 25
10 139 18
17 132 10
14 99 21
9 83 20
1 67 34
8 66 24
組隊結果：1號，8號
實現上述功能的Python程序如下，請回答下列問題：
m＝20　 #m表示申請人個數
id＝qa＝qb＝[0]*m
n＝0　 #變量n存儲滿足條件一的申請人個數
s＝″″
#讀取全部申請人的編號、QA和QB值，分別存入數組id、qa和qb，代碼略
h＝int(input(″請輸入h的值：″))
n＝m
for i in range(1，m)：
for j in range(m－1，i－1，－1)：
print(″編號″，″ QA值″，″QB值″)
for i in range(n)：
print(″%3d%3d%3d″%(id[i]，qa[i]，qb[i]))
maxx＝0
s＝″沒有滿足條件的組合″
#在滿足條件的組合中，尋找QB值之和最大的組合，若有并列，只保留第一個
for i in range(0，n－1)：
j＝i＋1
while ②________________：
if qb[i]＋qb[j]>maxx：
　　　　s＝″組隊結果：″＋str(id[i])＋″號，″＋str(id[j])＋″號″
　　　　③________________
j＋＝1
print(s)
(1)代碼中加框處代碼有錯誤請改正。
加框處的代碼應修改為_________________________________________________；
(2)請在劃線①②③處填入合適的代碼。
劃線①處應填入的代碼是____________________________________________；
劃線②處應填入的代碼是_______________________________________________；
劃線③處應填入的代碼是_____________________________________________。
答案　(1)qa[j]>h and qa[j]>qa[j－1] 或qa[j]>qa[j－1]
(2)①n＝i－1　②j<＝n－1 and abs(qa[i]－qa[j])解析　本題主要考查的是冒泡排序算法及其綜合應用。(1)程序首先使用冒泡排序算法找出所有符合條件一的申請人，根據程序運行窗口可知數據是按QA值降序排序的，并將滿足條件一的人數記錄在變量n中。排序方式有兩種，只將符合條件一的申請人進行降序排序，即加框處語句修改為qa[j]>h and qa[j]>qa[j－1]，將所有申請人進行降序排序，即加框處語句修改為qa[j]>qa[j－1]；(2)如果申請人不滿足條件一，則排序可以提前結束，滿足條件人數為i
－1人，因此，程序劃線①處代碼為n＝i－1；劃線②處所在的循環語句的功能是使用枚舉所有滿足條件一、條件二的申請人進行組隊，記錄組隊人QB值之和為最大的2個人，因此，②處代碼為j<＝n－1 and abs(qa[i]－qa[j])14.(7分)已知某水果店有 n 種水果，編號依次為 0～n－1，每種水果存量若干份。現為每位顧客分配兩份不同種類且該顧客喜歡的水果，為合理分配，每位顧客分別勾選自己喜歡的水果編號，每人至少勾選兩種(包含兩種)以上水果。編寫程序，根據水果存量數據以及顧客勾選數據，輸出水果是否能分配完成。請回答下列問題：
(1)若n為5，分配前每種水果存量數據如圖a所示，顧客勾選數據如圖b所示，則最后水果________(選填：能/不能)完成分配。
(2)實現上述功能的部分 Python 程序如下，請在劃線處填入合適的代碼。
def sort_f(x，y)：
　 for i in range(y)：
　for j in range(①______)：
　　 　　if num[fruit[j]]　　　 　fruit[j]，fruit[j＋1]＝fruit[j＋1]，fruit[j]
　　　return fruit
#讀取每種水果的存量數據，存入字典 num，例如：num＝{0：5，1：4，2：7，3：1，4：3，5：6}，代碼略。
#讀取每位顧客的勾選數據，存入列表 tch，例如：tch＝[[0，3，5]，[1，2]]，代碼略。
fruit＝[0，1，2，3，4，5] #存儲水果編號
fruit＝sort_f(0，len(fruit)－1)
②__________
for k in range(len(tch)):
　 c＝[]；p＝0
　while ③______________：
if fruit[p] in tch[k]:
　　　　num[fruit[p]]－＝1
　　　　c.append(p)
p＋＝1
　if len(c)<2：
flag＝False　　
break
　fruit＝sort_f(c[0]，2)
if flag：
　　　print(″水果能分配完成！″)
else：
　　print(″水果不能分配完成！″)
答案　(1)能　(2)①x，len(fruit)－i－1　②flag＝True　③len(c)<2 and num[fruit[p]]>0
解析　(1)由于每位顧客分配兩種水果，因此只勾選兩種水果的顧客只分配給他們勾選的水果，剩余勾選2種以上的顧客，從剩余水果中選取還有存量的水果分配給他們。“1，2”“1，3”分配好后，剩余“5，2，6，0，3”，此時還有“0，3，4”“1，3，4”需從中選取分配，3號水果存量為0，不作考慮，0，1，4號水果存量均大于等于2，足夠分配。因此能完成分配。
(2)分配時，按照水果存量情況降序排列，將列表fruit中水果編號按水果存量降序排列。枚舉每位顧客勾選數據，從列表fruit中從左往右，依次選取水果存量大的檢測是否為該顧客喜歡水果，如果是則將此水果分配給該顧客，一共選取兩種水果，用列表c存儲分配的水果編號的索引。該顧客分配完成后，利用列表c存儲的第一種水果編號索引作為再排序的起始位置，因為0～c[0]－1范圍內的水果存量未變，只要對列表c中兩個水果存量進行再排序，fruit按照最新存量進行降序排列，排2次即可。如果在分配過程中該顧客喜歡的水果無法分配兩份，則分配失敗。
15.(10分)將十進制數 n(264≥n≥3)轉化為 k(k≥2)進制數，若所有數位全為 1，則稱 k 是 n 的一個好進制數。例如，十進制數 31 可以轉化為(11)30 和(11111)2，因此 30 和 2 均是 31 的好進制數，其中 2 為 31 的最小好進制數。請回答下列問題：
(1)十進制數“21”的最小好進制數 k 是________。
(2)小明編寫程序，找出 n 的最小好進制數 k，請在劃線處填入合適的代碼。
n＝int(input(″輸入一個十進制數： ″))
def check(k，m): #計算 m 位全為 1 的 k 進制的十進制值，如(111)2 的十進制值為 7
　　　ans＝0
　　　for i in range(m)：
　　　　①____________
　　　return ans
ans＝n
for length in range(2，65)：
　②____________
　 j＝n－1
　 while i<＝j：
　 mid＝(i＋j)∥2
　tmp＝check(mid，length)
　if tmp＝＝n：
　　　if ans>mid：
　　　　ans＝mid
　　　　break
　elif ③____________：
　　 　i＝mid＋1
　else：
　　　j＝mid－1
print(n，″的最小好進制數是″，ans)
答案　(1)4　(2)①ans＝ans*k＋1 或 ans＝ans＋k**i 或 ans＝ans＋k**(m－i－1)　②i＝2　③tmp解析　本題考查進制轉換、對分查找等相關知識。(1)21＝16＋4＋1＝(111)4，故最小的好進制數是4。①空實現 k 進制、m 位 1 轉換為十進制數的過程，此處可采用累乘相加，即 ans＝ans*k＋1或 ans＝ans＋k**(m－i－1)等。②處填 i 的初始值。已知函數 check 的第 1 個參數為進制，第 2 個參數為 1 的位數，結合 tmp＝check(mid，length)這一句，可知 mid 為進制。本題的進制最小值為 2，進制最大值為 n－1(例如 64＝63＋1＝(11)63)。③外循環枚舉所有可能的位數，循環中采用對分法測試結果，即先找到進制的中位數 mid，計算 mid 進制下，length 位個 1 轉換為十進制數的 tmp。若 tmp＝＝n，則保留 mid 的最小值，進入下一輪大循環，查找更長的位數(位數越長意味著進制越小)。若 tmp(考試時間40分鐘　滿分50分)
一、選擇題(本題共12小題，每小題2分，共24分)
1.下列有關數據結構的敘述中正確的是(　　)
A.算法的設計和選擇總是依賴于數據結構
B.棧是限定僅在一端進行插入，在另一端進行刪除的線性表
C.數據結構與算法是相互獨立的，設計算法時不用考慮選用何種數據結構
D.鏈式存儲結構優于線性表的線性存儲結構
2.遞歸算法的執行過程，一般來說，可先后分為遞推階段和(　　)
A.合并階段 B.返回階段
C.回溯階段 D.回歸階段
3.定義如下函數：
def fn(n，num1，num2):
　if n＝＝1：
　 return num1
　return fn(n－1，num2，num1＋num2)
下列說法正確的是(　　)
A.該算法的時間復雜度是O(n)
B.fn(10，1，2)的效果等價于1＋2＋3…＋10
C.fn(5，1，1)的結果是22
D.fn(1，1，1)與fn(1，1，2)的返回結果不同
4.下列有兩段程序：
#程序段1 def rec(n)： if ：　　#① 　　 #② else： 　　return n＋rec(n－1) print(rec(10)) #程序段2 def rec(n)： ans＝0 for i in range(1，n＋1，1)： 　　ans＝ans＋i return ans print(rec(10))
關于兩個程序段的說法，正確的是(　　)
A.程序段 1 和程序段 2 的輸出結果不相同
B.程序段 1 和程序段 2 都采用了遞歸算法
C.若問題規模為 n，程序段 2 的時間復雜度為O(n2)
D.程序段 1 中，①和②兩方框處中的數字 1 同時修改為 0，輸出結果不變
5.下列四段程序中，時間復雜度為O(n)的是(　　)
6.有如下Python 程序段：
def fx(x)：
if x>3：
ans＝x*fx(x－1)
elif x>1：
ans＝x＋fx(x－1)
else：
ans＝2
return ans
n＝int(input(″please input n：″))
print(fx(n))
程序執行時，輸入n的值為6，則輸出的結果為(　　)
A.127 B.720 C.840 D.1440
7.有一個數組，采用冒泡排序，第一遍排序后的結果為：4，10，5，32，6，7，9，17，24該數組的原始順序不可能的是(　　)
A.10，5，32，6，7，9，17，24，4
B.10，5，32，6，7，9，4，17，24
C.10，5，32，4，6，7，9，17，24
D.4，10，5，32，17，9，24，6，7
8.采用冒泡排序算法對某數據序列進行排序，第一輪排序后的結果是“2，8，6，3，5，7，9”，則第二輪排序需要交換的次數為(　　)
A.4次或2次 B.4次或3次
C.3次或1次 D.2次或1次
9.有如下Python 程序段：
a＝[3，1，9，6]
#將以空格隔開的輸入數以列表的形式存儲
m＝len(a)
while m！＝1：
　　for i in range(m－1):
　if a[i]>a[i＋1]：
　　　　a[i]，a[i＋1]＝a[i＋1]，a[i]
　　　m－＝1
print(a)
執行程序后，輸出的結果為(　　)
A.[1，3，6，9] B.[9，6，3，1]
C.[1，6，3，9] D.[9，3，6，1]
10.互不相等的 10 個列表元素 s[0]、s[1]、s[2]……s[9]，有如下Python 程序段：
n＝10
for i in range( 5 ) ：
　for j in range(1，n－i):
　 if s[j]>s[j－1]：
　　 　s[j]，s[j－1]＝s[j－1]，s[j]
該程序段實現的是(　　)
A.s[0]到 s[5]的降序排列 B.s[0]到 s[5]的升序排列
C.s[5]到 s[9]的降序排列 D.s[5]到 s[9]的升序排列
11.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j：
　　　m＝(i＋j＋1)∥2
　　　n＝n＋1
　　　if key＝＝a[m]：
　　　　　break
　　　if key>a[m]：
　　　　　i＝m＋1
　　　else：
　　　　　j＝m－1
print(n)
列表a中各元素值依次為1～25，若查找鍵key為下列選項的值，程序段執行后，輸出結果與其他三項不同的是(　　)
A.7 B.12 C.19 D.22
12.有如下Python程序段：
import random
a＝[1，3，3，8，8，10，10，14，16，17]
key＝random.randint(0，9)*2
ans＝－1; f＝0
L＝0；R＝9
while L<＝R：
　　m＝(L＋R＋1)∥2
　　if a[m]＝＝key ：
　ans＝m
　break
　　if a[m]>key：
　R＝m－1
　f－＝1
　　else：
　L＝m＋1
　 f＋＝1
運行該程序段后，關于f和ans的結果，下列說法正確的是(　　)
A.f可能的最小值為－3
B.f的值可能為－1
C.ans的值可能為1
D.ans的值不可能為3
二、非選擇題(本題共3小題，共26分)
13.(9分)根據申請人的QA和QB值，從m個申請人中挑選2人組隊參加某挑戰賽。條件一是2人的QA值都必須大于指定參數h；條件二是2人的QA值之差(較大值減較小值)小于h。在滿足上述兩個條件的所有2人組合中，挑選QB值之和最大的一個組合。(QA、QB和h的值均為正整數)
編寫Python程序，實現上述挑選功能。運行程序，輸入參數h后，按QA值降序顯示滿足條件一的申請人信息，最后顯示組隊結果。程序運行界面如下圖所示。
請輸入h的值：60 符合條件一的申請人 編號　QA值　QB值 11 200 25 10 139 18 17 132 10 14 99 21 9 83 20 1 67 34 8 66 24 組隊結果：1號，8號
實現上述功能的Python程序如下，請回答下列問題：
m＝20　 #m表示申請人個數
id＝qa＝qb＝[0]*m
n＝0　 #變量n存儲滿足條件一的申請人個數
s＝″″
#讀取全部申請人的編號、QA和QB值，分別存入數組id、qa和qb，代碼略
h＝int(input(″請輸入h的值：″))
n＝m
for i in range(1，m)：
for j in range(m－1，i－1，－1)：
　　 　if ：
　　　　　qa[j]，qa[j－1]＝qa[j－1]，qa[j]
　　　　　qb[j]，qb[j－1]＝qb[j－1]，qb[j]
　　　　　id[j]，id[j－1]＝id[j－1]，id[j]
if qa[j－1]<＝h：
　①________________
　break
print(″符合條件一的申請人″)
print(″編號″，″ QA值″，″QB值″)
for i in range(n)：
print(″%3d%3d%3d″%(id[i]，qa[i]，qb[i]))
maxx＝0
s＝″沒有滿足條件的組合″
#在滿足條件的組合中，尋找QB值之和最大的組合，若有并列，只保留第一個
for i in range(0，n－1)：
j＝i＋1
while ②________________：
if qb[i]＋qb[j]>maxx：
　　　　s＝″組隊結果：″＋str(id[i])＋″號，″＋str(id[j])＋″號″
　　　　③________________
j＋＝1
print(s)
(1)代碼中加框處代碼有錯誤請改正。
加框處的代碼應修改為_________________________________________________；
(2)請在劃線①②③處填入合適的代碼。
劃線①處應填入的代碼是________________________________________________；
劃線②處應填入的代碼是_______________________________________________；
劃線③處應填入的代碼是________________________________________________。
14.(7分)已知某水果店有 n 種水果，編號依次為 0～n－1，每種水果存量若干份。現為每位顧客分配兩份不同種類且該顧客喜歡的水果，為合理分配，每位顧客分別勾選自己喜歡的水果編號，每人至少勾選兩種(包含兩種)以上水果。編寫程序，根據水果存量數據以及顧客勾選數據，輸出水果是否能分配完成。請回答下列問題：
(1)若n為5，分配前每種水果存量數據如圖a所示，顧客勾選數據如圖b所示，則最后水果________(選填：能/不能)完成分配。
(2)實現上述功能的部分 Python 程序如下，請在劃線處填入合適的代碼。
def sort_f(x，y)：
　 for i in range(y)：
　for j in range(①______)：
　　 　　if num[fruit[j]]　　　 　fruit[j]，fruit[j＋1]＝fruit[j＋1]，fruit[j]
　　　return fruit
#讀取每種水果的存量數據，存入字典 num，例如：num＝{0：5，1：4，2：7，3：1，4：3，5：6}，代碼略。
#讀取每位顧客的勾選數據，存入列表 tch，例如：tch＝[[0，3，5]，[1，2]]，代碼略。
fruit＝[0，1，2，3，4，5] #存儲水果編號
fruit＝sort_f(0，len(fruit)－1)
②__________
for k in range(len(tch)):
　 c＝[]；p＝0
　while ③______________：
if fruit[p] in tch[k]:
　　　　num[fruit[p]]－＝1
　　　　c.append(p)
p＋＝1
　if len(c)<2：
flag＝False　　
break
　fruit＝sort_f(c[0]，2)
if flag：
　　　print(″水果能分配完成！″)
else：
　　print(″水果不能分配完成！″)
15.(10分)將十進制數 n(264≥n≥3)轉化為 k(k≥2)進制數，若所有數位全為 1，則稱 k 是 n 的一個好進制數。例如，十進制數 31 可以轉化為(11)30 和(11111)2，因此 30 和 2 均是 31 的好進制數，其中 2 為 31 的最小好進制數。請回答下列問題：
(1)十進制數“21”的最小好進制數 k 是________。
(2)小明編寫程序，找出 n 的最小好進制數 k，請在劃線處填入合適的代碼。
n＝int(input(″輸入一個十進制數： ″))
def check(k，m): #計算 m 位全為 1 的 k 進制的十進制值，如(111)2 的十進制值為 7
　　　ans＝0
　　　for i in range(m)：
　　　　①____________
　　　return ans
ans＝n
for length in range(2，65)：
　②____________
　 j＝n－1
　 while i<＝j：
　 mid＝(i＋j)∥2
　tmp＝check(mid，length)
　if tmp＝＝n：
　　　if ans>mid：
　　　　ans＝mid
　　　　break
　elif ③____________：
　　 　i＝mid＋1
　else：
　　　j＝mid－1
print(n，″的最小好進制數是″，ans)
驗收卷(四)　數據結構與算法
1.A　[棧是限定在一端進行插入和刪除的線性表，而另一端封閉，隊列是限定僅在一端進行插入，在另一端進行刪除的線性表，因此B選項錯誤；數據結構與算法有著密不可分的關系，數據結構的不同選擇會影響算法的運行效率，因此，在設計算法需要考慮選用何種數據結構，故C選項錯誤；鏈式存儲結構不一定優于線性表的線性存儲結構，例如查找時，鏈式存儲結構需要從頭開始找，而線性表可直接通過下標找到，因此D選項錯誤；算法的設計和選擇總是依賴于數據結構，它們兩者是相輔相成的，因此，答案為A。]
2.D　[本題主要考查的是遞歸算法的執行過程。遞歸算法的執行過程分為遞推和回歸兩個階段，因此，答案為D。]
3.A　[A選項函數將調用n次，因此時間復雜度是O(n)。B選項該函數的功能是實現斐波那契數列效果；C選項，fn(5，1，1)的結果是 5；D選項fn(1，1，1)與fn(1，1，2)的返回結果相同，都是 1。]
4.D　[本題考查遞歸和迭代、時間復雜度的計算閱讀程序段 1，可知為遞歸算法實現 10＋9＋…＋1 的和；閱讀程序段 2，可知為迭代算法實現 1＋2＋…＋10。因此兩段程序輸出結果相同，A 錯誤；程序段 2 為迭代算法，B 錯誤；程序段 2 中只有一層循環，時間復雜度為 O(n)，C 錯誤；修改程序段 1 代碼，僅僅多遞歸一層函數，但是返回值＋0 并不會影響輸出結果，D 正確。]
5.D　[選項A、B中程序段的時間復雜度均為O(n2)，因此，AB選項錯誤；選項C中程序段的時間復雜度均為O(log2n)，因此C選項錯誤；選項D中程序段，外循環的時間復雜度均為O(log2n)，內循環的執行次數為20＋21＋…＋2k(k＝log2n)，根據等比數據求和公式，其和為n－1，即時間復雜度為O(n)，因此答案為D。]
6.C　[本題主要考查的是遞歸算法。n＝6，ans＝6*5*4*f(3)，而f(3)＝3＋2＋f(1)，已知f(1)＝2，因此ans＝840，故答案為C。]
7.D　[冒泡的方向可以從前往后排序，后面的數據先有序；也可以從后往前排序，前面的數據先有序。第一遍排序后的結果把最小的數排到了最前面，因此可以推斷是升序排列。]
8.A　[本題考查冒泡排序算法的相關知識。由第一輪數據“2，8，6，3，5，7，9”可知，采用冒泡排序對數據進行升序排序，但有兩種可能，一種是從后往前的冒泡升序，則第二輪排序后的數據為“2，3，8，6，5，7，9”，交換2次，另一種是從前往后的冒泡升序，則第二輪排序后的數據為“2，6，3，5，7，8，9”，交換4次。]
9.A　[本題考查冒泡排序的算法思想。從前往后冒泡實現升序排列，共排了m－1趟。]
10.C　[本題考查冒泡排序算法思想。分析冒泡排序內循環的代碼，是從左(前)向右(后)冒泡、降序。外循環只進行了5次，所以只有最后5個數(s[5]到 s[9])是有序的。]
11.A　[n的值為查找次數，7查找次數為2，其余查找次數是4。]
12.D　[查找一個0－18之間的隨機偶數key，畫出相應的二叉樹。A選項查找0，向左查找4次，f的值為－4。B選項向右查找1次，找到的數為3，不是偶數。C選項a[1]的值為3，不是偶數。D選項ans的值若為3，a[3]的值為8，而找到的第1個8的索引位置是4。]
13.(1)qa[j]>h and qa[j]>qa[j－1] 或qa[j]>qa[j－1]
(2)①n＝i－1　②j<＝n－1 and abs(qa[i]－qa[j])j<＝n－1 and qa[i]－qa[j]解析　本題主要考查的是冒泡排序算法及其綜合應用。(1)程序首先使用冒泡排序算法找出所有符合條件一的申請人，根據程序運行窗口可知數據是按QA值降序排序的，并將滿足條件一的人數記錄在變量n中。排序方式有兩種，只將符合條件一的申請人進行降序排序，即加框處語句修改為qa[j]>h and qa[j]>qa[j－1]，將所有申請人進行降序排序，即加框處語句修改為qa[j]>qa[j－1]；(2)如果申請人不滿足條件一，則排序可以提前結束，滿足條件人數為i－1人，因此，程序劃線①處代碼為n＝i－1；劃線②處所在的循環語句的功能是使用枚舉所有滿足條件一、條件二的申請人進行組隊，記錄組隊人QB值之和為最大的2個人，因此，②處代碼為j<＝n－1 and abs(qa[i]－qa[j])14.(1)能　(2)①x，len(fruit)－i－1　②flag＝True　③len(c)<2 and num[fruit[p]]>0
解析　(1)由于每位顧客分配兩種水果，因此只勾選兩種水果的顧客只分配給他們勾選的水果，剩余勾選2種以上的顧客，從剩余水果中選取還有存量的水果分配給他們。“1，2”“1，3”分配好后，剩余“5，2，6，0，3”，此時還有“0，3，4”“1，3，4”需從中選取分配，3號水果存量為0，不作考慮，0，1，4號水果存量均大于等于2，足夠分配。因此能完成分配。
(2)分配時，按照水果存量情況降序排列，將列表fruit中水果編號按水果存量降序排列。枚舉每位顧客勾選數據，從列表fruit中從左往右，依次選取水果存量大的檢測是否為該顧客喜歡水果，如果是則將此水果分配給該顧客，一共選取兩種水果，用列表c存儲分配的水果編號的索引。該顧客分配完成后，利用列表c存儲的第一種水果編號索引作為再排序的起始位置，因為0～c[0]－1范圍內的水果存量未變，只要對列表c中兩個水果存量進行再排序，fruit按照最新存量進行降序排列，排2次即可。如果在分配過程中該顧客喜歡的水果無法分配兩份，則分配失敗。
15.(1)4　(2)①ans＝ans*k＋1 或 ans＝ans＋k**i 或 ans＝ans＋k**(m－i－1)　②i＝2　③tmp解析　本題考查進制轉換、對分查找等相關知識。(1)21＝16＋4＋1＝(111)4，故最小的好進制數是4。①空實現 k 進制、m 位 1 轉換為十進制數的過程，此處可采用累乘相加，即 ans＝ans*k＋1或 ans＝ans＋k**(m－i－1)等。②處填 i 的初始值。已知函數 check 的第 1 個參數為進制，第 2 個參數為 1 的位數，結合 tmp＝check(mid，length)這一句，可知 mid 為進制。本題的進制最小值為 2，進制最大值為 n－1(例如 64＝63＋1＝(11)63)。③外循環枚舉所有可能的位數，循環中采用對分法測試結果，即先找到進制的中位數 mid，計算 mid 進制下，length 位個 1 轉換為十進制數的 tmp。若 tmp＝＝n，則保留 mid 的最小值，進入下一輪大循環，查找更長的位數(位數越長意味著進制越小)。若 tmp

展開更多......

收起↑