資源簡介

第七單元　數據結構與算法
信息技術(50分)
一、選擇題(本大題共12小題，每小題2分，共24分。每小題列出的四個備選項中只有一個是符合題目要求的，不選、多選、錯選均不得分)
1.定義如下遞歸函數：
def f(a，n)：
n＝n－1
if n＝＝0：
return a
else：
return f(a－1，n)＋f(a＋1，n)
print(f(5，3))
程序運行后﹐輸出的結果是(　　)
A.10 B.20
C.30 D.40
2.定義如下函數：
def f(s)：
if len(s)＝＝1：
return s[0]
elif len(s)＝＝2：
return s[0]＋s[1]
else：
return f(s[0：len(s)//3])＋f(s[len(s)//3：len(s)])
執行語句s＝f([1，2，3，4，5，6])，函數f被調用的次數是(　　)
A.3 B.5
C.7 D.15
3.定義如下函數：
def jc (n)：
if n＝＝l：　#①
return n
return n*jc(n－1)　#②
執行語句x＝jc(5)，下列說法正確的是(　　)
A.x的計算結果為120
B.程序執行完畢，①處代碼共執行1次
C.程序執行完畢，②處代碼共執行5次
D.如果①處代碼改成n<2，程序將無法正常執行
4.有如下Python程序段：
def f(s)：
if len(s)＝＝1：
return True
elif len(s)＝＝2：
return s[0]＝＝s[1]
elif s[0]＝＝s[－1]：
return f(s[1：－1])
else：
return False
print(f(″1234321″))
執行該程序段后，下列說法正確的是(　　)
A.輸出結果為False
B.函數f運用了迭代算法
C.函數f的調用次數為4
D.函數f的時間夏雜度為O(n2)
5.采用冒泡排序算法對數據序列“8，7，2，3，9，6，5”完成升序排序，排序2趟后，正確的順序是(　　)
A.2，3，8，7，5，6，9 B.2，3，8，7，9，6，5
C.2，3，5，6，7，8，9 D.2，3，7，5，6，8，9
6.采用冒泡排序算法對數據序列“2，3，4，5，1，0”完成升序排序，則需要交換的次數為(　　)
A.9次 B.12次 C.15次 D.18次
7.下列代碼采用冒泡排序對a列表中的n個數據升序排序，則①②兩處不可用的選項是(　　)
for i in range(①________)：
for j in range(②________)：
if a[j] 　　　 　a[i]，a[j－1]＝a[j－1]，a[j]
A.①1，n 　　 ②n－1，i－1，－1
B.①n，1，－1 　　 ②1，i－1
C.①1，n 　　 ②1，n－i＋1
D.①0，n－1 　　 ②n－1，i－1
8.有如下Python程序段：
s＝″ccbbac″
a＝[i for i in range(6)]
for i in range(5)：
for j in range(5－i)：
if s[a[j]]>s[a[j＋1]]：
　 　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
運行該程序段輸出的結果為(　　)
A.[4，3，2，5，1，0] B.[4，5，3，2，1，0]
C.[4，2，3，0，1，5] D.[4，3，2，5，0，1]
9.某排序算法的Python程序段如下：
'讀取n個整數，依次存入a[1]到a[n]中，代碼略
for i in range(1，n－1)：
for j in range(n，i＋1，－1)：
if a[j]>a[j－1]：
　　 　　a[j]，a[j]＝a[j－1]，a[j－1]
執行上述程序段，下列說法正確的是
A.交換過位置的數據，可能會再回到其初始位置
B.執行完成后，數組元素a[1]到a[n]從小到大排列
C.若n為6，整個排序過程總的比較次數是30
D.整個排序過程總的交換次數至少為1
10.某對分查找算法的Python程序段如下：
key＝int(input(″請輸入待查數據值：″))
d＝[17，18，20，23，24，25，28，32，34，35]
f＝False；s＝″″
i＝0；j＝len(d)－1
while i<＝j：
m＝(i＋j)//2
s＝s＋″，″＋str(d[m])
if d[m]＝＝key：
f＝True
break
if keyj＝m－1
else：
i＝m＋1
print(s)
輸入待查數據值為23，執行該程序段，則輸出的結果是(　　)
A.25，20，24，23 B.24，18，20，23
C.25，20，23 D.24，20，23
11.有如下Python程序段：
key＝int(input(″請輸入任意一個整數：″))
a＝[12，18，22，27，36，45]
ans＝0
i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j＋1)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
ans＋＝a[m]
print(ans)
執行以上程序段，輸入任意的key值，則ans的值不可能是(　　)
A.45 B.57
C.67 D.72
12.有如下對分查找程序，a為按非降序排序的整型數組；
import random
key＝random.randint(0，4)*2＋20
a＝[12，14，15，15，19，x，20，24，y，26]
c＝0
i＝0；j＝len(a)－1
while i<＝j：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
c＋＝1
測試所有可能的key值，程序執行后c均等于4，下列正確的x，y值可以為(　　)
A.19，25 B.20，26
C.20，25 D.20，24
二、非選擇題(本大題共3小題，其中第13小題7分，第14小題10分，第15小題9分，共26分)
13.小T編寫了一個Python程序功能如下：輸入需隨機生成的坐標點數量，經過程序執行后，自動生成并顯示相應數量的途經點坐標(坐標值為大于等于1小于10的實數，四舍五入保留一位小數)，試圖求出平面坐標系中一端(最左和最右的點稱為端)出發，按照一定的規則途經所有點到達另一端的路徑長度(四舍五入保留一位小數)。程序執行界面如圖所示。
(1)實現上述功能的Python程序如下，將劃橫線部分的代碼補充完整。
from random import*
from math import*
data＝[[0，0] for i in range(100)]
k＝int(input(″請輸入點的個數″))　#產生k個點的隨機坐標
for i in range(k)：
data[i][0]＝randint(0，90)/10＋1
data[i][1]＝randint(0，90)/10＋1
print('x：'，data[i][0]，' y：'，data[i][1])
flag＝False ; i＝0
while i<＝k－2 and not flag：
flag＝True
j＝0
while ①________：
if data[j][0]*100＋data[j][1]>data[j＋1][0]*100＋data[j＋1][1]：
　　 　　data[j]，data[j＋1]＝data[j＋1]，data[j]
　　　 　flag＝False
j＋＝1
②________
s＝0；length＝0
for i in range(k－1)：
x1＝③________　#y1的計算方式同x1，代碼略
length＝sqrt(x1＋y1)
s＋＝length
print(″路徑長度是：″，④________)
(2)由程序看，訪問坐標系中所有點的規則是________(單選，填字母：A.左上到右下/B.左下到右上/C.右下到左上/D.右上到左下)。　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
14.某工廠收到了n個產品的訂單，這n個產品分別在A、B兩個車間加工，并且必須先在A車間加工后才可以送到B車間加工。為了使得總加工時間最短，我們可以將這n個產品分為兩類，第一類在A車間加工時長少于在B車間加工時長，第二類在A車間加工時長不少于在B車間加工時長。第一類應將在A車間花費時間少的產品排在前面，第二類應將在B車間花費時間少的產品排在后面，然后先處理所有第一類產品，再處理第二類產品。可以證明，這樣排序后所有產品加工完成花費的總時間最少。例如有4種產品，它們在A車間加工時長分別為3、5、8、4，在B車間加工時長分別為6、1、2、7，產品分類、排序、合并、計算時長的過程如第15題圖所示，最后得出總時長為21。(每個產品在B車間開始加工需同時滿足它在A車間加工完并且B車間已加工完上一個產品這兩個條件)。
編寫程序模擬工廠對這n個產品的處理過程，計算總加工時間。請回答下列問題：
(1)由題意可知，若3種產品在A車間加工時長分別為5、7、3，B車間加工時長分別為6、1、2，則總加工時長為________。
(2)小華先編寫了如下將第一類產品排序的函數：
def sort1(a，b)：　#參數a、b的元素分別表示每個產品在A、B車間的加工時長。
n＝len(a)
for i in range(n－1)：
for j in________：
　　　　 if a[j]>a[j＋1]：
　　　　 　　a[j]，a[j＋1]＝a[j＋1]，a[j]
　　　　 　　b[j]，b[j＋1]＝b[j＋1]，b[j]
劃線處可以填寫的代碼有________(多選，填字母。全部選對的得2分，選對但不全的得1分，不選或有選錯的得0分)
A.range(n－1－i) B.range(n－1，i，－1)
C.range(i，n－1) D.range(n－2，i－1，－1)
(3)小強編寫了如下將第二類產品排序的函數：
def sort2(a，b)：　#參數a、b的元素分別表示每個產品在A、B車間的加工時長。
n＝len(a)
for i in range(1，n)：
k1，k2＝a[i]，b[i]
j＝i－1
while________：
　 　　　a[j＋1]，b[j＋1]＝a[j]，b[j]
　 　　　j－＝1
　　　　a[j＋1]，b[j＋1]＝k1，k2
①請在劃線處填入合適的代碼。
②此程序時間復雜度為________。(單選，填字母)
A.O(1) B.O(n)
C.O(n2) D.O(nlog2n)
(4)小張結合前兩位同學的程序，計算產品加工總時長。請在劃線處填入合適的代碼。
'''
讀取n個產品在A、B兩車間加工的時間，根據題目要求分為兩類，第一類產品在A、B兩車間加工的時間分別存儲在列表a1和列表b1中，并通過sort1()函數排序，第二類產品在A、B兩車間加工的時間分別存儲在列表a2和列表b2中，并通過sort2()函數排序，代碼略
'''
a＝a1＋a2
b＝b1＋b2
n＝len(a)
k，t＝0，0　#k為A加工時間，t為B加工時間
for i in range(n)：
k＋＝a[i]
if ①________：
t＝k
②________
print(″總加工時長最短為：″，t)
15.進入新學期第一天，班主任老師將班上N個同學(學號為1－N)排成一排，分配座位。從排隊到分配座位步驟如下：
步驟一：先將1號同學安排進隊；
步驟二：2～N號同學由老師依次指定入隊位置，如學號為i的同學由老師指定站在隊中某位同學的左側或右側；
步驟三：所有同學按照上述方法入隊完畢后，2人一組的方式依次分配到四個組別中；步驟四：輸出每組學生的名單。
請回答下列問題。
(1)若某班有4位同學，學號為1～4，完成步驟一后，執行步驟二的指令3次，每次指令包含兩個整數k和p(p為0或1)。若p為0，則表示插在k號同學的左側，p為1則表示插在k號同學的右側。若三條指令分別為10、21、10，則執行指令后隊伍從左到右學號分別為：________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def insert(k，x)：
R[x]＝R[k]
L[x]＝k
①________
R[k]＝x
L＝[0]*100；R＝[0]*100
insert(0，1)　#0的右邊插入1號同學
#info列表存儲各學生姓名和學號，格式如[[″張三″，1]，[″李四″，2]…]，代碼略
n＝len(info)
for i in range(2，n＋1)：
k＝int(input(″請問插入在幾號同學旁邊？″))
p＝int(input(″請輸入該同學的左側還是右側″))
if p＝＝0：
②________
else：
insert(k，i)
q＝[[]for i in range(4)]
i＝m＝0
③________
while x！＝0：
q[i].append(x)
m＝m＋1
if m%2＝＝0：
④________
x＝R[x]
for i in range(4)：
for j in q[i]：
print(info[j－1][0]，end＝″ ″)
print()
第七單元　數據結構與算法
1.B　[f(5，3)＝f(4，2)＋f(6，2)＝f(3，1)＋f(5，1)＋f(5，1)＋f(7，1)＝20。]
2.C　[s的長度為6，f(s)返回f([1，2])＋f([[3，4，5，6]])，調用2次，函數f([1，2])值為3，調用1次。f([[3，4，5，6]])返回f([[3，4])＋f([[5，6]])，調用2次。f([[3，4])和f([[5，6]])各調用1次，共調用7次。]
3.A　[本題考查遞歸的應用。該程序實現計算n的階乘。A選項jc(5)＝5*4*3*2*1＝120。B選項函數調用5次，該語句執行5次。C選項執行4次。D選項n<2和n＝＝1是等效的。]
4.C　[本題考查函數遞歸的分析和理解。該程序段的功能是利用遞歸判斷一個字符串是否是“回文串”。A選項″1234321″是回文串。B選項該函數內部調用了自身，是遞歸算法。C選項f(″1234321″)→f(″23432″)→f(″343″)→f(″4″)→True，調用4次。D選項程序內部只調用本身一次，算法復雜度是O(n)。]
5.A　[本題考查冒泡排序的算法思想。從后往前依次比較相鄰兩個位置數據的大小，并把較小數據換到前一位置。排序結果為2，3，8，7，5，6，9。從前往后冒泡的結果為2，3，7，6，5，8，9。]
6.A　[本題考查教材上的冒泡排序算法基本原理。第一趟交換5次，序列為“0，2，3，4，5，1，”。第二趟交換4次，序列為“0，1，2，3，4，5”。至此數據已經有序，無需交換。共交換9次。所以答案為A。]
7.B　[本題考查冒泡排序的算法思想。當i＝n時，j in range(1，n－1)，當j為最后一個值n－2時(range右邊為開區間，n－1取不到)，a[n－2]與a[n－3]比較大小，缺少a[n－1]與a[n－2]比較大小，不能完成所有n個數據的升序排序。]
8.C　[本題考查索引排序。數組a存儲的0～5的索引位置，程序實現從前往后冒泡，當條件s[a[j]]>s[a[j＋1]]成立時交換，實現升序排列，因此排序后的結果是abbccc，找到這些字母的索引位置。]
9.A　[本題考查冒泡排序算法思想。算法實現從左往右降序排列。A選項例如某個數后面有2個數，且一個數大他小，一個數比他大，當大的數往前交換后，第2次比他小的數又把換回來了。總的比較次數為n*(n－1)/2＝15。D選項如果原數據已經有序了，不會發生交換。]
10.B　[本題考查對分查找。根據對分查找的特點、中點位置取值(i＋j)//2是偏左的，最后輸出的應該24、18、20、23。]
11.A　[本題考查二分查找，找到后不退出，直到i>j為止后退出，ans記錄的是查找過程中所訪問到的數之和。]
12.D　[c表示查找次，查找到結果后并沒有結束循環，畫出如圖所示二叉樹，x的值介于20和24之間，但要查找4次，x的值必定為20。y的值介于24和26之間，但要查找4次，y的的值不能為26。由于查找的key是偶數，若y的值為25，須查找5次。]
13.(1)①j<＝k－i－2或者j解析　本題考查冒泡算法。(1)本程序實現從前往后冒泡，后面的數據先有序，flag表示某趟排序是否有數據交換的標志，若有沒有數據交換，提前結束排序。①坐標值為大于等于1小于10的實數，將x的坐標*100，意味著擴大x坐標的權重，即x是主關鍵字，若產生兩個x相等，那么再加上y坐標。從前往后冒泡，每次是i的對稱位置k－i－1有序，由于比較對象為j和j＋1，因此內循環的終點為k－i－2。②外循環i每次加1。③k個點，只有k－1條線段，因此循環k－1次。每次利用兩點距離公式進行求線段長度。④四舍五入保留一位小數顯示路徑長度。(2)以x為主關鍵字升序，y為次關鍵字升序，因此是從左下向右上形成路徑。
14.(1)16　(2)AD　(3)①j>＝0 and k2>b[j]　②C (4)①t解析　本題考查排序相關概念及算法時間復雜度。(1)根據劃分標準將3種產品分別編號為①②③，加工順序為①③②，加工時間段為：產品①0－5，5－11；產品③5－8，11－13；產品②8－15，15－16，總加工時長為16。(2)內循環表示掃描方向，若從左向右排序，比較對象為a[j]和a[j＋1]，左端點固定為0，第i趟排序右端點為n－1－i，當j＋1達到n－1－i時，j的值為n－2－i，由于該位置取不到，因此range值為(0，n－1－i)。若從右向左排序，右端點(j＋1的值)固定為n－1，左端點為i，因此range值為(n－2，i－1，－1)。(3)①對第二類產品按在B車間的加工時長做插入排序。內層循環尋找插入位置，將比k2小的元素依次右移一位，關注j的邊界不能小于0，此時j＋1處即為插入位置，對b[j＋1]賦值為k2。②插入排序的時間復雜度為O(n^2)。(4)計算總加工時長，累加產品時長，k為A加工時間，t為B加工時間；根據輸出最后的結果為t即為總時長，如果當前產品A車間加工的時長大于B車間加工時長，那當前產品進入B車間開始加工的時間即t＝k，故①處為t15.(1)2341　(2)①L[R[k]]＝x　②insert(L[k]，i)　③x＝R[0]　④i＝(i＋1)%4
解析　本題考查索引數組和雙向鏈表的知識。(1)在1左側插入2，隊伍為21，在2的右側插入3為231，在1的左側插入4，隊伍為2314。(2)①在學號k的右側插入x，則x的左側是k，右側是原k的右側，同時要修改k的右側指向。②insert程序的功能是在k的右側插入x，那么現在在x的左側插入意味著在k的前一個數L[k]的右側插入x。③由于0沒有存放學號，但他的右側是第1個學號，因此當前節點從R[x]開始遍歷各個元素。④i表示組別，共有4組，其值從0，1，2，3循環變化。

展開更多......

收起↑