资源简介

综合测试卷-2023—2024学年浙教版高中信息技术（2019）选择性必修1
一、选择题
1．定义如下函数：
def f(s,r):
if s-r**2<0 or r==0
return r+1
else:
return f(s-r**2,r-1)
执行语句k=f(50,5)后，k的值为（ ）
A．4 B．3 C．2 D．1
2．栈s的最大长度为4，初始已有两个元素在栈内，栈底为a，栈顶为b，经过一系列入栈、出栈操作，若元素入栈的顺序是c，d，e，f，则可能的出栈序列为（ ）
A．c，a，b，e，f，d B．b，d，f，e，c，a
C．a，b，d，c，e，f D．b，e，f，c，d，a
3．某二叉树的前序遍历结果为ABCEDF，在该二叉树基础上添加一个节点后的中序遍历为BGCADEF，则添加节点后的后序遍历结果为（ ）
A．CGBDFEA B．GCBADFE C．CGBEFDA D．GCBDFEA
4．使用数组存储某二叉树的形式如图所示，下列描述正确的是（ ）
0 1 2 3 4 5 6
A B C D
A．该二叉树的后序遍历为BDCA B．该二叉树的深度为2
C．该二叉树是一棵完全二叉树 D．该二叉树的叶子节点个数为3
5．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。

图a 图b
若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”所在节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为-1
链表更新顺序正确的是（ ）
A．③② B．③① C．①④ D．②④
6．有如下phthon程序，程序运行后，变量c的值为：（ ）
d=[1，7，5，2，3]
flag=False；last=i=c=0
while i<4 and flag==False：
flag=True
c+=1
for j in range（4，i，-1）：
if d[j] < d[j-1]：
d[j]，d[j-1]=d[j-1]，d[j]
flag=False；last=j
c+=1
i=last
A．6 B．7 C．8 D．9
7．有一棵完全二叉树，已知其中序遍历结果是CADGBEIHJ，则其前序遍历结果应该为（ ）
A．ABCDEFGHI B．EGACDBHIJ C．EACGBDIHJ D．EACDBHIJ
8．如下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种
9．找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下：
#链表a中存储了序列数据，head为其头指针，代码略
pre=p=head
maxpre=maxp=head
while p!=-1:
if a[p][0]>a[maxp][0]:
maxp=p ; maxpre=pre
pre=p
p=a[p][1]
if maxp==head:
head=a[head][1]
elif maxp!=pre:
①
a[pre][1]=maxp
②
#遍历输出链表a
划线处的代码应为（ ）
A．①a[maxp][1]=a[maxpre][1] ②a[maxp][1]=a[p][1]
B．①a[maxp][1]=a[maxpre][1] ②a[maxp][1]=p
C．①a[maxpre][1]=a[maxp][1] ②a[maxp][1]=a[p][1]
D．①a[maxpre][1]=a[maxp][1] ②a[maxp][1]=p
10．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（ ）
A．11 12 B．2 5 C．3 6 D．3 5
11．某二叉树的树形结构如图所示，其后序遍历结果为DBGEFCA，前序遍历的结果为（ ）
A．ABCDEFG B．ABDCEGF C．DBEGCFA D．ABDCGFE
12．栈s的最大长度为3，初始为空，经过一系列的入栈、出栈操作，若元素入栈的顺序是a，b，c，d，e，则可能的出栈序列为（ ）
A．a，e，d，c，b B．c，a，b，d，e
C．a，d，c，e，b D．e，d，c，b，a
13．某单向链表如下图所示，若要将数据data3和data4同时从链表中移除，至少需要修改几个节点的指针（ ）
A．1 B．2 C．3 D．4
14．栈S初始状态为空栈，将序列3,2,5,7,1中元素逐一入栈，当栈空或入栈元素比桟顶元素大时则入栈，否则出栈至符合条件再入栈。序列所有元素入栈完毕后，栈内剩余元素出栈，直至栈空。则出栈的顺序是（ ）
A．17523 B．37521 C．37512 D．32751
15．某对分查找算法Python程序段如下：
from random import randint
a=[8, 12,15,18, 18, 25, 25, 35, 47]
i=0; j=8
key=randint(8, 48)
while i<=j:
m=(i+j)//2
if key<=a[m]:
j=m-1
else:
i=m+l
print(i)
该程序执行完成后输出值为3，以下说法错误的是（ ）
A．key值可能是16到18的整数
B．该程序m=(i+j)//2被执行4次
C．该程序可实现查找第一个大于等于key值的位置
D．若key〈=a[m]改为key16．某二叉树的树形结构如图所示，其前序遍历结果为BADCFGE，则字符“G”所在的位置为（ ）
A．① B．② C．③ D．④
17．某种特殊的队列Q，支持以下三个操作：
操作Q1：若队列非空，队首元素出队，并输出；
操作Q2：若队列非空，队首元素出队；
操作Q3：一个元素入队；
以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。
若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是（ ）
A．当前队列中的元素个数为2
B．输出的元素个数为2
C．第一个输出的元素肯定比当前队首元素大
D．队列初始状态是否为空对输出结果有影响
18．定义如下函数：
def f（x,y）:
if x<=2 or y>20:
return x+y
return f（x-1,y+1）
执行语句k=f（5,1）后，k的值为（ ）
A．6 B．7 C．8 D．9
19．以下两个程序段的功能相同，实现的功能是：删除列表a（元素个数为n）中的重复元素（只保留一个），并将剩下的元素降序输出。
# 程序段① # 对列表a进行降序排序，代码略 i=1 while i0: print（i,end=""）
关于上述两个程序段及功能的描述，正确的是（ ）
A．同样的数据规模，两个程序段的时间效率一样
B．程序段①加框处语句是否执行不受列表a原数据的影响
C．程序段②加框处语句修改为“for i in range（1,max_num+1）”，输出结果不变
D．在实现该功能的过程中，程序段②比程序段①需要更多的存储空间
20．有如下程序段：
def fun（k）: if k==1: return ″1″ elif k%2==0: return fun（k-1）+str（k%2） else: return str（k%2）+fun（k-1）
执行语句s=fun（5），则s的值为（ ）
A．″00111″ B．″11010″ C．″11100″ D．″10110″
二、填空题
21．迭代算法与递归算法都需要 某些代码，两者既有区别又有密切的联系。迭代是重复 的活动，其目的通常是逼迫 ，其结束方式，通常使用 结束循环。
递归的重复方式是重复 ，其结束方式是遇到 的情况时逐层返回。
22．结合分治策略，递归也可以用 三个字概况。分：将原有问题 成K个子问题；治：对这K个子问题 。如果子问题的规模仍然不够小，则将其再分解为K个子问题，如此进行下去，直到问题足够小时，就很容易求出子问题的解。合：将求出的小规模问题的解 为一个更大规模问题的解，自下而上逐步求出原问题的解。
23．在数学与计算机领域中，递归函数是指用 定义该函数的方法。
24．def f(x,y):
ans=y;
for i in range(1,y-x+1):
ans = ans + f(x+i,y-i)
return ans;
def init():
x = int(input())
y = int(input())
print(f(x,y))
init()
(1)
输入：4
5
输出：
(2)
输入：3
6
输出：
25．小明同学所在城市的地铁线路局部图，如图所示。他计划从A站出发去B站附近的图书馆学习。假设地铁各线路每两站间行车用时相等，记为t1，停靠站时间忽略不计；换乘地铁的用时也都相等，记为t2。
（1）如果t1＝t2，小明同学希望尽快到达B站，试为他推荐一条最佳乘车路线。
（2）设t1＝2min，t2＝lmin，则小明从A站出发到达B站的最短用时为 min。
三、操作题
26．某快递驿站有A、B两类货架，收到的包裹重量小于等于10存放于A货架，其余存放于B货架。编写程序模拟生成取件码和顾客的取件过程，取件码是根据当前已处理的包裹数量生成，如A-0001表示当天第一个处理的包裹存放在A货架，B-0003表示当天第三个处理的包裹存放在B货架。取件码与顾客手机号关联，程序根据输入的手机号显示其所有包裹的取件码，并允许顾客一次性提取或者部分提取。程序的部分运行界面如图a和图b所示。
图a 图b
（1）当前已处理的包裹取件码是A-0158，若下一个包裹重量是12，其取件码为 。
（2）定义函数save（pnum，code），参数pnum为手机号，code为取件码。函数功能是将一条包裹信息存储到列表goods和列表dic中。如图a的包裹数据，手机号“1801215”在两个列表中的数据分别为goods[4]=["B-0005"，-1]、goods[9]=["A-0010"，4]和dic[2]=["180****1215"，9，2]。
①若调用该函数继续存储手机号“180****1215”的包裹，其取件码是“B-0011”，则对应dic[2]的值变为["180****1215"， ， ]。
②函数save代码如下，程序中加框处代码有错，请改正 。
def save（pnum，code）：
goods．append（[code，-1]）
n=len（goods）-1
print（n，"号包裹的手机号："，pnum，"取件码："，code）
num=search（dic，pnum）#函数返回手机号pnum在dic中的索引号，未找到返回-1
if num==-1：
dic.append（[pnum，n，1]） #新增一个包裹信息
else：
goods[n][1]=dic[num][1]
dic[num][1]=n

（3）实现取件功能的部分Python程序如下，请在划线处填入合适的代码。
x=input（"请输入您的手机号："）
num=search（dic，x）
if num！=-1：
#输出手机号为x的当前所有包裹信息，代码略
op=int（input（"输入0取全部包裹，输入1取部分包裹："））
if op==0：
print（"您的包裹已经取完！"）
del dic[num] #删除dic中索引为num的元素
else：
order=input（"请输入本次的取件码，只输入#表示结束取件："）
while order！="#"：

p，q=head，head
while goods[q][0]！=order：
p=q

if p==head：
dic[num][1]=goods[q][1]
else：
goods[p][1]=goods[q][1]
dic[num][2]-=1
if dic[num][2]==0：
print（"您的包裹已经取完！"）
break
#输出手机号为x的当前所有包裹信息，代码略
order=input（"请输入本次的取件码，只输入#表示结束取件："）
else：
print（"查无此号，请检查后重新输入！"）
27．为了进一步改善山区居民的生活，移动公司要将移动信号覆盖到某个山区小村，需要在现有信号基站到目标山区中间的若干山峰上建设基站。经过前期勘探，依次记录了n个山峰的信息，山峰编号依次为0到n﹣1，其中编号为0的山峰作为起点（信号接入位置），编号为n﹣1的山峰作为终点（目标覆盖区域），起点和终点必须建有基站。
工程师筛选中间基站建设位置的的过程中，若某一环节需要根据海拔高度筛选。从起点基站开始逐个山峰根据海拔高度，确定是否可以建设基站。具体规则如下：
①相邻两个基站的高度差的绝对值不能超过设定值d
②若最后一个选择的山峰与终点的高度差超过d，则需要在两座山峰之间建增加一个辅助基站，该基站建设高度为两座山峰的平均值，编号为n。
小梦编写了一个Python程序用于模拟这一过程。程序中n个山峰的海拔高度已存入列表a，用链表存储从起点到终点符合“海拔要求”的基站编号信息。
例如有7座山峰，海拔高度为a＝[100，80，90，88，80，66，60]，设定值d＝10。则依次选择的山峰的编号为0，2，3，4，7，6，海拔高度依次为100，90，88，80，70，60，其中编号为4的山峰高度为80，与终点（6号山顶）山峰的高度60超过d，则需增加一个编号为7，高度为70的辅助基站。执行效果如图所示。

（1）如果编号0到4的山峰的海拔高度依次为60，50，30，40，60，且d＝10，则选定的基站的高度依次为 。
（2）请在划线处填入合适的代码。 、 、

28．某会务组根据参会者到达指定上车点时间和每位参会者可以等待的时间信息，安排车辆接送参会者去宾馆（不考虑车子座位数量）。参会者到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如“08：15 2”表示参会者当天8点15分到达上车点，最多等待2分钟（每个人的等待时间都小于10），那么该参会者最晚8点17分出发去宾馆（若8点17分刚到的参会者也一同出发）。编写Python程序，统计接送n个参会者所需的最少车辆数。运行程序，显示所有参会者提交的信息，按到达时间先后排列，再显示所需的最少车辆数，程序运行结果如图所示。
（1）若将图中第4行“08：154”数据改为“08：151”，程序输出的结果是否会发生改变 （A．会改变B．不会改变）
（2）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
a=［'08：15 4'，'08：14 3'，'08：23 4'，'08：15 2'，'08：12 2'，'08：17 1'，'08：17 3'，'08：19 4'，'08：21 4'，'08：17 1'］
def tran（str1）：
ss=int（str1［：2］）*60+int（str1［3：6］）
return ss
for i in range（len（a）-1）：
for j in range（len（a）–1，i，-1）：
if a［j］a［j］，a［j-1］=a［j-1］，a［j］
n=len（a）
b=［］
c=［］
for i in range（n）：
b.append（tran（a［i］［：5］））
c.append（b［-1］+int（a［i］［6：］））
for j in range（i，0，-1）：
①
if c［k］>c［j］：
b［k］，b［j］=b［j］，b［k］
c［k］，c［j］=c［j］，c［k］
else：
break
sum=0
flag=［False for i in range（n）］
for i in range（n）：
if flag［i］==False：
for j in range（i，n）：
if ② ：
flag［j］=True
③
print（'接送所有参会者最少需要%d辆车'%sum）
29．临近年关，学校为活跃新年气氛，举办迎新年联欢活动，最后一个节目为“我是大赢家”抽奖活动，为增强互动效果，最后中大奖的中奖者由教师们自己互动产生，游戏规则是：全校所有教工，每人获得一个随机编号，编号不得重复，然后按照编号大小顺时针手拉手围成一个圈，最后一个老师与第一个老师手拉手，接下来由第1个人指定m的值，从编号为１的人开始报数（1,2,3…），报到m的人出圈，不再参加互动游戏，接着再由出圈人的上一位老师新指定m的值，并重新开始报数，逆时针报到m的人出列，游戏过程中出圈的人由老师们自己决定，如此继续，顺时针出一个人，逆时针出一个人，直到圈中只剩下一个人，他就是今天的最大赢家。小明编写了一个Python程序实现上述功能，程序运行时，输入参加游戏的人数，每次有人出圈后，再输入下一个要出圈的人数。
#删除索引为P 的游戏者
def delete(a,head,p):
if a[p][1]!=-1:
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
if head==p:
head=a[head][2]
return head
n=int(input("请输入参数游戏的人数"))
a=[[i+1,i-1,i+1] for i in range(n)]
a[0][1]=n-1
a[n-1][2]=0
p=head=0
while :
m=int(input("请输入顺时针数第几位人出局"))
for i in range(m-1):
head=delete(a,head,p)
p=a[p][1] #退回到上一位游戏者
if a[head][1]!=head:
m=int(input("请输入逆时针数第几位人出局"))
for i in range(m-1):
p=a[p][1]
head=delete(a,head,p)
#退回到上一位游戏者
print (a[head])
30．小萌通过“问卷星”收集到一些学生数据，如图a所示。在按关键字“用户名”进行排序的过程中，对数据进行整理，删除重复数据，处理结果如图b所示。

图a

图b
（1）在数据整理时，常见的数据问题有 （多选，选填字母）。
A．数据缺失 B．数据重复 C．逻辑错误 D．格式不一致
（2）实现上述功能的Python程序如下，请在划线处填入合适的代码。
a=[]
csv_file=open("xuehao.csv", "r", encoding='utf-8')
flines=csv_file. readlines() #将文件中所有数据按行读入flines中
csv_file. close() #关闭文件
# 将每个数据行中的各项信息以“，”作为分隔符切割成字符串存入列表a中
for line in flines:
tmp=list(line. strip("\n"). split(","))
a. append(tmp)
n=len(a)
i=1; m=n-l #变量m表示删除重复数据后的实际数据个数
while i for j in range(m, i, -1):
if :
tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp
elif a[j][4]==a[j-1][4]:
a[j]=a[m]

i+=1
for i in range (m+1):
print (a[i])
参考答案：
1．B
2．B
3．D
4．A
5．A
6．C
7．B
8．A
9．D
10．C
11．D
12．C
13．A
14．B
15．D
16．C
17．D
18．A
19．D
20．C
21． 重复执行 反馈过程 所需目标或结果 计数器 调用函数自身 满足终止条件
22． “分”“治”“合” 分解 分别求解 合并
23．函数自身
24． 9 22
25． A-L-K-H-G-B 或 A-L-K-J-I-B 12
26． B-0159 10 3 dic[num][2]+=1或dic[num][2]=dic[num][2]+1 head=dic[num][1] q=goods[q][1]
27． 60 50 40 50 60 i=i+1 link[p][1]=n temp=link[temp][1]
28． A k=j-1 flag［j］== False and b［j］<=c［i］或b［j］<=c［i］ sum+=1或sum=sum+1
29． a[a[p][2]][1]=a[p][1]或等同答案 a[head][2]!=head: 或len(a)!=1 或等同答案 p=a[p][2]或等同答案 p=a[p][2]或等同答案
30． ABCD a[j][4]

展开更多......

收起↑