资源简介

(共43张PPT)
第六章　大数据时代数据的组织
验收卷(六)　综合练习(B)
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.下列关于数据结构的说法，正确的是(　　)
D
解析　A选项数组中未使用到的空间导致内存浪费。B选项若删除的是头节点，只要修改头指针即可。C选项实现“后退”按钮的功能是栈的功能。D选项栈是一种受限的数据结构，只能在一端进行操作。
A.数组的最大元素数量在定义时就已确定，因此在操作过程中不会导致内存浪费
B.删除链表节点时，链表中必定存在某个节点的指针区域发生变化
C.浏览器采用队列结构组织网页数据从而实现“后退”按钮的功能
D.栈结构只有一端开放，数据进、出操作都只能在开放的一端进行
B
2.幼儿园中 8 个小朋友，依次编号(1－8)玩游戏，按编号顺序排队围成一圈，由编号 1 号的小朋友开始报数，报数报到 3 的小朋友出列，下一个编号的小朋友又从 1 开始报数，一直反复直到剩下最后一人，请问在该问题上采用的适合数据结构和剩下的小朋友的编号是(　　)
A.二叉树7 B.队列7 C.栈4 D.链表 4
解析　本题考查数据结构的相关知识。适合的数据结构应为队列，出队的顺序为：3，6，1，5，2，8，4，最后剩下的一人编号为 7。
B
3.在利用栈来判断一个表达式的括号(只有小括号)是否匹配的过程中，当遇到表达式中的一个左括号时，就让其进栈，遇到一个右括号时，就对栈进行一次出栈操作；当栈最后为空，表示括号是配对的，否则是不配对的。现有表达式“(a＋b)*c＋((d－e)*f＋g)*h”，针对该表达式设计栈的大小至少为(　　)
A.1 B.2 C.3 D.4
解析　遇到第一个左括号进栈，遇到第一个右括号时，栈中的左括号出栈。遇到第二个和第三个左括号，依次进栈。遇到第二个右括号，依次出栈，遇到第三个右括号，又依次出栈。此时栈为空，表达式中的括号配对成功。整个过程中，栈中最多有2个左括号，所以栈的大小至少为2。
D
4.有一棵树，节点的度和个数如下表所示。
解析　树中所有节点的度之和加1为节点总数，因此1*4＋2*3＋3*2＋4*1＝21。节点数为x＋4＋3＋2＋1＝x＋10，因此可以得到叶子节点数为11个。
度 0 1 2 3 4
节点个数 x 4 3 2 1
则叶子节点x的个数为(　　)
A.8 B.9 C.10 D.11
B
5.已知某二叉树的中序遍历结果为BFDGAEHC，层序遍历(从上往下、从左往右)结果为ABCDEFGH，则下列有关该二叉树的说法，正确的是(　　)
A.该二叉树是完全二叉树
B.用数组存储该二叉树时，节点F对应的数组下标为9
C.该二叉树有4个叶子节点
D.该二叉树的前序遍历结果为ABDFGCHE
解析　A为整棵树的根节点，从中序遍历来看，B和C分别是整棵树的左右节点。FDG是节点B的右子树，EH是节点C的左子树。第3层左边第1个节点为D，因此F是D的左子树，G是D的右子树。第3层左边第2个节点为E，因此H为E的右子树。画出树的形态如图所示。该树只有3个叶子节点，前序遍历为ABDFGCEH。
6.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　c[tail]＝a[i]
　tail＝tail＋1
　elif a[i]>c[head]：
　 head＝head＋1
print(c[head：tail])
解析　若队列中数据元素小于2或者t的值为0，则将a[i]入队，否则当a[i]大于c[head]时出队，a中元素既可以不入队，也可以不出队(t为1，且a[i]小于等于c[head])。A选项8，10入队，2和7可以不入队，11让8出队，队列中只剩下1个元素，9入队，接着t的值为0，16入队。B选项8，10入队后，接着t的值依次为1，1，0，0，0。C选项队首为8，当遍历到11时，要么让8出队，要么产生的t为0，11入队，因此C不可能。D选项11让队首8出队，当遍历到16时，产生的t为0，16入队。
C
7.有如下 Python 程序段：
import random
a＝[23，25，40，16，21，－1，－1，－1，21，－1，－1，－1，－1，－1，－1，－1，－1，－1，－1]
st＝[0]*10
key＝random.randint(10，19)*2＋1
top＝－1
n＝len(a)
i＝0；p＝0
while itop＋＝1；st[top]＝p
　　　if a[st[top]]＝＝－1 or key＝＝a[st[top]]:
　break
　　　elif key>a[st[top]]:
　 p＝p*2＋2
　else：
　p＝p*2＋1
　　i＋＝1
while(top！＝－1):
　　　print(st[top]，end＝″ ″)
　　　top－＝1
B
解析　本题考查栈的算法实现。产生21到39之间的任意奇数key，将列表a中对应数据的索引存放到栈中，若栈顶数据为空或者栈顶对应的值和key相同时，结束循环，若key值大于栈顶数据，将p*2＋2个位置存入栈中。若key小于栈顶数据时，将p*2＋1个位置入栈。A选项Key值大于23且小于等于39时，0，2，5位置数据入栈。C选项key值等于23时，存入数据为0，结束循环。D选项当key小于23时，0，1，3，8位置数据入栈。B选项当key值为21，不会出现0，1，4数据入栈。
B
8.定义如下函数：
def inquire(x，y，key)：
　 m＝(x＋y)∥2
　 if key＝＝a[m]：
　 return ″M″
　　elif key　return ″R″＋inquire(m＋1，y，key)
　　else：
　 return ″L″＋inquire(x，m－1，key)
数组a的元素为[55，49，37，26，24，14，3，3，1]，若执行语句h＝inquire(0，8，14)，则h的值是(　　)
A.LRM B.RLM C.MRL D.MLR
解析　程序的功能采用二分查找法查找14的过程。依次查找的数据为24，3和14，因此先向右查找，再向左查找，最后一次找到。
9.定义如下两个函数，fac_1和fac_2：
def fac_1(n)：
res＝1
for i in range(1，n＋1):
　　res *＝i
return res
def fac_2(n)：
if n＝＝1：
　　 return 1
else：
　return n * fac_2(n－1)
解析　本题考查迭代与递归的算法思想。两处程序的功能均为求n的阶乘。A选项程序fac_1体现迭代算法思想。B选项fac_1(4)只调用1次，而fac_2(4)要调用4次。C选项返回值均为24。D选项均循环了n次，因此算法效率一样。
B
下列说法正确的是(　　)
A.fac_1和fac_2都采用递归算法
B.执行fac_1(4)和fac_2(4)时，两个函数被调用次数不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函数的算法时间效率远大于fac_1
C
10.有如下Python程序段：
a＝list(map(int，input().split())) #将输入的数据转换成列表
n＝len(a)
for i in range(2)：
　for j in range(n－1，i，－1 )：
　if a[j] % 3>a[j－1] % 3：
　　　a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
解析　本题考查程序冒泡排序。从右往左(从后往前)进行了2趟排序，排序比较是元素%3后，最前面的2个元素除3余数一定是所有元素中最大的。
11.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下：
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　i＝0
　 j＝len(s)－1
　 rt＝″0″
　while i<＝j：
　m＝(i＋j)∥2
　if s[m]＝＝k：
　　　dc[k]＝rt
　　　break
　elif s[m]　 　　　　i＝m＋1
　　 　rt＋＝″1″
　else：
　 　j＝m－1
　　　rt＋＝″0″
inp＝input(″请输入英文字符串： ″).upper()
#将输入的英文字母转为大写
解析　构建一棵26个节点的升序二叉树，由于26小于31，因此最多查找4次，用一个4位二进制数存储访问的节点(标记为1)。
for c in inp：
　print(dc[c]，end＝″ ″)
当程序运行后，输入“OK”后，其输出的二进制编码为(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
A
12.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
i＋＝1
　　if i＝＝k：
　p＝people[q][1]
　people[q][1]＝people[p][1]
　if p＝＝head：
　　　head＝people[q][1]
　i＝1
　n－＝1
　　q＝people[q][1]
print(people[head][0])
该程序段运行后，若输入 2，则输出的结果为(　　)
A.3 B.5 C.6 D.2
B
解析　本题考查循环链表的算法实现。每遍历一次，i增加1，实现计数。第1次删除节点2，第2次删除节点4，第3、4、5分别删除节点6、3、1，链表中只剩下节点5。
二、非选择题(本题共3小题，共26分)
13.(6分)水房里一共有m个水龙头，每个龙头每秒钟的供水量均为1。现有按接水顺序从1到n编号的n名同学进行接水。一开始，m位同学同时接水，下一名排队等候接水的同学，接替接水时间最短同学的水龙头位置开始接水，以此类推，当其中一个水龙头完成某个同学的接水任务时，下一位等候的学生自动接上。每个水龙头的供水时间为在该水龙头上接水所有学生时间之和，所有同学接水的时间为供水时间最长的水龙头。第4位学生将在第1个水龙头接水，该水龙头放水8秒时，第4位和第5位学生分别接在第1个和第2个水龙头接水，第6位学生将在第9秒开始在第3个水龙头进行接水。
(1)7位学生在3个水龙头中接水时间(单位：秒)分别为“4，5，7，1，6，2，8”(不包括双引号)，则所有同学接水的总时间为________秒。
(2)编写程序运行结果如图所示，代码如下，请在划线处填入合适的代码。
需要取水时间分别为：4，8，9，4，5，6，8，7
笼头1取水时间：4，4，5，7
笼头2取水时间：8，6
笼头3取水时间：9，8
最多取水时间为：20
#读取n名同学进行接水时间存储到数组a中，代码略
m＝3；n＝len(a)
q＝[[0 for j in range(n)]for i in range(m)] #构建三个队列，用于记录每个水龙头接水情况
head＝[0]*3；tail＝[1]*3
q[0][0]＝a[0]；q[1][0]＝a[1]；q[2][0]＝a[2]
h＝3；t＝0 #h表示队列a中的指针，用于读取每个人的接水时间。t表示当前时间。
totaltime＝[a[0]，a[1]，a[2]] #存储每个水龙头总的接水时间
flag＝False
while ①________：
for i in range(3)：
if ②________：
　　　　if h　　　　　　　q[i][tail[i]]＝a[h]
　　　　　　　totaltime[i]＋＝a[h]
　　　　　　　h＋＝1
　　　　　　　③________
　　　　else：
　　　　　　flag＝True　　　　
t＋＝1
maxx＝max(totaltime)
#输出每个水龙头接水时间和最长接水时间，代码略。
答案　(1)15　(2)①not flag　②totaltime[i]＝＝t ③tail[i]＋＝1
解析　本题考查队列的基本操作。(1)水龙头1取水时间为4＋1＋6＝11，水龙头2取水时间为5＋2＋8＝15，水龙头3取水时间为7，最大取水时间为15。h表示队列a中的指针，用于读取每个人的接水时间。当条件h14.(10分)某停车场分为省内区和省外区，省内客车只能停靠在省内区，省外客车只能停靠在省外区。每辆客车抵达后，如果相应的区(省内区/省外区)还有空闲的近车位，就停靠在近车位，否则停靠在远车位(假设远车位的数量充足)。现给定未来一段时间客车的抵达、离开时刻，根据省内区和省外区的停车位数量，使停靠在近车位的客车数量最多，并显示各个车位停车情况。
车辆班次信息存储在 bc 列表中，存入顺序为先省内再省外，列表中的每个元素包含三个数据项，分别对应每个班次客车的车型(0 代表省内，1 代表省外)、抵达时间、离开时间。将省内班次和省外班次分别按抵达时间做升序排序，并计算停靠在近车位的车辆数量最多的车位分配方案，并显示各个车位停车情况，代码运行效果如图所示。
[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
省内班次：5　省外班次：4
最多停的班次数：7　分配省内车位数2　省外车位数：1
1号车位情况
[0，1，5]
[0，6，10]
[0，13，18]
2号车位情况
[0，3，8]
[0，9，14]
3号车位情况
[1，2，11]
[1，12，16]
(1)上图所示例子，车位分配方案改为省内 1 个、省外 2 个，则最多停靠班次数为________辆。
(2)实现上述功能的程序如下，请在划线处填入合适的代码。
def sort(st，ed): #对区间[st，ed]之间所有的车次按到达时间升序排列。
　for i in range(st，ed)：
　 for j in range(st，①__________):
　　　 　if bc[j][1]>bc[j＋1][1]：
　　　　 bc[j]，bc[j＋1]＝bc[j＋1]，bc[j]
bc＝[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
#[班次类型，抵达时间，离开时间] 0 表示省内 1 表省外 m＝3；x＝0；y＝0 #m 个近车位，x 个省内班次，y 个省外班次
for i in range(len(bc))：
　　　if bc[i][0]＝＝0:
x＋＝1
　　　else：
y＋＝1
print('省内班次数：'，str(x)，'省外班次数：'，str(y))
sort(0，x－1)
sort(x，x＋y－1)
maxstack＝[[0]*100 for i in range(m)]
maxtop＝[－1]*m；maxans＝0；maxi＝0；maxj＝0 #存储停车最多时的方案
def check(st，ed，j，stack，top):
　num＝－1
　for i in range(st，ed＋1)：
　if top[i]＝＝－1 or ②__________：
　 　　num＝i
　　 　break
　return num
for i in range(0，m＋1)：
　stack＝[[0]*100 for i in range(m)]
　 top＝[－1]*m；ans＝0
　for j in range(x＋y)：
if j　　　　k＝check(0，i－1，j，stack，top)
else：
　　　　k＝③________
if k！＝－1：
　　　　ans＋＝1；top[k]＋＝1
　　　　④__________
if ans>maxans:
maxans＝ans；maxstack＝stack；maxtop＝top
maxi＝i；maxj＝m－i
print('最多停的班次数：'，maxans，'分配省内车位数：'，maxi，'省外车位数：'，maxj)
for i in range(m)：
　print(i＋1，'号车位情况')
　 for j in range(maxtop[i]＋1):
print(bc[maxstack[i][j]])
答案　(1)6
(2)①ed－i＋st
②bc[stack[i][top[i]]][2]③check(i，m－1，j，stack，top)
④stack[k][top[k]]＝j
解析　(1)省内 1 个车位，分别停[0，1，5]、[0，6，10]、[0，13，18]共3个班次。省外2个车位，一个车位停[1，2，11]、[1，12，16]，另一个车位停[1，4，15] 共3个班次。(2)①内循环决定每趟排序的次数和起址位置。开始位置为st，因此实现从前往后冒泡，第一趟排序变量j的的终值为ed，此时变量i的值为st，随着i的增加，内循环终值将不断地减小，因此终值的值为ed＋st－i。②check函数判断某个班次是否可以停放到某个车位上。st表示起始车位编号，ed 表示结束车位编号，j 表示班次编号，stack 表示停车场的车位停放车辆信息，top 表示每个车位上停车数量的列表(即栈顶)。循环遍历起始车位到结束车位的车位列表，判断当前车位是否可以停放该班次，如果可以停放，则返回该
车位的编号；否则返回－1。停放的条件：该车位没有车辆停放或者该班次编号和前面已经停放的车辆班次再停放时间上没有重叠。bc[stack[i][top[i]]][2]表示标号为 i 的停车位最后停放车辆的离开时间。③枚举停车场中省内和省外车位的数量，计算出停车场中停放班次最多的方案。外循环枚举停车场中省内车位的数量，内循环枚举班次列表中的所有班次。当 j15.(10分)有60个人要组建一个聚会，每人的喜好是一个数值，为提升聚会效果，会务组要把参会人员进行分组，分组原则是：
1)每组不超过8人
2)组内新增人员的喜好值必须与现有组内人员的平均喜好值相差在5以内
3)若新增人员无法加入现有小组，则被分入新组建小组
采用Python编写了程序，运行结果如图所示：
第1组：4，6，8，2，2，7，2，8
第2组：50，45，43，48，48，43，43，42
第3组：14，11，13，16，17，18，17，13
第4组：21，26，19，23，23，18，23，22
第5组：37，35，38，34，33，35，33，33
第6组：16，13，10
第7组：43，45，47，40，45，44，44
第8组：28，28，33，29，34，32，27，33
第9组：37，38
(1)如图所示，当前数据已被分组，若再新增一个数“47”，会被分在第________组。
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
#读取n个人的喜好值，存储到列表a中代码略。
h＝[－1 for i in range(n)] #创建n个空的链表
ave＝[[0 for j in range(2)]for i in range(60)]
#用于存储每组喜好值的总和和人数
b＝[]
for i in a：
　j＝0 #表示从第0条链表开始遍历
　 p＝h[j]
　 while p！＝－1：
if abs(i－ave[j][0]/ave[j][1])>5 or ave[j][1]＝＝8：
　　　j＋＝1
　　 　①________
else：
　　　p＝b[p][1]
　b.append([i，－1])
　if h[j]＝＝－1: #每组第一个人，添加到链表头
　②________
　else：　　　　
　p＝h[j]　　　　
　while p！＝－1：
　　　bp＝p
　　　p＝b[p][1]
　 ③________
　　ave[j][0]＋＝i
　　ave[j][1]＋＝1
#输出各个分组情况，代码略
答案　(1)7　(2) ①p＝h[j]　 ②h[j]＝len(b)－1 ③b[bp][1]＝len(b)－1
解析　(1)第2至5组人数已经达到8人，第7组目前平均值为44，加入第7组后的平均喜好值相差在5以内。(2)分析程序可得，i表示当前参会人员个人喜好值；j表示当前组(从0开始编号)；p表示遍历链表b 的位置；变量h用于存储每组的头结点在链表b中的位置；①内层While循环中if语句表示当前的参会人员不能加入到该组，因此需要查看后面组的平均值以及当前总人数看是否能够加入到这些组中，知道找到第一个能插入的组，因此j＋＝1为往后找能存储的组，当找到可以加入的组时，需要添加在b中相应链表中，因此需要找到当前组的
头结点位置赋值给p，便于后续插入时查找位置。②该空位于if语句中，每组的第一个人，添加到链表头，h存储每组头结点的位置，由于是第一个，因此将该人员在b中的位置值复制给h相应组处，答案为h[j]＝len(b)－1。③非该组第一个人，插入时指针值为－1，单向链表因此需要修改前驱节点的指针值为该节点的位置，通过上个while循环可得前驱节点的位置存储在变量p中，因此答案为b[bp][1]＝len(b)－1。验收卷(六)　综合练习(B)
(考试时间40分钟　满分50分)
一、选择题(本题共12小题，每小题2分，共24分)
1.下列关于数据结构的说法，正确的是(　　)
A.数组的最大元素数量在定义时就已确定，因此在操作过程中不会导致内存浪费
B.删除链表节点时，链表中必定存在某个节点的指针区域发生变化
C.浏览器采用队列结构组织网页数据从而实现“后退”按钮的功能
D.栈结构只有一端开放，数据进、出操作都只能在开放的一端进行
2.幼儿园中 8 个小朋友，依次编号(1－8)玩游戏，按编号顺序排队围成一圈，由编号 1 号的小朋友开始报数，报数报到 3 的小朋友出列，下一个编号的小朋友又从 1 开始报数，一直反复直到剩下最后一人，请问在该问题上采用的适合数据结构和剩下的小朋友的编号是(　　)
A.二叉树7 B.队列7 C.栈4 D.链表 4
3.在利用栈来判断一个表达式的括号(只有小括号)是否匹配的过程中，当遇到表达式中的一个左括号时，就让其进栈，遇到一个右括号时，就对栈进行一次出栈操作；当栈最后为空，表示括号是配对的，否则是不配对的。现有表达式“(a＋b)*c＋((d－e)*f＋g)*h”，针对该表达式设计栈的大小至少为(　　)
A.1 B.2 C.3 D.4
4.有一棵树，节点的度和个数如下表所示。
度 0 1 2 3 4
节点个数 x 4 3 2 1
则叶子节点x的个数为(　　)
A.8 B.9 C.10 D.11
5.已知某二叉树的中序遍历结果为BFDGAEHC，层序遍历(从上往下、从左往右)结果为ABCDEFGH，则下列有关该二叉树的说法，正确的是(　　)
A.该二叉树是完全二叉树
B.用数组存储该二叉树时，节点F对应的数组下标为9
C.该二叉树有4个叶子节点
D.该二叉树的前序遍历结果为ABDFGCHE
6.有如下Python程序段：
import random
a＝[8，10，2，7，11，9，16]
c＝[0]*len(a)
head＝0；tail＝0
for i in range(len(a)):
　t＝random.randint(0，1)
　 if tail－head<2 or t＝＝0：
　c[tail]＝a[i]
　tail＝tail＋1
　elif a[i]>c[head]：
　 head＝head＋1
print(c[head：tail])
执行该程序段后，输出的内容不可能是(　　)
A.[10，9，16] B.[8，10，11，9，16]
C.[8，10，2，9] D.[10，7，16]
7.有如下 Python 程序段：
import random
a＝[23，25，40，16，21，－1，－1，－1，21，－1，－1，－1，－1，－1，－1，－1，－1，－1，－1]
st＝[0]*10
key＝random.randint(10，19)*2＋1
top＝－1
n＝len(a)
i＝0；p＝0
while i　　　top＋＝1；st[top]＝p
　　　if a[st[top]]＝＝－1 or key＝＝a[st[top]]:
　break
　　　elif key>a[st[top]]:
　 p＝p*2＋2
　else：
　p＝p*2＋1
　　i＋＝1
while(top！＝－1):
　　　print(st[top]，end＝″ ″)
　　　top－＝1
执行以上程序，不可能得到的输出结果是(　　)
A.5 2 0 B.10 4 1 0 C.0 D.8 3 1 0
8.定义如下函数：
def inquire(x，y，key)：
　 m＝(x＋y)∥2
　 if key＝＝a[m]：
　 return ″M″
　　elif key　return ″R″＋inquire(m＋1，y，key)
　　else：
　 return ″L″＋inquire(x，m－1，key)
数组a的元素为[55，49，37，26，24，14，3，3，1]，若执行语句h＝inquire(0，8，14)，则h的值是(　　)
A.LRM B.RLM C.MRL D.MLR
9.定义如下两个函数，fac_1和fac_2：
def fac_1(n)： res＝1 for i in range(1，n＋1): 　　res *＝i return res
def fac_2(n)： if n＝＝1： 　　 return 1 else： 　return n * fac_2(n－1)
下列说法正确的是(　　)
A.fac_1和fac_2都采用递归算法
B.执行fac_1(4)和fac_2(4)时，两个函数被调用次数不同
C.fac_1(4)和fac_2(4)的返回值不同
D.fac_2函数的算法时间效率远大于fac_1
10.有如下Python程序段：
a＝list(map(int，input().split())) #将输入的数据转换成列表
n＝len(a)
for i in range(2)：
　for j in range(n－1，i，－1 )：
　if a[j] % 3>a[j－1] % 3：
　　　a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
以下运行结果不可能的是(　　)
A.[20，50，10，40，30，60]　　B.[5，8，1，3，4，6]
C.[9，17，16，4，12，5] D.[17，11，1，4，9，6]
11.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下：
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
　i＝0
　 j＝len(s)－1
　 rt＝″0″
　while i<＝j：
　m＝(i＋j)∥2
　if s[m]＝＝k：
　　　dc[k]＝rt
　　　break
　elif s[m]　 　　　　i＝m＋1
　　 　rt＋＝″1″
　else：
　 　j＝m－1
　　　rt＋＝″0″
inp＝input(″请输入英文字符串： ″).upper()
#将输入的英文字母转为大写
for c in inp：
　print(dc[c]，end＝″ ″)
当程序运行后，输入“OK”后，其输出的二进制编码为(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
12.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
i＋＝1
　　if i＝＝k：
　p＝people[q][1]
　people[q][1]＝people[p][1]
　if p＝＝head：
　　　head＝people[q][1]
　i＝1
　n－＝1
　　q＝people[q][1]
print(people[head][0])
该程序段运行后，若输入 2，则输出的结果为(　　)
A.3 B.5 C.6 D.2
二、非选择题(本题共3小题，共26分)
13.(6分)水房里一共有m个水龙头，每个龙头每秒钟的供水量均为1。现有按接水顺序从1到n编号的n名同学进行接水。一开始，m位同学同时接水，下一名排队等候接水的同学，接替接水时间最短同学的水龙头位置开始接水，以此类推，当其中一个水龙头完成某个同学的接水任务时，下一位等候的学生自动接上。每个水龙头的供水时间为在该水龙头上接水所有学生时间之和，所有同学接水的时间为供水时间最长的水龙头。第4位学生将在第1个水龙头接水，该水龙头放水8秒时，第4位和第5位学生分别接在第1个和第2个水龙头接水，第6位学生将在第9秒开始在第3个水龙头进行接水。
(1)7位学生在3个水龙头中接水时间(单位：秒)分别为“4，5，7，1，6，2，8”(不包括双引号)，则所有同学接水的总时间为________秒。
(2)编写程序运行结果如图所示，代码如下，请在划线处填入合适的代码。
需要取水时间分别为：4，8，9，4，5，6，8，7 笼头1取水时间：4，4，5，7 笼头2取水时间：8，6 笼头3取水时间：9，8 最多取水时间为：20
#读取n名同学进行接水时间存储到数组a中，代码略
m＝3；n＝len(a)
q＝[[0 for j in range(n)]for i in range(m)] #构建三个队列，用于记录每个水龙头接水情况
head＝[0]*3；tail＝[1]*3
q[0][0]＝a[0]；q[1][0]＝a[1]；q[2][0]＝a[2]
h＝3；t＝0 #h表示队列a中的指针，用于读取每个人的接水时间。t表示当前时间。
totaltime＝[a[0]，a[1]，a[2]] #存储每个水龙头总的接水时间
flag＝False
while ①________：
for i in range(3)：
if ②________：
　　　　if h　　　　　　　q[i][tail[i]]＝a[h]
　　　　　　　totaltime[i]＋＝a[h]
　　　　　　　h＋＝1
　　　　　　　③________
　　　　else：
　　　　　　flag＝True　　　　
t＋＝1
maxx＝max(totaltime)
#输出每个水龙头接水时间和最长接水时间，代码略。
14.(10分)某停车场分为省内区和省外区，省内客车只能停靠在省内区，省外客车只能停靠在省外区。每辆客车抵达后，如果相应的区(省内区/省外区)还有空闲的近车位，就停靠在近车位，否则停靠在远车位(假设远车位的数量充足)。现给定未来一段时间客车的抵达、离开时刻，根据省内区和省外区的停车位数量，使停靠在近车位的客车数量最多，并显示各个车位停车情况。
车辆班次信息存储在 bc 列表中，存入顺序为先省内再省外，列表中的每个元素包含三个数据项，分别对应每个班次客车的车型(0 代表省内，1 代表省外)、抵达时间、离开时间。将省内班次和省外班次分别按抵达时间做升序排序，并计算停靠在近车位的车辆数量最多的车位分配方案，并显示各个车位停车情况，代码运行效果如图所示。
[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]] 省内班次：5　省外班次：4 最多停的班次数：7　分配省内车位数2　省外车位数：1 1号车位情况 [0，1，5] [0，6，10] [0，13，18] 2号车位情况 [0，3，8] [0，9，14] 3号车位情况 [1，2，11] [1，12，16]
(1)上图所示例子，车位分配方案改为省内 1 个、省外 2 个，则最多停靠班次数为________辆。
(2)实现上述功能的程序如下，请在划线处填入合适的代码。
def sort(st，ed): #对区间[st，ed]之间所有的车次按到达时间升序排列。
　for i in range(st，ed)：
　 for j in range(st，①__________):
　　　 　if bc[j][1]>bc[j＋1][1]：
　　　　 bc[j]，bc[j＋1]＝bc[j＋1]，bc[j]
bc＝[[0，6，10]，[0，1，5]，[0，9，14]，[0，13，18]，[0，3，8]，[1，12，16]，[1，2，11]，[1，7，17]，[1，4，15]]
#[班次类型，抵达时间，离开时间] 0 表示省内 1 表省外 m＝3；x＝0；y＝0 #m 个近车位，x 个省内班次，y 个省外班次
for i in range(len(bc))：
　　　if bc[i][0]＝＝0:
x＋＝1
　　　else：
y＋＝1
print('省内班次数：'，str(x)，'省外班次数：'，str(y))
sort(0，x－1)
sort(x，x＋y－1)
maxstack＝[[0]*100 for i in range(m)]
maxtop＝[－1]*m；maxans＝0；maxi＝0；maxj＝0 #存储停车最多时的方案
def check(st，ed，j，stack，top):
　num＝－1
　for i in range(st，ed＋1)：
　if top[i]＝＝－1 or ②__________：
　 　　num＝i
　　 　break
　return num
for i in range(0，m＋1)：
　stack＝[[0]*100 for i in range(m)]
　 top＝[－1]*m；ans＝0
　for j in range(x＋y)：
if j　　　　k＝check(0，i－1，j，stack，top)
else：
　　　　k＝③________
if k！＝－1：
　　　　ans＋＝1；top[k]＋＝1
　　　　④__________
if ans>maxans:
maxans＝ans；maxstack＝stack；maxtop＝top
maxi＝i；maxj＝m－i
print('最多停的班次数：'，maxans，'分配省内车位数：'，maxi，'省外车位数：'，maxj)
for i in range(m)：
　print(i＋1，'号车位情况')
　 for j in range(maxtop[i]＋1):
print(bc[maxstack[i][j]])
15.(10分)有60个人要组建一个聚会，每人的喜好是一个数值，为提升聚会效果，会务组要把参会人员进行分组，分组原则是：
1)每组不超过8人
2)组内新增人员的喜好值必须与现有组内人员的平均喜好值相差在5以内
3)若新增人员无法加入现有小组，则被分入新组建小组
采用Python编写了程序，运行结果如图所示：
第1组：4，6，8，2，2，7，2，8 第2组：50，45，43，48，48，43，43，42 第3组：14，11，13，16，17，18，17，13 第4组：21，26，19，23，23，18，23，22 第5组：37，35，38，34，33，35，33，33 第6组：16，13，10 第7组：43，45，47，40，45，44，44 第8组：28，28，33，29，34，32，27，33 第9组：37，38
(1)如图所示，当前数据已被分组，若再新增一个数“47”，会被分在第________组。
(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。
#读取n个人的喜好值，存储到列表a中代码略。
h＝[－1 for i in range(n)] #创建n个空的链表
ave＝[[0 for j in range(2)]for i in range(60)]
#用于存储每组喜好值的总和和人数
b＝[]
for i in a：
　j＝0 #表示从第0条链表开始遍历
　 p＝h[j]
　 while p！＝－1：
if abs(i－ave[j][0]/ave[j][1])>5 or ave[j][1]＝＝8：
　　　j＋＝1
　　 　①________
else：
　　　p＝b[p][1]
　b.append([i，－1])
　if h[j]＝＝－1: #每组第一个人，添加到链表头
　②________
　else：　　　　
　p＝h[j]　　　　
　while p！＝－1：
　　　bp＝p
　　　p＝b[p][1]
　 ③________
　　ave[j][0]＋＝i
　　ave[j][1]＋＝1
#输出各个分组情况，代码略
验收卷(六)　综合练习(B)
1.D　[A选项数组中未使用到的空间导致内存浪费。B选项若删除的是头节点，只要修改头指针即可。C选项实现“后退”按钮的功能是栈的功能。D选项栈是一种受限的数据结构，只能在一端进行操作。]
2.B　[本题考查数据结构的相关知识。适合的数据结构应为队列，出队的顺序为：3，6，1，5，2，8，4，最后剩下的一人编号为 7。]
3.B　[遇到第一个左括号进栈，遇到第一个右括号时，栈中的左括号出栈。遇到第二个和第三个左括号，依次进栈。遇到第二个右括号，依次出栈，遇到第三个右括号，又依次出栈。此时栈为空，表达式中的括号配对成功。整个过程中，栈中最多有2个左括号，所以栈的大小至少为2。]
4.D　[树中所有节点的度之和加1为节点总数，因此1*4＋2*3＋3*2＋4*1＝21。节点数为x＋4＋3＋2＋1＝x＋10，因此可以得到叶子节点数为11个。]
5.B　[A为整棵树的根节点，从中序遍历来看，B和C分别是整棵树的左右节点。FDG是节点B的右子树，EH是节点C的左子树。第3层左边第1个节点为D，因此F是D的左子树，G是D的右子树。第3层左边第2个节点为E，因此H为E的右子树。画出树的形态如图所示。该树只有3个叶子节点，前序遍历为ABDFGCEH。]
6.C　[若队列中数据元素小于2或者t的值为0，则将a[i]入队，否则当a[i]大于c[head]时出队，a中元素既可以不入队，也可以不出队(t为1，且a[i]小于等于c[head])。A选项8，10入队，2和7可以不入队，11让8出队，队列中只剩下1个元素，9入队，接着t的值为0，16入队。B选项8，10入队后，接着t的值依次为1，1，0，0，0。C选项队首为8，当遍历到11时，要么让8出队，要么产生的t为0，11入队，因此C不可能。D选项11让队首8出队，当遍历到16时，产生的t为0，16入队。]
7.B　[本题考查栈的算法实现。产生21到39之间的任意奇数key，将列表a中对应数据的索引存放到栈中，若栈顶数据为空或者栈顶对应的值和key相同时，结束循环，若key值大于栈顶数据，将p*2＋2个位置存入栈中。若key小于栈顶数据时，将p*2＋1个位置入栈。A选项Key值大于23且小于等于39时，0，2，5位置数据入栈。C选项key值等于23时，存入数据为0，结束循环。D选项当key小于23时，0，1，3，8位置数据入栈。B选项当key值为21，不会出现0，1，4数据入栈。]
8.B　[程序的功能采用二分查找法查找14的过程。依次查找的数据为24，3和14，因此先向右查找，再向左查找，最后一次找到。]
9.B　[本题考查迭代与递归的算法思想。两处程序的功能均为求n的阶乘。A选项程序fac_1体现迭代算法思想。B选项fac_1(4)只调用1次，而fac_2(4)要调用4次。C选项返回值均为24。D选项均循环了n次，因此算法效率一样。]
10.C　[本题考查程序冒泡排序。从右往左(从后往前)进行了2趟排序，排序比较是元素%3后，最前面的2个元素除3余数一定是所有元素中最大的。]
11.A　[构建一棵26个节点的升序二叉树，由于26小于31，因此最多查找4次，用一个4位二进制数存储访问的节点(标记为1)。]
12.B　[本题考查循环链表的算法实现。每遍历一次，i增加1，实现计数。第1次删除节点2，第2次删除节点4，第3、4、5分别删除节点6、3、1，链表中只剩下节点5。 ]
13.(1)15　(2)①not flag　②totaltime[i]＝＝t　③tail[i]＋＝1
解析　本题考查队列的基本操作。(1)水龙头1取水时间为4＋1＋6＝11，水龙头2取水时间为5＋2＋8＝15，水龙头3取水时间为7，最大取水时间为15。h表示队列a中的指针，用于读取每个人的接水时间。当条件h14.(1)6　(2)①ed－i＋st　②bc[stack[i][top[i]]][2]解析　(1)省内 1 个车位，分别停[0，1，5]、[0，6，10]、[0，13，18]共3个班次。省外2个车位，一个车位停[1，2，11]、[1，12，16]，另一个车位停[1，4，15] 共3个班次。
(2)①内循环决定每趟排序的次数和起址位置。开始位置为st，因此实现从前往后冒泡，第一趟排序变量j的的终值为ed，此时变量i的值为st，随着i的增加，内循环终值将不断地减小，因此终值的值为ed＋st－i。②check函数判断某个班次是否可以停放到某个车位上。st表示起始车位编号，ed 表示结束车位编号，j 表示班次编号，stack 表示停车场的车位停放车辆信息，top 表示每个车位上停车数量的列表(即栈顶)。循环遍历起始车位到结束车位的车位列表，判断当前车位是否可以停放该班次，如果可以停放，则返回该车位的编号；否则返回－1。停放的条件：该车位没有车辆停放或者该班次编号和前面已经停放的车辆班次再停放时间上没有重叠。bc[stack[i][top[i]]][2]表示标号为 i 的停车位最后停放车辆的离开时间。③枚举停车场中省内和省外车位的数量，计算出停车场中停放班次最多的方案。外循环枚举停车场中省内车位的数量，内循环枚举班次列表中的所有班次。当 j15.(1)7　(2) ①p＝h[j]　 ②h[j]＝len(b)－1
③b[bp][1]＝len(b)－1
解析　(1)第2至5组人数已经达到8人，第7组目前平均值为44，加入第7组后的平均喜好值相差在5以内。(2)分析程序可得，i表示当前参会人员个人喜好值；j表示当前组(从0开始编号)；p表示遍历链表b 的位置；变量h用于存储每组的头结点在链表b中的位置；①内层While循环中if语句表示当前的参会人员不能加入到该组，因此需要查看后面组的平均值以及当前总人数看是否能够加入到这些组中，知道找到第一个能插入的组，因此j＋＝1为往后找能存储的组，当找到可以加入的组时，需要添加在b中相应链表中，因此需要找到当前组的头结点位置赋值给p，便于后续插入时查找位置。②该空位于if语句中，每组的第一个人，添加到链表头，h存储每组头结点的位置，由于是第一个，因此将该人员在b中的位置值复制给h相应组处，答案为h[j]＝len(b)－1。③非该组第一个人，插入时指针值为－1，单向链表因此需要修改前驱节点的指针值为该节点的位置，通过上个while循环可得前驱节点的位置存储在变量p中，因此答案为b[bp][1]＝len(b)－1。

展开更多......

收起↑