精品解析：安徽滁州市定远县定远县育才学校2025-2026学年高二上学期2月期末信息技术试题

""

定远育才学校2025-2026学年高二（上）期末 信息技术试题 一、选择题：本大题共25小题，共50分。 1. 考生凭准考证上的座位号在考场内对号入座，座位号依次递增，且每个人的座位号都是固定的，适合用来存储考生的准考证信息的数据结构是（ ） A. 链表 B. 数组 C. 队列 D. 二叉树 【答案】B 【解析】 【详解】本题考查数据结构的选择能力。题目要求存储考生的准考证信息，且座位号依次递增并固定，这种情况下，适合使用数组。数组是一种线性表数据结构，支持通过下标快速访问元素，且元素在内存中是连续存储的，适合存储固定大小且顺序访问的数据。链表虽然也可以存储数据，但由于其节点不连续，访问效率不如数组。队列和二叉树则不适合用于这种固定顺序的存储需求。故答案为：B。 2. 玩一种寻宝游戏，根据第一条线索指向下一个地点，再根据在该地点找到的新线索去往下一个地点，直到最后“寻宝”成功。和该寻宝游戏相似的数据结构是（ ） A. 树 B. 链表 C. 队列 D. 栈 【答案】B 【解析】 【详解】本题考查数据结构的基本概念和应用能力。题目描述的寻宝游戏过程是线性且顺序的，符合链表的特性。链表是一种线性数据结构，其中的元素按顺序排列，每个元素指向下一个元素，类似于根据线索逐步找到下一个地点的过程。树结构具有分支，队列和栈则涉及到先进先出或后进先出的操作，不符合题目中线性顺序的特点。故答案为：B。 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 【答案】B 【解析】 【详解】本题考查队列的基本操作及数组元素的移动过程。入队过程（数组初始状态为空）： 入队23：a[0] = 23（下标0）。 入队4：a[1] = 4（下标1）。 入队1：a[2] = 1（下标2）。 入队5：a[3] = 5（下标3）。 入队6：a[4] = 6（下标4）。 队满：数组状态为[23, 4, 1, 5, 6]，数字5位于a[3]（下标3）。 出队23（a[0]）： 移除a[0]（23），后续数据前移：a[1]=4 → a[0]，a[2]=1 → a[1]，a[3]=5 → a[2]，a[4]=6 → a[3]。 数组状态：[4, 1, 5, 6, 空]。 数字5位置变化：从下标3 → 下标2。 出队4（a[0]）： 移除a[0]（4），后续数据前移：a[1]=1 → a[0]，a[2]=5 → a[1]，a[3]=6 → a[2]。 数组状态：[1, 5, 6, 空, 空]。 数字5位置变化：从下标2 → 下标1。 出队1（a[0]）： 移除a[0]（1），后续数据前移：a[1]=5 → a[0]，a[2]=6 → a[1]。 数组状态：[5, 6, 空, 空, 空]。 数字5位置变化：从下标1 → 下标0。 数字5位置下标变化序列：3 → 2 → 1 → 0。故选B。 4. 有人物简介如图所示。 图中没有体现的数据表现形式是（    ） A. 文字 B. 音频 C. 图像 D. 数值 【答案】B 【解析】 【详解】本题考查数据。根据题中人物简介图片可知，图中数据表现形式为数值，文字，图像。因此，本题选择B。 5. 现需要在存放着无重复非负整数的数组a中，找出最大值max1和次大值max2。实现该功能的程序如下，方框中应填入的正确代码为（ ） max1=max2=0 for i in range(len(a)): print("最大值为:"+str(max1)+",次大值为:"+str(max2)) A. B. C. D. 【答案】C 【解析】 【详解】本题考查的是数组的操作。遍历数组a中的元素，若a[i]大于最大值max1，则将此时的最大值max1赋值给次大值max2，将a[i]赋值给最大值max1。当a[i]小于最大值max1但大于次大值max2时，将次大值更新为a[i]，故方框中应填入的正确代码为选项C。 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]。实现该功能的程序段如下，方框中应填入的正确代码为（ ） temp=a[x] for i in range: a[i]=a[i+1] a[n-1]=temp A. （n-2,x-1,-1） B. （x,n-1） C. （x+1,n） D. （n-1,x,-1） 【答案】B 【解析】 【详解】本题考查Python程序设计相关内容。由“a[i]=a[i+1]”及示例“n为5，数组a为[0,3,4,6,7]，x为2，移动后a为[0,3,6,7,4]”知，程序段作用是将[x+1,n-1]元素依次前移一个位置，然后将x位置元素放在末尾，即n-1位置，则i的取值范围是[x,n-2]，结合range函数特点，方框中应填入的代码是：（x,n-1）。故本题答案是B选项。 7. 使用列表d模拟链表结构（节点数），如图a所示，每个节点包含数据区域和指针区域，h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]…d[n-1][0]中，最终保持节点链接关系不变，结果如图b所示。实现上述功能的Python程序段如下，方框中应填入的正确代码为（ ） p,i=h,0 while p!=-1: · tp=d[p][1] · if p==i: · · i+=1 · elif p>i: · · d[i][0],d[p][0]=d[p][0],d[i][0] · · · · i+=1 · p=tp '''调整头指针h及指针区域，保持节点链接关系不变，代码略''' A. B. C. D. 【答案】B 【解析】 【详解】本题考查链表。根据代码可知，当前节点为节点p，p从头节点开始进行遍历。变量i是从0开始顺序增加的，当p和i相等时，意味着该节点已经按链表顺序存放到d中的正确位置，因此不需要处理。当p>i时，需要修改数据的存放位置，即通过代码“d[i][0]，d[p][0]=d[p][0]，d[i][0]”将节点i和节点p的数据区域进行交换，交换之后，剩余节点必须仍然按照原链表的顺序遍历，故还要修改节点p的指针，指向节点i的后继，即d[p][1]=d[i][1]，再修改节点i的指针，指向节点p，即d[i][1]=p。循环结束后，还需要修改头指针h的值，以及重新调整每个节点的指针区域。因此，本题选择B。 8. 删除如下图中单向链表中 p 指向的节点（head 为头指针），正确的操作是（ ） A. p 指向节点的 next 值设为－1 B. 头指针 head 指向节点的 next 值设为 p 指向节点的 next 值 C. p 指向节点 next 值设为头指针 head 指向节点的 next 值 D. 将头指针 head 指向 p 指向节点的后续节点 【答案】B 【解析】 【详解】本题考查链表。删除单向链表节点是通过将该节点的前驱节点的指针指向该节点的后继节点来实现的。图中p所指节点的前驱节点为头指针head所指节点，后继节点为指针区域next所指节点q，将head所指节点的指针next指向p所指节点的后继节点，即head所指节点的next值赋为q。因此正确答案是B。 9. 一棵二叉树的深度为7，则该二叉树中的节点数最多为（ ） A. 127 B. 64 C. 63 D. 129 【答案】A 【解析】 【详解】本题考查二叉树相关内容。对于一棵二叉树，其节点数最多的情况是满二叉树。满二叉树的特点是每一层的节点数都达到了最大值，深度为k的二叉树，其总节点数为2k-1。则深度为7的二叉树最多有127个节点。故本题答案是A选项。 10. 有二叉树用数组表示如下图所示： 则关于该二叉树说法正确的是（ ） A. 该二叉树是完全二叉树 B. 该二叉树的叶子节点有3个，分别是C、H、M C. 该二叉树的后序遍历序列为C-F-A-M-G-H-D D. 该二叉树的层数为3，节点F在第3层 【答案】C 【解析】 【详解】本题考查二叉树相关内容。二叉树的数组表示是将非完全二叉树补全为一棵完全二叉树，然后从根节点开始，按从上而下、自左往右的顺序对节点进行编号，节点编号与数组的下标一一对应。根据二叉树的数组表示，可以画出非完全二叉树，如图所示： A选项，这是一棵非完全二叉树，选项错误。B选项，该二叉树的叶子节点有2个，分别是C、M，选项错误。C选项，后序遍历按“左右根”的顺序对二叉树节点进行访问，故该二叉树的后序遍历顺序为：C-F-A-M-G-H-D，选项错误。D选项，该二叉树的层数为4，节点F在第3层，选项错误。故本题答案是C选项。 11. 数学表达式3/（5*2）可用二叉树表示，如图所示。下列关于该二叉树的说法，正确的是（ ） A. 是完全二叉树 B. 叶子节点数为2 C. 前序遍历结果为352*/ D. 用数组表示为 【答案】D 【解析】 【详解】本题考查二叉树相关内容。A选项，完全二叉树是指除最后一层外，每一层上的节点数均达到最大值，且在最后一层上只缺少右边的若干节点，此二叉树不符合完全二叉树定义，选项说法错误。B选项，叶子节点数为3：3、5、2，选项说法错误。C选项，依据前序遍历规则，其前序遍历序列为/3*52，选项说法错误。D选项，将二叉树按照完全二叉树的结构存储，从根节点开始，逐层从左到右存储节点值，如果某个位置对应的节点不存在，则用一个特殊值（假设用null）表示，图片所示为该二叉树的顺序存储结构，选项说法正确。故本题答案是D选项。 12. 下列关于抽象数据类型的说法，不正确的是  （    ） A. 抽象数据类型在使用时无须知道内部实现的任何具体细节 B. 定义一个抽象数据类型，需要给出明确的形式要求、功能要求和类型名 C. 程序设计语言的内置类型不是抽象数据类型 D. 将问题分解成多个规模较小且容易处理的问题，建立功能模块 【答案】C 【解析】 【详解】本题考查抽象数据类型的基本概念和特性。程序设计语言的内置类型（如整数int、浮点数float、数组等）本质上是抽象数据类型。因为它们提供了数据操作的抽象接口（如+、-、索引等），而隐藏了底层实现细节（如在硬件中的二进制表示）。例如，在高级语言（如Python或Java）中，用户直接使用这些类型的操作，无需关心内部机制，因此内置类型属于抽象数据类型（ADT）的范畴。故答案为：C。 13. 定义如下函数： def fun(text, old, new): ans = [] i = 0 while i <= len(text) - len(old): if text[i:i+len(old)] == old: ans.append(new) i += len(old) # 匹配到子串后，跳过该子串的长度，避免重复匹配 else: ans.append(text[i]) i += 1 ans.extend(text[i:]) # 处理循环结束后剩余的字符 return "".join(ans) 已知自定义函数fun(text,old,new)与Python字符串内置方法str.replace(old,new)功能相似，则划线处应填入的代码是（ ） A. i+=1 B. i+=len(text) C. i+=len(new) D. i+=len(old) 【答案】D 【解析】 【详解】本题考查字符串替换的实现原理。题目要求实现一个与Python字符串内置方法str.replace(old,new)功能相似的自定义函数fun(text,old,new)。在函数中，使用while循环遍历字符串，当找到与old匹配的子串时，将其替换为new。关键在于正确更新索引i以跳过已替换的部分。由于每次替换后需要跳过被替换的old字符串长度，因此划线处应填入i+=len(old)。故答案为：D。 14. 某超市打算引入一套收银管理系统，已知备选系统1和2分别把各商品的价格存储在数组和链表中，下列说法正确的是（ ） A. 若收银系统中添加商品价格的操作比较多，则应选择备选系统1 B. 若收银系统中删除商品价格的操作比较多，则应选择备选系统1 C. 若收银系统中查询商品价格的操作比较多，则应选择备选系统2 D. 若收银系统中删除商品价格的操作比较多，则应选择备选系统2 【答案】D 【解析】 【详解】本题考查数组和链表的特性及在收银系统场景中的应用选择。A选项错误，数组存储空间连续，添加元素时需移动大量后续元素，操作效率低，添加商品价格操作多不应选系统1（数组）；B选项错误，数组删除元素同样需要移动后续元素，效率低，删除操作多不应选系统1（数组）；C选项错误，链表需从头节点遍历查询，访问效率低，数组支持随机访问，查询操作多应选系统1而非系统2（链表）；D选项正确，链表删除元素仅需修改节点指针指向，无需移动大量元素，操作效率高，删除商品价格操作多应选择系统2（链表）。因此，本题选择D选项。 15. 下列程序段的时间复杂度为（ ） n = int(input("n=")) s = 0 for i in range(1, n+1): for j in range(1, n+1): for k in range(1, n+1): s = s + k A. O(n) B. O(n2) C. O(n3) D. O(n log2n) 【答案】C 【解析】 【详解】本题考查时间复杂度的计算。程序段中有三个嵌套的循环，分别是 for i in range(1, n+1)、 for j in range(1, n+1)和for k in range(1, n+1)。每个循环都从 1 到 n，因此每个循环的迭代次数为 n。由于这三个循环是嵌套的，整个程序段的总操作次数为 n * n * n，即 n 的三次方。因此，该程序段的时间复杂度为 O(n³)。故答案为：C。 16. 下列程序段中（输入n的值的代码略）与流程图功能不一致的是（ ） A. 程序段① B. 程序段② C. 程序段③ D. 程序段④ 【答案】B 【解析】 【详解】本题考查程序段与流程图的功能一致性分析能力。先从流程图可知，每次循环对 n 做了a = (n − 1) % 2，然后将该 a “拼”到字符串最前端，再令 n = n // 2，直到 n = 0 为止。检验各程序段输出是否与流程图一致，只需挑选一些 n 值（如 n = 4 或 7）代入各段程序，看最终输出是否与流程图相同。 程序段①、③、④经逐步代入验证，均能与流程图对应的结果相匹配。 程序段②在拼接字符串时使用了“…+f(n//2)”的方式，测试如 n = 4 时得到”110”，而流程图应输出“011”，故与流程图不一致。故答案为：B。 17. 执行如下程序段后，数组a的值为（ ） a = ["231", "34", "23", "234", "123"] for i in range(1, 5): for j in range(5 - i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] A. ["23","34","123","231","234"] B. ["234","231","123","34","23"] C. ["34","234","231","23","123"] D. ["123","23","231","234","34"] 【答案】D 【解析】 【详解】本题考查Python中冒泡排序算法的实现以及字符串比较的规则。该程序段采用冒泡排序的双层循环结构对字符串数组进行升序排序，Python中字符串比较遵循按字符ASCII码逐个比较的规则，前序字符相同时长度长的字符串更大。初始数组为["231", "34", "23", "234", "123"]，外层循环控制排序轮次，内层循环进行相邻元素比较交换：i=1时数组变为["231","23","234","123","34"]；i=2时数组变为["23","231","123","234","34"]；i=3时数组变为["23","123","231","234","34"]；i=4时数组变为["123","23","231","234","34"]。因此，本题选择D选项。 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 【答案】C 【解析】 【分析】 【详解】本题考查的是对分查找。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。在数组中的数据是有序的，如果是增序的，是指下标越小的数组元素中存储的数据也越小，减序则相反。本题依次访问的数据为172,177,178，选项C正确。 19. 某对分查找算法的 Python 程序段如下： a = [8, 17, 24, 30, 36, 40, 55, 58, 61, 66] L, R = 0, 9 s = [] key = int(input("请输入要查找的数据：")) while L <= R: m = (L + R + 1) // 2 if a[m] == key: break elif a[m] > key: R = m - 1 else: L = m + 1 s.append(a[m]) print(s) 执行该程序段，当输入的值为30时，程序输出的结果是 A. [40, 24] B. [40, 24, 36] C. [24, 36] D. [36, 17, 24] 【答案】B 【解析】 【详解】本题主要考查对分查找算法及Python程序实现。当输入的值为30时，第一次循环，m = (L + R + 1) // 2=5，a[5]=40>key，R=m-1=4， s.append(a[m])=[40]；第二次循环，m = (L + R + 1) // 2=2，a[2]=24<key，L=m+1=3， s.append(a[m])=[40，24]；第三次循环，m = (L + R + 1) // 2=4，a[4]=36>key，R=m-1=3，s.append(a[m])=[40，24，36]；第四次循环，m = (L + R + 1) // 2=3，a[3]=30=key，循环结束，故程序输出的结果是[40, 24, 36]，故本题选B选项。 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. ①③ 【答案】C 【解析】 【详解】本题考查二分查找算法的使用条件相关知识。①错误，该组数据为无序数据，不满足二分查找要求数据有序的前提条件。②正确，该组数据为降序有序数据，满足二分查找的使用条件。③正确，该组数据为升序有序数据，满足二分查找的使用条件。因此，适合使用二分查找的是②③，本题选择C选项。 21. 下列关于实时查询数据系统中数据结构的说法，不正确的是（ ） A. 在实时查询系统中使用数组结构，插入数据信息的时效性较差 B. 在链表中查找数据时效性较高，插入数据时效性较低 C. 跳跃表基于有序链表，通过索引表跳跃着进行查找 D. 跳跃表通过跨区间、跳跃性的比较，减少了数据比较的次数，提高了效率 【答案】B 【解析】 【详解】本题考查数据结构在实时查询系统中的应用及其性能特点。选项A正确描述了数组结构在插入数据时的时效性问题，因为数组需要移动元素来插入新数据，时效性较差。选项B错误，因为链表在查找数据时效性较低，而插入数据时效性较高，因为链表插入数据只需调整指针。选项C正确描述了跳跃表的结构和查找方式，跳跃表通过索引表进行跳跃查找。选项D正确描述了跳跃表的效率优势，通过减少数据比较次数提高查找效率。因此，选项B的描述不正确。故答案为：B。 22. 某实时查询系统中约有400万条数据记录，如以跳跃表的形式来设计数据结构，其中每一级索引以二分形式来创建，则最多需要创建的索引级数是（ ） A. 17 B. 22 C. 100 D. 1000 【答案】B 【解析】 【详解】本题考查跳跃表的数据结构及其索引级数的计算能力。跳跃表是一种随机化的数据结构，支持快速的查找、插入和删除操作。对于一个包含 n 个元素的跳跃表，索引级数的最大值通常与 log2n 相关。题目中给出数据记录数为 400 万，即 n=4000000。因此，索引级数的最大值为 log24000000。计算 log24000000≈21.93158因此，索引级数的最大值约为 22。故答案为：B。 23. GeoHash字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串中，表示区域最大的是（ ） A. wtw B. wtw37 C. wtw37q D. wtw37j 【答案】A 【解析】 【详解】本题考查GeoHash字符串长度与区域大小的关系。GeoHash的字符串越短，表示的区域越大，因为短字符串代表的区域覆盖范围更广。题目要求选择表示区域最大的GeoHash字符串，因此需要选择长度最短的字符串。选项中，A选项“wtw”的长度最短，表示的区域最大。故答案为：A。 24. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串表示的区域中，与"wx4g0ec1"表示的区域最邻近的是（ ） A. "wz15j7f9" B. "wx4g0ebc" C. "wx4f8995" D. "wx451gbc" 【答案】B 【解析】 【详解】本题考查GeoHash字符串的公共前缀特性及其在邻近点搜索中的应用。GeoHash是一种用于地理位置编码的字符串表示方法，字符串的公共前缀越长，表示两个点的地理位置越接近。题目要求找出与“wx4g0ec1”最邻近的GeoHash字符串。解析过程如下：1. 目标GeoHash字符串为“wx4g0ec1”。2. 选项A：“wz15j7f9”，公共前缀为“w”，长度为1。3. 选项B：“wx4g0ebc”，公共前缀为“wx4g0e”，长度为6。4. 选项C：“wx4f8995”，公共前缀为“wx4”，长度为3。5. 选项D：“wx451gbc”，公共前缀为“wx4”，长度为3。通过比较各选项与目标字符串的公共前缀长度，选项B的公共前缀最长，为6。因此，选项B表示的区域与“wx4g0ec1”最邻近。故答案为：B。 25. GeoHash广泛应用于空间索引，尤其是POI数据查询的算法，根据材料，GeoHash算法涉及的空间索引技术主要是（ ） A. R树索引的空间索引技术 B. 四叉树编码索引的空间索引技术 C. 多级索引的空间索引技术 D. 网格索引的空间索引技术 【答案】D 【解析】 【详解】本题考查GeoHash算法对应的空间索引技术类型。A选项错误，R树索引是基于矩形边界的动态索引结构，通过将空间对象封装成最小外接矩形构建树形结构，与GeoHash原理不同；B选项错误，四叉树编码索引是将二维空间递归划分为四个象限进行编码，而GeoHash是将二维经纬度空间编码为一维字符串，核心是网格划分而非四叉树递归划分；C选项错误，多级索引是通过多层索引结构提升查询效率的索引设计方式，并非GeoHash对应的核心空间索引技术类型；D选项正确，GeoHash的核心原理是将地球表面的二维经纬度空间划分为大小不等的矩形网格，每个网格对应一个GeoHash编码，本质上属于网格索引的空间索引技术。因此，本题选择D选项。 二、非选择题：本大题共5小题，共50分。 26. 某校高二段n个班级举行飞镖比赛，初赛每位学生投掷飞镖并记录总成绩，每班录取前3名学生（成绩相同也被录取）。用Python程序实现各班按成绩降序输出，输出内容为班级、序号、总成绩，运行结果如图所示，请回答下列问题： （1）定义如下insert(h,info)函数，指针h指向该班的头节点，列表info的4个数据项依次为班级编号、学生序号、总成绩、后一节点的指针（初值为-1）。函数的功能是将学生信息info插入到指定班级的链表中，并确保链表中的节点按总成绩从高到低排序，返回该班级的头指针。请在划线处填入合适的代码 ①____、②____ （2）实现按照总成绩从高到低输出指定班级前3名学生信息的Python程序如下，请在划线处填入合适的代码 ①____、②____ （3）程序中加框处代码有错，请改正。____ 【答案】 ①. h= len(lst)- 1或return len(lst)-1 ②. p=q ③. last = lst[p][2] ④. bj = int(i[1:3]) ⑤. num<3 or lst[p][2]==last 【解析】 【详解】本题考查链表的插入操作及排序输出的实现能力。 （1）insert 函数的目的是将学生信息 info 插入到指定班级的链表中，并且保证链表中的节点按照总成绩从高到低排序。①处，当新节点的总成绩大于当前链表头节点的总成绩时，首先，执行 lst.append(info) 将新节点添加到列表 lst 的末尾。 接着，lst[len(lst) - 1][3] = h 将新节点的指针指向原来的头节点，此时新节点成为新的头节点。 所以，需要更新头指针 h 的值为新节点在 lst 中的索引，即 h = len(lst) - 1。这样，链表的头指针就指向了新插入的节点，新节点成为了链表的第一个节点。②处，在链表中查找合适的插入位置时，程序使用两个指针 p 和 q 来遍历链表，p 初始指向头节点 h，q 初始指向 lst[p][3]（即 p 节点的下一个节点）。 在 while 循环中，只要 q 不为 -1（表示未到达链表末尾）且 lst[q][2] > info[2]（即 q 节点的总成绩大于新节点的总成绩），就需要继续向后查找插入位置。 在每次循环中，需要将 p 指针移动到 q 指针的位置，以便继续向后遍历链表，所以 p = q。 （2）主程序的主要功能是读取学生参赛信息，将每个学生的信息插入到对应的班级链表中，然后按班级输出前 3 名学生的信息。 ①处，get 函数用于输出指定班级前 3 名学生的信息。 在遍历链表时，需要记录当前节点的总成绩，以便判断后续节点的总成绩是否与当前成绩相同。 所以，在每次输出一个节点的信息后，使用 last = lst[p][2] 记录当前节点的总成绩。②处，已知学生参赛信息存储在列表 data 中，每个元素是一个字符串，例如 'S010138' 表示班级 01 学生序号 01 总成绩为 38。 要从字符串中提取班级编号，字符串的第 2 到 3 个字符表示班级编号，所以使用 bj = int(i[1:3]) 提取并转换为整数类型。 （3）原条件存在逻辑错误。 原条件的含义是当已经输出的学生数量大于 3 且当前节点的总成绩等于上一个节点的总成绩时才继续输出，这与题目要求不符。 正确的逻辑应该是当已经输出的学生数量小于 3 或者当前节点的总成绩等于上一个节点的总成绩时，继续输出该节点的信息。所以应改为 num < 3 or lst[p][2] == last。这样可以确保输出前 3 名学生的信息，并且如果有成绩相同的学生也会一并输出。 27. 某年级举办文艺比赛，设有“合唱”和“趣味操”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程序如下，请在划线处填入合适的代码。_______ _______ _______ 【答案】 ①. 231 ②. BC ③. 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] 【解析】 【详解】本题考查Python综合应用。 （1）根据题目中的规则，对3个班级的较短项目表演时长进行升序排列，得到新的序列为[2，1，3]。然后根据各班表演项目的时长，按照“合唱”或“趣味操”的顺序依次添加到新的序列中。由于班级1的时长较短的项目为“合唱”，班级2的时长较短的项目为“趣味操”，班级3的时长较短的项目为“合唱”，所以最终的比赛顺序为231。故答案为：231。 （2）根据题目中的规则，对于较短时长所对应的项目为“合唱”的班级，直接将其添加到新的序列中；对于较短时长所对应的项目为“趣味操”的班级，将其从后往前依次添加到新的序列中。因此，在遍历完所有班级后，需要将栈顶的班级从后往前添加到新的序列中，即执行r.append(st[top])和top-=1。所以，top+=1应添加在位置①，top-=1应添加在位置④。此外，当top+=1添加在位置②，top-=1应添加在位置③也可以实现功能。故答案为：BC。 （3）在这个位置，我们需要检查当前班级的合唱时长是否大于趣味操时长。如果是，我们就将该班级的信息添加到列表m中，同时将其项目标记为1，表示趣味操。因此，这个空应该填写一个条件判断语句，用于比较合唱时长和趣味操时长。故答案为：data[i][0]>data[i][1]。在这里，我们需要设置一个循环的结束条件。变量ed表示尚未排序的班级数量，我们需要在所有班级都排序完成后结束循环。因此，这个空应该填写一个表达式，用于计算尚未排序的班级数量。故答案为：ed=n-1或ed=len(data)-1或ed=len(m)-1。在这个位置，我们需要计算当前班级完成比赛的时间。根据题目中的规则，当前班级完成比赛的时间等于前一个班级完成比赛的时间加上当前班级合唱项目的时长。因此，这个空应该填写一个表达式，用于计算当前班级完成比赛的时间。故答案为：t[i-1]+data[r[i-1]][0]。 28. 小蓝在学习二叉树的遍历时，发现前序遍历、中序遍历和后序遍历这三种遍历方式都不能很好反映出节点间的父子关系，于是他自创了一种新的遍历方式——“小蓝遍历”。其遍历的顺序如下：(a)访问根节点；(b)遍历左子树(若存在)；(c)遍历右子树(若存在)；(d)再次访问根节点。可以发现在“小蓝遍历”中，二叉树的每个节点都被访问了2次。例如，图a中二叉树的“小蓝遍历”为1-2-4-7-7-8-8-4-5-5-2-3-6-6-3-1。 图a 图b 请根据此背景，回答下列问题： （1）图a中以节点2为根的子树所对应的“小蓝遍历”为（ ）。 （2）小蓝发现“小蓝遍历”可以直观反映出节点的父子关系：在遍历过程中子节点第一次访问时间要晚于父节点，而第二次访问时间要早于父节点。于是小蓝利用这种遍历方式输入一棵二叉树，并编程求解任意两个节点之间的路径。如图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 = #步骤c print("-".join(ans)) #列表转换为字符串格式并输出 （3）加框处代码有误，请予以改正。____ （4）若输入的二叉树节点总数为n，则单次执行path()函数的时间复杂度为（ ）（单选，填字母） A.O(1) B.O(n) C.O(n2) D. O(2n) 【答案】 ①. 2-4-7-7-8-8-4-5-5-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!=[]或其他等价答案） ⑤. px[::-1]+[tmp]+py ⑥. B 【解析】 【详解】本题考查二叉树的遍历、栈的应用、列表的切片以及时间复杂度的计算等知识。 （1）题目中给出图a的“小蓝遍历”为：1-2-4-7-7-8-8-4-5-5-2-3-6-6-3-1。以节点2为根的子树对应的“小蓝遍历”中第一个数据和最后一个数据都为2，且为图a“小蓝遍历”的子序列，故以节点2为根的子树的“小蓝遍历”为：2-4-7-7-8-8-4-5-5-2。故答案为：2-4-7-7-8-8-4-5-5-2。 （2）path()函数的作用是求出根节点到某个节点的路径。其思路为：遍历“小蓝遍历”序列，当该节点第一次出现时，将其压栈，故答案为：top+=1 或 top=top+1；当栈顶元素和当前前节点相同时，将栈顶元素其弹出。若当前栈顶元素等于要找的节点时退出循环，此时从栈底元素到栈顶元素即为从根节点到该节点的路径，故答案为：st[:top+1]。。px、py分别存储根节点到x、y的路径。while循环实现从前往后删除两个序列的相同部分，每执行一次循环体，序列px和py的长度减少1，循环条件还需判断px和py的长度不为0，故答案为：len(px)>0 and len(py)>0 and px[0]== py[0]。 （3）px、py分别存储根节点到x、y的路径。要求x到y的路径需要将px路径反转在拼接；tmp为整型数据，不是列表，不能和列表直接拼接，需要将其转换为列表在进行拼接。故答案为：px[::-1]+[tmp]+py。 （4）二叉树节点数为n，则该二叉树的“小蓝遍历”共有2*n个数据，该path()函数的时间复杂度由for循环决定，for循环执行的次数为2*n次，去掉常数项，时间复杂度为O(n)。故答案为：B。 29. 如图所示是在Python中通过8组数据绘制得到的曲线图像及代码。 （1）图1所示的图表称之为 ______ 。 （2）程序第1行的功能 ______ 。 （3）程序运行结果从图1变为图2，应在第9行填写的代码是 ______ 。 （4）通过观察这8组数据的曲线变化趋势，推测此图像函数是 ______ 。 【答案】 ①. 散点图 ②. 导入numpy库，并给numpy起别名为np ③. plt.plot（x,y） ④. y=1/x 【解析】 【详解】本题考查图表类型识别和Python绘图代码的理解与应用。 （1）图1所示的图表称之为散点图。散点图用于显示数据点的分布情况，通常用于观察变量之间的关系。 （2）程序第1行的功能是导入numpy库，并给numpy起别名为np。这样可以方便地使用numpy库中的函数和方法。 （3）程序运行结果从图1变为图2，应在第9行填写的代码是plt.plot(x, y)。这行代码用于绘制折线图，将数据点连接起来，形成图2所示的曲线。 （4）通过观察这8组数据的曲线变化趋势，推测此图像函数是y=1/x。数据点的y值是x值的倒数，形成了典型的反比例函数曲线。 30. 某项活动有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,8 ②. B ③. 4 ④. data[i][1]-=m或data[i][1]=data[i][1]-m ⑤. j=data[i][1] ⑥. b[j-data[i][1]].append(v) 【解析】 【详解】本题考查Python程序设计综合。 （1）分组情况如图所示。 1号单位所分配的分组编号为：1，8。 （2）①考查冒泡排序，根据代码“if lst[j-1][1] < 1st[j][1]”以及if语句下面的代码可知，虚线框处将lst从右向左比较剩余员工人数，且较大的元素左移，因此，第一次执行后，lst[0][1]的位置上将放有剩余员工人数最大的元素。②程序若不执行break语句，则冒泡排序循环体执行次数是n-1次。若“for j…”在执行过程中检测到lst[i][1]值为0，则执行break语句。根据列表lst可知，第4趟循环时，1st[3][1]为0，执行break语句退出循环，故虚线框中的程序段执行4次。 （3）①处在各单位内部分组，data[i][1]存储单位员工人数，若data[i][1]大于等于小组人数上限m，则可进行一次分组，分组后为小组分配一个分组编号，每进行一次分组，data[i][1]存储的剩余人数为data[i][1]-m，若该值仍大于等于m，则需循环处理进行再次分组。故填入代码为data[i][1]-=m。②处利用“桶”的思想对剩余员工进行分组，先创建“空桶”，用桶编号0～m-1来表示对应小组的空位数，可能存在多个小组有相同空位数的情况。划线②处将单位编号为i的未分配剩余员工人数赋值给j，下方while循环寻找是否存在空位数满足要求的已建小组，若找到空位数满足要求的小组，则将该单位未分配人数分配到该小组中，若没有找到，则新建一个小组，故填入代码为j=data[i][1]。③处更新“桶”中的小组空位数情况。若没有新建小组，则程序是从空位数为j的小组中取到分组编号v，将剩余员工人数分配进去后，新的空位数为j-data[i][1]，在空位数为j-data[i][1]的桶中更新分组编号v。若新建小组分配剩余员工人数，则该小组的分组编号为v，空位数为m-data[i][1]，在新建小组的情况中，变量j值等于变量m值，即在空位数为j-data[i][1]的桶中更新分组编号v。故填入代码为b[j-data[i][1]].append(v)。 第1页/共1页 学科网（北京）股份有限公司 $ 定远育才学校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中，找出最大值max1和次大值max2。实现该功能的程序如下，方框中应填入的正确代码为（ ） max1=max2=0 for i in range(len(a)): print("最大值为:"+str(max1)+",次大值为:"+str(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]。实现该功能的程序段如下，方框中应填入的正确代码为（ ） temp=a[x] for i in range: a[i]=a[i+1] a[n-1]=temp A. （n-2,x-1,-1） B. （x,n-1） C. （x+1,n） D. （n-1,x,-1） 7. 使用列表d模拟链表结构（节点数），如图a所示，每个节点包含数据区域和指针区域，h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]…d[n-1][0]中，最终保持节点链接关系不变，结果如图b所示。实现上述功能的Python程序段如下，方框中应填入的正确代码为（ ） p,i=h,0 while p!=-1: · tp=d[p][1] · if p==i: · · i+=1 · elif p>i: · · d[i][0]d[p][0]=d[p][0],d[i][0] · · · · i+=1 · p=tp '''调整头指针h及指针区域，保持节点链接关系不变，代码略''' A. B. C. D. 8. 删除如下图中单向链表中 p 指向的节点（head 为头指针），正确的操作是（ ） A. p 指向节点的 next 值设为－1 B. 头指针 head 指向节点 next 值设为 p 指向节点的 next 值 C. p 指向节点的 next 值设为头指针 head 指向节点的 next 值 D. 将头指针 head 指向 p 指向节点的后续节点 9. 一棵二叉树的深度为7，则该二叉树中的节点数最多为（ ） A. 127 B. 64 C. 63 D. 129 10. 有二叉树用数组表示如下图所示： 则关于该二叉树的说法正确的是（ ） A. 该二叉树是完全二叉树 B. 该二叉树的叶子节点有3个，分别是C、H、M C. 该二叉树的后序遍历序列为C-F-A-M-G-H-D D. 该二叉树的层数为3，节点F在第3层 11. 数学表达式3/（5*2）可用二叉树表示，如图所示。下列关于该二叉树的说法，正确的是（ ） A. 是完全二叉树 B. 叶子节点数为2 C. 前序遍历结果为352*/ D. 用数组表示为 12. 下列关于抽象数据类型的说法，不正确的是  （    ） A. 抽象数据类型在使用时无须知道内部实现的任何具体细节 B. 定义一个抽象数据类型，需要给出明确的形式要求、功能要求和类型名 C. 程序设计语言的内置类型不是抽象数据类型 D. 将问题分解成多个规模较小且容易处理的问题，建立功能模块 13. 定义如下函数： def fun(text, old, new): ans = [] i = 0 while i <= len(text) - len(old): if text[i:i+len(old)] == old: ans.append(new) i += len(old) # 匹配到子串后，跳过该子串的长度，避免重复匹配 else: ans.append(text[i]) i += 1 ans.extend(text[i:]) # 处理循环结束后剩余的字符 return "".join(ans) 已知自定义函数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. 下列程序段的时间复杂度为（ ） n = int(input("n=")) s = 0 for i in range(1, n+1): for j in range(1, n+1): for k in range(1, n+1): s = s + k A. O(n) B. O(n2) C. O(n3) D. O(n log2n) 16. 下列程序段中（输入n的值的代码略）与流程图功能不一致的是（ ） A 程序段① B. 程序段② C. 程序段③ D. 程序段④ 17. 执行如下程序段后，数组a的值为（ ） a = ["231", "34", "23", "234", "123"] for i in range(1, 5): for j in range(5 - i): if a[j] > a[j + 1]: a[j], a[j + 1] = a[j + 1], a[j] 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 程序段如下： a = [8, 17, 24, 30, 36, 40, 55, 58, 61, 66] L, R = 0, 9 s = [] key = int(input("请输入要查找的数据：")) while L <= R: m = (L + R + 1) // 2 if a[m] == key: break elif a[m] > key: R = m - 1 else: L = m + 1 s.append(a[m]) print(s) 执行该程序段，当输入的值为30时，程序输出的结果是 A. [40, 24] B. [40, 24, 36] C. [24, 36] 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 23. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串中，表示区域最大的是（ ） A. wtw B. wtw37 C. wtw37q D. wtw37j 24. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串表示的区域中，与"wx4g0ec1"表示的区域最邻近的是（ ） A. "wz15j7f9" B. "wx4g0ebc" C. "wx4f8995" D. "wx451gbc" 25. GeoHash广泛应用于空间索引，尤其是POI数据查询的算法，根据材料，GeoHash算法涉及的空间索引技术主要是（ ） A. R树索引的空间索引技术 B. 四叉树编码索引的空间索引技术 C. 多级索引的空间索引技术 D. 网格索引的空间索引技术 二、非选择题：本大题共5小题，共50分。 26. 某校高二段n个班级举行飞镖比赛，初赛每位学生投掷飞镖并记录总成绩，每班录取前3名学生（成绩相同也被录取）。用Python程序实现各班按成绩降序输出，输出内容为班级、序号、总成绩，运行结果如图所示，请回答下列问题： （1）定义如下insert(h,info)函数，指针h指向该班的头节点，列表info的4个数据项依次为班级编号、学生序号、总成绩、后一节点的指针（初值为-1）。函数的功能是将学生信息info插入到指定班级的链表中，并确保链表中的节点按总成绩从高到低排序，返回该班级的头指针。请在划线处填入合适的代码 ①____、②____ （2）实现按照总成绩从高到低输出指定班级前3名学生信息的Python程序如下，请在划线处填入合适的代码 ①____、②____ （3）程序中加框处代码有错，请改正。____ 27. 某年级举办文艺比赛，设有“合唱”和“趣味操”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. 小蓝在学习二叉树的遍历时，发现前序遍历、中序遍历和后序遍历这三种遍历方式都不能很好反映出节点间的父子关系，于是他自创了一种新的遍历方式——“小蓝遍历”。其遍历的顺序如下：(a)访问根节点；(b)遍历左子树(若存在)；(c)遍历右子树(若存在)；(d)再次访问根节点。可以发现在“小蓝遍历”中，二叉树的每个节点都被访问了2次。例如，图a中二叉树的“小蓝遍历”为1-2-4-7-7-8-8-4-5-5-2-3-6-6-3-1。 图a 图b 请根据此背景，回答下列问题： （1）图a中以节点2为根的子树所对应的“小蓝遍历”为（ ）。 （2）小蓝发现“小蓝遍历”可以直观反映出节点的父子关系：在遍历过程中子节点第一次访问时间要晚于父节点，而第二次访问时间要早于父节点。于是小蓝利用这种遍历方式输入一棵二叉树，并编程求解任意两个节点之间的路径。如图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 = #步骤c print("-".join(ans)) #列表转换为字符串格式并输出 （3）加框处代码有误，请予以改正。____ （4）若输入的二叉树节点总数为n，则单次执行path()函数的时间复杂度为（ ）（单选，填字母） A.O(1) B.O(n) C.O(n2) D. O(2n) 29. 如图所示是在Python中通过8组数据绘制得到的曲线图像及代码。 （1）图1所示的图表称之为 ______ 。 （2）程序第1行的功能 ______ 。 （3）程序运行结果从图1变为图2，应在第9行填写的代码是 ______ 。 （4）通过观察这8组数据曲线变化趋势，推测此图像函数是 ______ 。 30. 某项活动有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页/共1页 学科网（北京）股份有限公司 $