資源簡介

數組和鏈表專項習題
選擇題
在一個長度為n的數組中的第i個元素（1<=i<=n）之前插入一個新元素時，需向后移動的元素個數為（ ）
A.i B.n-i C.n-i+1 D.n-i-1
2.在單向鏈表中，增加頭指針的目的是（ ）
A.標識表節點中首節點的位置
B.算法實現上的方便
C.使單向鏈表至少有一個節點
D.說明單向鏈表是線性表的鏈式存儲實現
3.在一個包含n（n>1）個節點的單鏈表上，沒有頭和尾兩個指針，下列操作需要遍歷多個節點的是（ ）
A.刪除該鏈表中的第一個節點
B.刪除該鏈表中的最后一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
4.某python程序段如下：
a=[28,29,79,14,24,43]
m=int(input(“請輸入一個整數：”))
pos=-1
for i in range(len(a)):
if a[i]>m:
if pos==-1 or a[i]pos=i
運行該程序段，若輸入40，變量pos的值是（ ）
A.-1 B.2 C.3 D.5
5.有下列python程序段：
a=[3,7,8,2,19,10,16,12]
n=len(a)
for i in range(2):
k=i
for j in range(i+1,n):
if a[k]k=j
if i!=k:
a[i],a[k]=a[k],a[i]
下列說法正確的是（ ）
程序段執行后，數組a中的元素為[19,16,8,2,3,10,7,12]
程序段執行后，數組a中的元素為[3,2,8,7,19,10,16,12]
程序段執行后，變量k的值為7
程序段執行后，數組a中數據元素發生位置變化的有2個
6.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
則程序執行后，鏈表a有幾個節點（ ）
A.1 B.2 C.3 D.4
7.有如下python程序段：
r=0
for e in a:
if e%3!=0:
a[r]=e
r+=1
del a[r:]
已知a的初始值為[9,1,2,3,3,5,3,3,4,6]，則執行上述代碼段后，a的值為（ ）
A.[9,1,2,3,3,5,3,3,4,6] B.[1,2,5,4]
C.[9,3,3,3,3,6] D.[9,1,2,5,4,6]
8.有如下python程序段：
for i in range(1,1001):
flag=True
for j in range(3):
if i%a[2*j]!=a[2*j+1]:
flag=False
if flag：
ans=i
break
已知列表a=[3,1,5,1,7,3]，該段程序執行后，變量ans的值為（ ）
A.31 B.41 C.136 D.137
9.有如下Python程序段：
def rotate(a,r):
right_len=len(a)-r
for i in range(r-1,-1,-1):
temp=a[i]
for j in range(i+1,i+right_len+1):
a[j-1]=a[j]
a[i+right_len]=temp
return a
則當執行語句print(rotate([1,2,3,4,5,6,7,8],3))時，程序輸出值為
（ ）
A.[1,2,3] B.[4,5,6,7,8]
C.[1,2,3,4,5,6,7,8] D.[4,5,6,7,8,1,2,3]
10.有如下python程序段：
n=6
a=[[0]*n for i in range(n)]
for i in range(n):
for j in range(i+1)：
if j==0 or j==i:
a[i][j]=1
else:
a[i][j]=a[i-1][j-1]+a[i-1][j]
則程序執行后a[4]的值為（ ）
A.[1,3,3,1] B.[1,4,6,4,1]
C.[1,4,6,4,1,0] D.[1,5,10,10,5,1]
11.有如下python程序段：
a=[[1,1],[2,2],[3,3],[4,-1]]
head=0
cur=a[head][1]
a[head][1]=-1
while cur!=-1:
next_=a[cur][1]
a[cur][1]=head
head,cur=cur,next_
則程序執行后，a的值為（ ）
A.[[1,1],[2,2],[3,3],[4,-1]]
B.[[1,-1],[2,0],[3,1],[4,2]]
C.[[4,1],[3,2],[2,3],[1,-1]]
D.[[4,-1],[3,0],[2,1],[1,2]]
12.有如下python程序段：
n=6
a=[[0 for i in range(n)]for j in range(n)]
for s in range(1,(n+1)//2+1):
for i in range(s-1,n-s+1):
a[i][s-1]=a[i][n-s]=s
a[s-1][i]=a[n-s][i]=s
for i in range(n):
for j in range(n):
print(f”{a[i][j]:3}”,end=””)
print( )
則程序執行后輸出的結果為（ ）
B.
C. D.
非選擇題
已知1班、2班各有m位同學，要在兩個班中挑選身高最高的n位同學參加合唱隊。小明編寫了如下程序：
a=[0]*m
b=[0]*m
hc=[0]*m
#讀取兩個班同學的身高數據，分別存儲在數組a、數組b中；
分別將兩個班同學的身高數據進行降序排列，代碼略。
m1=0
m2=0
for i in range(n):
if a[m1]>=b[m2]:
hc[i]=a[m1]
____①_______
else:
hc[i]=b[m2]
_____②_______
print(“身高前n位的值是：”，hc)
學校組織藝術比賽，每班可派1位選手參賽。班里有10位多才多藝的學生想要參加，老師采用下列方法來進行選擇：10位學生每人選取1個編號，分別是1、2、3、…、10；學生按照編號由小到大的順序圍成一個圓圈，從編號為1的學生開始報數，報數到3的學生出圈，即被淘汰；下一個編號為4的學生
重新從1開始報數，報數到3的學生繼續出圈……以此類推，由最后剩下的同學參加比賽。
類是用來描述具有相同的屬性和方法的對象的集合，它定義了每個對象所共有的屬性和方法，Python中使用class關鍵字來定義類。小李編寫了程序計算最終能留下的“幸運編號”。
他定義了兩個類來協調表示單向鏈表，即單向鏈表的節點類（LinkNode）和單向鏈表類（LinkList），并在LinkList類中定義了circle( )方法來構造一個長度為n的循環單向鏈表。然后模仿報數的過程，逐次把報數為3的學生節點從循環鏈表中刪除，直到只剩下一個節點為止。
實現上述功能的python程序如下，請在劃線處填入合適的代碼。
class LinkNode:
def_init_(self,data_,next_=none):
self.data=data_
self.next=next_
class LinkList:
def _init_(self): #初始化空鏈表
self.head=None
#構造一個長度為n的循環單向鏈表
def circle(self,n):
self.head=LinkNode(n) “head的節點編號為n”
p=self.head
for i in range(1,n):
p.next=LinkNode(i)
p=p.next
p.next=_____①______
n,m=10,3
a=LinkList( )
circle(n)
pre=a.head #注意head的節點編號為n
while pre!=pre.next:
for i in range(1,m): #報數[1,m-1]的人留下
pre=______②_____
pre.next=______③________ “報數m的人離開（刪除該節點）”print(f”幸運編號為：{pre.data}”)數組和鏈表專項習題
選擇題
在一個長度為n的數組中的第i個元素（1<=i<=n）之前插入一個新元素時，需向后移動的元素個數為（ C ）
A.i B.n-i C.n-i+1 D.n-i-1
解析：選C，在數組中某個位置插入一個新的數據時，必須先將該位置及其后的所有數據向后移動一個位置。第i個元素的下標為i-1，故需要向后移動的元素個數為n-i+1。
2.在單向鏈表中，增加頭指針的目的是（B）
A.標識表節點中首節點的位置
B.算法實現上的方便
C.使單向鏈表至少有一個節點
D.說明單向鏈表是線性表的鏈式存儲實現
解析：選B，每個鏈表必定有一個頭指針，以實現對鏈表的引用和邊界處理，即算法實現上的方便。
3.在一個包含n（n>1）個節點的單鏈表上，沒有頭和尾兩個指針，下列操作需要遍歷多個節點的是（ B ）
A.刪除該鏈表中的第一個節點
B.刪除該鏈表中的最后一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
解析：選B,鏈表節點的刪除，并沒有將元素從列表中刪除，而僅僅
修改了節點指針域的值，通過將被刪除節點的前驅節點和其后繼節點
直接相連的方式實現。題目中描述的該單鏈表中沒有頭指針和尾指針，
此時若要刪除該鏈表中的最后一個節點需遍歷多個節點。
4.某python程序段如下：
a=[28,29,79,14,24,43]
m=int(input(“請輸入一個整數：”))
pos=-1
for i in range(len(a)):
if a[i]>m:
if pos==-1 or a[i]pos=i
運行該程序段，若輸入40，變量pos的值是（ D ）
A.-1 B.2 C.3 D.5
解析：選D，改題通過遍歷數組a中的元素，找出比40大的元素a[i]并且要滿足pos==-1或a[i]5.有下列python程序段：
a=[3,7,8,2,19,10,16,12]
n=len(a)
for i in range(2):
k=i
for j in range(i+1,n):
if a[k]k=j
if i!=k:
a[i],a[k]=a[k],a[i]
下列說法正確的是（ A ）
程序段執行后，數組a中的元素為[19,16,8,2,3,10,7,12]
程序段執行后，數組a中的元素為[3,2,8,7,19,10,16,12]
程序段執行后，變量k的值為7
程序段執行后，數組a中數據元素發生位置變化的有2個
解析：選A，找出數組中2個最大的數，并讓其與前2個數組元素進行位置的交換。
6.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
則程序執行后，鏈表a有幾個節點（C ）
A.1 B.2 C.3 D.4
解析：選C，程序創建了一個擁有4個節點的鏈表a，剛開始其頭指針head值為3，則頭節點為a[3]。語句head=a[head][1]的作用是刪除頭節點，并讓頭指針指向新的頭節點a[0]。故程序執行后，鏈表a的節點數量為3。
7.有如下python程序段：
r=0
for e in a:
if e%3!=0:
a[r]=e
r+=1
del a[r:]
已知a的初始值為[9,1,2,3,3,5,3,3,4,6]，則執行上述代碼段后，a的值為（ B ）
A.[9,1,2,3,3,5,3,3,4,6] B.[1,2,5,4]
C.[9,3,3,3,3,6] D.[9,1,2,5,4,6]
解析：選B，該程序的功能是刪除數組a中值為3的倍數的元素，其中r表示剩余數組元素的右邊界，若e不是3的倍數，則要保留e，用其覆蓋a[r]，同時讓r右移一位，最后刪除a[r:]即可。
8.有如下python程序段：
for i in range(1,1001):
flag=True
for j in range(3):
if i%a[2*j]!=a[2*j+1]:
flag=False
if flag：
ans=i
break
已知列表a=[3,1,5,1,7,3]，該段程序執行后，變量ans的值為（ A）
A.31 B.41 C.136 D.137
解析：選A，改題關鍵點在i%a[2*j]!=a[2*j+1]，分別把i和j的值代進去，發現當i的值為31和136時，flag的值都為True，但后面的break語句決定了ans只會被賦值一次，所以ans=31。
9.有如下Python程序段：
def rotate(a,r):
right_len=len(a)-r
for i in range(r-1,-1,-1):
temp=a[i]
for j in range(i+1,i+right_len+1):
a[j-1]=a[j]
a[i+right_len]=temp
return a
則當執行語句print(rotate([1,2,3,4,5,6,7,8],3))時，程序輸出值為
（ D ）
A.[1,2,3] B.[4,5,6,7,8]
C.[1,2,3,4,5,6,7,8] D.[4,5,6,7,8,1,2,3]
解析：該題選D，該程序通過依次將左側元素右移len(a)-r位，總共移動r輪，實現了將數組a向左旋轉r個位置的功能，當r=3時，返回的列表a=[4,5,6,7,8,1,2,3]。
10.有如下python程序段：
n=6
a=[[0]*n for i in range(n)]
for i in range(n):
for j in range(i+1)：
if j==0 or j==i:
a[i][j]=1
else:
a[i][j]=a[i-1][j-1]+a[i-1][j]
則程序執行后a[4]的值為（ C ）
A.[1,3,3,1] B.[1,4,6,4,1]
C.[1,4,6,4,1,0] D.[1,5,10,10,5,1]
解析：選C，該程序的功能是生成n行楊輝三角形，使用二維數組a來存儲楊輝三角的各個元素值，初始化為0，之后根據規則依次生成各行的元素。a[4]即為第5行的元素。
11.有如下python程序段：
a=[[1,1],[2,2],[3,3],[4,-1]]
head=0
cur=a[head][1]
a[head][1]=-1
while cur!=-1:
next_=a[cur][1]
a[cur][1]=head
head,cur=cur,next_
則程序執行后，a的值為（ B ）
A.[[1,1],[2,2],[3,3],[4,-1]]
B.[[1,-1],[2,0],[3,1],[4,2]]
C.[[4,1],[3,2],[2,3],[1,-1]]
D.[[4,-1],[3,0],[2,1],[1,2]]
解析：選B，該程序通過修改各個節點的指針值，來實現逆置鏈表a的功能，程序運行結束后head的值為3。
12.有如下python程序段：
n=6
a=[[0 for i in range(n)]for j in range(n)]
for s in range(1,(n+1)//2+1):
for i in range(s-1,n-s+1):
a[i][s-1]=a[i][n-s]=s
a[s-1][i]=a[n-s][i]=s
for i in range(n):
for j in range(n):
print(f”{a[i][j]:3}”,end=””)
print( )
則程序執行后輸出的結果為（ A ）
B.
C. D.
解析：選A，由最外層for循環可知，變量s的值從1到3，內層for循環限制了變量i的范圍，使其左右邊界逐步向中間縮小。程序的功能是從外到內生成一個值為s的環。
非選擇題
已知1班、2班各有m位同學，要在兩個班中挑選身高最高的n位同學參加合唱隊。小明編寫了如下程序：
a=[0]*m
b=[0]*m
hc=[0]*m
#讀取兩個班同學的身高數據，分別存儲在數組a、數組b中；
分別將兩個班同學的身高數據進行降序排列，代碼略。
m1=0
m2=0
for i in range(n):
if a[m1]>=b[m2]:
hc[i]=a[m1]
____①_______
else:
hc[i]=b[m2]
_____②_______
print(“身高前n位的值是：”，hc)
解析：①處填m1=m1+1,②處填m2=m2+1。根據題目要求要把數組a和數組b中最大的n個身高數據存入數組hc中，當選擇數組a的數據存儲后，對應數組a的下標m1后移；同理，當選擇數組b的數據存儲后，對應數組b的下標m2后移。
2.學校組織藝術比賽，每班可派1位選手參賽。班里有10位多才多藝的學生想要參加，老師采用下列方法來進行選擇：10位學生每人選取1個編號，分別是1、2、3、…、10；學生按照編號由小到大的順序圍成一個圓圈，從編號為1的學生開始報數，報數到3的學生出圈，即被淘汰；下一個編號為4的學生重新從1開始報數，報數到3的學生繼續出圈……以此類推，由最后剩下的同學參加比賽。
類是用來描述具有相同的屬性和方法的對象的集合，它定義了每個對象所共有的屬性和方法，Python中使用class關鍵字來定義類。小李編寫了程序計算最終能留下的“幸運編號”。他定義了兩個類來協調表示單向鏈表，即單向鏈表的節點類（LinkNode）和單向鏈表類（LinkList），并在LinkList類中定義了circle( )方法來構造一個長度為n的循環單向鏈表。然后模仿報數的過程，逐次把報數為3的學生節點從循環鏈表中刪除，直到只剩下一個節點為止。
實現上述功能的python程序如下，請在劃線處填入合適的代碼。
class LinkNode:
def_init_(self,data_,next_=none):
self.data=data_
self.next=next_
class LinkList:
def _init_(self): #初始化空鏈表
self.head=None
#構造一個長度為n的循環單向鏈表
def circle(self,n):
self.head=LinkNode(n) “head的節點編號為n”
p=self.head
for i in range(1,n):
p.next=LinkNode(i)
p=p.next
p.next=_____①______
n,m=10,3
a=LinkList( )
circle(n)
pre=a.head #注意head的節點編號為n
while pre!=pre.next:
for i in range(1,m): #報數[1,m-1]的人留下
pre=______②_____
pre.next=______③________ “報數m的人離開（刪除該節點）”
print(f”幸運編號為：{pre.data}”)
解析：①處填self.head，②處填pre.next，③處填pre.next.next。
該題要構造循環鏈表，需要將尾節點的后繼指針指向頭節點，形成一個閉環，故第①空答案為self.head；從第一個人開始報數，報數[1,m-1]的人留下，報數m的人離開。pre表示當前節點的前驅節點的下標，用語句pre=pre.next指向下一個節點，pre.next=pre.next.next表示刪除pre的后繼節點（即當前節點）。程序執行后輸出“幸運編號為：4”。

展開更多......

收起↑