资源简介

第二章 数据的存储方式 章节测试
一、选择题
1．有如下图所示的单向链表：
从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（ ）
A．共需查找3次
B．删除数据元素“5”的节点，后续节点需要移动3次
C．头指针head将指向数据元素“7”的节点
D．操作完成后，链表中数据元素的个数为6个
2．某Python程序如下：
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end='->')
p=a[p][1]
print(a[p][0])
程序运行后，输出的结果是（ ）
A．3->7->2->1 B．3->2->7->1 C．1->7->3->2 D．3->7->1->2
3．使用链表结构模拟某校游玩路线，链表a中每一个节点包含三个数据，第1个为景点名称，第2个为预计游玩时间（单位：分钟），第3个为下一个景点指针。该校可以从多个景点开始游玩，但只能从“南大门”离开，输出显示从各景点进入路线及预计总时间的代码如下。a=[["校训石",21,2]，["行政楼",40,2]，["风雨操场",50,5]，["丽泽湖",30,4]，["西餐厅",60,5]，["南大门",20,-1]]
head=[0,1,3]
for i in range(len(head)):
(1)
s=a[p][1]
while a[p][2]!=-1:
print(a[p][0],end="→")
(2)
(3)
print(a[p][0])
print("预计时间：",s,"分钟")
上述程序划线处的可选代码有：
①p=head ②p=head[i] ③s=s+a[p][1] ④p=a[p][2]
则（1)、(2)、(3）处代码依次为（ ）
A．①③④ B．①④③ C．②③④ D．②④③
4．下列数据中，不属于列表的是（ ）
A．{10，15，20，25} B．[10，1.5，20，2.5]
C．[10,15,20，25] D．[a,"b"，20，25]
5．使用链表结构模拟某景区游玩路线，链表a中每一个节点包含三个数据，第1个为景点名称，第2个为预计游玩时间（单位：分钟），第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从"天梯"离开，输出显示各大门进入路线及预计总时间的代码如下。
a=[["迎客松",21,2]，["激流勇进",40,2]，["天空栈道",50,5]，["一线天",30,4]，["飞来峰",60,5]，["天梯",20,-1]
head=[0,1,3]
for i in range(len(head)):
(1)
s=a[p][1]
while a[p][2]! =－1:
print(a[p][0],end="－－>")
(2)
(3)
print(a[p][0])
print("预计时间：",s,"分钟")
上述程序划线处的可选代码有：
①p=head ②p=head[i] ③s=s+a[p][1] ④p=a[p][2]
则(1)，(2)，(3)处代码依次为（ ）
A．①③④ B．①④③ C．②③④ D．②④③
6．使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有的偶数项（头节点为该链表的第1项），部分代码如下：
p=head #head指向该链表的头节点
while p!=-1:
q=a[p][1]
if （1） :
（2）
p=a[p][1]
上述程序段划线处可选语句为
①q!=-1 ②a[q][1]!=-1 ③a[q][1]=a[p][1] ④a[p][1]=a[q][1]
则（1）（2）处填入的语句依次为（ ）
A．①③ B．①④ C．②③ D．②④
7．利用列表模拟某单向非循环链表a(其中可能存在已被删除的节点），下列程序运行完毕后，变量p肯定表示尾节点的节点位置的是（　　）
A． B． C． D．
8．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（ ）来表示。
A．数组 B．链表 C．栈 D．队列
9．用Python程序实现删除链表的倒数第n（n不大于链表长度）个节点，如n=2时，链表
更新为。
部分代码如下：
# 读入链表存储在列表s中，head存储链表的头节点，代码略
n=int(input())
pl=p2=head
while p2!=-1:
if n>=0：
(1)
n -= l
else:
(2)
p2 = s[p2] [1]
if p1 == head :
head=s[head] [1]
else：
(3)
上述程序段中划线处可选的语句为：
①p1=s[p1][1] ②p2=s[p2][1] ③s[p1][1]=s[s[p1][1]][1] ④s[p2][1]=s[s[p2][1]][1]
则（1）~（3）划线处语句依次为（ ）
A．①③④ B．①④③ C．②①④ D．②①③
10．现采用新的排队方案为小明、小红、小丽、小辉四人排队，
Python程序段如下：
linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]]
def reset(head):
if linklist[head][1]==- 1 or head==- 1:
return head
else:
new_head=reset(linklist[head][1])
linklist[linklist[head][1]][1]=head
linklist[head][1]=- 1
return new head
p=h=reset(0)
while p!=- 1:
print(linklist[p][0],end="")
p=linklist[p][1]
执行该程序段后，输出的结果是（ ）
A．小明小红小丽小辉 B．小明小辉小丽小红
C．小辉小丽小红小明 D．小明小丽小红小辉
11．下列关于数组的描述，正确的是（ ）
A．数组的大小是固定的，但可以有不同类型的数组元素
B．数组的大小是可变的，但所有数组元素的类型必须相同
C．数组的大小是固定的，所有数组元素的类型必须相同
D．数组的大小是可变的，可以有不同类型的数组元素
12．在Python中可以使用列表模拟单向链表，如链表中的节点p，a[p] [0]存储p节点的数据，a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x（x作为p的新后继节点），需要执行的语句是（ ）
A．a[p][1]=x; a[x][1]=a[p][1] B．a[x][1]=a[p][1]; a[p][1]=x
C．a[p][0]=x; a[x][0]=a[p][0] D．a[x][0]=a[p][0]; a[p][0]=x
13．设有一个5×8的二维数组a，若按行优先的顺序存储数组元素，则元素a[3][5]前面元素的个数为(　　)
A．21 B．22 C．29 D．37
14．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（ ）
A．删除该链表中的最后一个节点
B．删除该链表中的第一个节点
C．在该链表第一个节点前插入一个新节点
D．在该链表最后一个节点后插入一个新节点
15．运用Python编程处理数据时，经常会用到pandas库，其中Series是一维数据结构，下图程序运行后的结果

A．水蜜桃 B．3 C．水蜜桃 D．“猕猴桃” ”水蜜桃”
16．在单向链表如下图所示，在data2与data3之间插入一个新节点data4（p指向data2，r指向data4。列表data来记录链表数据域，列表next来记录指针域），在以下选项中选择正确的执行步骤（ ）
①next[p]= next[r] ②next[p]= r ③next[r]= p
④next[r]= -1 ⑤next[r]= next[p] ⑥next[p]= -1
A．③⑥ B．⑤② C．①④ D．⑤②④
17．a数组定义如下：a=[2,5,0,3,6,8]，则运算表达式“a[1]+a[3]+a[5]”的结果为（ ）
A．16 B．8 C．10 D．13
18．有关数组特征描述中，下列说法不正确的是（ ）
A．同一数组中，每个数组元素的数据类型是相同的
B．通过数组名和下标可以对数组中任意位置的数组元素进行高效访问
C．数组的存储空间固定不变
D．数组是非顺序存储结构
19．设有数组定义语句：Dim a(5) As Integer，Listl 为列表框控件。下列给数组元素赋值的语句，错误的是（ ）。
A．a(3)=3
B．a(3)=VAL(InputBox(“InputData”）
C．a(3)=Listl.ListIndex
D．a=Array(1,2,3,4,5,6)
20．语句Dim a&(1 To 20)，b#(2,-1 To 1)定义两个数组，其类型分别为： （ ）
A．二维单精度实型数组和二双精度型数组
B．二维长整型数组和二维单精度实型数组
C．一维单精度实型数组和二维整型数组
D．一维长整型数组和二维双精度型数组
二、操作题
21．为分析数据中各元素的变化情况，进行如下定义：
若在数组d中满足d[a]<…d[i+1]>…>d[b]，则从下标a到下标b区间的数据称为一个波峰，下标a到b的距离即为一个波峰的长度（长度≥3）。例如：数组d元素为“78,46,50,37,5,42,6,6,23”，存在2个波峰，分别是从d[1]到d[4]和d[4]到d[6]，波峰长度分别为4和3。编写程序分析数据，找出所有波峰，按波峰长度降序排序（若波峰长度相同，则按开始下标升序），并输出波峰长度和开始到结束元素下标；若不存在，则输出“不存在波峰”，运行结果如图所示。
请回答下列问题：
（1）根据题意，若数组d元素“23,14,35,31,13,20,3,40,10,10,9”，则最长的波峰长度为 。
（2）执行程序，若数组d元素“2,1,1,2”，则I处while语句中循环体的执行次数是 。
（3）实现上述功能的程序代码如下，请在划线处填入合适的代码。
#读取待处理数据，保存在数组d中，并显示输出，代码略
mt, i, n=[], 1, len（d）
while iwhile i< n and d [i] < = d [i-1]: # I
i += 1
st = i-1
while i < n and d [i] > d [i-1]:
i += 1
if i==n or
continue #跳出本轮循环，然后继续进行下一轮循环
while i < n and d [i] < d [i-1]:
i += 1
In=i-st
if len（mt）==0:
mt. append（[In, st, -1]） #为mt追加一个列表元素
head = 0; q = head
else:
while p != -1 and( ):
q = p
p = mt [p] [2]
if p==head:
mt. append（[In, st, head]）
head= len（mt）-1
else:
mt. append（[In, st, p]）
=len（mt）-1
if len（mt）==0:
print（“不存在波峰”）
else:
print（“输出结果（长度：开始下标～结束下标）:”）
p = head
while p != -1:
print（mt [p] [0],“:”, mt [p] [1],“～”, mt [p] [0] + mt [p] [1] -1）
p = mt [p] [2]
22．某校针对高三高考成绩进行分析时，其中有两个主要指标：班级各科平均成绩和班级总分平均成绩。高考成绩保存在“kscj.csv”文件中，格式如图a所示，每行有四个项目，分别是“学号”、“姓名”、“学科”和“得分”，其中“学号”的前两位表示班级编号，后两位表示该学生班内编号，两种编号均从“01”递增编号。
设计如下Python程序，执行后输出上述两个主要指标，如图b所示。请回答下列问题。

图a 图b
（1）通读下列程序代码后，可知程序中各班级队列采用的数据结构为 （选填，数组/链表）。
（2）函数dataToClassQue功能：根据班级编号，将数据分配到各个班级队列。请在划线处填入合适的代码。
def dataToClassQue(data) :
num = len(data)
for i in range(num):
classId = data[i][0]
if queInfo[classId-1][0]=-1 :
queInfo[classId-1][0]=i
else:

queInfo[classId-1][1]=i
return
（3）函数dataProcessing功能：统计各班各科平均分和班总分平均分。请在划线处填入合适的代码。
def dataProcessing(data):
for classId in range(1 ,classNumber+1):
①
score = [[0,0] for i in range(10)] #班级各科平均分和相应人数初始化
p = queInfo[classId- 1][0]
while p!=-1 :
subjectId = data[p][3]
total += data[p][4]
②
score[subjectIld][1]+= 1
p = data[p][-1]
for subjectId in range(10):
if score[subjectId][1]!=0.
t= ③
#函数round(t,x)用于对变量t四舍五入保留x位小数
averageScore[classId- 1][subjectId] = round(t,1)
averageScore[classId-1][10] = round(total/score[0][1],1)
return
def readFile(data) :
#读入原始学生数据，预处理后，存储到data中，代码略
#data数据格式：[[6,10,'白凯修',0,117,-1],[6,10, '白凯修',1,109,-1],……]
#每条记录的信息包括：班级编号，班内编号，姓名，学科编号，得分和预留值-1
return maxCassId #返回最大班级编号
def fmtPrint():
#格式化输出，如第15题图b所示，代码略。
return
#主程序：
course= {'语文':0, '数学':1, '英语':2, '物理':3, '化学':4, '生物':5, '政治':6, '历史':7, '地理':8, '技术':9}
data=[] #存储读入的数据
classNumber = readFile(data)
queInfo = [[-1,-1] for i in range(classNumber)] #初始化队列，用于存储各班级信息
averageScore = [[0 for k in range(11)] for i in range(classNumber)]#初始化各班各科以及总分平均分
dataToClassQue(data)
dataProcessing(data)
fmtPrint()
23．某信息仅包含大写字母，字符数不超过n*n（n*n为密钥矩阵规模，n>0），加密过程如图a所示：
图a
图b
（1）已知密钥矩阵按图a中所示，若原文为“OK”，则加密后的密文是 ，若输入的密文是“10，1，24，2，”，则原文是 。
（2）根据上述加密算法编写解密程序，运行界面如图c所示。请在划线①②③处填上合适的代码。
图c
def getmm（x，n）: #获取位置编号x的位置密钥值
row=（x-1）%n
col=（x-1）//n
if① ：
row=n-1-row
return key[row][col]
#生成规模为n*n的密钥矩阵，存入二维矩阵key中
n=int（input（"请输入密钥矩阵规模n:"））
key=[[i*n+j+l for j in range(n)] for i in range(n)]
#密文解密
p=input("请输入密文: ")
mw=[]
bmz=[]
t=0
for i in range (1en(p)):
#依次读取密文字符串中的数值，结果存入到列表mw中
s=p[i]
if s!=",":
.②
else:
mw. append (t)
t=0
k=len (mw)
for i in range(k//2) : #对密文解密，结果存入列表bmz中
bmz. append (mw [2*i]- ③
yw="
for i in range (k//2): #转换为字母输出
yw=ywtchr (bmz [i]-1+ord("A"))
print("原文为:"+yw)
24．某工程包含n个任务（编号为0-n-1），每天可以有多个任务同时进行。某些任务之间有依赖关系，如图a所示，任务4依赖于任务1，任务1依赖于任务2。即任务2完成后才可以开始任务1，任务1完成后才可以开始任务4，不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。
现已对该工程的依赖关系进行了梳理，结果如图b所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。
图a 图b
请回答下列问题：
（1）若某工程有6个任务，任务间依赖关系如图a所示，完成任务0~5所需天数分别为2，1，3，5，1，6，则工程最快完成需要 天。
（2）定义如下erase（1st）函数，参数1st列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系，返回保留的依赖关系的个数。
def erase（lst）：
i=0
j=len（1st）-1
while i<=j：
if 1st[i][2]=='T'：
i+=1
else：
if lst[j][2]=='T'：
1st[i]=1st[j]
i+=1
j-=1
return i
若1st列表依次存储图b所示的依赖关系，如1st[0]为[0，5，T]，调用erase（lst）的数，则语句
"1st[i]=1st[j]”的执行次数为 。
（3）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
def proc（n，lst，task）：
pr=[0]*n
w=[0]*n #w[i]存放任务1最晚必须开始的时间
m=erase（1st）
for i in① ：
task[lst[i][1]][1]=1st[i][0]
pr[lst[i][0]]=1
c=[]
days=0 #days存放工程最快完成所需的天数
for I in range（n）：
if pr[i]==0：
k=i
s=0
while k！=-1：
c．append（k）
s+=task[k][0]
②
if s>days：
days=s
for i in range（n-1，-1，-1）：
k=c[i]
if task[k][1]==-1:
w[k]=days-task[k][0]+1
else：
③
#输出days，以及保存在w中的每个任务最晚必须开始的时间，代码略
```
工程包含的任务数存入变量n
任务间的依赖关系存入1st列表
1st[0]包含3项，任务1st[i][0]依赖于任务1st[i][1]，1st[i][2]存放保留/删除标记，任务数据存入task列表
task[i]包含2项，task[i][0]为完成任务主所需天数，task[i][1]的初值为-1
代码略
```
proc（n，1st，task）
25．在Python语言中，可以使用列表来模拟链表节点的插入操作。以下Python程序段用二维列表来定义单向链表。如要在该链表中插入节点，可以通过程序来修改相应节点的指针达到目的。
（1）如下图所示，请根据程序补充完整未插入数据前的链表数据区域的值（依次填写）① 、 、 、 。此时链表的头指针的值是② 。
（2）实现链表插入的 Python 程序如下，请在程序划线处填入合适的代码。
data=[[8,-1],[7,4],[5,5],[6,0],[1,3],[2,1]] # 定义单向链表
head=2 leng=len(data)
pos=int(input("请输入要插入的位置（0~%d）之间："%(leng)))
val=int(input("请输入要插入的数据值："))
data.append([val,leng])
# 插入节点：
p=head
if pos== : # 加在链表最前面，作为首节点
data[leng][1]=p
head= # 更新头指针
else:
q=data[p][1]
c=0
while c < pos-1 and q!=-1:
p=q
q=data[p][1]
c+=1
# 更新指针
data[p][1]=leng
# 用列表形式来显示插入后的链表：
p=head
s=[ ]
while p!=-1:
s.append( )
p=data[p][1]
print(s)
参考答案
1．D
2．A
3．D
4．A
5．D
6．B
7．B
8．B
9．D
10．C
11．C
12．B
13．C
14．A
15．B
16．B
17．A
18．D
19．D
20．D
21．4 2次 d[i]==d[i-1] In==mt[p][0] and st>mt[p][1] mt[q][2]
22．链表 data[queInfo[classId-1][1]][-1]=i total=0 scoree[subjectIld][0]+=data[p][4] scoree[subjectIld][0]/score[subjectIld][1]
23．16,1,15,2, IT col%2==1 或其他等价答案 t=t*10+int(s) 或其他等价答案 getmm(mw[2*i+1],n)
24．8 1 range（m） 或range（0，m） 或range（0，m，1） 或range（m-1，-1，-1）或range（erase（1st）） 或range（0，erase（1st）） 或range（0，erase（1st），1） 或range（erase（1st）-1，-1，-1） k=task[k][1] w[k]=w[task[k][1]]-task[k][0] 或w[k]=w[c[i+1]]-task[k][0] 这里面可以把k换成c[i]
25．2 7 1 6 2 0 leng data[leng][1]=q data[p][0]

展开更多......

收起↑