安徽省定远县育才学校2025-2026学年高二（上）期末信息技术试题（含答案）

定远育才学校2025-2026学年高二（上）期末
信息技术试题
题号 一 二 总分
得分
一、选择题：本大题共25小题，共50分。
1.考生凭准考证上的座位号在考场内对号入座，座位号依次递增，且每个人的座位号都是固定的，适合用来存储考生的准考证信息的数据结构是（）
A. 链表 B. 数组 C. 队列 D. 二叉树
2.玩一种寻宝游戏，根据第一条线索指向下一个地点，再根据在该地点找到的新线索去往下一个地点，直到最后“寻宝”成功。和该寻宝游戏相似的数据结构是（）
A. 树 B. 链表 C. 队列 D. 栈
3.利用队列的思想对数组数据进行操作。例如，有一个长度为5的空数组a，数据依次入队，队满之后将所有数据从a[0]开始出队，即从数组中删除a[0]处的数据，a[1]及其之后的数据需要前移。将数据23，4，1，5，6逐个入队后出队，则当数据23，4，1出队后，数字5在数组中的位置下标的变化是（）
A. 4→3→2→1→0 B. 3→2→1→0 C. 2→1→0 D. 4→0
4.有人物简介如图所示。
图中没有体现的数据表现形式是 （ ）
A. 文字 B. 音频 C. 图像 D. 数值
5.数组a有n个无重复的非负整数，现要找出最大值max1和次大值max2。实现该功能的程序段如下，方框中应填入的正确代码为（）
A. B. C. D.
6.数组元素a[0]至a[n-1]依次存放着n个数据，现要将x(0≤x< n-1)位置的元素移动至a[n-1]，例如：n为5，数组a为[0,3,4,6,7]，x为2，移动后a为[0,3,6,7,4]。实现该功能的程序段如下，划线处应填入的正确代码为（）
A. n-2,x-1,-1 B. x,n-1 C. x+1,n D. n-1,x,-1
7.使用列表d模拟链表结构（节点数n>0），如图a所示，每个节点包含数据区域和指针区域，h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]…d[n-1][0]中，最终保持节点链接关系不变，结果如图b所示。实现上述功能的Python程序段如下，方框中应填入的正确代码为（）
A. B. C. D.
8.

A. A B. B C. C D. D
9.一棵二叉树的深度为7，则该二叉树中的节点数最多为（）
A. 127 B. 64 C. 63 D. 129
10.有二叉树用数组表示如下表所示：
则关于该二叉树的说法正确的是( )
A. 该二叉树是完全二叉树
B. 该二叉树的叶子节点有 3 个，分别是
C.
该二叉树的后序遍历序列为C-F-A-M-G-H-D
D. 该二叉树的层数为3，节点F在第3层
11.数学表达式3/(5*2)可用二叉树表示,如图所示。下列关于该二叉树的说法,正确的是

A. 是完全二叉树 B. 叶子节点数为 2
C. 前序遍历结果为352*/ D. 用数组表示为/3* 52
12.下列关于抽象数据类型的说法，不正确的是 （ ）
A. 抽象数据类型在使用时无须知道内部实现的任何具体细节
B. 定义一个抽象数据类型，需要给出明确的形式要求、功能要求和类型名
C. 程序设计语言的内置类型不是抽象数据类型
D. 将问题分解成多个规模较小且容易处理的问题，建立功能模块
13.定义如下函数：
已知自定义函数fun(text,old,new)与Python字符串内置方法str.replace(old,new)功能相似，则划线处应填入的代码是 （ ）
A. i+=1 B. i+=len(text) C. i+=len(new) D. i+=len(old)
14.某超市打算引入一套收银管理系统，已知备选系统1和2分别把各商品的价格存储在数组和链表中，下列说法正确的是（）
A. 若收银系统中添加商品价格的操作比较多，则应选择备选系统1
B. 若收银系统中删除商品价格的操作比较多，则应选择备选系统1
C. 若收银系统中查询商品价格的操作比较多，则应选择备选系统2
D. 若收银系统中删除商品价格的操作比较多，则应选择备选系统2
15.下列程序段的时间复杂度为（）
A. O(n) B. O(n2) C. O(n3) D. O(n log2n)
16.下列程序段中（输入n的值的代码略）与流程图功能不一致的是
A. 程序段① B. 程序段② C. 程序段③ D. 程序段④
17.执行如下程序段后，数组a的值为（）
A. ["23","34","123","231","234"] B. ["234","231","123","34","23"]
C. ["34","234","231","23","123"] D. ["123","23","231","234","34"]
18.某7位学员的身高（单位：cm）从高到低依次为：178，177，175，172，170，165，162，在用二分查找法找到178的过程中，依次被访问到的数据是（）
A. 178 B. 172，175，178
C. 172，177，178 D. 172，175，177，178
19.有如下Python程序段：
执行该程序段后，输入key的值为30，输出的结果是 （ ）
A. [40,24] B. [40,24,36] C. [40,24,36,30] D. [36,17,24]
20.要在一组数据中查找某一特定数据，可以根据数据结构选择合适的查找方法，有下列三组数据：
①52，76，5，59，46，29，62，64，26，27
②76，64，62，59，52，46，29，27，26，5
③5，26，27，29，46，52，59，62，64，76
适合使用二分查找的是 （ ）
A. ①②③ B. ①② C. ②③ D. ①③
21.下列关于实时查询数据系统中数据结构的说法，不正确的是 （ ）
A. 在实时查询系统中使用数组结构，插入数据信息的时效性较差
B. 在链表中查找数据时效性较高，插入数据时效性较低
C. 跳跃表基于有序链表，通过索引表跳跃着进行查找
D. 跳跃表通过跨区间、跳跃性的比较，减少了数据比较的次数，提高了效率
22.某实时查询系统中约有400万条数据记录，如以跳跃表的形式来设计数据结构，其中每一级索引以二分形式来创建，则最多需要创建的索引级数是（）
A. 17 B. 22 C. 100 D. 1000
GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。
23.下列GeoHash字符串中，表示区域最大的是（）
A. wtw B. wtw37 C. wtw37q D. wtw37j
24.下列GeoHash字符串表示的区域中，与"wx4g0ec1"表示的区域最邻近的是（）
A. "wz15j7f9" B. "wx4g0ebc" C. "wx4f8995" D. "wx451gbc"
25.GeoHash广泛应用于空间索引，尤其是POI数据查询的算法，根据材料，GeoHash算法涉及的空间索引技术主要是（）
A. R树索引的空间索引技术 B. 四叉树编码索引的空间索引技术
C. 多级索引的空间索引技术 D. 网格索引的空间索引技术
二、非选择题：本大题共5小题，共50分。
26.（10分）某校高二段n个班级举行飞镖比赛，初赛每位学生投掷飞镖并记录总成绩，每班录取前3名学生（成绩相同也被录取）。用Python程序实现各班按成绩降序输出，输出内容为班级、序号、总成绩，运行结果如图所示，请回答下列问题：
（1）定义如下insert(h，info)函数，指针h指向该班的头节点，列表info的4个数据项依次为班级编号、学生序号、总成绩、后一节点的指针（初值为-1）。函数的功能是将学生信息info插入到指定班级的链表中，并确保链表中的节点按总成绩从高到低排序，返回该班级的头指针。请在划线处填入合适的代码
（2）实现按照总成绩从高到低输出指定班级前3名学生信息的Python程序如下，请在划线处填入合适的代码
（3）程序中加框处代码有错，请改正。
27. （12分）某年级举办文艺比赛，设有“合唱”和“趣味操”2个项目，每个班级按先“合唱”再“趣味操”的比赛顺序进行。比赛场地分别在“音乐教室”和“操场”，一个场地同一时间只允许一个班级表演。为使比赛在最短时间内结束，利用Python程序合理调整各班表演顺序，并计算每个班级完成比赛的结束时间。
例如，有5个班级参加比赛，各班2个项目的表演时长如图a所示，找出各班2个项目中的较短时长，并按较短时长升序排列，得到新的序列如图b所示，再对各班按图b序列进行遍历，若该班时长较短的项目为“合唱”，或2个项目时长相等，则从前往后依次添加到新的序列中，若该班时长较短的项目为“趣味操”，则从后往前依次添加到新的序列中，得到最终的比赛顺序如图c所示，最后通过计算得到每个班级完成比赛的结束时间如图d所示。
请回答下列问题：
（1）若有3个班级参加比赛，各班2个项目的表演时长如图e所示，则班级的比赛顺序为________________（填3位数字，如123表示比赛顺序为1班、2班、3班）。
（2）定义如下sy(m)函数，功能是根据较短时长所对应的项目得到各班级最终的比赛顺序。参数m[i]由3个数据项构成，m[i][0]表示班级名称为m[i][0]+1，m[i][1]表示班级2个项目中表演较短的时长，m[i][2]表示表演较短时长所对应的项目，其中0表示“合唱”，1表示“趣味操”，m已按m[i][1]进行升序排列。
为实现该函数的功能，top+=1与top-=1两条语句应分别添加在________________（多选，填字母）位置。
A．①③ B．①④ C．②③ D．②④
（3）实现上述功能的部分Python程序如下，请在划线处填入合适的代码。
28. （10分） 小蓝在学习二叉树的遍历时，发现前序遍历、中序遍历和后序遍历这三种遍历方式都不能很好反映出节点间的父子关系，于是他自创了一种新的遍历方式——“小蓝遍历”。其遍历的顺序如下：
(a)访问根节点；(b)遍历左子树(若存在)；(c)遍历右子树(若存在)；(d)再次访问根节点。可以发现在“小蓝遍历”中，二叉树的每个节点都被访问了2次。例如，第15题图a中二叉树的“小蓝遍历”为1-2-4-7-7-8-8-4-5-5-2-3-6-6-3-1。
第 15 题图 a 第 15 题图 b
请根据此背景，回答下列问题：
（1）第 15题图a中以节点2为根的子树所对应的“小蓝遍历”为▲。
（2）小蓝发现“小蓝遍历”可以直观反映出节点的父子关系：在遍历过程中子节点第一次访问时间要晚于父节点，而第二次访问时间要早于父节点。于是小蓝利用这种遍历方式输入一棵二叉树，并编程求解任．意．两．个．节．点．之．间．的．路．径．。如第 15题图b所示，节点5到节点 8的路径为5-2-4-8。
具体求解的过程如下：
a. 分别求从根节点到两个节点的路径序列。图b中到5的路径序列为[1,2,5]，到8的路径 序列为[1,2,4,8]。
b. 从前往后删除两个序列的相同部分，并记录最后一个相同节点。上述例子中两个序列的相同部分为[1,2]，最后一个相同节点为2。
c. 将剩余部分和最后一个相同节点按顺序拼接起来。上述例子中[5]、[2]和[4,8]拼接得到 [5,2,4,8]。
请根据算法描述在划线处填入合适的代码。
def path(a,x): #步骤a st = ["*"] * len(a) top = -1
for i in a:
if top>═0 and st[top]══i: top-═1
else:
_____________①___________
st[top]=i if st[top]══x:
break
return______________②_____________
s = input() #s表示“小蓝遍历”，如“1-2-3-3-2-1” x = input() #x表示起点
y = input() #y表示终点
a = s.split( - ) #将s转换为列表格式px = path(a,x)
py = path(a,y)
while____________________③ : #步骤b tmp=px[0]
px=px[1:]
py=py[1:]
ans = px+tmp+py #步骤c
print("-".join(ans)) #列表转换为字符串格式并输出
（3）加框处代码有误，请予以改正。
（4）若输入的二叉树节点总数为 n，则单次执行path()函数的时间复杂度为 ▲ 。（单选，填字母）
A. O(1) B. O(n) C. O(n2) D. O(2n)
29. （8分）如图所示是在Python中通过8组数据绘制得到的曲线图像及代码。
(1) 图1所示的图表称之为 ______ 。
(2) 程序第1行的功能 ______ 。
(3) 程序运行结果从图1变为图2，应在第9行填写的代码是 ______ 。
(4) 通过观察这8组数据的曲线变化趋势，推测此图像函数是 ______ 。
30. （10分）某项活动有n个单位（编号1到n）参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。
若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。
设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。
编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：
（1）由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为__________。
（2）定义如下bubble_sort(1st)函数，参数1st的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对1st进行降序排序。
调用该函数，若1st为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]]，请回答①和②两个问题。
①虚线框中的程序段第1次执行后，关于1st中的剩余员工人数，下列说法正确的是__________（单选，填字母）。
A．1st[0][1]数值最小 B．1st[0][1]数值最大 C．1st[5][1]数值最小 D．1st[5][1]数值最大
②虚线框中的程序段执行的次数为__________。
（3）实现分组功能的部分Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中划线处填入合适的代码。
答 案
1.B 2.B 3.B 4.B 5.C 6.B 7.B 8.B 9.A 10.C 11.D 12.C 13.D 14.D 15.C
16.B 17.D 18.C 19.B 20.C 21.B 22.B 23A 24.B 25.D
26.(1)①h= len(lst)- 1或return len(lst)-1
②p=q
(2)①last = lst[p][2]
②bj = int(i[1:3])
(3)num<3 or lst[p][2]==last
27.（1）231
（2）BC
（3）①data[i][0]>data[i][1] 或其他等价答案② ed=n-1 或 ed=len(data)-1 或 ed=len(m)-1 ③t[i-1]+data[r[i-1]][0]
28.(1)2-4-7-7-8-8-4-5-5-2(-可以用其他符号代替)
(2)①top+=1或top=top+1
② st[:top+1] 或等价答案
③ len(px)>0 and len(py)>0 and px[0]==py[0]
(说明:len(px)>0 可以写成 px!=或其他等价答案)
(3)px[::-1]+[tmp]+py
(4)B
29.（1）散点图
（2）导入numpy库，并给numpy起别名为np
（3）】plt.plot（x,y）
（4）y=1/x
30.（1）1,8
（2）①B ②4
（3）①data[i][1]-=m或data[i][1]=data[i][1]-m ②j=data[i][1] ③b[j-data[i][1]].append(v)