第二章數(shù)據(jù)的存儲方式章節(jié)測試20232024學年粵教版高中信息技術選修1

第二章數(shù)據(jù)的存儲方式章節(jié)測試一、選擇題1．有如下圖所示的單向鏈表：從頭指針head指向的節(jié)點開始查找數(shù)據(jù)元素“5”，并刪除該節(jié)點，下列說法正確的是（

）A．共需查找3次 B．刪除數(shù)據(jù)元素“5”的節(jié)點，后續(xù)節(jié)點需要移動3次C．頭指針head將指向數(shù)據(jù)元素“7”的節(jié)點 D．操作完成后，鏈表中數(shù)據(jù)元素的個數(shù)為6個2．某Python程序如下：a=[[3,2],[2,3],[7,1],[1,0]]p=head=0whilea[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>23．使用鏈表結構模擬某校游玩路線，鏈表a中每一個節(jié)點包含三個數(shù)據(jù)，第1個為景點名稱，第2個為預計游玩時間（單位：分鐘），第3個為下一個景點指針。該?？梢詮亩鄠€景點開始游玩，但只能從“南大門”離開，輸出顯示從各景點進入路線及預計總時間的代碼如下。a=[["校訓石",21,2]，["行政樓",40,2]，["風雨操場",50,5]，["麗澤湖",30,4]，["西餐廳",60,5]，["南大門",20,1]]head=[0,1,3]foriinrange(len(head)):

(1)

s=a[p][1]

whilea[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．下列數(shù)據(jù)中，不屬于列表的是（

）A．{10，15，20，25} B．[10，，20，2.5]C．[10,15,20，25] D．[a,"b"，20，25]5．使用鏈表結構模擬某景區(qū)游玩路線，鏈表a中每一個節(jié)點包含三個數(shù)據(jù)，第1個為景點名稱，第2個為預計游玩時間（單位：分鐘），第3個為下一個景點指針。景區(qū)可以從多個景點的大門進入，但只能從"天梯"離開，輸出顯示各大門進入路線及預計總時間的代碼如下。a=[["迎客松",21,2]，["激流勇進",40,2]，["天空棧道",50,5]，["一線天",30,4]，["飛來峰",60,5]，["天梯",20,1]head=[0,1,3]foriinrange(len(head)):(1)

s=a[p][1]

whilea[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節(jié)點的a[p][0]存儲數(shù)據(jù)，a[p][1]存儲其后繼節(jié)點的指針。編寫Python程序刪除鏈表中所有的偶數(shù)項（頭節(jié)點為該鏈表的第1項），部分代碼如下：p=head

#head指向該鏈表的頭節(jié)點whilep!=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．利用列表模擬某單向非循環(huán)鏈表a(其中可能存在已被刪除的節(jié)點），下列程序運行完畢后，變量p肯定表示尾節(jié)點的節(jié)點位置的是（）A．

B．

C．

D．

8．尋寶游戲中通過一個線索找到下一個線索，最好用下列數(shù)據(jù)組織形式中的（

）來表示。A．數(shù)組 B．鏈表 C．棧 D．隊列9．用Python程序?qū)崿F(xiàn)刪除鏈表的倒數(shù)第n（n不大于鏈表長度）個節(jié)點，如n=2時，鏈表更新為。部分代碼如下：#讀入鏈表存儲在列表s中，head存儲鏈表的頭節(jié)點，代碼略n=int(input())pl=p2=headwhilep2!=1:

ifn>=0：

(1)

n=l

else:

(2)

p2=s[p2][1]ifp1==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．現(xiàn)采用新的排隊方案為小明、小紅、小麗、小輝四人排隊，Python程序段如下：linklist=[["小明",1],["小紅",2],["小麗",3],["小輝",1]]defreset(head):

iflinklist[head][1]==1orhead==1:

returnhead

else:

new_head=reset(linklist[head][1])

linklist[linklist[head][1]][1]=head

linklist[head][1]=1

returnnewheadp=h=reset(0)whilep!=1:

print(linklist[p][0],end="")

p=linklist[p][1]執(zhí)行該程序段后，輸出的結果是（

）A．小明小紅小麗小輝 B．小明小輝小麗小紅C．小輝小麗小紅小明 D．小明小麗小紅小輝11．下列關于數(shù)組的描述，正確的是（

）A．數(shù)組的大小是固定的，但可以有不同類型的數(shù)組元素B．數(shù)組的大小是可變的，但所有數(shù)組元素的類型必須相同C．數(shù)組的大小是固定的，所有數(shù)組元素的類型必須相同D．數(shù)組的大小是可變的，可以有不同類型的數(shù)組元素12．在Python中可以使用列表模擬單向鏈表，如鏈表中的節(jié)點p，a[p][0]存儲p節(jié)點的數(shù)據(jù)，a[p][1]存儲p指向后繼節(jié)點的指針。若要在p節(jié)點之后插入新的節(jié)點x（x作為p的新后繼節(jié)點），需要執(zhí)行的語句是（

）A．a(chǎn)[p][1]=x;a[x][1]=a[p][1] B．a(chǎn)[x][1]=a[p][1];a[p][1]=xC．a(chǎn)[p][0]=x;a[x][0]=a[p][0] D．a(chǎn)[x][0]=a[p][0];a[p][0]=x13．設有一個5×8的二維數(shù)組a，若按行優(yōu)先的順序存儲數(shù)組元素，則元素a[3][5]前面元素的個數(shù)為()A．21 B．22 C．29 D．3714．已知一個有7個節(jié)點的單向鏈表，設有頭指針head和尾指針tail，如右圖所示，下列操作需要遍歷多個節(jié)點的是（

）A．刪除該鏈表中的最后一個節(jié)點B．刪除該鏈表中的第一個節(jié)點C．在該鏈表第一個節(jié)點前插入一個新節(jié)點D．在該鏈表最后一個節(jié)點后插入一個新節(jié)點15．運用Python編程處理數(shù)據(jù)時，經(jīng)常會用到pandas庫，其中Series是一維數(shù)據(jù)結構，下圖程序運行后的結果

A．水蜜桃 B．3 C．水蜜桃 D．“獼猴桃””水蜜桃”16．在單向鏈表如下圖所示，在data2與data3之間插入一個新節(jié)點data4（p指向data2，r指向data4。列表data來記錄鏈表數(shù)據(jù)域，列表next來記錄指針域），在以下選項中選擇正確的執(zhí)行步驟（

）①next[p]=next[r]

②next[p]=r

③next[r]=p④next[r]=1

⑤next[r]=next[p]

⑥next[p]=1A．③⑥ B．⑤② C．①④ D．⑤②④17．a(chǎn)數(shù)組定義如下：a=[2,5,0,3,6,8]，則運算表達式“a[1]+a[3]+a[5]”的結果為（

）A．16 B．8 C．10 D．1318．有關數(shù)組特征描述中，下列說法不正確的是（

）A．同一數(shù)組中，每個數(shù)組元素的數(shù)據(jù)類型是相同的B．通過數(shù)組名和下標可以對數(shù)組中任意位置的數(shù)組元素進行高效訪問C．數(shù)組的存儲空間固定不變D．數(shù)組是非順序存儲結構19．設有數(shù)組定義語句：Dima(5)AsInteger，Listl為列表框控件。下列給數(shù)組元素賦值的語句，錯誤的是（

）。A．a(chǎn)(3)=3B．a(chǎn)(3)=VAL(InputBox(“InputData”）C．a(chǎn)(3)=D．a(chǎn)=Array(1,2,3,4,5,6)20．語句Dima&(1To20)，b#(2,1To1)定義兩個數(shù)組，其類型分別為：（

）A．二維單精度實型數(shù)組和二雙精度型數(shù)組B．二維長整型數(shù)組和二維單精度實型數(shù)組C．一維單精度實型數(shù)組和二維整型數(shù)組D．一維長整型數(shù)組和二維雙精度型數(shù)組二、操作題21．為分析數(shù)據(jù)中各元素的變化情況，進行如下定義：若在數(shù)組d中滿足d[a]<…<d[i1]<d[i]>d[i+1]>…>d[b]，則從下標a到下標b區(qū)間的數(shù)據(jù)稱為一個波峰，下標a到b的距離即為一個波峰的長度（長度≥3）。例如：數(shù)組d元素為“78,46,50,37,5,42,6,6,23”，存在2個波峰，分別是從d[1]到d[4]和d[4]到d[6]，波峰長度分別為4和3。編寫程序分析數(shù)據(jù)，找出所有波峰，按波峰長度降序排序（若波峰長度相同，則按開始下標升序），并輸出波峰長度和開始到結束元素下標；若不存在，則輸出“不存在波峰”，運行結果如圖所示。請回答下列問題：（1）根據(jù)題意，若數(shù)組d元素“23,14,35,31,13,20,3,40,10,10,9”，則最長的波峰長度為。（2）執(zhí)行程序，若數(shù)組d元素“2,1,1,2”，則I處while語句中循環(huán)體的執(zhí)行次數(shù)是。（3）實現(xiàn)上述功能的程序代碼如下，請在劃線處填入合適的代碼。#讀取待處理數(shù)據(jù)，保存在數(shù)組d中，并顯示輸出，代碼略mt,i,n=[],1,len（d）whilei<n:whilei<nandd[i]<=d[i1]:

#I

i+=1st=i1

whilei<nandd[i]>d[i1]:

i+=1ifi==norcontinue

#跳出本輪循環(huán)，然后繼續(xù)進行下一輪循環(huán)whilei<nandd[i]<d[i1]:i+=1In=istiflen（mt）==0:mt.append（[In,st,1]）

#為mt追加一個列表元素head=0;q=headelse:

whilep!=1and():

q=p

p=mt[p][2]

ifp==head:

mt.append（[In,st,head]）

head=len（mt）1

else:

mt.append（[In,st,p]）=len（mt）1iflen（mt）==0:print（“不存在波峰”）else:print（“輸出結果（長度：開始下標～結束下標）:”）p=headwhilep!=1:print（mt[p][0],“:”,mt[p][1],“～”,mt[p][0]+mt[p][1]1）p=mt[p][2]22．某校針對高三高考成績進行分析時，其中有兩個主要指標：班級各科平均成績和班級總分平均成績。高考成績保存在“kscj.csv”文件中，格式如圖a所示，每行有四個項目，分別是“學號”、“姓名”、“學科”和“得分”，其中“學號”的前兩位表示班級編號，后兩位表示該學生班內(nèi)編號，兩種編號均從“01”遞增編號。設計如下Python程序，執(zhí)行后輸出上述兩個主要指標，如圖b所示。請回答下列問題。

圖a

圖b（1）通讀下列程序代碼后，可知程序中各班級隊列采用的數(shù)據(jù)結構為（選填，數(shù)組/鏈表）。（2）函數(shù)dataToClassQue功能：根據(jù)班級編號，將數(shù)據(jù)分配到各個班級隊列。請在劃線處填入合適的代碼。def

dataToClassQue(data):

num=len(data)

foriinrange(num):

classId=data[i][0]

ifqueInfo[classId1][0]=1:

queInfo[classId1][0]=i

else:

queInfo[classId1][1]=i

return（3）函數(shù)dataProcessing功能：統(tǒng)計各班各科平均分和班總分平均分。請在劃線處填入合適的代碼。defdataProcessing(data):

forclassIdinrange(1,classNumber+1):

①

score=[[0,0]foriinrange(10)]

#班級各科平均分和相應人數(shù)初始化

p=queInfo[classId1][0]

whilep!=1:

subjectId=data[p][3]

total+=data[p][4]

②

score[subjectIld][1]+=1

p=data[p][1]

forsubjectIdinrange(10):

ifscore[subjectId][1]!=0.

t=③

#函數(shù)round(t,x)用于對變量t四舍五入保留x位小數(shù)

averageScore[classId1][subjectId]=round(t,1)

averageScore[classId1][10]=round(total/score[0][1],1)

returndefreadFile(data):

#讀入原始學生數(shù)據(jù)，預處理后，存儲到data中，代碼略

#data數(shù)據(jù)格式：[[6,10,'白凱修',0,117,1],[6,10,'白凱修',1,109,1],……]

#每條記錄的信息包括：班級編號，班內(nèi)編號，姓名，學科編號，得分和預留值1

returnmaxCassId

#返回最大班級編號deffmtPrint():

#格式化輸出，如第15題圖b所示，代碼略。

return#主程序：course={'語文':0,'數(shù)學':1,'英語':2,'物理':3,'化學':4,'生物':5,'政治':6,'歷史':7,'地理':8,'技術':9}data=[]

#存儲讀入的數(shù)據(jù)classNumber=readFile(data)queInfo=[[1,1]foriinrange(classNumber)]

#初始化隊列，用于存儲各班級信息averageScore=[[0forkinrange(11)]foriinrange(classNumber)]#初始化各班各科以及總分平均分dataToClassQue(data)dataProcessing(data)fmtPrint()23．某信息僅包含大寫字母，字符數(shù)不超過n*n（n*n為密鑰矩陣規(guī)模，n>0），加密過程如圖a所示：圖a圖b（1）已知密鑰矩陣按圖a中所示，若原文為“OK”，則加密后的密文是，若輸入的密文是“10，1，24，2，”，則原文是。（2）根據(jù)上述加密算法編寫解密程序，運行界面如圖c所示。請在劃線①②③處填上合適的代碼。圖cdef

getmm（x，n）:

#獲取位置編號x的位置密鑰值

row=（x1）%n

col=（x1）//n

if①：

row=n1row

returnkey[row][col]#生成規(guī)模為n*n的密鑰矩陣，存入二維矩陣key中n=int（input（"請輸入密鑰矩陣規(guī)模n:"））key=[[i*n+j+lforjinrange(n)]foriinrange(n)]#密文解密p=input("請輸入密文:")mw=[]bmz=[]t=0foriinrange(1en(p)):#依次讀取密文字符串中的數(shù)值，結果存入到列表mw中s=p[i]ifs!=",":.②else:mw.append(t)t=0k=len(mw)foriinrange(k//2):

#對密文解密，結果存入列表bmz中bmz.append(mw[2*i]③yw="foriinrange(k//2):

#轉(zhuǎn)換為字母輸出yw=ywtchr(bmz[i]1+ord("A"))print("原文為:"+yw)24．某工程包含n個任務（編號為0n1），每天可以有多個任務同時進行。某些任務之間有依賴關系，如圖a所示，任務4依賴于任務1，任務1依賴于任務2。即任務2完成后才可以開始任務1，任務1完成后才可以開始任務4，不存在一個任務依賴于多個任務，或多個任務依賴于同一個任務的情況?，F(xiàn)已對該工程的依賴關系進行了梳理，結果如圖b所示，標記“T”表示依賴關系需保留，標記“F”表示依賴關系需刪除。根據(jù)每個任務完成所需的天數(shù)和梳理后的依賴關系，編寫程序，首先刪除標記為“F”的依賴關系，然后計算工程最快完成所需的天數(shù)，并以工程最快完成所需的天數(shù)為期限，計算每個任務最晚必須開始的時間。圖a

圖b請回答下列問題：（1）若某工程有6個任務，任務間依賴關系如圖a所示，完成任務0~5所需天數(shù)分別為2，1，3，5，1，6，則工程最快完成需要天。（2）定義如下erase（1st）函數(shù)，參數(shù)1st列表的每個元素表示一個依賴關系。函數(shù)的功能是刪除標記為“F”的依賴關系，返回保留的依賴關系的個數(shù)。deferase（lst）：

i=0

j=len（1st）1

whilei<=j：

if1st[i][2]=='T'：

i+=1

else：

iflst[j][2]=='T'：

1st[i]=1st[j]

i+=1

j=1

returni若1st列表依次存儲圖b所示的依賴關系，如1st[0]為[0，5，T]，調(diào)用erase（lst）的數(shù)，則語句"1st[i]=1st[j]”的執(zhí)行次數(shù)為。（3）實現(xiàn)上述功能的部分Python程序如下，請在劃線處填入合適的代碼。defproc（n，lst，task）：

pr=[0]*n

w=[0]*n

#w[i]存放任務1最晚必須開始的時間

m=erase（1st）

foriin①：

task[lst[i][1]][1]=1st[i][0]

pr[lst[i][0]]=1

c=[]

days=0

#days存放工程最快完成所需的天數(shù)

forIinrange（n）：

ifpr[i]==0：

k=i

s=0

whilek！=1：

c．a(chǎn)ppend（k）

s+=task[k][0]

②

ifs>days：

days=s

foriinrange（n1，1，1）：

k=c[i]

iftask[k][1]==1:

w[k]=daystask[k][0]+1

else：

③#輸出days，以及保存在w中的每個任務最晚必須開始的時間，代碼略```工程包含的任務數(shù)存入變量n任務間的依賴關系存入1st列表1st[0]包含3項，任務1st[i][0]依賴于任務1st[i][1]，1st[i][2]存放保留/刪除標記，任務數(shù)據(jù)存入task列表task[i]包含2項，task[i][0]為完成任務主所需天數(shù)，task[i][1]的初值為1代碼略```proc（n，1st，task）25．在Python語言中，可以使用列表來模擬鏈表節(jié)點的插入操作。以下Python程序段用二維列表來定義單向鏈表。如要在該鏈表中插入節(jié)點，可以通過程序來修改相應節(jié)點的指針達到目的。（1）如下圖所示，請根據(jù)程序補充完整未插入數(shù)據(jù)前的鏈表數(shù)據(jù)區(qū)域的值（依次填寫）①、、、。此時鏈表的頭指針的值是②。（2）實現(xiàn)鏈表插入的Python程序如下，請在程序劃線處填入合適的代碼。data=[[8,1],[7,4],[5,5],[6,0],[1,3],[2,1]]

#定義單向鏈表head=2leng=len(data)pos=int(input("請輸入要