資源簡介

第二章 數據與鏈表 章節測試
一、選擇題
1．下列說法或用法正確的是( ）
A．OPTION BASE 6
B．OPTION BASE 語句的位置可以任意
C．DIM A(6,3 TO 7)定義的是二維數組
D．數組元素的下標不能是負數。
2．有一組含有9個元素的有序鏈表：1->3->5->6->8->11->15->18->20，現為該鏈表增設關鍵節點，建立索引，下列說法不正確的是（ ）
A．一級索引中的關鍵節點為1,5,8,15,20
B．二級索引中的關鍵節點為1,8,20
C．若要在建立的一級索引的基礎上插入元素7，則需要比較3次即可找到7插入的位置
D．若要在建立的二級索引的基礎上查找元素18，則需要比較4次就可以找到元素18
3．有如下程序段：
a=[[2,2,1],[8,0,4],[3,3,0],[6,-1,2],[8,1,-1]]
ans=head=3
p=a[head][2]
while p!=-1:
if a[ans][0] < a[p][0] :
ans=p
p=a[p][2]
print(ans,a[ans][0],sep=",")
則程序運行后，下列說法正確的是（ ）
A．鏈表數據值依次為2->8->3->6->8
B．程序輸出結果為4,8
C．a[0][2]的值為1，雙向鏈表a的頭節點數據值為2
D．a[1][1]的值為0，雙向鏈表a的尾節點數據值為8
4．下列Python程序段的功能是在鏈表link1中刪除數據為key的所有節點，link1鏈表中的每個節點由一個數據域和一個指針域組成。
#建立鏈表 link1，代碼略
key=int(input("輸入要刪除的數據："))
head=0
while link1[head][0]==key and head!=- 1:
head=link1[head][1]
p=q=head
if head==- 1:
print("全部數據刪除")
else:
q=link1[q][1]
while ① :
if link1[q][0]==key:
②
else:
p=link1[p][1]
q=link1[q][1]
則劃線①②處的代碼分別為（　　）
A．①link1[q][1]!=- 1 ②link1[p][1]=link1[q][1]
B．①link1[q][1]!=- 1 ②link1[q][1]=link1[p][1]
C．①q!=- 1 ②link1[q][1]=link1[p][1]
D．①q!=- 1 ②link1[p][1]=link1[q][1]
5．數組a的數據存放情況如下表，則當i=2時，a[6/i-1]的值是（ ）。
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
48 52 98 26 47 22 82 33
A．98 B．26 C．52 D．22
6．使用Python的二維列表來模擬單向鏈表，如下代碼創建一個擁有4個節點的鏈表a
a=[["cat",1],[ "dog",2],[ "pig",-1],[ "rabbit",0]]
head=3
依次輸出各節點數據域的值，內容為(　　)
A．"cat","dog","pig","rabbit" B．"pig","rabbit","cat","dog"
C．"pig","dog","cat","rabbit" D．"rabbit","cat","dog","pig"
7．一頭指針 head=2 的單向鏈表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通過以下 Python 程序段，轉換為原鏈表的逆序鏈表，即頭指針 head=1，L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。
q=-1
p=head #head 為原鏈表頭指針
while p!=-1 :
tmp=L[p][1]
head=q
上述程序段中方框處可選的語句為：①p=tmp ②q=p ③L[p][1]=q
則方框處語句依次為( )
A．③②① B．③①② C．①③② D．①②③
8．將英文單詞“student”中的每個字符按次序以單鏈表的形式進行存儲，操作過程中漏掉了字符 e，存儲狀態如圖所示：
現將字符e存放于1111H處，并按正確的次序插入單鏈表中，則元素d、e、n的“鏈接地址”依次是（ ）
A．100CH，1014H，1111H B．100CH，1111H，1014H
C．1111H，100CH，1014H D．1111H，1014H，100CH
9．王老師用鏈表模擬某次比賽中運動員的出場次序，運動員號碼存儲如下：a=[[“056”，4]，[“134”，-1]，[“215”，5]，[“098”，0]，[“144”，2]，[“024”，1]]。假設head=3，小明同學的號碼是“215”，則他的出場次序是（ ）
A．2 B．4 C．5 D．6
10．一維數組a（下標從0開始）中元素值依次為11--100之間的奇數，則數組元素a[k]的值是（ ）
A．2*k+10 B．2*k+11 C．2*k+12 D．2*k+13
11．關于數組和鏈表，以下描述不正確的是（ ）
A．數組通過下標訪問或遍歷序列中的數據元素
B．常見的鏈表有單向鏈表、雙向鏈表和循環鏈表
C．一般情況下，數組元素的插入和刪除效率比鏈表要低
D．一般情況下，數組元素的查找效率比鏈表要低
12．有個列表n=[‘水果’, ‘砂糖橘’,’蘋果’, ‘橙子’],請把列表中’蘋果’改為’橘子’，選出修改正確的語句（ ）
A．n[2]= ‘橘子’ B．n[‘橘子’] C．n[3]= ‘橘子’ D．list[‘橘子’]
13．在日常幻燈片(如使用 PowerPoint 制作的講稿) 的放映中， 可以通過超鏈接的方式進行幻燈片之間的任意跳轉。與這種幻燈片的組織方式相似的數據結構是（ ）
A．鏈表 B．隊列 C．棧 D．樹
14．有如下Python程序段，其功能是將一個單向鏈表轉換成原鏈表的逆序鏈表：
lst=[[15,4],[30,-1],[8,0],[5,2],[19,1]]
head=3
p=head
q=-1
while p!=-1:
tmp=lst[p][1]
head=q
上述程序段執行后lst內容變為[[15,2],[30,4],[8,3],[5,-1],[19,0]]。方框處可選代碼有：①q=p ②p=tmp ③lst[p][1]=q，則方框處的語句依次為（ ）
A．①②③ B．②③① C．③①② D．③②①
15．有如下 Python 程序段
def bianli(head):
pt = head
while pt != -1:
print(data[pt][0],data[pt][1],"->",end='')
pt = data[pt][1]
print()
data = [['A',1],['B',2],['C',3],['D',-1]]
head = 0
bianli(head) #遍歷鏈表，顯示初始狀態為“A 1 ->B 2 ->C 3 ->D -1 ->”
qt = head
pt = data[qt][1]
bianli(head) #遍歷鏈表，顯示最終狀態為“A 2 ->C 1 ->B 3 ->D -1 ->”
執行該程序段后，鏈表遍歷結果由初始狀態變為最終狀態，上述程序段中方框處可選代碼為：
①data[data[qt][1]][1] = pt
②data[qt][1] = data[pt][1]
③data[pt][1] = data[data[pt][1]][1]
則方框處代碼的正確順序是（ ）
A．①②③ B．①③② C．②①③ D．②③①
二、填空題
16．在程序運行過程中可以改變數組元素個數的是( )數組，不可以改變數組元素個數的是( )數組。
17．在數組a中，數據的存放情況如下表，當i = 8時，a[i mod 3］的值為 。
18．運行以下VB程序，結果是 。
19．數組 d 的初始值如表所示，則 d(d(3))+d(4)的值 ( )。
20．數組a和數組b的數據存放情況如下表，則b[a[5]-2]的值是 。
數組a
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
2 5 4 1 6 3 8 7
數組b
b[1] b[2] b[3] b[4] b[5] b[6] b[7] B[8]
1 4 2 3 7 5 9 6
三、判斷題
21．“鏈表”存儲相鄰節點不需要連續空間。( )
四、操作題
22．某餐廳輔助配餐程序提供給用戶基于預算的點菜功能，該程序主要由“菜單顯示”及“訂單管理”兩大基本模塊組成，具體如下：
◆菜單顯示功能：輸出菜價小于等于預算經費余額且在售的菜品；
◆訂單管理功能：包括輸出訂單中的菜品信息，訂單菜品的刪除和添加等。
(1)菜品數據相對穩定，為了便于查找菜品， 采用①結構較為合理，訂單數據涉及頻繁的增加或刪除，采用② 結構較為合理。上述①、②處可填的內容為 (單選， 填字母:A．數組、鏈表/B．鏈表、數組)
(2) 餐廳菜品數據表如下所示，每道菜由 4 個數據項組成，第一項為菜品編號， 第二項為菜品名稱， 第三項的菜品單價(以“分”為單位，該數據項為0表示菜品已下架)，第四項為當月銷量。實現菜單顯示和輸出訂單菜品信息的程序如下，餐廳菜單保存在menu 中， 格式為：menu=[[0,"太湖三寶",18800,535]， [1,"湖羊肉",11800,446],…]。

程序運行結果如圖所示， 請在劃線處填入合適的代碼。

#讀取餐館全部菜品數據保存到menu 中， 數據類型及格式見題干描述，代碼略。 sal=int(input("☆ 請輸入你的消費預算(單位:分):"))
print("☆ 可供選擇的菜品:")
for i in range(len(menu)):
if and menu[i][2]<=sal:
print(' ',menu[i])
n=input("☆ 請輸入預選擇的菜品編號， 以逗號分隔:").split(',')
x=len(n)
lis=[[int(n[i]),i+1] for i in range(x)]
lis[x-1][1]=-1
p=0
while p!=-1:
bh=lis[p][0]
if menu[bh][2]<=sal:+6
y=p
else:
lis[y][1]=lis[p][1]
p=lis[p][1]
p=0;s=''
while p!=-1:
s+=menu[lis[p][0]][1]+' '

print('☆ 點單成功的菜品:'+s)
print("☆ 剩余金額:"+str(sal))
23．使用Python程序隨機生成一個長度為指定值n的雙向鏈表，并刪除其中值為奇數的數據。Python中可以利用嵌套列表來模擬鏈表，長度為n的列表中，每個元素為一個長度為3的子列表，作為鏈表的節點，其中第一個數據表示節點的數據區域，第二個數據表示節點的前驅指針，第三個數據表示節點的后繼指針，若指針域為空則對應區域的數據表示為-1。滿足上述要求的Python程序代碼如下，程序實現示例如圖所示。
（1）若生成的鏈表a的值為22→21→13→14→19→17→21→11，則程序運行結束后鏈表a的長度是 。
（2）若要刪除的是鏈表中值為3的倍數的節點，則加框處的語句應該修改為 。
（3）請在劃線處填入合適的代碼。
def print_list(list, head):
while head!=-1:
if list [head] [2] ==-1:
print(list [head] [0])
else:
print(list [head] [0], end = "→")
head=
import random
a=[]
head=-1
n=int(input("輸入鏈表的長度："))
for i in range(n):
node=[random. randint(10, 22), -1, head]
a. append(node)
if head!= -1:
a[head][1] =len(a)-1
head=
print_list(a, head)
p=head
while p!=-1:
if
if a[p][1]!=-1:
=a[p][2]
if a[p][2]!= -1:
a[a[p][2]][1]=a[p][1]
if head==p:
head=a[p][2]
p=a[p][2]
print("刪除奇數后的鏈表為：",end="")
print_list(a, head)
24．“網上預約掛號系統”的就診規則為：年齡大于等于80歲的患者優先就診，其余患者按照順序就診，現系統根據預約順序記錄了某天某科室患者的就診號、姓名和年齡，部分數據如圖a所示。經系統處理后輸出患者的就診順序，部分數據如圖b所示，請回答下列問題。
圖a 圖b
（1）創建output函數，輸出患者就診順序，請在劃線處填上合適代碼。
def output（1st，p）：
k=1
print（"患者就診順序："）
while p ！=-1：
print（k，"號"，1st[p][1]）

p=1st[p][3]
（2）實現按規則排出患者就診順序的Python程序如下，請在劃線處填入合適代碼。
#讀取患者信息存入pat列表，列表的每個元素包含3個數據項，分別對應患者的就診號、姓名和年齡，pat=[['021036'，'張*星'，32]，…]，代碼略
①
for i inrange（n）：
pat[i].append（-1） #pat[i]追加一個元素-1
head=0
for i inrange(1,n):
if pat[i][2]>=80:
if ② :
pat[i][3]=head
head=i
else:
p=head
while pat[pat[p][3]][2]>=80 and pat[p][3]!=-1:
p=pat[p][3]
③
pat[p][3]=i
else:
q=p=head
while p!=-1:
④
p=pat[p][3]
pat[q][3]=i
output(pat,head)
25．根據社團選課結束后的數據分析發現，部分社團的選報人數超過了40人，由于人數太多不便于開展活動， 學校團委決定將人數超過40人的社團隨機分成兩個班。小北使用鏈式結構實現了該分班功能。 現以對“MULA 商社”進行分班為例(“MULA商社.xlsx”文件截圖如圖c所示)，具體實 現程序如下，請在劃線處填入合適的代碼。
圖 c
import pandas as pd
import random
df = pd.read_excel("MULA 商社.xlsx")
namelist = df.values.tolist() #將數據轉換成列表
# 將數據轉換成列表后， namelist=[[101, "鄧**","MULA 商社"], ]
k = 0
data = [["" for i in range(2)] for j in range(len(namelist))]
for item in namelist: #初始化鏈表結構
data[k][0] = item
data[k][1] = k+1
k+=1
head = 0
n = length = len(data) #每次抽取時剩余人數
namelist1 = []
namelist2 = []
for i in range(n//2+1): #生成 MULA 商社 1 班名單
t = random.randint(0,length-1)
p = head
q = data[p][1]
if t == 0:
namelist1.append(data[head][0])
else:
while t != 1: #從頭節點開始查找第 t 個節點所在位置
p = q
q = data[p][1]
t = t-1
namelist1.append(data[q][0])
length = length-1
#生成 MULA 商社 2 班名單及將生成的兩份名單保存成電子表格文件，代碼略
26．小明來到探險島尋寶，島上共有N個寶藏（標號為0至N-1）。每個寶藏有一條路連接下一個寶藏，寶藏號和下一個寶藏號使用鏈表存儲。小明想知道，從其中一個寶藏出發，最多可以找到多少個寶藏。
例如，共有5個寶藏，輸入“1，3，4，4，1，”表示0~4各寶藏點連接的下一個寶藏依次是：1，3，4，4，1（如下表）。則最多可以找到4個寶藏，路徑為：0號1號3號4號。
寶藏號 0 1 2 3 4
下一個寶藏號 1 3 4 4 1
程序代碼如下：
s=input("請輸入寶藏連接的情況：")
t=0;c="";a=[]
for i in s:
if i!=",":
c+=i
else:
a.append([t,int(c)])
c=""
①
max=0
for head in range(0,t): #枚舉尋找寶藏起點
g=[]
p=head
while p not in g:
g.append(p)
②
if len(g)>max :
③
print(max)
（1) 若有 4 個寶藏，且每個寶藏的連接情況為：2,0,0,1，那么小明最多可以挖到的寶藏數是 。
（2) 請將代碼補充完整。
參考答案：
1．C
2．C
3．D
4．D
5．C
6．D
7．A
8．C
9．B
10．B
11．D
12．A
13．A
14．C
15．D
16．動態 靜態
17．53
18．2
19．20
20．3
21．正確
22．A menu[i][2]!=0 sal-=menu[bh][2] p=lis[p][1]
23．2 a[p][0]%3==0: list[head][2] i a[a[p][1]][2]
24．k+=1 或 k=k+1
n=len(pat) pat[head][2]<80 pat[i][3]=pat[p][3] q=p
25．data[k-1][1] = -1 head = data[head][1] 或head = data[p][1] data[p][1] = data[q][1]
26．t+=1 p=a[p][1] max=len(g) 4

展開更多......

收起↑