资源简介

第二章 数据与链表 章节测试
一、选择题
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

展开更多......

收起↑