数组和链表专项习题
选择题
在一个长度为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”。