資源簡介

第二章 2.2 鏈 表
一、選擇題(每小題列出的四個備選項中只有一個是符合題目要求
的，不選、多選、錯選均不得分)
1.下列有關鏈表的說法，正確的是 ( )
A.可快速訪問任何一個數據元素
B.插入、刪除操作無需移動數據元素
C.鏈表占用固定的存儲空間
D.鏈表不一定含有頭指針
2. 已知一個有7個節點的單向鏈表，設有頭指針head 和尾指針tail, 如 圖所示，下列操作需要遍歷多個節點的是 ( )
列表索引數據域指針域
0 1 head → 2 tail → 3 4 5 6 i 5
n 0
m 4
g -1
0 6
n 3
r 1
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
3. 由 n個節點鏈接成的單向鏈表如圖所示，其中head 為頭指針，現要
刪除鏈表中的尾節點(end所指節點),下列操作正確的是 ( )
end
head→ datal next data2 next data3 next datan -1
A.將end所指節點的數據值改為0
B.將end所指節點的next值改為head
C.將end所指節點的前驅節點的next值改為0
D.將end所指節點的前驅節點的next值改為-1
4.下列關于鏈表的敘述，正確的是 ( )
A.線性鏈表中的各元素在存儲空間中的位置必須是連續的
B.線性鏈表中的表頭元素一定存儲在其他元素的前面
C.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但
表尾元素一定存儲在其他元素的后面
D.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且
各元素在存儲空間中的存儲順序也是任意的
5.Python中可以使用二維列表來模擬雙向鏈表，用包含三個元素的 列表來表示一個節點，其中第一個元素存儲數據，第二、三個元素 分別存儲前驅節點的地址和后繼節點的地址(-1表示無前驅節點 或后繼節點)。下列代碼創建了一個有4個節點的升序(從小到大)
雙向鏈表a:
a=[[12,2,3],[18,3,- 1],[10,- 1.0].[14,0. 1]]
head=2
現使用append()方法插入新數據17,并使a依舊保持升序，則插入
后的列表a是 ( )
A.[[12,2,3],[18,3,- 1],[10,- 1.0].[14,0,1],[17,3,1]]
B.[[12,2,3],[18,3,- 1],[10,- 1,0].[14,0,4],[17,3,1]]
C.[[12,2,3],[18,4,- 1],[10,- 1.0].[14,0,4],[17,3,1]]
D.[[12,2,3],[18,4,- 1],[10,- 1.0].[14,0,1],[17,3,1]]
6. 有單向鏈表如圖所示，在data2 與data3 之間插入一個新節點data4 (p指向data2,r指向data4。 列表data記錄鏈表數據域，列表next記
錄各節點的指針域),則下列執行步驟及順序正確的是 ( )
(
datal
next
data2
next
data3
next
data4
next
P
)
①next[p]=next[r]②next[r]=p ③next[p]=r ④next{r}=-1
⑤ next[p]=-1 ⑥next[r]-next[p]
A.⑤②④ B.⑤② C.①④ D.⑥③
7. 某Python程序如下：
s=[[8,2],[5,-1],[6,1],[9,0]]
p=head=0
while s[p][1]!=head:
print(s[p][0],end="->")
p=s[p][1]
print(s[p][0])
程序運行后，輸出的結果是 ( )
A.8->6->5->9 B.9->5->6->8
C.8->5->6->9 D.9->6->5->8
8. 某Python程序如下：
a=[[7,1],[8,2],[9,- 1]]
head=0
p=1
a.append([6,a[p][1]I)
a[p][1]=len(a)- 1
程序運行后，下列說法正確的是 ( )
A.a[2][0]的值為6,單向鏈表a的尾節點數據值為6
B.a[2][0]的值為9,單向鏈表a的尾節點數據值為6
C.a[3][1]的值為2,單向鏈表a的尾節點數據值為9
D.a[3][1]的值為-1,單向鏈表a的尾節點數據值為9
二、非選擇題
9. 雙向鏈表也叫雙鏈表，它的每個數據都有兩個指針，分別指向前驅 節點和后繼節點。在Python中用二維列表來模擬雙向鏈表，用包 含3個元素的列表來表示每一個節點，其中第一個元素存儲數據， 后兩個元素分別存儲指向前驅節點和后繼節點的指針。若沒有前 驅或后繼節點則對應的指針值為-1。下列程序產生了一些兩位數 的隨機正整數，并依次存儲到雙向鏈表a中。現要求刪除其中值為
偶數的節點，請在劃線處填入合適的代碼。
import random
a= [ ]
head=- 1
for i in range(8):
node=[ ① ,head,- 1]
a.append(node)
if head!=- 1:
a[head][2]=i
head= ②
p=head=0
while p!=- 1:
if a[p][0]%2==0:
if ③ :
a[a[pl[1]][2]=a[p][2]
if a[p][2]!= -1:
a[a[pl[2]][1]=a[p][1]
if head==p:
head= ④
p=a[p][2]
10. 山頂上有10個圓形排列的洞， 一只狐貍和一只兔子各住一個洞 狐貍總想吃掉兔子。 一天兔子對狐貍說：“你想吃我有一個條件， 先把洞從1～10編上號，你先到1號洞找我；第二次隔1個洞(即3 號洞)找我，第三次隔2個洞(即6號洞)找我，之后以此類推，次數 不限。但狐貍從早到晚進進出出了1000次，仍沒有找到兔子。請問兔子可能躲在哪個洞里
實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
hone=[]
n=10
m=1000
#構造一個循環鏈表，并給n 個洞編號，設置洞的初始標志為0
#鏈表的節點樣式為：[洞的標志，洞的編號]
fori in range(n- 1):
hone.append([0,i+1])
①
#狐貍開始找兔子，將進入過的洞標志改為1,尋找m 次結束
head=0 #第一個洞的位置
k=head
hone[0][0]=1
for i in range(1,m):
for j in range(1,i+2):
②
hone[k][0]=1
#輸出標志仍為0的洞，即兔子可能藏身地點
for i in range(len(hone)):
if hone[i][0]==0:
print("兔子可能躲在第"+ ③ +"號洞")
11.傳話游戲。 一個班級中的n 個同學(編號為1～n) 正在玩一個游 戲，每人在紙條上隨機寫一個1～n 之間的數字。接下來，每位同 學傳一句話給紙條上編號對應的另一位同學，收到這句話的同學 又繼續將這句話傳給自己紙條上編號對應的同學。問在游戲的過程中，有多少人會收到自己傳出去的話
(1)以五位同學為例，每人的信息和紙條信息如表所示，有 位同學能收到自己傳出去的話。
同學本人編號 1 2 3 4 5
紙條上的編號 5 4 2 1 2
(2)根據抽象與建模，若編程解決該問題，則適合使用 (選填：數組/鏈表/隊列)來存儲和處理數據。
(3)實現上述功能的Python程序如下，請在劃線處填入合適的 代碼。
(4)若將程序加框處代碼改為cntimport random
n=int(input(”輸入班級人數：")
#隨機生成紙條信息
zhitiao=[random.randint(1,n)fori in range(n+1)]
ans=0
fori in range(1.n+1):#對每個同學進行傳話過程的模擬
cnt=1 #cnt存儲傳話經過的人數
p=i
while zhitiaolpl!=i and cnt<=n:
①
cnt+=1
if zhitiao[p] == i:
②
print(ans)
12. 下列Python程序的功能是使用類的方法創建一個鏈表，并在鏈表
中間插入一個新節點。
class Nodei
def init (self.data=None):
self.data=data
self.next=None
class Link list( )
def init (self):
self.head=None
def print list(self):
ptr=self.head
while ptr:
print(ptr.data)
ptr=ptr.next
def insert node(self,pre node,newdata):
if pre node==None:
print("插入位置不對")
else:
new node=Node(newdata)
①
②
link=Link list()
link.head=Node(1)
n2=Node(5)
n3=Node(9)
link.head.next=n2
n2.next=n3
link.print list()
print("新的鏈表")
link.insert node(n2,7)
③ #打印鏈表
請回答下列問題：
(1)操作后的新鏈表中的節點是
(2)請在劃線處填入合適的代碼。

展開更多......

收起↑