资源简介

验收卷(五)　综合练习(A)
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.下列关于数据结构与算法效率的描述，不正确的是(　　)
A.队列和栈都是一种线性表，但两者有不相同的特性
B.采用相同公式求解n！，使用迭代算法比递归算法的算法效率高
C.使用数组结构在进行数据插入和删除操作时，一定会引起数据移动
D.某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个节点
2.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5 C.4　5 D.4　6
3.如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为“d，e，f，g”，已知元素p已经出栈，则入栈顺序不可能是(　　)
A.d，e，f，g，p B.p，d，e，f，g
C.d，e，p，f，g D.d，e，g，p，f
4.已知一棵完全二叉树的节点总数为 12，则有关该二叉树的说法正确的是(　　)
A.树的度为12 B.树的层数为3
C.叶子节点数为5 D.最后一层有5个节点
5.某二叉树的树形结构如图所示，其中序遍历结果为FDGBAEC。若补全为完全二叉树后，按从上到下、自左往右的顺序用一维数组a存储，其中根节点存储于元素a[0]中，则元素a[6]的值为(　　)
A.D B.F C.G D.C
6.有如下Python 程序段：
import random
q＝[0]*5
head，tail＝0，0
for i in range(5)：
　if random.randint(0，i)%2＝＝0：
　 q[tail]＝random.randint(1，9) #随机生成1到9之间的整数
　elif head　q[tail]＝q[head]
　head＋＝1
　tail＋＝1
print(q)
执行该程序段后，列表q 的值不可能是(　　)
A.[1，0，1，0，9] B.[5，4，3，2，1]
C.[5，8，3，0，0] D.[5，5，6，0，6]
7.有如下 Python程序段：
a＝[21，5，10，9，18，10，5，18，12，11]
n＝len(a)
st＝[0]*n; top＝－1
for i in range(n)：
　if top＝＝－1：
　　　top＋＝1
　　　st[top]＝a[i]
　else：
　if a[i]%2＝＝0：
　　 　while top>－1 and a[i]>st[top]：
　　　　　top－＝1
　　　top＋＝1
　　　st[top]＝a[i]
while top>－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
执行该程序段后，输出结果为(　　)
A.12　18　18　21 B.18　18　12
C.21　18　18　12 D.11　12　18　18　21
8.定义如下函数：
def chg(k)：
　if k＝＝－1：
　return ″″
　else：
　 c＝chr(ord(″a″)＋k)
　if k%2＝＝1：
　　　return c＋chg(k－1)
　else：
　　　return chg(k－1)＋c
执行语句m＝chg(4)后，m的值为(　　)
A.″ecabd″ B.″dbace″ C.″abcde″ D.″edcba″
9.下面Python 程序运行后，输出结果不可能的是(　　)
from random import randint
a＝[3，4，5，6，7，8]
def f(x)：
　if x<2：
　return a[x]＋f(2*x＋randint(1，3))
　else：
　return a[x]
A.8 B.9 C.10 D.13
10.列表a中存储了8个元素，即a[0]，a[1]，…，a[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
　for j in range(n－1，i，－1)：
　 if a[j]　　　a[j－1]，a[j]＝a[j]，a[j－1]
该程序段实现的是(　　)
A.a[0]到a[7]升序排序
B.a[4]到a[7]升序排序
C.a[0]到a[7]的数据对4取余之后升序排序
D.a[0]到a[3]、a[4]到a[7]分别升序排序
11.如下 Python 程序段：
import random
a＝[1，3，5，7，9，11，13，15]
key＝random.randint(1，8)*2
i，j＝0，len(a)－1
s＝0
while i<＝j：
　m＝(i＋j＋1)∥2
　 if a[m]＝＝key：
　break
　if a[m]>key：
　j＝m－1；s－＝1
　else：
　i＝m＋1；s＋＝1
print(s)
上述程序执行完以后，s 的值可能有(　　)
A.4 种 B.5种 C.7种 D.8 种
12.将链表中的奇数节点和偶数节点分别排在一起，奇数节点和偶数节点的相对顺序不变。如原始链表为，新链表为。部分程序如下：
#读入链表，存储在列表a中，head存储链表的头节点
odd＝head
even＝a[odd][1]
tmp＝even
while a[odd][1]！＝－1 and a[even][1]！＝－1：
a[odd][1]＝tmp
上述程序段中方框处可选的语句为
①odd＝a[odd][1]
②even＝a[even][1]
③a[odd][1]＝a[even][1]
④a[even][1]＝a[odd][1]
则方框处语句依次为(　　)
A.①③②④ B.①②③④ C.③②④① D.③①④②
二、非选择题(本题共3小题，共26分)
13.(6分)疫情防控期间，某工厂为了将流水线上已生产的口罩及时装箱，并尽量分配给更多的疫情地区，需要设计一个程序实现自动化装箱。装箱要求为：流水线上生产的每包口罩数量有可能不同，装入箱子的口罩必须为流水线上连续的若干包，每箱内的口罩数量必须相同，在已知每包口罩数量和口罩总包数的前提下，装尽可能多的箱子。
例l：某流水线上有8包口罩，每包口罩的数量如下表：
包序号 1 2 3 4 5 6 7 8 每箱 数量
每包数量 12 3 9 6 6 9 3 12
箱号 (方案1) 1 2 2 3 3 4 4 5 12
箱号 (方案2) 1 1 2 2 3 3 4 4 15
箱号 (方案3) 1 1 1 1 2 2 2 2 30
在上述情况下，有3种分箱方案，方案1为最优方案。
例2：某流水线上有8包口罩，每包口罩的数量如下表：
序号 1 2 3 4 5 6 7 8
数量 1 3 5 7 9 11 13 15
在上述情况下，没有符合要求的装箱方案。
按照上述要求，编写一个Python程序，功能如下：读取流水线上每包口罩的数量，输出分箱结果，若存在装箱方案，则输出最多的装箱数，否则输出“无方案”。程序界面如图所示。
包编号：1　2　3　4　5　6　7　8 包数量：12　3　9　6　6　9　3　12 方案1每箱12包，箱号：1—1，2—3，4—5，6—7，8—8 方案2每箱15包，箱号：1—2，3—4，5—6，7—8 方案3每箱30包，箱号：1—4，5—8 总共方案数为3，第一种方案最佳。
(1)假如流水线上生产的每包口罩数量依次为“16，5，3，8，7，9”，按照上述装箱要求，则装箱结果为________________。
(2)代码如下，请在程序划线处填入合适的代码。
def F(x): #数字按固定长度输出
　 return (″　　 ″＋str(x))[－5：]
def Sa(a，h，t): #将数组索引号h至t－1之间的数值相加。
　 s＝0
　 for i in range(h，t)：
　 s＋＝a[i]
　 return s
#读取各包中口罩数量到数组a，并输出，代码略
maxa＝0；suma＝0
for i in a: #统计口罩数量最多的包编号和累加各包口罩数量。
　 if i>maxa：
　maxa＝i
　 ①____________
m＝0
for i in range(maxa，suma)：
　 xh＝[]
　 head＝0；tail＝1
　 while tail<＝n：
　 f＝False
　 t＝Sa(a，head，tail)
if t　　　 ②____________
　 elif t＝＝i：
　　 　 xh.append(tail－1)
　　　 f＝True
　　　 head＝tail
　　　　③____________
　 else：
　　　 break
　 if f：
　 m＋＝1
　 s＝″方案″＋str(m)＋″每箱″＋str(i)＋″包，箱号：1－″
　 for j in xh：
　　　 s＝s＋str(j＋1)＋″，″＋str(j＋2)＋″－″
　 print(s[：－3])
14.(10分)某弹珠游戏，弹珠从起点到终点需要经过若干节点(不存在绕圈现象，且保证可以到达)，但方案可能不唯一。各节点关系如图a所示，寻找线路的方法：第1轮节点A进栈，作为当前节点，同时对A作起点标志为真操作，发现有B、D可以连通，B和D分别进栈，栈顶为D；第2轮以D为当前节点，对D作起点标志为真操作，从该节点出发，枚举所有的路线，直到到达终点。找到终点后，枚举栈中节点，查找起点标志为真的节点，输出可以从起点到终点达到的线路；接着对当前节点作出栈处理，往前查找一个出栈标志为假的节点，继续重复查找，直到栈中元素为空。
用数组存储各节点信息，节点A、B、C、D、E、F、G、H分别编号为0～7。数值1表示表格中左侧节点可达上方节点，数值0表示无法抵达。程序运行的结果如图所示，请在划线处填入合适的代码。
路径1：A，D，G，H 路径2：A，D，E，F，H 路径3：A，D，E，C，F，H 路径4：A，B，C，F，H
(1)起点为D，终点为F，经过节点数最少的线路图为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
n＝8
#n为总的节点数，读取n*n个节点之间的信息，存储在二维数组 a中，若a[i][j]值为1，表示i节点到j节点可达。代码略。
st＝[0]*n
st[0]＝0；top＝0 #构建一个n个元素的栈
f＝[False]*n #是否以该节点为起点向后查找过
tot＝0 #记录可行路径的数量
while top！＝－1：
①________
f[cur]＝True　　
for i in range(n)：
　　 　if a[cur][i]＝＝1 ：
　　if i＝＝n－1：
　　　 　　tot＋＝1
　　　　 　s＝″″；j＝0
　　　　　 while j<＝top：
　　　　　　 　if ②________：
　　　　　　　　　s＝s＋str(chr(st[j]＋65))＋″，″
　　　　　　　 j＋＝1
　　　　　print(″路径″＋str(tot)＋″：″＋s＋chr(64＋n))
　 　　　　top－＝1
　　　　　while top>＝0 and f[st[top]]：
　　　　　　　top－＝1　　　　　　　　
　　 　else：　　　　　　
　　　 　　top＋＝1
　　　　 　③________
15.(10分)王老师组织同学参加答题游戏，由“A”，“B”，“C”，“D”4个小组参与游戏，每个小组由k名学生组成，由1人代表小组答题。抽签确定开始的小组，每一轮按A→B→C→D→A顺序轮流作答，每答对一题加10分，每个选手答错一题即遭淘汰，由同组下一个选手补上，若该组所有选手都已淘汰则该组即遭淘汰，其他小组继续轮流作答，直到剩下最后一组，即为获胜小组，若最后一轮没有小组幸存，则分数最高的小组获胜。
(1)若每组有两个选手，从A组开始，经过3轮答题，答题结果为“TFTF”，“FFFT”，“FTF”(答对用T表示，答错用F表示)，则获胜的小组是______。
(2)王老师用链表数据结构设计了答题游戏的算法，并用 Python 编写程序模拟，实现了输入每组人数，随机产生开始的小组，输入每轮答题的情况，输出最后获胜的队伍。
该程序的 Python 代码如下，请在划线处填入合适的代码，完善程序。
def findmax(score)：
　#findmax 函数功能是在 4 个小组查找分数最高的小组并输出，代码略
def printlist(head): #输出当前剩余小组的得分情况
　　　print(dlist[head][0]，″组得分是″，score[dlist[head][0]])
　　　cur＝①________
　　　while cur！＝head：
print(dlist[cur][0]，″组得分是″，score[dlist[cur][0]])
cur＝dlist[cur][1]
k＝int(input(″输入每个组的人数：″))
code＝″ABCD″
dlist＝[[code[i]，i＋1] for i in range(4) ] #初始化链表 dlist
dlist[3][1]＝②________
head＝randint(0，3) #随机产生开始的小组
print(″从″，code[head]，″开始答题″)
number＝{} #存储每组剩余替补人数
score＝{} #存储每组得分数据
for i in dlist：
　number[i[0]]＝k－1
　score[i[0]]＝0
cur＝head
pre＝(head－1)%4
left＝4
while left>1：
　ans＝input(″输入本轮答题情况″)
　 for j in ans：
　　if j＝＝″T″：
　　　　score[dlist[cur][0]]＋＝10
　　　　pre＝dlist[pre][1]
　　　　cur＝dlist[cur][1]
　 　else：
　　　　if number[dlist[cur][0]]！＝0：
#该组还有替补选手，则继续参赛
　　　　　number[dlist[cur][0]]－＝1
　　　　　pre＝dlist[pre][1]
　　　　　cur＝dlist[cur][1]
　　　else：
　　　　　 #在链表中删除当前节点
　　　　　if cur＝＝head：
　　　　　　　head＝dlist[cur][1]
　　　　　print(dlist[cur][0]，″组被淘汰″)
　　　　　cur＝dlist[cur][1]
　　　　　left－＝1
　　　if left！＝0：
print(″剩余小组得分情况″)
printlist(head)
if __④________：
　print(″最终获胜的组是：″，dlist[head][0])
else：
findmax(score)
验收卷(五)　综合练习(A)
1.C　[本题考查不同数据结构的特性和算法描述。A选项队列和栈都是一种线性表，队列的特性是先进先出，栈的特性是先进后出。B选项递归求 n！要递推和回归两个阶段(分解问题，逐级返回)，迭代求 n！循环代码中参与运算的变量作为下一次循环计算的初始值。当 n 越大，迭代算法的效率明显高于递归算法。C选项使用数组这种数组结构在数组尾部进行数据插入和删除操作时，不会引起数据移动；D选项链表的操作需要从头指针开始，遍历到需要操作的节点，因为某单向链表(节点数>2)，所以在对该链表进行删除尾节点的操作时需要遍历从头指针开始到尾指针等多个节点。]
2.D　[本题考查队列的基本操作。T操作既有入队，又有出队，因此共有6次入队，4次出队，每次出队和入队，指针分别加1。]
3.D　[本题主要考查的是栈的入栈和出栈操作。已知当前栈中的元素从栈底到栈顶依次为“d，e，f，g”，说明入栈顺序为“d、e、f、g”，而元素f的进栈顺序则没有要求，因为元素d进栈可直接出栈，因此，ABC选项都有可能，D选项不可能是入栈顺序，因为元素f应在元素g之前入栈。]
4.D　[本题考查二叉树的基本性质。符合完全二叉树的两个条件为：①只有最下二层中的节点度数小于2；②最下一层的叶子节点都依次排列在该层最左边位置。A选项度指树的最大节点数。B选项若为满二叉树，第3层及前面所有节点数和为7，因此至少4层。C选项最后一层上有5个节点，即有叶子节点数为5，但第3层上还有一个叶子节点。]
5.D　[元素a[6]位于二叉树从上至下，从左到右第7个位置，即第3层最后一个。根据中序遍历画出图示如图所示。]
6.C　[循环5次，每次循环有3种可能，一是当i为偶数时，入队一个[1，9] 之间的整数，二是当i为奇数时，且q[tail－1]7. A　[本题考查栈的入栈和出栈。把握出入栈的条件，当栈为空(top＝＝－1)时入栈；当a[i]是偶数时，把栈顶中比该数小的数出栈，自身入栈。21入栈，10入栈，18先让10出栈，再入栈，18入栈，12入栈。]
8.B　[依次调用函数时，k的值为4，3，2，1，0，因此对应的字母c依次为edcba。chg(4)＝chg(3)＋″e″；chg(3)＝″d″＋chg(2) ；chg(2)＝chg(1)＋″c″；chg(1)＝″b″＋chg(0) ；chg(0)＝chg(－1)＋″a″，依次进行回归，chg(1)＝″ba″，chg(2)＝″bac″，chg(3)＝″dbac″，chg(4)＝″dbace″。]
9.C　[若第1次产生的随机数为1，则返回a[0]＋f(2*0＋1)，即3＋f(1)。若x的值为1，函数返回a[1]＋f(2*1＋randint(1，3))，产生随机数分别为1，2，3时，返回值依次为4＋6＝10，4＋7＝11，4＋8＝12，则3＋f(1)的值依次为13，14，15。若第1次产生的随机数为2，则返回a[0]＋f(2*0＋2)，其值为3＋5＝8。若第1次产生的随机数为3，则返回a[0]＋f(2*0＋3)，其值为3＋6＝9。]
10.D　[a[7]和a[6]、a[6]和a[5]、a[5]和a[4]依次比较，实现a[4]到a[7]升序，j为4时，并没有和a[3]比较和交换，但a[3]和a[2]、a[2]和a[1]、a[1]和a[0]依次比较和交换，形成有序序列。]
11.A　[本题考查对分查找。列表 a 中的元素为1－15 中的奇数，查找的 key 为 2－16 中的偶数，所以查找的结果不存在 a[m]＝＝key 也就是找到的情况，break 不会被执行。查找的过程如下：s 的值可能为－2，－1，1，3，共4种。]
12.D　[本题考查链表的插入。先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表；再连接两个链表得到新链表。]
13.(1)3　(2)①suma＋＝i　②tail＋＝1　③tail＝head＋1
解析　本题考查队列的基本操作。(1)以16包为一箱，因此箱号分别为1，2，2，2，3，3。共3箱。
(2)①统计口罩数量最多的包编号和累加各包口罩数量。 每箱口罩的数量肯定在maxa与suma－1之间，变量i枚举区间中每个数，当累积的数量t14.(1)DEF　(2)①cur＝st[top]　 ②f[st[j]]　③st[top]＝i
解析　本题考查栈的基本操作。(1)略。(2)栈st用于存储每次出现新的节点数，当有新的节点出现，不断地进栈，若找到终点，则开始出栈，并对每次访问起点的栈作好标记。①中将获取当前节点cur的值为st[top]。②变量j从0开始，不断地枚举栈，找到标志为真的节点，构成查找的路径。③发现一个新的节点，把新的节点入栈。
15.(1)C　(2)①dlist[head][1]　②0　③dlist[pre][1]＝dlist[cur][1]
④left＝＝1
解析　(1) A组各轮次结果分别为TFF，B组为FF，C组为TFT，D组为FTF，因此获胜的为C组。
(2)①链表 dlist数据区域值为组的名称，指针为下一下组的索引，已经输出头节点的信息，因此当前节点cur的初值为头节点的下一节点。②每一轮按A→B→C→D→A顺序轮流作答，将要构建一个循环链表，尾节点将指向第1个节点。③在链表中删除当前节点cur，将前驱指向当前节点的后继。④最后剩下一组，该组获胜。(共44张PPT)
第六章　大数据时代数据的组织
验收卷(五)　综合练习(A)
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
C
解析　本题考查不同数据结构的特性和算法描述。A选项队列和栈都是一种线性表，队列的特性是先进先出，栈的特性是先进后出。B选项递归求 n！要递推和回归两个阶段(分解问题，逐级返回)，迭代求 n！循环代码中参与运算的变量作为下一次循环计算的初始值。当 n 越大，迭代算法的效率明显高于递归算法。C选项使用数组这种数组结构在数组尾部进行数据插入和删除操作时，不会引起数据移动；D选项链表的操作需要从头指针开始，遍历到需要操作的节点，因为某单向链表(节点数>2)，所以在对该链表进行删除尾节点的操作时需要遍历从头指针开始到尾指针等多个节点。
A.队列和栈都是一种线性表，但两者有不相同的特性
B.采用相同公式求解n！，使用迭代算法比递归算法的算法效率高
C.使用数组结构在进行数据插入和删除操作时，一定会引起数据移动
D.某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个节点
D
2.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5 C.4　5 D.4　6
解析　本题考查队列的基本操作。T操作既有入队，又有出队，因此共有6次入队，4次出队，每次出队和入队，指针分别加1。
D
解析　本题主要考查的是栈的入栈和出栈操作。已知当前栈中的元素从栈底到栈顶依次为“d，e，f，g”，说明入栈顺序为“d、e、f、g”，而元素f的进栈顺序则没有要求，因为元素d进栈可直接出栈，因此，ABC选项都有可能，D选项不可能是入栈顺序，因为元素f应在元素g之前入栈。
D
4.已知一棵完全二叉树的节点总数为 12，则有关该二叉树的说法正确的是(　　)
A.树的度为12 B.树的层数为3
C.叶子节点数为5 D.最后一层有5个节点
解析　本题考查二叉树的基本性质。符合完全二叉树的两个条件为：①只有最下二层中的节点度数小于2；②最下一层的叶子节点都依次排列在该层最左边位置。A选项度指树的最大节点数。B选项若为满二叉树，第3层及前面所有节点数和为7，因此至少4层。C选项最后一层上有5个节点，即有叶子节点数为5，但第3层上还有一个叶子节点。
D
5.某二叉树的树形结构如图所示，其中序遍历结果为FDGBAEC。若补全为完全二叉树后，按从上到下、自左往右的顺序用一维数组a存储，其中根节点存储于元素a[0]中，则元素a[6]的值为(　　)
解析　元素a[6]位于二叉树从上至下，从左到右第7个位置，即第3层最后一个。根据中序遍历画出图示如图所示。
A.D B.F C.G D.C
6.有如下Python 程序段：
import random
q＝[0]*5
head，tail＝0，0
for i in range(5)：
　if random.randint(0，i)%2＝＝0：
　 q[tail]＝random.randint(1，9) #随机生成1到9之间的整数
　elif head　q[tail]＝q[head]
　head＋＝1
　tail＋＝1
print(q)
解析　循环5次，每次循环有3种可能，一是当i为偶数时，入队一个[1，9] 之间的整数，二是当i为奇数时，且q[tail－1]C
7.有如下 Python程序段：
a＝[21，5，10，9，18，10，5，18，12，11]
n＝len(a)
st＝[0]*n; top＝－1
for i in range(n)：
　if top＝＝－1：
　　　top＋＝1
　　　st[top]＝a[i]
　else：
　if a[i]%2＝＝0：
　　 　while top>－1 and a[i]>st[top]：
　　　　　top－＝1
A
解析　本题考查栈的入栈和出栈。把握出入栈的条件，当栈为空(top＝＝－1)时入栈；当a[i]是偶数时，把栈顶中比该数小的数出栈，自身入栈。21入栈，10入栈，18先让10出栈，再入栈，18入栈，12入栈。
　　　top＋＝1
　　　st[top]＝a[i]
while top>－1：
　　　print(st[top]，end＝″ ″)
　　　top－＝1
执行该程序段后，输出结果为(　　)
A.12　18　18　21 B.18　18　12
C.21　18　18　12 D.11　12　18　18　21
B
8.定义如下函数：
def chg(k)：
　if k＝＝－1：
　return ″″
　else：
　 c＝chr(ord(″a″)＋k)
　if k%2＝＝1：
　　　return c＋chg(k－1)
　else：
　　　return chg(k－1)＋c
执行语句m＝chg(4)后，m的值为(　　)
A.″ecabd″ B.″dbace″ C.″abcde″ D.″edcba″
解析　依次调用函数时，k的值为4，3，2，1，0，因此对应的字母c依次为edcba。chg(4)＝chg(3)＋″e″；chg(3)＝″d″＋chg(2) ；chg(2)＝chg(1)＋″c″；chg(1)＝″b″＋chg(0) ；chg(0)＝chg(－1)＋″a″，依次进行回归，chg(1)＝″ba″，chg(2)＝″bac″，chg(3)＝″dbac″，chg(4)＝″dbace″。
C
from random import randint
a＝[3，4，5，6，7，8]
def f(x)：
　if x<2：
　return a[x]＋f(2*x＋randint(1，3))
　else：
　return a[x]
A.8 B.9 C.10 D.13
解析　若第1次产生的随机数为1，则返回a[0]＋f(2*0＋1)，即3＋f(1)。若x的值为1，函数返回a[1]＋f(2*1＋randint(1，3))，产生随机数分别为1，2，3时，返回值依次为4＋6＝10，4＋7＝11，4＋8＝12，则3＋f(1)的值依次为13，14，15。若第1次产生的随机数为2，则返回a[0]＋f(2*0＋2)，其值为3＋5＝8。若第1次产生的随机数为3，则返回a[0]＋f(2*0＋3)，其值为3＋6＝9。
D
10.列表a中存储了8个元素，即a[0]，a[1]，…，a[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
　for j in range(n－1，i，－1)：
　 if a[j]　　　a[j－1]，a[j]＝a[j]，a[j－1]
该程序段实现的是(　　)
A.a[0]到a[7]升序排序
B.a[4]到a[7]升序排序
C.a[0]到a[7]的数据对4取余之后升序排序
D.a[0]到a[3]、a[4]到a[7]分别升序排序
解析　a[7]和a[6]、a[6]和a[5]、a[5]和a[4]依次比较，实现a[4]到a[7]升序，j为4时，并没有和a[3]比较和交换，但a[3]和a[2]、a[2]和a[1]、a[1]和a[0]依次比较和交换，形成有序序列。
11.如下 Python 程序段：
import random
a＝[1，3，5，7，9，11，13，15]
key＝random.randint(1，8)*2
i，j＝0，len(a)－1
s＝0
while i<＝j：
　m＝(i＋j＋1)∥2
　 if a[m]＝＝key：
　break
　if a[m]>key：
　j＝m－1；s－＝1
　else：
　i＝m＋1；s＋＝1
print(s)
上述程序执行完以后，s 的值可能有(　　)
A.4 种 B.5种 C.7种 D.8 种
A
解析　本题考查对分查找。列表 a 中的元素为1－15 中的奇数，查找的 key 为 2－16 中的偶数，所以查找的结果不存在 a[m]＝＝key 也就是找到的情况，break 不会被执行。查找的过程如下：s 的值可能为－2，－1，1，3，共4种。
12.将链表中的奇数节点和偶数节点分别排在一起，奇数节点和偶数节点的相对顺序不变。如原始链表为 ，新链表为 。部分程序如下：
#读入链表，存储在列表a中，head存储链表的头节点
odd＝head
even＝a[odd][1]
tmp＝even
while a[odd][1]！＝－1 and a[even][1]！＝－1：

解析　本题考查链表的插入。先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表；再连接两个链表得到新链表。
a[odd][1]＝tmp
上述程序段中方框处可选的语句为
①odd＝a[odd][1]
②even＝a[even][1]
③a[odd][1]＝a[even][1]
④a[even][1]＝a[odd][1]
则方框处语句依次为(　　)
A.①③②④ B.①②③④ C.③②④① D.③①④②
D
二、非选择题(本题共3小题，共26分)
13.(6分)疫情防控期间，某工厂为了将流水线上已生产的口罩及时装箱，并尽量分配给更多的疫情地区，需要设计一个程序实现自动化装箱。装箱要求为：流水线上生产的每包口罩数量有可能不同，装入箱子的口罩必须为流水线上连续的若干包，每箱内的口罩数量必须相同，在已知每包口罩数量和口罩总包数的前提下，装尽可能多的箱子。
例l：某流水线上有8包口罩，每包口罩的数量如下表：
包序号 1 2 3 4 5 6 7 8 每箱
数量
每包数量 12 3 9 6 6 9 3 12
箱号 (方案1) 1 2 2 3 3 4 4 5 12
箱号 (方案2) 1 1 2 2 3 3 4 4 15
箱号 (方案3) 1 1 1 1 2 2 2 2 30
在上述情况下，有3种分箱方案，方案1为最优方案。
例2：某流水线上有8包口罩，每包口罩的数量如下表：
序号 1 2 3 4 5 6 7 8
数量 1 3 5 7 9 11 13 15
在上述情况下，没有符合要求的装箱方案。
按照上述要求，编写一个Python程序，功能如下：读取流水线上每包口罩的数量，输出分箱结果，若存在装箱方案，则输出最多的装箱数，否则输出“无方案”。程序界面如图所示。
(1)假如流水线上生产的每包口罩数量依次为“16，5，3，8，7，9”，按照上述装箱要求，则装箱结果为________________。
包编号：1　2　3　4　5　6　7　8
包数量：12　3　9　6　6　9　3　12
方案1每箱12包，箱号：1—1，2—3，4—5，6—7，8—8
方案2每箱15包，箱号：1—2，3—4，5—6，7—8
方案3每箱30包，箱号：1—4，5—8
总共方案数为3，第一种方案最佳。
(2)代码如下，请在程序划线处填入合适的代码。
def F(x): #数字按固定长度输出
　 return (″　　 ″＋str(x))[－5：]
def Sa(a，h，t): #将数组索引号h至t－1之间的数值相加。
　 s＝0
　 for i in range(h，t)：
　 s＋＝a[i]
　 return s
#读取各包中口罩数量到数组a，并输出，代码略
maxa＝0；suma＝0
for i in a: #统计口罩数量最多的包编号和累加各包口罩数量。
　 if i>maxa：
　maxa＝i
if i>maxa：
　maxa＝i
　 ①____________
m＝0
for i in range(maxa，suma)：
　 xh＝[]
　 head＝0；tail＝1
　 while tail<＝n：
　 f＝False
　 t＝Sa(a，head，tail)
if t　　　 ②____________
　 elif t＝＝i：
　　 　 xh.append(tail－1)
　　　 f＝True
　　　 head＝tail
　　　　③____________
　 else：
　　　 break
　 if f：
　 m＋＝1
　 s＝″方案″＋str(m)＋″每箱″＋str(i)＋″包，箱号：1－″
　 for j in xh：
　　　 s＝s＋str(j＋1)＋″，″＋str(j＋2)＋″－″
　 print(s[：－3])
解析　本题考查队列的基本操作。(1)以16包为一箱，因此箱号分别为1，2，2，2，3，3。共3箱。
(2)①统计口罩数量最多的包编号和累加各包口罩数量。 每箱口罩的数量肯定在maxa与suma－1之间，变量i枚举区间中每个数，当累积的数量t答案　(1)3　(2)①suma＋＝i　②tail＋＝1 ③tail＝head＋1
14.(10分)某弹珠游戏，弹珠从起点到终点需要经过若干节点(不存在绕圈现象，且保证可以到达)，但方案可能不唯一。各节点关系如图a所示，寻找线路的方法：第1轮节点A进栈，作为当前节点，同时对A作起点标志为真操作，发现有B、D可以连通，B和D分别进栈，栈顶为D；第2轮以D为当前节点，对D作起点标志为真操作，从该节点出发，枚举所有的路线，直到到达终点。找到终点后，枚举栈中节点，查找起点标志为真的节点，输出可以从起点到终点达到的线路；接着对当前节点作出栈处理，往前查找一个出栈标志为假的节点，继续重复查找，直到栈中元素为空。
用数组存储各节点信息，节点A、B、C、D、E、F、G、H分别编号为0～7。数值1表示表格中左侧节点可达上方节点，数值0表示无法抵达。程序运行的结果如图所示，请在划线处填入合适的代码。
路径1：A，D，G，H
路径2：A，D，E，F，H
路径3：A，D，E，C，F，H
路径4：A，B，C，F，H
(1)起点为D，终点为F，经过节点数最少的线路图为________。
(2)实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
n＝8
#n为总的节点数，读取n*n个节点之间的信息，存储在二维数组 a中，若a[i][j]值为1，表示i节点到j节点可达。代码略。
st＝[0]*n
st[0]＝0；top＝0 #构建一个n个元素的栈
f＝[False]*n #是否以该节点为起点向后查找过
tot＝0 #记录可行路径的数量
while top！＝－1：
①________
f[cur]＝True　　
for i in range(n)：
　　 　if a[cur][i]＝＝1 ：
　　if i＝＝n－1：
　　　 　　tot＋＝1
　　　　 　s＝″″；j＝0
　　　　　 while j<＝top：
　　　　　　 　if ②________：
　　　　　　　　　s＝s＋str(chr(st[j]＋65))＋″，″
　　　　　　　 j＋＝1
　　　　　print(″路径″＋str(tot)＋″：″＋s＋chr(64＋n))
　 　　　　top－＝1
　　　　　while top>＝0 and f[st[top]]：
　　　　　　　top－＝1　　　　　　　　
　　 　else：　　　　　　
　　　 　　top＋＝1
　　　　 　③________
解析　本题考查栈的基本操作。(1)略。(2)栈st用于存储每次出现新的节点数，当有新的节点出现，不断地进栈，若找到终点，则开始出栈，并对每次访问起点的栈作好标记。①中将获取当前节点cur的值为st[top]。②变量j从0开始，不断地枚举栈，找到标志为真的节点，构成查找的路径。③发现一个新的节点，把新的节点入栈。
答案　(1)DEF　(2)①cur＝st[top]　 ②f[st[j]] ③st[top]＝i
15.(10分)王老师组织同学参加答题游戏，由“A”，“B”，“C”，“D”4个小组参与游戏，每个小组由k名学生组成，由1人代表小组答题。抽签确定开始的小组，每一轮按A→B→C→D→A顺序轮流作答，每答对一题加10分，每个选手答错一题即遭淘汰，由同组下一个选手补上，若该组所有选手都已淘汰则该组即遭淘汰，其他小组继续轮流作答，直到剩下最后一组，即为获胜小组，若最后一轮没有小组幸存，则分数最高的小组获胜。
(1)若每组有两个选手，从A组开始，经过3轮答题，答题结果为“TFTF”，“FFFT”，“FTF”(答对用T表示，答错用F表示)，则获胜的小组是______。
(2)王老师用链表数据结构设计了答题游戏的算法，并用 Python 编写程序模拟，实现了输入每组人数，随机产生开始的小组，输入每轮答题的情况，输出最后获胜的队伍。
该程序的 Python 代码如下，请在划线处填入合适的代码，完善程序。
def findmax(score)：
　#findmax 函数功能是在 4 个小组查找分数最高的小组并输出，代码略
def printlist(head): #输出当前剩余小组的得分情况
　　　print(dlist[head][0]，″组得分是″，score[dlist[head][0]])
　　　cur＝①________
　　　while cur！＝head：
print(dlist[cur][0]，″组得分是″，score[dlist[cur][0]])
cur＝dlist[cur][1]
k＝int(input(″输入每个组的人数：″))
code＝″ABCD″
dlist＝[[code[i]，i＋1] for i in range(4) ] #初始化链表 dlist
dlist[3][1]＝②________
head＝randint(0，3) #随机产生开始的小组
print(″从″，code[head]，″开始答题″)
number＝{} #存储每组剩余替补人数
score＝{} #存储每组得分数据
for i in dlist：
　number[i[0]]＝k－1
　score[i[0]]＝0
cur＝head
pre＝(head－1)%4
left＝4
while left>1：
　ans＝input(″输入本轮答题情况″)
　 for j in ans：
　　if j＝＝″T″：
　　　　score[dlist[cur][0]]＋＝10
　　　　pre＝dlist[pre][1]
　　　　cur＝dlist[cur][1]
　 　else：
　　　　if number[dlist[cur][0]]！＝0：
#该组还有替补选手，则继续参赛
　　　　　cur＝dlist[cur][1]
　　　　　left－＝1
　　　if left！＝0：
print(″剩余小组得分情况″)
printlist(head)
if __④________：
　print(″最终获胜的组是：″，dlist[head][0])
else：
　　findmax(score)
答案　(1)C　(2)①dlist[head][1]　②0
③dlist[pre][1]＝dlist[cur][1]　④left＝＝1
解析　(1) A组各轮次结果分别为TFF，B组为FF，C组为TFT，D组为FTF，因此获胜的为C组。
(2)①链表 dlist数据区域值为组的名称，指针为下一下组的索引，已经输出头节点的信息，因此当前节点cur的初值为头节点的下一节点。②每一轮按A→B→C→D→A顺序轮流作答，将要构建一个循环链表，尾节点将指向第1个节点。③在链表中删除当前节点cur，将前驱指向当前节点的后继。④最后剩下一组，该组获胜。

展开更多......

收起↑