资源简介

第五单元　数据存储
信息技术(50分)
一、选择题(本大题共10小题，每小题2分，共20分。每小题列出的四个备选项中只有一个是符合题目要求的，不选、多选、错选均不得分)
1.有如下Python程序代码
num＝[0]*10
n＝36；s＝0
for i in range(n)：
j＝9
num[j]＋＝1
while num[j]＝＝2：
num[j]＝0
j－＝1
num[j]＋＝1
for i in range(10)：
s＋＝num[i]
print(s)
执行此代码后，变量s的值为(　　)
A.2 B.3
C.4 D.5
2.阅读以下程序段：
a＝[]
n＝int(input(″请输入一个整数：″))
k＝n
while n>0：
a.append(n%10)
n＝n//10
s＝0
for i in range(len(a))：
s＋＝a[i]**(len(a))
if k＝＝s：
print(″YES″)
else：
print(″NO″)
运行程序，如果程序要输出YES，则输入的数字可能是(　　)
A.21 B.90
C.153 D.400
3.下列关于数据结构说法，不正确的是(　　)
A.队列和栈都是操作受限的线性表
B.计算机中一般会采用树形结构来管理文件
C.链表中数据元素的逻辑顺序是通过链表中指针指向实现的
D.同一个数组中的元素的数据类型可以不同
4.下列关于数据结构的说法，正确的是(　　)
A.用程序实现问题解决时只能采用一种数据结构
B.数据的逻辑结构是指数据元素间的关系
C.链表比数组更适合大量数据元素的随机访问
D.数组不必占用一片连续存储的单元
5.有如下Python程序段：
a＝[[0 for i in range(3)]for j in range(3)]
for i in range(3)：
for j in range(3)：
a[i][j]＝i*5＋j＋1
for i in range(1，3)：
　 for j in range(2)：
　 print(a[j][i]，end＝″ ″)
程序段执行后，输出的结果是(　　)
A.2 3 7 8 B.7 12 8 13
C.2 7 3 8 D.6 7 11 12
6.有如下程序段，输入列表a的值保证至少有一个是非负整数。
#输入列表a
t＝0；ans＝0
n＝len(a)
for i in range(n)：
t＋＝a[i]
if t<0：
t＝0
if t>ans：
ans＝t
print(ans)
当列表a的值为[3，－1，2，－5，3，4，－1，2]时，程序输出的结果为(　　)
A.3 B.7
C.8 D.14
7.有如下Python程序段：
from random import randint
a＝[randint(1，10) for i in range(5)]
for i in range(1，5)：
key＝randint(3，6)*2
j＝i－1
while j >＝0 and key a[j＋1]＝a[j]
j－＝1
a[j＋1]＝key
执行该程序段后，列表a的值不可能是(　　)
A.[3，6，8，10，12] B.[1，5，8，9，12]
C.[6，10，10，12，12] D.[8，9，10，10，12]
8.已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　　)
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
9.有如下Python程序段：
a＝[[7，3]，[5，0]，[2，1]，[9，－1]]
head＝2
key＝int(input(″输入一个数字″))
p＝q＝head
while p！＝－1 and a[p][0]q＝p
p＝a[p][1]
if p＝＝head：
a.append([key，head])
head＝len(a)－1
else：
a.append([key，p])
a[q][1]＝len(a)－1
print(a[－1])
程序段运行后，若输入2，则输出的结果是(　　)
A.[2，－1] B.[2，1]
C.[2，2] D.[2，3]
10.采用Python二维列表模拟链表，a＝[[″A″，1]，[″B″，2]，[″C″，3]，[″D″，4]，[″E″，5]，[″F″，－1]]。表示链表为：A→B→C→D→E→F。有以下Python程序：
head＝0；p＝a[head][1]
a[head][1]＝－1
while p！＝－1：
p＝a[p][1]
if p＝＝－1：
break
t＝a[p][1]
a[p][1]＝head
head＝p
p＝t
执行以上程序后，以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
二、非选择题(本大题共4小题，共30分)
11.数组a存储降序排序的m个数据，数组b存储升序排列的n个数据，两个数组中存储的数据为[1，20]范围的不重复的随机数。现将两个数组的数据合并到c数组中，使c数组的数据为左右交替上升。
a[0] a[1] a[2] a[3] a[4]
19 17 6 4 3
b[0] b[1] b[2] b[3] b[4] b[5]
5 7 8 13 15 20
c[0] c[1] c[2] c[3] c[4] c[5] c[6] c[7] c[8] c[9] c[10]
3 5 7 13 17 20 19 15 8 6 4
a＝[19，17，6，4，3]
b＝[5，7，8，13，15，20]
m＝len(a)；n＝len(b)
c＝[－1]*(m＋n)
pa＝m－1；pb＝0；pc＝0；
k＝1
while ①________：
if pa＝＝－1 or a[pa]>b[pb]：
s＝b[pb]
pb＋＝1
elif pb＝＝n or a[pa]s＝a[pa]
②________
c[pc]＝s
k＝1－k
print(c)
(1)若数组a为14，9，5，3，数组b为1，2，7，15，20，则数组c为________。
(2)请在划线处填入合适的代码。
(3)加框处代码有错，请改正。
12.编写Python程序，功能是根据A城和B城同一时间段内的温度数据，计算两城温差(A城温度－B城温度)。A城数据和B城数据分别为包含若干个记录的序列，其中，A城每个记录包含温度及其截止时间，B城每个记录包含温度及其持续时长。两城温差计算结果表示为若干个记录的序列，每个记录包含温差及其持续时长。持续时长是指同一温度(或温差)保持不变的最大时长。示例见下表。
表中，A城数据有4个记录，其中第1个记录为(温度30，截止时间2)，第2个记录为(温度33，截止时间4)，这表明从开始到第2小时的温度都是30，此后到第4小时的温度都是33。B城数据有4个记录，其中第3个记录为(温度21，持续时长2)，这表明第5、第6这2个小时的温度都是21。两城温差计算结果的第4个记录为(温差10，持续时长3)，这表明第5、第6、第7这3个小时的温差都是10。
程序运行的结果如图所示：
城市A各时间段的温度：30 31 32 城市A温度截止时间：4 6 7 城市B各时间段的温度：20 22 21 22 城市B温度截止时间：3 4 6 7 城市各时间段的温差：10 8 10 城市温差的持续时间：3 1 3
(1)若将示例中A城数据修改为3个记录，依次是(温度30，截止时间4)、(温度31，截止时间6)、(温度32，截止时间7)，B城数据不变，则两城温差计算结果中第1个记录为(温差10，持续时长________)(填数值)。
(2)实现上述功能的代码如下，请在划线处填入合适的代码。
#读取两个城市各阶段的温度，分别存储在数组ha和hb中
#读取城市A的截止时间存储到数组ta中，读取城市B的持续时长存储到数组tb中
na＝3；nb＝4
for i in range(1，nb)：　#将B 城第i 个记录中的持续时长转换为截止时间
①________
print(tb)
i＝0；j＝0；n＝0；p0＝0
h＝[0]*30；t＝[0]*30
while idiff＝ha[i]－hb[j]
p1＝ta[i]
if ②________：
i＋＝1
if p1>＝tb[j]：
p1＝tb[j]
j＋＝1
if n＝＝0 or diff！＝h[n－1]：
h[n]＝diff
t[n]＝p1－p0
n＋＝1
else：
③________
p0＝p1
#输出温度差及持续时长，代码略。
13.链表的插入排序。数据保存在链表da中，对da中数据采用插入排序方法，进行非降序排列。算法描述如下：
1)从头节点的下一个节点开始，往前找到合适的位置，将该节点插入到相应位置，重复以上操作，使得全部节点中的数据有序。
2)每个节点的插入方法：如果当前节点的值比头节点小，将该节点插入到头节点前面，成为新的头节点，当前节点的前驱指针指向后继节点，前驱指针不变。如果当前节点值大于等于头节点值，从头节点开始不断向后遍历，当遍历节点的值大于当前节点的值或遍历的指针指向当前节点，停止遍历，若遍历到当前节点，说明当前节点的位置不需要移动，移到当前指针时，其对应的前驱指针也要同步移动。如果要插入到前面的某个位置时，当前指针移动，但前驱指针并没有移动。
注意要点：①当前节点cur的前驱节点位置什么时候变化？什么时候不变？②为什么需要用变量tcur保存cur的后继位置da[cur][1]。
(1)实现上述功能的Python程序如下，请在划线处填入合适的代码。
(2)程序中加框处代码有错，请改正。
#产生并输出一个链表da，代码略。
ha＝0
cur＝da[ha][1]
qc＝ha
while ：
①________
if da[cur][0]da[qc][1]＝da[cur][1]
da[cur][1]＝ha
ha＝cur
else：
q＝ha
while q！＝cur and da[q][0]<＝da[cur][0]：
　　　　 ②________
　　　 　q＝da[q][1]
if q！＝cur：
　　　 　da[qc][1]＝da[cur][1]
　　　 　da[qh][1]＝cur
　　　 　da[cur][1]＝q
else：
　　　 　③________
cur＝tcur
14.某医院每天提前发放100个预约号，考虑到老年人身体原因，预约病人按照以下规则进行就诊：
①老年人(年龄>＝60岁)比非老年人优先就诊。
②老年人按年龄从大到小的顺序就诊，年龄相同的按预约顺序就诊。
③非老年人按预约顺序就诊。
小王根据以上规则编写了一个Python程序，程序运行时，实时读取病人预约数据，并根据以上规则，实时调整并显示当前诊顺序，程序运行界面如图所示。
请输入病人的信息：40 当前就诊顺序为：40 请输入病人的信息：15 当前就诊顺序为：40 15 请输入病人的信息：67 当前就诊顺序为：67 40 15 请输入病人的信息：75 当前就诊顺序为：75 67 40 15 请输入病人的信息：30 当前就诊顺序为：75 67 40 15 30
(1)如图所示，若当前就诊顺序为“75 67 40 15 30”，下一位预约病人年龄为60，则就诊顺序变为________。
(2)实现上述功能的代码如下，请在划线处填入合适的代码。
#遍历链表data，头指针为head
def visit(data，head)：
cur＝head
while cur ！＝－1：
print(data[cur][0]，end＝″ ″)
cur＝data[cur][1]
print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分别表示链表头节点和尾节点所在位置
for i in range(100)：
#为了简洁，本程序只输入、存储病人的年龄信息
age＝int(input(″请输入病人的信息：″))
cur＝head
if age >＝60：
while cur！＝－1 and data[cur][0]>＝age: #查找第一个数据域小于age的节点
　　　 　pre＝cur
　　　 　①________
if cur＝＝head：　#在头节点插入新节点
　　　 　data.append([age，cur])
　　 　　head＝len(data) － 1
else：　#在链表中间插入新节点
　　　 　data.append([age，cur])
　　　 　②________
if cur＝＝－1：　#更新尾指针位置
　　　 　tail＝len(data) － 1
else：　#直接插在链表尾节点后
data.append([age，－1])
if head＝＝－1：　#添加第一个节点
　　　 　head＝tail＝0
else：
　　　 　③________
　　　　 tail＝len(data) － 1
print(″当前就诊顺序为：″)
visit(data，head)
第五单元　数据存储
1.A　[本题考查数制转换的程序实现。每次在最后一位(num[9])加1，且num[j]＝＝2时，该位变0，高位进一。该程序的功能是将36转换成二进制，并统计二进制数上每个的和。]
2.C　[本题考查累加求和。程序的功能是各个位数字的3次方和为他本身。3^3＋5^3＋1^2＝27＋125＋1＝153。]
3.D　[本题考查数据结构基本知识。A选项队列、栈只能在一端或两端操作的线性表。B选项计算机中采用树形结构来管理文件。C选项链表由数据域和指针域组成，指针域存储下一个节点的位置。D选项同一数组中元素的数据类型相同。]
4.B　[本题考查数据结构。A选项程序实现可以采用多种数据结构。B选项数据的逻辑结构指的是数据元素间的关系。C选项数组比链表访问高效，链表增加和删除比数组高效。D选项数组采用的是线性存储，需要划出连续的存储空间。]
5.C　[本题主要考查二维数组。创建一个3行3列值全为0的二维数组a。第1次嵌套for循环执行完，列表a的值为[[1，2，3]，[6，7，8]，[11，12，13]]，依次输出2，7，3，8。]
6.C　[本题考查枚举算法。遍历数组a，将数组中数据进行累加，若累加和小于0，t的值为0，否则找到累加和最大的一段为3＋4－1＋2＝8。]
7.B　[本题考查排序算法和随机数函数。首先列表a中的初始值是[1，10]内的5个随机数。key的取值只能是6、8、10、12。while循环会将key插入列表a的合适位置上，使得列表a的值非降序排列，因此选项A、C、D都是有可能的。]
8.A　[本题考查链表节点的插入和删除。若删除链表的头节点，只需移动头指针。若在链表尾节点后插入一个新节点，只要将尾节点指向新增节点，新增节点为新的尾节点。若要删除最后一个节点，需修改尾节点前驱的指针区域值，因此需遍历多个节点。]
9.C　[本题考查链表的相关知识。先建立了一个升序链表，接下来从head开始，查找key插入的位置。若key>a[p][0]则继续向后找。本题key＝2，一开始就不满足循环条件，2应插到链表头部。首先向列表中追加key，并将指针指向head，同时调整head指针位置，故a[－1][0]＝2，指针a[－1][1]＝2。]
10.A　[本题代码通过迭代和逆转，实现只提取奇数位的链表元素，并逆序输出。]
11.(1)1，3，7，14，20，15，9，5，2　(2)①pa>＝0 or pb②pa－＝1　(3)pc＝m＋n－pc－k
解析　本题考查双指针的基本操作。(1)按左右递增的顺序填充数组c。(2)①pa指向数组a的最后位置，pb指向数组b的开始位置，均指向每个数组的最小位置，两个数组中只要有一个指针没有超范围时，就要继续归并。②语句s＝a[pa]指将a数组的数据归并到c，因此pa向前移动。(3)当pc为0，k为1，下一位置在pc的对称位置，即m＋n－1－pc。接下来k为0，下一位置在pc前面一个数据(pc－1)的对称位置，m＋n－1－(pc－1)，综合可得pc＝m＋n－pc－k。
12.(1)3　(2)①tb[i]＝tb[i]＋tb[i－1]　②ta[i]<＝tb[j]
③t[n－1]＝t[n－1]＋p1－p0
解析　本题考查前缀和、枚举算法。
时间 第1 小时 第2 小时 第3 小时 第4 小时 第5 小时 第6 小时 第7 小时
A城温度 30 30 30 30 31 31 32
A城 数据 温度 30 31 32
截止时间 4 6 7
B城温度 20 20 20 22 21 21 22
B城 数据 温度 20 22 21 22
持续时长 3 1 2 1
计算 结果 温差 10 8 10
持续时长 3 1 3
(1)根据上面的图表，明显可以看出第一个记录为10的时候是第3小时结束时，即持续时长为3小时。(2)本题考查求最长相同子序列及其个数，涉及数组概念。①求当前记录的截止时间，只要将前一个记录的持续时长tb[i－1]加上当前记录的持续时长tb[i])即可。②A城和B城比较时，取截止时间小的赋值给p1，再判断记录是否判断完毕，如果完毕取下一个记录。A城第一个记录温度为30，截止时间为2，而B城第一个记录温度为20，截止时间为3，取他们公共部分温差为10的，截止时间只能到2，因此需要将p1设置为小的那个截止时间。这样A城的第一记录已经用完，所以需要i＝i＋1，到下一个记录，而B城第一记录里有3个，只用了2个，所以记录不跳到下一记录。③求相同子序列及其个数，那就得判断每个子序是否与前一个相同(代码：diff！＝h[n])，就可以知道代码中最后一个分支模块是进行子序列相同判断和处理的，那么else中应该是处理子序列相同的情况，如果子序列相同，只要增加子序列个数即可。
13.(1)①tcur＝da[cur][1]　②qh＝q　③qc＝cur (2)cur！＝－1
解析　本题考查链表元素的插入。(1)①cur表示当前要插入的节点，头元素只有一个节点，肯定有序，因此其初值为da[ha][1]。将某个节点移动到前面后，该节点的指针域将更新，循环体最后一条语句为cur＝tcur，那么下一个当前节点就是当前节点的后继的指针要保存在tcur中。②某个节点要插入到新位置p，那么要知道p的前驱是什么，因此在查找位置时，同时要保存前驱节点位置。③完成当前节点的插入时，若当前节点位置发生变化，那么在遍历到下一个当前节点cur时，他的前驱是不会变化的，只有当前节点位置没有发生变化，其前驱是要同步移动。(2)略。
14.(1)75 67 60 40 15 30　(2) ①cur＝data[cur][1]　②data[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本题考查链表的基本操作，学生需要有链表节点的概念，链表用列表来模拟的过程。(1)若当前就诊顺序为“75 67 40 15 30”，下一位预约病人年龄为60，根据题干描述“老年人(年龄>＝60岁)比非老年人优先就诊，老年人按年龄从大到小的顺序就诊”，因此将60插入到40前，结果是75 67 60 40 15 30。(2)根据题干描述，本题分两种情况，年龄>＝60岁时，按年龄降序，年龄<60岁时，按预约顺序。因此，主要涉及链表的插入操作，年龄>＝60岁时为头插入和中间插入，按预约顺序尾插入。①的功能是比较数据大小，从头节点开始依次遍历，根据数据值找到第一个比当前数据小的节点cur，pre为前驱节点，因此，①处答案为cur＝data[cur][1]，表示从当前节点到下一节点。在链表中间插入新节点时，需要在插入节点后，更改前驱节点的指针区域。因此②处答案为data[pre][1]＝len(data)－1。直接插在链表尾节点后，尾节点变成了前驱节点，更改前驱节点的指针区域。因此③处答案为data[tail][1]＝len(data)－1。

展开更多......

收起↑