資源簡介

2023-2024學年高二上學期浙教版(2019)選修一2.2 鏈表
一、選擇題
1．如下圖所示的鏈表：
假如要查找元素11，共需遍歷的次數為（ ）
A．5 B．6 C．7 D．8
2．尋寶游戲中通過一個線索找到下一個線索，最好用下列數據組織形式中的（ ）來表示。
A．數組 B．鏈表 C．棧 D．隊列
3．小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。

圖a 圖b
若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上海”所在節點的next值賦為“杭州”所在節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上海”所在節點的next值
④“杭州”所在節點的next值賦為-1
鏈表更新順序正確的是（ ）
A．③② B．③① C．①④ D．②④
4．把單向鏈表第1個節點的位置口叫奇數位置，第2個節點的位置叫偶數位置，以此類推。現將所有偶數位置的節點依次取出后，放在所有奇數位置節點的后面。實現該功能的 Python代碼段如下，方框中應填入的正確代碼為（ ）
a=[['a',1],['b',2]. ['c',3],['d',4],[ 'e',-1]]
head=odd=0 #鏈表 a頭節點指針是 head
evenhead=even=a[head][1]
while even!=-1 and a[even][1]!=-1:
a[odd][1]=evenhead #將鏈表連接在奇數鏈表之后
A． B． C． D．
5．鏈表中的節點通常包含哪兩部分（ ）
A．數據域和控制域 B．數據域和指針域 C．指令域和地址域 D．標志域和內容域
6．有如下 Python程序，用于判斷鏈表是否為回文鏈表（回文鏈表是指正序遍歷和逆序遍歷得到的結點順序一致的鏈表），則劃線處代碼是（ ）
a=[[1,1],[2,2],[8,3],[2,4],[1,-1]]
st=[];head=0;flag=True
slow, fast=head, head
while ① :
st.append (a[slow][o])
slow=a[slow][1]
fast=a[a[fast][1]][1]
if ② :
slow=a[slow][1]
while slow!=-1:
if st.pop () !=a[slow][0]:
flag=False
slow=a[slow][1]
if flag:
print("是回文鏈表!")
else:
print("不是回文鏈表!")
A．①fast!=-1 or a[fast][1]!=-1 ②fast!=-1 B．①fast!=-1 or a[fast][1]!=-1 ②a[fast][1]!=-1
C．①fast!=-1 and a[fast][1]!=-1 ②fast!=-1 D．①fast!=-1 and a[fast][1]!=-1 ②a[fast][1]!=-1
7．有如下圖所示的單向鏈表：
從頭指針head指向的節點開始查找數據元素“5”，并刪除該節點，下列說法正確的是（ ）
A．共需查找3次 B．刪除數據元素“5”的節點，后續節點需要移動3次
C．頭指針head將指向數據元素“7”的節點 D．操作完成后，鏈表中數據元素的個數為6個
8．創建一個空鏈表時，通常會設置什么來表示鏈表的起始（ ）
A．尾指針 B．頭指針指向一個空節點
C．頭指針指向NULL或-1 D．無需設置特殊標記
9．一頭指針 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．①②③
10．有如下 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．②③①
11．用兩個列表a、b分別保存單向鏈表中的數據區域和指針區域。如下圖所示，在節點x與節點y之間插入一個新節點，操作步驟正確的是（ ）
①b[i]= b[y] ②b[i]= b[x] ③b[y]= i
④b[x]=i ⑤b[i]= x ⑥b[i]= y
A．③⑥ B．④② C．①③ D．②④
12．使用列表d模擬鏈表結構（節點數大于0），每個節點包含數據區域和指針區域，h為頭指針。下列程序段實現了刪除數據區域為奇數的節點。
q=p=h=2
while p！=-1：
if d[h][0]%2==1：
（1）
q=p=h
elif d[p][0]%2==1：
（2）
p=d[p][1]
else：
q=p
p=d[p][1]
劃線處可選代碼如下：
①h=d[h][1] ②p=d[p][1] ③d[p][1]=d[q][1] ④d[q][1]=d[p][1]
下列選項中，代碼順序正確的是（ ）
A．①③ B．②③ C．①④ D．②④
13．利用列表模擬某單向非循環鏈表a(其中可能存在已被刪除的節點），下列程序運行完畢后，變量p肯定表示尾節點的節點位置的是（　　）
A． B． C． D．
14．如果一個鏈表的頭指針為head，要訪問鏈表中第i個節點，需要進行幾次指針移動（ ）
A．i次 B．i-1次 C．i+1次 D．無法確定，取決于鏈表長度
15．使用列表a模擬鏈表結構（節點數大于0），每個節點包含數據區域和指針區域，head為頭指針，如a=[["Z"，2]，["J"，0]，["H"，-1]，["S"，1]]，head=3，現要修改該鏈表各節點的鏈接關系，修改結果為a=[["Z"，1]，["J"，3]，["H"，0]，["S"，-1]]，head=2。實現該功能的程序段如下，方框中應填入的正確代碼為（ ）
q=head;p=-1
while q!=-1：

head=p
A． a[q][1]=p nxt=a[q][1] p=q q=nxt B． a[q][1]=p nxt=a[q][1] q=nxt p=q C． nxt=a[q][1] a[q][1]=p q=nxt p=q D．nxt=a[q][1] a[q][1]=p p=q q=nxt
A．A B．B C．C D．D
二、填空題
16．在數據結構中， 是一種允許在任何位置插入和刪除元素的數據結構。
三、操作題
17．現有n條編碼（每條編碼占1行，編號1到n）存儲于某文本文件中，使用字符“：”對每條編碼進行分隔，形成若干段，如圖a所示。任一條編碼的每一段均以十六進制形式表示（字母大寫），最左段編碼對應的十六進制數大于0。編寫一個Python程序，實現對文件中所有編碼的升序排序。
實現對編碼排序的方法如下：排序處理前，需對每一條編碼按從右到左進行段編號，如圖b所示。首先從編號為1的段開始，根據每條編碼在第1段的內容，對編碼編號進行排序，再按編號為2的段進行排序，……，直至完成各段編碼的處理。
圖a 圖b
請回答下列問題：
（1）各段排序的加工遍數為該段所對應編碼的最長位數。現若僅對圖b中所示的前4條編碼進行排序，第1段編碼的部分加工過程如下表所示，則第4遍加工完成后的編碼編號次序為 （單選，填字母。A．3->1->2->4 /B．1->3->4->2）。
編碼比較（從右向左第i位） 加工結果（編碼編號次序）
原始內容 AE F3B AD 7AA6 1->2->3->4
第1遍加工 7AA6 F3B AD AE 4->2->3->1
第2遍加工 F3B 7AA6 AD AE 2->4->3->1
第3遍加工 AD AE 7AA6 F3B 3->1->4->2
（2）定義如下pick（hex，i）函數，函數功能是返回十六進制數hex從右向左第i位（1≤i）的值。
def pick（hex，i）：
dic= {'0'：0，'1'：1，'2'：2，'3'：3，'4'：4，'5'：5，'6'：6，'7'：7，'8'：8，'9'：9，'A'：10，'B'：11，'C'：12，'D'：13，'E'：14，'F'：15}
if i>len（hex）：
return 0
t= return dic[t]
為實現該函數功能，方框內的語句應修改為：
（3）實現第k段編碼處理功能的Python程序如下，程序中用到的列表函數與方法如圖c所示，請在程序中劃線處填入合適的代碼。
函數與方法 功能
w.append（x） 在列表w末尾添加元素x
w.pop（x） 將列表w中索引為x的元素從w中刪除
圖c
def process（k，lenk）： #根據第k段編碼從右向左第i位的值，進行升序排序
for i in range（1，lenk+1）：
bucket=[]
for j in range（16）： # bucket[i]（0≤j≤15）列表存放值為j的編碼編號
bucket.append（[]）
p=nex[Head]
while p！=-1：
①
bucket[t].append（p）
p=nex[p]
p=Head
for j in range（16）：
while ② :
t=bucket[i][0]
nex[p]=t；p=t；nex[p]=-1
bucket[j].pop（0）
``` 讀取1至n條編碼數據，各編碼分段處理后依次存入列表data的data[1]至data[n]中，
圖b中第1、2條編碼分別存放在data[1]，data[2]中，data-[[]，[76A'，'0'，'9B'，'AE']，['9F'，'7A7'，'F3B']，……]，代碼略 ```
nex = [-1]*（n+1）
Head=0；nex[Head]=1；maxk= 0
for i in range（1，n+1）：
nex[i] = i+1
maxk = max（maxk，len（data[i]））
nex[n]=-1
res =[] #res 列表中存放已排序的編碼編號
for k in range（1，maxk+1）：
pre= Head；cur=nex[Head]；lenk=0
while cur！=-1：
if k <= len（data[cur]）：
lenk = max（lenk，len（data[cur][-k]））
pre=cur
else：
res.append（cur）
③
cur=nex[cur]
process（k，lenk）
# 按升序輸出處理后的所有編碼，代碼略
18．某音樂平臺的曲庫中共有n首（編號為0~n-1）歌曲，每首歌曲初始的熱度值均為0。歌曲列表分為熱榜區和非熱榜區，熱榜區按熱度值降序排列，若熱度值相同則按歌曲編號升序排列；非熱榜區按歌曲編號升序排列，某時刻的榜單如圖a所示。用戶對歌曲的操作會改變其熱度值，規則如圖b所示。
初始狀態時，n首歌曲都在非熱榜區，若某歌曲的熱度值大于等于預設的閾值時，則將其移至熱榜區；相反，若熱榜區中某歌曲的熱度值小于預設的閾值時，則將其移至非熱榜區。
現有一段時間內的操作記錄存儲在"operation.csv"文件中，部分數據如圖c所示，編寫Python程序模擬兩個榜區歌曲的實時更新功能。

圖a 圖b 圖c
（1）若該曲庫中有三首歌曲，編號分別為0、1、2，初始熱度值均為0，熱榜閾值為3。經過圖c所示的若干個操作后，最終熱榜區顯示的歌曲編號依次為 。
（2）定義函數printsongs（headA,headB），其功能是輸出某次操作后songs中的歌曲榜單信息。如圖a所示的歌曲榜單，該曲庫中共有10首歌。此時headA和headB的值分別為6和0；編號8、9的歌曲數據在列表中分別表示為songs[8]、songs[9]，其值分別為[8,-2,"懸溺",-1]、[9,8,"如果這就是愛",0]。
函數printsongs代碼如下，請在劃線處填入合適的代碼。
def printsongs（headA,headB）:
print（"###熱榜歌曲###"）
p=headA
while p!=headB:
print（"歌曲編號:",songs[p][0],"歌曲名:",songs[p][2],"熱度值:",songs[p][1]）
print（"###非熱榜歌曲###"）
while p!=-1:
#其他代碼略
（3）實現曲庫從非熱榜區移至熱榜區或更新熱榜區的部分Python程序如下，請在劃線處填入合適的代碼。
'''
讀取曲庫和操作數據，分別存入列表songs和op中。songs中的每個元素包含三個數據項，分別對應歌曲的編號、熱度值、名稱。op中每個元素包含兩個數據項，分別對應歌曲編號和操作編號。代碼略
'''
inc=[0,1,3,-5] #操作編號對應的數值變化
val=int（input（'請輸入熱榜閾值'））#閾值設置
for i in range（0,len（songs）-1）:
songs[i].append（i + 1）
songs[len（songs）-1].append（-1）
headA,headB=0,0
for x in op:
p,q=headA,headA
while q!=-1 and songs[q][0]!=x[0]:
p=q
q=songs[q][3]
if q==-1:
print（"未找到該歌曲"）
else:
tmp=songs[q][1]#修改前的熱度值
songs[q][1]+=① #修改后的熱度值
if（tmp=val） or（songs[q][1]>=tmp>=val）:#上熱榜或升榜
px, py=headA,headA
while py!= 1 and（songs[py][1]>songs[q][1]or ② ）:
px=py
py=songs[py][3]
if q==headB:
headB=songs[headB][3]
if py != q:
songs[p][3]= songs[q][3]
③
if py == headA or headA == headB:
headA=q
else:
songs[px][3]=q
printsongs（headA,headB）#輸出當前操作后的榜單
#其他情況代碼略
參考答案：
1．B
2．B
3．A
4．A
5．B
6．C
7．D
8．C
9．A
10．D
11．D
12．C
13．B
14．B
15．D
16．鏈表（或LinkedList）
17． A hex[-i]或hex[len（hex）-i] t=pick（data[p][-k], i） len（bucket[i]）>0或len（bucket[i]）>=1或bucket[i]！=[] nex[pre]=nex[cur]
18． 0，2 p= songs[p][3] inc[x[1]] songs[py][1]==songs[q][1] and songs[py][0]

展開更多......

收起↑