資源簡介

第二章 數據的存儲方式 章節測試
一、選擇題
1．有如下圖所示的單向鏈表：
從頭指針head指向的節點開始查找數據元素“5”，并刪除該節點，下列說法正確的是（ ）
A．共需查找3次
B．刪除數據元素“5”的節點，后續節點需要移動3次
C．頭指針head將指向數據元素“7”的節點
D．操作完成后，鏈表中數據元素的個數為6個
2．某Python程序如下：
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end='->')
p=a[p][1]
print(a[p][0])
程序運行后，輸出的結果是（ ）
A．3->7->2->1 B．3->2->7->1 C．1->7->3->2 D．3->7->1->2
3．使用鏈表結構模擬某校游玩路線，鏈表a中每一個節點包含三個數據，第1個為景點名稱，第2個為預計游玩時間（單位：分鐘），第3個為下一個景點指針。該校可以從多個景點開始游玩，但只能從“南大門”離開，輸出顯示從各景點進入路線及預計總時間的代碼如下。a=[["校訓石",21,2]，["行政樓",40,2]，["風雨操場",50,5]，["麗澤湖",30,4]，["西餐廳",60,5]，["南大門",20,-1]]
head=[0,1,3]
for i in range(len(head)):
(1)
s=a[p][1]
while a[p][2]!=-1:
print(a[p][0],end="→")
(2)
(3)
print(a[p][0])
print("預計時間：",s,"分鐘")
上述程序劃線處的可選代碼有：
①p=head ②p=head[i] ③s=s+a[p][1] ④p=a[p][2]
則（1)、(2)、(3）處代碼依次為（ ）
A．①③④ B．①④③ C．②③④ D．②④③
4．下列數據中，不屬于列表的是（ ）
A．{10，15，20，25} B．[10，1.5，20，2.5]
C．[10,15,20，25] D．[a,"b"，20，25]
5．使用鏈表結構模擬某景區游玩路線，鏈表a中每一個節點包含三個數據，第1個為景點名稱，第2個為預計游玩時間（單位：分鐘），第3個為下一個景點指針。景區可以從多個景點的大門進入，但只能從"天梯"離開，輸出顯示各大門進入路線及預計總時間的代碼如下。
a=[["迎客松",21,2]，["激流勇進",40,2]，["天空棧道",50,5]，["一線天",30,4]，["飛來峰",60,5]，["天梯",20,-1]
head=[0,1,3]
for i in range(len(head)):
(1)
s=a[p][1]
while a[p][2]! =－1:
print(a[p][0],end="－－>")
(2)
(3)
print(a[p][0])
print("預計時間：",s,"分鐘")
上述程序劃線處的可選代碼有：
①p=head ②p=head[i] ③s=s+a[p][1] ④p=a[p][2]
則(1)，(2)，(3)處代碼依次為（ ）
A．①③④ B．①④③ C．②③④ D．②④③
6．使用列表模擬單向鏈表，鏈表中p節點的a[p][0]存儲數據，a[p][1]存儲其后繼節點的指針。編寫Python程序刪除鏈表中所有的偶數項（頭節點為該鏈表的第1項），部分代碼如下：
p=head #head指向該鏈表的頭節點
while p!=-1:
q=a[p][1]
if （1） :
（2）
p=a[p][1]
上述程序段劃線處可選語句為
①q!=-1 ②a[q][1]!=-1 ③a[q][1]=a[p][1] ④a[p][1]=a[q][1]
則（1）（2）處填入的語句依次為（ ）
A．①③ B．①④ C．②③ D．②④
7．利用列表模擬某單向非循環鏈表a(其中可能存在已被刪除的節點），下列程序運行完畢后，變量p肯定表示尾節點的節點位置的是（　?。?br/>A． B． C． D．
8．尋寶游戲中通過一個線索找到下一個線索，最好用下列數據組織形式中的（ ）來表示。
A．數組 B．鏈表 C．棧 D．隊列
9．用Python程序實現刪除鏈表的倒數第n（n不大于鏈表長度）個節點，如n=2時，鏈表
更新為。
部分代碼如下：
# 讀入鏈表存儲在列表s中，head存儲鏈表的頭節點，代碼略
n=int(input())
pl=p2=head
while p2!=-1:
if n>=0：
(1)
n -= l
else:
(2)
p2 = s[p2] [1]
if p1 == head :
head=s[head] [1]
else：
(3)
上述程序段中劃線處可選的語句為：
①p1=s[p1][1] ②p2=s[p2][1] ③s[p1][1]=s[s[p1][1]][1] ④s[p2][1]=s[s[p2][1]][1]
則（1）~（3）劃線處語句依次為（ ）
A．①③④ B．①④③ C．②①④ D．②①③
10．現采用新的排隊方案為小明、小紅、小麗、小輝四人排隊，
Python程序段如下：
linklist=[["小明",1],["小紅",2],["小麗",3],["小輝",-1]]
def reset(head):
if linklist[head][1]==- 1 or head==- 1:
return head
else:
new_head=reset(linklist[head][1])
linklist[linklist[head][1]][1]=head
linklist[head][1]=- 1
return new head
p=h=reset(0)
while p!=- 1:
print(linklist[p][0],end="")
p=linklist[p][1]
執行該程序段后，輸出的結果是（ ）
A．小明小紅小麗小輝 B．小明小輝小麗小紅
C．小輝小麗小紅小明 D．小明小麗小紅小輝
11．下列關于數組的描述，正確的是（ ）
A．數組的大小是固定的，但可以有不同類型的數組元素
B．數組的大小是可變的，但所有數組元素的類型必須相同
C．數組的大小是固定的，所有數組元素的類型必須相同
D．數組的大小是可變的，可以有不同類型的數組元素
12．在Python中可以使用列表模擬單向鏈表，如鏈表中的節點p，a[p] [0]存儲p節點的數據，a[p][1]存儲p指向后繼節點的指針。若要在p節點之后插入新的節點x（x作為p的新后繼節點），需要執行的語句是（ ）
A．a[p][1]=x; a[x][1]=a[p][1] B．a[x][1]=a[p][1]; a[p][1]=x
C．a[p][0]=x; a[x][0]=a[p][0] D．a[x][0]=a[p][0]; a[p][0]=x
13．設有一個5×8的二維數組a，若按行優先的順序存儲數組元素，則元素a[3][5]前面元素的個數為(　　)
A．21 B．22 C．29 D．37
14．已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如右圖所示，下列操作需要遍歷多個節點的是（ ）
A．刪除該鏈表中的最后一個節點
B．刪除該鏈表中的第一個節點
C．在該鏈表第一個節點前插入一個新節點
D．在該鏈表最后一個節點后插入一個新節點
15．運用Python編程處理數據時，經常會用到pandas庫，其中Series是一維數據結構，下圖程序運行后的結果

A．水蜜桃 B．3 C．水蜜桃 D．“獼猴桃” ”水蜜桃”
16．在單向鏈表如下圖所示，在data2與data3之間插入一個新節點data4（p指向data2，r指向data4。列表data來記錄鏈表數據域，列表next來記錄指針域），在以下選項中選擇正確的執行步驟（ ）
①next[p]= next[r] ②next[p]= r ③next[r]= p
④next[r]= -1 ⑤next[r]= next[p] ⑥next[p]= -1
A．③⑥ B．⑤② C．①④ D．⑤②④
17．a數組定義如下：a=[2,5,0,3,6,8]，則運算表達式“a[1]+a[3]+a[5]”的結果為（ ）
A．16 B．8 C．10 D．13
18．有關數組特征描述中，下列說法不正確的是（ ）
A．同一數組中，每個數組元素的數據類型是相同的
B．通過數組名和下標可以對數組中任意位置的數組元素進行高效訪問
C．數組的存儲空間固定不變
D．數組是非順序存儲結構
19．設有數組定義語句：Dim a(5) As Integer，Listl 為列表框控件。下列給數組元素賦值的語句，錯誤的是（ ）。
A．a(3)=3
B．a(3)=VAL(InputBox(“InputData”）
C．a(3)=Listl.ListIndex
D．a=Array(1,2,3,4,5,6)
20．語句Dim a&(1 To 20)，b#(2,-1 To 1)定義兩個數組，其類型分別為： （ ）
A．二維單精度實型數組和二雙精度型數組
B．二維長整型數組和二維單精度實型數組
C．一維單精度實型數組和二維整型數組
D．一維長整型數組和二維雙精度型數組
二、操作題
21．為分析數據中各元素的變化情況，進行如下定義：
若在數組d中滿足d[a]<…d[i+1]>…>d[b]，則從下標a到下標b區間的數據稱為一個波峰，下標a到b的距離即為一個波峰的長度（長度≥3）。例如：數組d元素為“78,46,50,37,5,42,6,6,23”，存在2個波峰，分別是從d[1]到d[4]和d[4]到d[6]，波峰長度分別為4和3。編寫程序分析數據，找出所有波峰，按波峰長度降序排序（若波峰長度相同，則按開始下標升序），并輸出波峰長度和開始到結束元素下標；若不存在，則輸出“不存在波峰”，運行結果如圖所示。
請回答下列問題：
（1）根據題意，若數組d元素“23,14,35,31,13,20,3,40,10,10,9”，則最長的波峰長度為 。
（2）執行程序，若數組d元素“2,1,1,2”，則I處while語句中循環體的執行次數是 。
（3）實現上述功能的程序代碼如下，請在劃線處填入合適的代碼。
#讀取待處理數據，保存在數組d中，并顯示輸出，代碼略
mt, i, n=[], 1, len（d）
while iwhile i< n and d [i] < = d [i-1]: # I
i += 1
st = i-1
while i < n and d [i] > d [i-1]:
i += 1
if i==n or
continue #跳出本輪循環，然后繼續進行下一輪循環
while i < n and d [i] < d [i-1]:
i += 1
In=i-st
if len（mt）==0:
mt. append（[In, st, -1]） #為mt追加一個列表元素
head = 0; q = head
else:
while p != -1 and( ):
q = p
p = mt [p] [2]
if p==head:
mt. append（[In, st, head]）
head= len（mt）-1
else:
mt. append（[In, st, p]）
=len（mt）-1
if len（mt）==0:
print（“不存在波峰”）
else:
print（“輸出結果（長度：開始下標～結束下標）:”）
p = head
while p != -1:
print（mt [p] [0],“:”, mt [p] [1],“～”, mt [p] [0] + mt [p] [1] -1）
p = mt [p] [2]
22．某校針對高三高考成績進行分析時，其中有兩個主要指標：班級各科平均成績和班級總分平均成績。高考成績保存在“kscj.csv”文件中，格式如圖a所示，每行有四個項目，分別是“學號”、“姓名”、“學科”和“得分”，其中“學號”的前兩位表示班級編號，后兩位表示該學生班內編號，兩種編號均從“01”遞增編號。
設計如下Python程序，執行后輸出上述兩個主要指標，如圖b所示。請回答下列問題。

圖a 圖b
（1）通讀下列程序代碼后，可知程序中各班級隊列采用的數據結構為 （選填，數組/鏈表）。
（2）函數dataToClassQue功能：根據班級編號，將數據分配到各個班級隊列。請在劃線處填入合適的代碼。
def dataToClassQue(data) :
num = len(data)
for i in range(num):
classId = data[i][0]
if queInfo[classId-1][0]=-1 :
queInfo[classId-1][0]=i
else:

queInfo[classId-1][1]=i
return
（3）函數dataProcessing功能：統計各班各科平均分和班總分平均分。請在劃線處填入合適的代碼。
def dataProcessing(data):
for classId in range(1 ,classNumber+1):
①
score = [[0,0] for i in range(10)] #班級各科平均分和相應人數初始化
p = queInfo[classId- 1][0]
while p!=-1 :
subjectId = data[p][3]
total += data[p][4]
②
score[subjectIld][1]+= 1
p = data[p][-1]
for subjectId in range(10):
if score[subjectId][1]!=0.
t= ③
#函數round(t,x)用于對變量t四舍五入保留x位小數
averageScore[classId- 1][subjectId] = round(t,1)
averageScore[classId-1][10] = round(total/score[0][1],1)
return
def readFile(data) :
#讀入原始學生數據，預處理后，存儲到data中，代碼略
#data數據格式：[[6,10,'白凱修',0,117,-1],[6,10, '白凱修',1,109,-1],……]
#每條記錄的信息包括：班級編號，班內編號，姓名，學科編號，得分和預留值-1
return maxCassId #返回最大班級編號
def fmtPrint():
#格式化輸出，如第15題圖b所示，代碼略。
return
#主程序：
course= {'語文':0, '數學':1, '英語':2, '物理':3, '化學':4, '生物':5, '政治':6, '歷史':7, '地理':8, '技術':9}
data=[] #存儲讀入的數據
classNumber = readFile(data)
queInfo = [[-1,-1] for i in range(classNumber)] #初始化隊列，用于存儲各班級信息
averageScore = [[0 for k in range(11)] for i in range(classNumber)]#初始化各班各科以及總分平均分
dataToClassQue(data)
dataProcessing(data)
fmtPrint()
23．某信息僅包含大寫字母，字符數不超過n*n（n*n為密鑰矩陣規模，n>0），加密過程如圖a所示：
圖a
圖b
（1）已知密鑰矩陣按圖a中所示，若原文為“OK”，則加密后的密文是 ，若輸入的密文是“10，1，24，2，”，則原文是 。
（2）根據上述加密算法編寫解密程序，運行界面如圖c所示。請在劃線①②③處填上合適的代碼。
圖c
def getmm（x，n）: #獲取位置編號x的位置密鑰值
row=（x-1）%n
col=（x-1）//n
if① ：
row=n-1-row
return key[row][col]
#生成規模為n*n的密鑰矩陣，存入二維矩陣key中
n=int（input（"請輸入密鑰矩陣規模n:"））
key=[[i*n+j+l for j in range(n)] for i in range(n)]
#密文解密
p=input("請輸入密文: ")
mw=[]
bmz=[]
t=0
for i in range (1en(p)):
#依次讀取密文字符串中的數值，結果存入到列表mw中
s=p[i]
if s!=",":
.②
else:
mw. append (t)
t=0
k=len (mw)
for i in range(k//2) : #對密文解密，結果存入列表bmz中
bmz. append (mw [2*i]- ③
yw="
for i in range (k//2): #轉換為字母輸出
yw=ywtchr (bmz [i]-1+ord("A"))
print("原文為:"+yw)
24．某工程包含n個任務（編號為0-n-1），每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4，不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況。
現已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。
根據每個任務完成所需的天數和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數，并以工程最快完成所需的天數為期限，計算每個任務最晚必須開始的時間。
圖a 圖b
請回答下列問題：
（1）若某工程有6個任務，任務間依賴關系如圖a所示，完成任務0~5所需天數分別為2，1，3，5，1，6，則工程最快完成需要 天。
（2）定義如下erase（1st）函數，參數1st列表的每個元素表示一個依賴關系。函數的功能是刪除標記為“F”的依賴關系，返回保留的依賴關系的個數。
def erase（lst）：
i=0
j=len（1st）-1
while i<=j：
if 1st[i][2]=='T'：
i+=1
else：
if lst[j][2]=='T'：
1st[i]=1st[j]
i+=1
j-=1
return i
若1st列表依次存儲圖b所示的依賴關系，如1st[0]為[0，5，T]，調用erase（lst）的數，則語句
"1st[i]=1st[j]”的執行次數為 。
（3）實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def proc（n，lst，task）：
pr=[0]*n
w=[0]*n #w[i]存放任務1最晚必須開始的時間
m=erase（1st）
for i in① ：
task[lst[i][1]][1]=1st[i][0]
pr[lst[i][0]]=1
c=[]
days=0 #days存放工程最快完成所需的天數
for I in range（n）：
if pr[i]==0：
k=i
s=0
while k！=-1：
c．append（k）
s+=task[k][0]
②
if s>days：
days=s
for i in range（n-1，-1，-1）：
k=c[i]
if task[k][1]==-1:
w[k]=days-task[k][0]+1
else：
③
#輸出days，以及保存在w中的每個任務最晚必須開始的時間，代碼略
```
工程包含的任務數存入變量n
任務間的依賴關系存入1st列表
1st[0]包含3項，任務1st[i][0]依賴于任務1st[i][1]，1st[i][2]存放保留/刪除標記，任務數據存入task列表
task[i]包含2項，task[i][0]為完成任務主所需天數，task[i][1]的初值為-1
代碼略
```
proc（n，1st，task）
25．在Python語言中，可以使用列表來模擬鏈表節點的插入操作。以下Python程序段用二維列表來定義單向鏈表。如要在該鏈表中插入節點，可以通過程序來修改相應節點的指針達到目的。
（1）如下圖所示，請根據程序補充完整未插入數據前的鏈表數據區域的值（依次填寫）① 、 、 、 。此時鏈表的頭指針的值是② 。
（2）實現鏈表插入的 Python 程序如下，請在程序劃線處填入合適的代碼。
data=[[8,-1],[7,4],[5,5],[6,0],[1,3],[2,1]] # 定義單向鏈表
head=2 leng=len(data)
pos=int(input("請輸入要插入的位置（0~%d）之間："%(leng)))
val=int(input("請輸入要插入的數據值："))
data.append([val,leng])
# 插入節點：
p=head
if pos== : # 加在鏈表最前面，作為首節點
data[leng][1]=p
head= # 更新頭指針
else:
q=data[p][1]
c=0
while c < pos-1 and q!=-1:
p=q
q=data[p][1]
c+=1
# 更新指針
data[p][1]=leng
# 用列表形式來顯示插入后的鏈表：
p=head
s=[ ]
while p!=-1:
s.append( )
p=data[p][1]
print(s)
參考答案
1．D
2．A
3．D
4．A
5．D
6．B
7．B
8．B
9．D
10．C
11．C
12．B
13．C
14．A
15．B
16．B
17．A
18．D
19．D
20．D
21．4 2次 d[i]==d[i-1] In==mt[p][0] and st>mt[p][1] mt[q][2]
22．鏈表 data[queInfo[classId-1][1]][-1]=i total=0 scoree[subjectIld][0]+=data[p][4] scoree[subjectIld][0]/score[subjectIld][1]
23．16,1,15,2, IT col%2==1 或其他等價答案 t=t*10+int(s) 或其他等價答案 getmm(mw[2*i+1],n)
24．8 1 range（m） 或range（0，m） 或range（0，m，1） 或range（m-1，-1，-1）或range（erase（1st）） 或range（0，erase（1st）） 或range（0，erase（1st），1） 或range（erase（1st）-1，-1，-1） k=task[k][1] w[k]=w[task[k][1]]-task[k][0] 或w[k]=w[c[i+1]]-task[k][0] 這里面可以把k換成c[i]
25．2 7 1 6 2 0 leng data[leng][1]=q data[p][0]

展開更多......

收起↑