資源簡介

第五單元　數據存儲
信息技術(50分)
一、選擇題(本大題共10小題，每小題2分，共20分。每小題列出的四個備選項中只有一個是符合題目要求的，不選、多選、錯選均不得分)
1.有如下Python程序代碼
num＝[0]*10
n＝36；s＝0
for i in range(n)：
j＝9
num[j]＋＝1
while num[j]＝＝2：
num[j]＝0
j－＝1
num[j]＋＝1
for i in range(10)：
s＋＝num[i]
print(s)
執行此代碼后，變量s的值為(　　)
A.2 B.3
C.4 D.5
2.閱讀以下程序段：
a＝[]
n＝int(input(″請輸入一個整數：″))
k＝n
while n>0：
a.append(n%10)
n＝n//10
s＝0
for i in range(len(a))：
s＋＝a[i]**(len(a))
if k＝＝s：
print(″YES″)
else：
print(″NO″)
運行程序，如果程序要輸出YES，則輸入的數字可能是(　　)
A.21 B.90
C.153 D.400
3.下列關于數據結構說法，不正確的是(　　)
A.隊列和棧都是操作受限的線性表
B.計算機中一般會采用樹形結構來管理文件
C.鏈表中數據元素的邏輯順序是通過鏈表中指針指向實現的
D.同一個數組中的元素的數據類型可以不同
4.下列關于數據結構的說法，正確的是(　　)
A.用程序實現問題解決時只能采用一種數據結構
B.數據的邏輯結構是指數據元素間的關系
C.鏈表比數組更適合大量數據元素的隨機訪問
D.數組不必占用一片連續存儲的單元
5.有如下Python程序段：
a＝[[0 for i in range(3)]for j in range(3)]
for i in range(3)：
for j in range(3)：
a[i][j]＝i*5＋j＋1
for i in range(1，3)：
　 for j in range(2)：
　 print(a[j][i]，end＝″ ″)
程序段執行后，輸出的結果是(　　)
A.2 3 7 8 B.7 12 8 13
C.2 7 3 8 D.6 7 11 12
6.有如下程序段，輸入列表a的值保證至少有一個是非負整數。
#輸入列表a
t＝0；ans＝0
n＝len(a)
for i in range(n)：
t＋＝a[i]
if t<0：
t＝0
if t>ans：
ans＝t
print(ans)
當列表a的值為[3，－1，2，－5，3，4，－1，2]時，程序輸出的結果為(　　)
A.3 B.7
C.8 D.14
7.有如下Python程序段：
from random import randint
a＝[randint(1，10) for i in range(5)]
for i in range(1，5)：
key＝randint(3，6)*2
j＝i－1
while j >＝0 and key a[j＋1]＝a[j]
j－＝1
a[j＋1]＝key
執行該程序段后，列表a的值不可能是(　　)
A.[3，6，8，10，12] B.[1，5，8，9，12]
C.[6，10，10，12，12] D.[8，9，10，10，12]
8.已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如圖所示，下列操作需要遍歷多個節點的是(　　)
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
9.有如下Python程序段：
a＝[[7，3]，[5，0]，[2，1]，[9，－1]]
head＝2
key＝int(input(″輸入一個數字″))
p＝q＝head
while p！＝－1 and a[p][0]q＝p
p＝a[p][1]
if p＝＝head：
a.append([key，head])
head＝len(a)－1
else：
a.append([key，p])
a[q][1]＝len(a)－1
print(a[－1])
程序段運行后，若輸入2，則輸出的結果是(　　)
A.[2，－1] B.[2，1]
C.[2，2] D.[2，3]
10.采用Python二維列表模擬鏈表，a＝[[″A″，1]，[″B″，2]，[″C″，3]，[″D″，4]，[″E″，5]，[″F″，－1]]。表示鏈表為：A→B→C→D→E→F。有以下Python程序：
head＝0；p＝a[head][1]
a[head][1]＝－1
while p?。剑?：
p＝a[p][1]
if p＝＝－1：
break
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
執行以上程序后，以head為首的鏈表結構為(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
二、非選擇題(本大題共4小題，共30分)
11.數組a存儲降序排序的m個數據，數組b存儲升序排列的n個數據，兩個數組中存儲的數據為[1，20]范圍的不重復的隨機數?，F將兩個數組的數據合并到c數組中，使c數組的數據為左右交替上升。
a[0] a[1] a[2] a[3] a[4]
19 17 6 4 3
b[0] b[1] b[2] b[3] b[4] b[5]
5 7 8 13 15 20
c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] c[10]
3 5 7 13 17 20 19 15 8 6 4
a＝[19，17，6，4，3]
b＝[5，7，8，13，15，20]
m＝len(a)；n＝len(b)
c＝[－1]*(m＋n)
pa＝m－1；pb＝0；pc＝0；
k＝1
while ①________：
if pa＝＝－1 or a[pa]>b[pb]：
s＝b[pb]
pb＋＝1
elif pb＝＝n or a[pa]s＝a[pa]
②________
c[pc]＝s
k＝1－k
print(c)
(1)若數組a為14，9，5，3，數組b為1，2，7，15，20，則數組c為________。
(2)請在劃線處填入合適的代碼。
(3)加框處代碼有錯，請改正。
12.編寫Python程序，功能是根據A城和B城同一時間段內的溫度數據，計算兩城溫差(A城溫度－B城溫度)。A城數據和B城數據分別為包含若干個記錄的序列，其中，A城每個記錄包含溫度及其截止時間，B城每個記錄包含溫度及其持續時長。兩城溫差計算結果表示為若干個記錄的序列，每個記錄包含溫差及其持續時長。持續時長是指同一溫度(或溫差)保持不變的最大時長。示例見下表。
表中，A城數據有4個記錄，其中第1個記錄為(溫度30，截止時間2)，第2個記錄為(溫度33，截止時間4)，這表明從開始到第2小時的溫度都是30，此后到第4小時的溫度都是33。B城數據有4個記錄，其中第3個記錄為(溫度21，持續時長2)，這表明第5、第6這2個小時的溫度都是21。兩城溫差計算結果的第4個記錄為(溫差10，持續時長3)，這表明第5、第6、第7這3個小時的溫差都是10。
程序運行的結果如圖所示：
城市A各時間段的溫度：30 31 32 城市A溫度截止時間：4 6 7 城市B各時間段的溫度：20 22 21 22 城市B溫度截止時間：3 4 6 7 城市各時間段的溫差：10 8 10 城市溫差的持續時間：3 1 3
(1)若將示例中A城數據修改為3個記錄，依次是(溫度30，截止時間4)、(溫度31，截止時間6)、(溫度32，截止時間7)，B城數據不變，則兩城溫差計算結果中第1個記錄為(溫差10，持續時長________)(填數值)。
(2)實現上述功能的代碼如下，請在劃線處填入合適的代碼。
#讀取兩個城市各階段的溫度，分別存儲在數組ha和hb中
#讀取城市A的截止時間存儲到數組ta中，讀取城市B的持續時長存儲到數組tb中
na＝3；nb＝4
for i in range(1，nb)：　#將B 城第i 個記錄中的持續時長轉換為截止時間
①________
print(tb)
i＝0；j＝0；n＝0；p0＝0
h＝[0]*30；t＝[0]*30
while idiff＝ha[i]－hb[j]
p1＝ta[i]
if ②________：
i＋＝1
if p1>＝tb[j]：
p1＝tb[j]
j＋＝1
if n＝＝0 or diff！＝h[n－1]：
h[n]＝diff
t[n]＝p1－p0
n＋＝1
else：
③________
p0＝p1
#輸出溫度差及持續時長，代碼略。
13.鏈表的插入排序。數據保存在鏈表da中，對da中數據采用插入排序方法，進行非降序排列。算法描述如下：
1)從頭節點的下一個節點開始，往前找到合適的位置，將該節點插入到相應位置，重復以上操作，使得全部節點中的數據有序。
2)每個節點的插入方法：如果當前節點的值比頭節點小，將該節點插入到頭節點前面，成為新的頭節點，當前節點的前驅指針指向后繼節點，前驅指針不變。如果當前節點值大于等于頭節點值，從頭節點開始不斷向后遍歷，當遍歷節點的值大于當前節點的值或遍歷的指針指向當前節點，停止遍歷，若遍歷到當前節點，說明當前節點的位置不需要移動，移到當前指針時，其對應的前驅指針也要同步移動。如果要插入到前面的某個位置時，當前指針移動，但前驅指針并沒有移動。
注意要點：①當前節點cur的前驅節點位置什么時候變化？什么時候不變？②為什么需要用變量tcur保存cur的后繼位置da[cur][1]。
(1)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
(2)程序中加框處代碼有錯，請改正。
#產生并輸出一個鏈表da，代碼略。
ha＝0
cur＝da[ha][1]
qc＝ha
while ：
①________
if da[cur][0]da[qc][1]＝da[cur][1]
da[cur][1]＝ha
ha＝cur
else：
q＝ha
while q！＝cur and da[q][0]<＝da[cur][0]：
　　　　 ②________
　　　 　q＝da[q][1]
if q?。絚ur：
　　　 　da[qc][1]＝da[cur][1]
　　　 　da[qh][1]＝cur
　　　 　da[cur][1]＝q
else：
　　　 ?、踎_______
cur＝tcur
14.某醫院每天提前發放100個預約號，考慮到老年人身體原因，預約病人按照以下規則進行就診：
①老年人(年齡>＝60歲)比非老年人優先就診。
②老年人按年齡從大到小的順序就診，年齡相同的按預約順序就診。
③非老年人按預約順序就診。
小王根據以上規則編寫了一個Python程序，程序運行時，實時讀取病人預約數據，并根據以上規則，實時調整并顯示當前診順序，程序運行界面如圖所示。
請輸入病人的信息：40 當前就診順序為：40 請輸入病人的信息：15 當前就診順序為：40 15 請輸入病人的信息：67 當前就診順序為：67 40 15 請輸入病人的信息：75 當前就診順序為：75 67 40 15 請輸入病人的信息：30 當前就診順序為：75 67 40 15 30
(1)如圖所示，若當前就診順序為“75 67 40 15 30”，下一位預約病人年齡為60，則就診順序變為________。
(2)實現上述功能的代碼如下，請在劃線處填入合適的代碼。
#遍歷鏈表data，頭指針為head
def visit(data，head)：
cur＝head
while cur ?。剑?：
print(data[cur][0]，end＝″ ″)
cur＝data[cur][1]
print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分別表示鏈表頭節點和尾節點所在位置
for i in range(100)：
#為了簡潔，本程序只輸入、存儲病人的年齡信息
age＝int(input(″請輸入病人的信息：″))
cur＝head
if age >＝60：
while cur?。剑? and data[cur][0]>＝age: #查找第一個數據域小于age的節點
　　　 　pre＝cur
　　　 ?、賍_______
if cur＝＝head：　#在頭節點插入新節點
　　　 　data.append([age，cur])
　　 　　head＝len(data) － 1
else：　#在鏈表中間插入新節點
　　　 　data.append([age，cur])
　　　 　②________
if cur＝＝－1：　#更新尾指針位置
　　　 　tail＝len(data) － 1
else：　#直接插在鏈表尾節點后
data.append([age，－1])
if head＝＝－1：　#添加第一個節點
　　　 　head＝tail＝0
else：
　　　 ?、踎_______
　　　　 tail＝len(data) － 1
print(″當前就診順序為：″)
visit(data，head)
第五單元　數據存儲
1.A　[本題考查數制轉換的程序實現。每次在最后一位(num[9])加1，且num[j]＝＝2時，該位變0，高位進一。該程序的功能是將36轉換成二進制，并統計二進制數上每個的和。]
2.C　[本題考查累加求和。程序的功能是各個位數字的3次方和為他本身。3^3＋5^3＋1^2＝27＋125＋1＝153。]
3.D　[本題考查數據結構基本知識。A選項隊列、棧只能在一端或兩端操作的線性表。B選項計算機中采用樹形結構來管理文件。C選項鏈表由數據域和指針域組成，指針域存儲下一個節點的位置。D選項同一數組中元素的數據類型相同。]
4.B　[本題考查數據結構。A選項程序實現可以采用多種數據結構。B選項數據的邏輯結構指的是數據元素間的關系。C選項數組比鏈表訪問高效，鏈表增加和刪除比數組高效。D選項數組采用的是線性存儲，需要劃出連續的存儲空間。]
5.C　[本題主要考查二維數組。創建一個3行3列值全為0的二維數組a。第1次嵌套for循環執行完，列表a的值為[[1，2，3]，[6，7，8]，[11，12，13]]，依次輸出2，7，3，8。]
6.C　[本題考查枚舉算法。遍歷數組a，將數組中數據進行累加，若累加和小于0，t的值為0，否則找到累加和最大的一段為3＋4－1＋2＝8。]
7.B　[本題考查排序算法和隨機數函數。首先列表a中的初始值是[1，10]內的5個隨機數。key的取值只能是6、8、10、12。while循環會將key插入列表a的合適位置上，使得列表a的值非降序排列，因此選項A、C、D都是有可能的。]
8.A　[本題考查鏈表節點的插入和刪除。若刪除鏈表的頭節點，只需移動頭指針。若在鏈表尾節點后插入一個新節點，只要將尾節點指向新增節點，新增節點為新的尾節點。若要刪除最后一個節點，需修改尾節點前驅的指針區域值，因此需遍歷多個節點。]
9.C　[本題考查鏈表的相關知識。先建立了一個升序鏈表，接下來從head開始，查找key插入的位置。若key>a[p][0]則繼續向后找。本題key＝2，一開始就不滿足循環條件，2應插到鏈表頭部。首先向列表中追加key，并將指針指向head，同時調整head指針位置，故a[－1][0]＝2，指針a[－1][1]＝2。]
10.A　[本題代碼通過迭代和逆轉，實現只提取奇數位的鏈表元素，并逆序輸出。]
11.(1)1，3，7，14，20，15，9，5，2　(2)①pa>＝0 or pb②pa－＝1　(3)pc＝m＋n－pc－k
解析　本題考查雙指針的基本操作。(1)按左右遞增的順序填充數組c。(2)①pa指向數組a的最后位置，pb指向數組b的開始位置，均指向每個數組的最小位置，兩個數組中只要有一個指針沒有超范圍時，就要繼續歸并。②語句s＝a[pa]指將a數組的數據歸并到c，因此pa向前移動。(3)當pc為0，k為1，下一位置在pc的對稱位置，即m＋n－1－pc。接下來k為0，下一位置在pc前面一個數據(pc－1)的對稱位置，m＋n－1－(pc－1)，綜合可得pc＝m＋n－pc－k。
12.(1)3　(2)①tb[i]＝tb[i]＋tb[i－1]?、趖a[i]<＝tb[j]
③t[n－1]＝t[n－1]＋p1－p0
解析　本題考查前綴和、枚舉算法。
時間 第1 小時 第2 小時 第3 小時 第4 小時 第5 小時 第6 小時 第7 小時
A城溫度 30 30 30 30 31 31 32
A城 數據 溫度 30 31 32
截止時間 4 6 7
B城溫度 20 20 20 22 21 21 22
B城 數據 溫度 20 22 21 22
持續時長 3 1 2 1
計算 結果 溫差 10 8 10
持續時長 3 1 3
(1)根據上面的圖表，明顯可以看出第一個記錄為10的時候是第3小時結束時，即持續時長為3小時。(2)本題考查求最長相同子序列及其個數，涉及數組概念。①求當前記錄的截止時間，只要將前一個記錄的持續時長tb[i－1]加上當前記錄的持續時長tb[i])即可。②A城和B城比較時，取截止時間小的賦值給p1，再判斷記錄是否判斷完畢，如果完畢取下一個記錄。A城第一個記錄溫度為30，截止時間為2，而B城第一個記錄溫度為20，截止時間為3，取他們公共部分溫差為10的，截止時間只能到2，因此需要將p1設置為小的那個截止時間。這樣A城的第一記錄已經用完，所以需要i＝i＋1，到下一個記錄，而B城第一記錄里有3個，只用了2個，所以記錄不跳到下一記錄。③求相同子序列及其個數，那就得判斷每個子序是否與前一個相同(代碼：diff?。絟[n])，就可以知道代碼中最后一個分支模塊是進行子序列相同判斷和處理的，那么else中應該是處理子序列相同的情況，如果子序列相同，只要增加子序列個數即可。
13.(1)①tcur＝da[cur][1]?、趒h＝q　③qc＝cur (2)cur?。剑?
解析　本題考查鏈表元素的插入。(1)①cur表示當前要插入的節點，頭元素只有一個節點，肯定有序，因此其初值為da[ha][1]。將某個節點移動到前面后，該節點的指針域將更新，循環體最后一條語句為cur＝tcur，那么下一個當前節點就是當前節點的后繼的指針要保存在tcur中。②某個節點要插入到新位置p，那么要知道p的前驅是什么，因此在查找位置時，同時要保存前驅節點位置。③完成當前節點的插入時，若當前節點位置發生變化，那么在遍歷到下一個當前節點cur時，他的前驅是不會變化的，只有當前節點位置沒有發生變化，其前驅是要同步移動。(2)略。
14.(1)75 67 60 40 15 30　(2) ①cur＝data[cur][1]?、赿ata[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本題考查鏈表的基本操作，學生需要有鏈表節點的概念，鏈表用列表來模擬的過程。(1)若當前就診順序為“75 67 40 15 30”，下一位預約病人年齡為60，根據題干描述“老年人(年齡>＝60歲)比非老年人優先就診，老年人按年齡從大到小的順序就診”，因此將60插入到40前，結果是75 67 60 40 15 30。(2)根據題干描述，本題分兩種情況，年齡>＝60歲時，按年齡降序，年齡<60歲時，按預約順序。因此，主要涉及鏈表的插入操作，年齡>＝60歲時為頭插入和中間插入，按預約順序尾插入。①的功能是比較數據大小，從頭節點開始依次遍歷，根據數據值找到第一個比當前數據小的節點cur，pre為前驅節點，因此，①處答案為cur＝data[cur][1]，表示從當前節點到下一節點。在鏈表中間插入新節點時，需要在插入節點后，更改前驅節點的指針區域。因此②處答案為data[pre][1]＝len(data)－1。直接插在鏈表尾節點后，尾節點變成了前驅節點，更改前驅節點的指針區域。因此③處答案為data[tail][1]＝len(data)－1。

展開更多......

收起↑