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

定远育才学校2025-2026学年高二（上）1月月考 信息技术试卷 一、选择题：本大题共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. 采用相同公式求解 n!，使用迭代算法比递归算法的算法效率高 C. 使用数组结构在进行数据插入和删除操作时，一定会引起数据移动 D. 某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个节点 5. 数组元素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 6. 数组元素a[0]至a[n-1]依次存放着n个数据，现需要删除下标为x（0≤x< n-1）的元素。实现该功能的Python程序段如下，方框中应填入的正确代码为（ ） A. a[i+1]=a[i] B. a[i]=a[i+1] C. a[i-1]=a[i] D. a[i]=a[i-1] 7. 数组元素a[0]至a[n-1]依次存放着n个数据，现需要将元素a[n-1]插入在下标为x（0≤x< n-1）的位置，例如：n为5，数组a为[0,3,4,6,7]，x为2，插入操作后a为[0,3,7,4,6]。实现该功能的程序段如下，方框中应填入的正确代码为（ ） A. a[i+1]=a[i] B. a[i-1]=a[i] C. a[i]=a[i+1] D. a[i]=a[i-1] 8. 有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ） A. 2，9，5 B. 2，5，8 C. 5，8，2 D. 8，3，2 9. 如图所示为线性数据结构，下列关于线性结构的说法不正确的是（ ） A. 每个数据元素都有且仅有一个前驱和一个后继 B. 常见的线性数据结构有队列和栈 C. 可以使用数组或链表来存储线性数据结构 D. 栈的操作特征是“后进先出”，队列的操作特征是“先进先出” 10. 有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ） A. 2，9，5 B. 2，5，8 C. 5，8，2 D. 8，3，2 11. 列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为（ ） A. t B. n C. i D. r 12. 表达式树是包含表达式的数据结构，表达式树对于一些高性能的场景下有较大实用性。如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述中不正确的是（　　） A. 表达式树的根节点左右子树的深度差不会超过1 B. 对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理 C. 该表达式树对应的表达式为(6-3)/2+5*(7+2)/8 D. 该表达式树中的内部节点比分支节点少一个 13. 有二叉树用数组表示如下表所示，则关于该二叉树的说法正确的是（ ） 0 1 2 3 4 5 6 7 8 9 10 11 12 D A H F G C M A. 该二叉树完全二叉树 B. 该二叉树的叶子节点有3个，分别是C、H、M C. 该二叉树的后序遍历序列为C-F-A-M-G-H-D D. 该二叉树的层数为3，节点F在第3层 14. 有如下Python程序段： 执行该程序段后，输出的结果是（ ） A. A-B-D-C-E-F B. D-B-A-E-C-F C. D-B-E-F-C-A D. A-B-C-D-E-F 15. 有如下两个Python程序段，下列关于两个程序段的说法，正确的是（ ） A. 程序段1和程序段2都采用了递归算法 B. 若问题规模为n，程序段1和程序段2的时间复杂度都是O(n) C. 程序段1和程序段2的输出结果不相同 D. 程序段1中，代码（1）和代码（2）两处中的数字1同时修改为0，输出结果不变 16. 在数据序列1，3，4，5，5，7，9，10，11中查找第一个不小于5的元素下标，则下列说法中正确的是（ ） A. 使用顺序查找算法从左向右扫描，需要比较的次数为5次 B. 使用顺序查找算法从右向左扫描，需要比较的次数为6次 C. 使用二分查找算法中间位置左偏，需要比较的次数为4次 D. 使用二分查找算法中间位置右偏，需要比较的次数为3次 17. 有如下Python程序段： 下列关于该程序的说法，正确的是（ ） A. 程序执行结束后，a[0]的值为6 B. 程序的算法时间复杂度为O(n) C. 程序的算法时间复杂度为O(n2) D. 程序的算法空间复杂度为O(n2) 18. 有如下Python程序段： 执行该程序段后，数组a的值是（ ） A. [7,7,6,5,5,4] B. [7,6,5,4] C. [4,5,5,6,7,7] D. [4,5,6,7] 19. 下列关于实时查询数据系统中数据结构的说法，不正确的是（ ） A. 在实时查询系统中使用数组结构，插入数据信息的时效性较差 B. 链表中查找数据时效性较高，插入数据时效性较低 C. 跳跃表基于有序链表，通过索引表跳跃着进行查找 D. 跳跃表通过跨区间、跳跃性的比较，减少了数据比较的次数，提高了效率 20. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串中，表示区域最大的是（ ） A. wtw B. wtw37 C. wtw37q D. wtw37j 21. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串表示的区域中，与"wx4g0ec1"表示的区域最邻近的是（ ） A. "wz15j7f9" B. "wx4g0ebc" C. "wx4f8995" D. "wx451gbc" 22. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。GeoHash广泛应用于空间索引，尤其是POI数据查询的算法，根据材料，GeoHash算法涉及的空间索引技术主要是（ ） A. R树索引的空间索引技术 B. 四叉树编码索引的空间索引技术 C. 多级索引的空间索引技术 D. 网格索引的空间索引技术 23. 在如图所示的跳跃表中删除原链表中的元素10，则下列删除元素10之后的状态正确的是（ ） A. B. C. D. 24. 下面有关数据结构的说法不正确的是（ ） A. 在程序设计中，数据结构设计时主要考虑对象之间逻辑关系的实现 B. 链表结构适用于初始规模确定但在处理过程中频繁进行插入、删除操作的数据 C 数组结构中采用下标访问数据，访问效率要高于链表结构 D. 大多数软件中都有“撤销”功能，实现此功能应采用队列结构 25. 定义如下函数： 已知自定义函数fun(text,old,new)与Python字符串内置方法str.replace(old,new)功能相似，则划线处应填入的代码是（ ） A. i+=1 B. i+=len(text) C. i+=len(new) D. i+=len(old) 二、非选择题：本大题共3小题，共50分 26. 某校高二段n个班级举行飞镖比赛，初赛每位学生投掷飞镖并记录总成绩，每班录取前3名学生（成绩相同也被录取）。用Python程序实现各班按成绩降序输出，输出内容为班级、序号、总成绩，运行结果如图所示，请回答下列问题： （1）定义如下insert(h,info)函数，指针h指向该班的头节点，列表info的4个数据项依次为班级编号、学生序号、总成绩、后一节点的指针（初值为-1）。函数的功能是将学生信息info插入到指定班级的链表中，并确保链表中的节点按总成绩从高到低排序，返回该班级的头指针。请在划线处填入合适的代码 ①____、②____ （2）实现按照总成绩从高到低输出指定班级前3名学生信息的Python程序如下，请在划线处填入合适的代码 ①____、②____ （3）程序中加框处代码有错，请改正。____ 27. 一款智力玩具，有x种颜色的n个不同直径的同心圆盘（x＜n）。将圆盘串在倒T字型支架上，垂直俯视，直径不大于上方的圆盘将被遮挡，现从上方依次取走一片圆盘，记下能看到的颜色。最后说出取走几片圆盘后看到颜色种数最多，并说出颜色。某人取了6片5种颜色的圆盘随机叠放，如图a所示。他编写了如下程序来验证自己的结果是否正确，程序运行结果如图b所示。 请回答下列问题： （1）函数pop的功能是____。 （2）实现上述功能的部分程序如下页所示，请在划线处填入合适的代码。 ①____、②____、③____ 28. 正则表达式是用一些特定的字符组成的一个“规则字符串”。它可以实现检查一个字符串中是否包含有某种子串、将匹配的子串替换或者从字符串中取出符合某个条件的子串等操作。现规定2个符号规则： ①“.”可以匹配任意单个字符，例如a="wer"，b=".e."，则字符串a与b匹配。 ②“*”匹配0个或多个前一位字符，例如a="aadbc"，b="a*b*c，c="aaaaabc"，则字符串a与b不匹配，字符串b与c匹配。因为此时b匹配字符串是"abc"或"aabbc"或"aaabbbbbbbc"等。 请回答下列问题： （1）若字符串a="edffffgn"，b=".d*g."，则a与b____（选填：匹配/不匹配）。 （2）现有一个规则字符串p，包含规定的规则符号，编写如下Python程序，判断一个常规字符串s是否与p匹配，请在划线处填入合适的代码。 ①____、②____、③____ 第1页/共1页 学科网（北京）股份有限公司 $ 定远育才学校2025-2026学年高二（上）1月月考 信息技术试卷 一、选择题：本大题共25小题，共50分 1. 玩一种寻宝游戏，根据第一条线索指向下一个地点，再根据在该地点找到的新线索去往下一个地点，直到最后“寻宝”成功。和该寻宝游戏相似的数据结构是（ ） A. 树 B. 链表 C. 队列 D. 栈 【答案】B 【解析】 【详解】本题考查数据结构的基本概念和应用能力。题目描述的寻宝游戏过程是线性且顺序的，符合链表的特性。链表是一种线性数据结构，其中的元素按顺序排列，每个元素指向下一个元素，类似于根据线索逐步找到下一个地点的过程。树结构具有分支，队列和栈则涉及到先进先出或后进先出的操作，不符合题目中线性顺序的特点。故答案为：B。 2. 下列关于数组和链表的存储结构与逻辑结构关系的说法，正确的是（ ） A. 链表的存储结构与逻辑结构一致 B. 数组的存储结构对逻辑结构没有影响 C. 存放相同数据的数组存储空间大于链表 D. 链表数据逻辑结构由指针表示 【答案】D 【解析】 【详解】本题考查数据结构中数组和链表的存储结构与逻辑结构关系的理解。链表的逻辑结构是线性的（元素有顺序），但存储结构中元素（节点）在内存中不一定连续，而是通过指针链接。因此，存储结构与逻辑结构不一致。数组的存储结构对逻辑结构有影响，因为数组是连续存储的，逻辑结构通常是线性的。存放相同数据的数组通常比链表占用更少的存储空间，因为链表需要额外的指针来维护节点之间的关系。链表数据的逻辑结构由指针表示，指针用于连接各个节点，形成链式结构。故答案为：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 【答案】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. 采用相同公式求解 n!，使用迭代算法比递归算法的算法效率高 C. 使用数组结构在进行数据插入和删除操作时，一定会引起数据移动 D. 某单向链表(节点数>2)设有头尾指针，在删除该链表尾节点时需要遍历多个节点 【答案】C 【解析】 【详解】本题考查数据结构与算法效率相关内容。A选项，队列是一种先进先出（FIFO）的线性表，栈是一种先进后出（LIFO）的线性表，它们都是数据按顺序排列的线性结构，但因为进出数据的规则不同，所以有不同的特性，选项正确。B选项，采用相同公式求解n!，迭代比递归更高效（原因：无函数调用开销；内存占用更低；更适合计算大数阶乘），选项正确。C选项，在数组结构中，当在数组末尾插入或删除元素时，不需要移动其他数据，选项错误。D选项，单向链表中每个节点只知道下一个节点的地址，有头尾指针的单向链表（节点数>2），要删除尾节点，需要先找到尾节点的前一个节点，因为单向链表无法从后往前遍历，所以需要从链表头开始，依次顺着每个节点的指针遍历多个节点，直到找到尾节点的前一个节点，然后修改该节点的指针，使其不再指向尾节点，从而实现尾节点的删除，选项正确。故本题答案是C选项。 5. 数组元素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 【答案】B 【解析】 【详解】本题考查数组元素的移动操作及循环控制。由“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选项。 6. 数组元素a[0]至a[n-1]依次存放着n个数据，现需要删除下标为x（0≤x< n-1）的元素。实现该功能的Python程序段如下，方框中应填入的正确代码为（ ） A. a[i+1]=a[i] B. a[i]=a[i+1] C. a[i-1]=a[i] D. a[i]=a[i-1] 【答案】C 【解析】 【详解】本题考查数组元素的删除操作及数组元素的移动。为了删除下标为x的元素，需要将x后面的元素依次向前移动一位，从而覆盖掉x位置的元素。具体来说，从x+1开始遍历到n-1，将每个元素a[i]赋值给a[i-1]，即a[i-1]=a[i]。这样，原本在x位置的元素就被覆盖掉了，数组长度减1。故答案为：C。 7. 数组元素a[0]至a[n-1]依次存放着n个数据，现需要将元素a[n-1]插入在下标为x（0≤x< n-1）的位置，例如：n为5，数组a为[0,3,4,6,7]，x为2，插入操作后a为[0,3,7,4,6]。实现该功能的程序段如下，方框中应填入的正确代码为（ ） A. a[i+1]=a[i] B. a[i-1]=a[i] C. a[i]=a[i+1] D. a[i]=a[i-1] 【答案】A 【解析】 【详解】本题考查数组元素的插入操作及循环控制。初始a=[0,3,4,6,7]，x=2,n=5。首先备份最后一个元素7。接着通过for循环，i范围从n-2开始到x结束，根据a终值为[0,3,7,4,6]，可推导出循环体是进行了后移移位操作，既a[i+1]=a[i]。故本题应选A。 8. 有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ） A. 2，9，5 B. 2，5，8 C. 5，8，2 D. 8，3，2 【答案】B 【解析】 【详解】本题考查的是队列操作。队列操作原则是先进先出。经过TTT操作后队首到队尾的元素依次为9,5,8,3,2；再经过Q操作后队首到队尾的元素依次为5,8,3,2；再经过TT操作后队首到队尾的元素依次为3,2,5,8；再经过Q操作后队首到队尾的元素依次为2,5,8。故选项B正确。 9. 如图所示为线性数据结构，下列关于线性结构的说法不正确的是（ ） A. 每个数据元素都有且仅有一个前驱和一个后继 B. 常见的线性数据结构有队列和栈 C. 可以使用数组或链表来存储线性数据结构 D. 栈的操作特征是“后进先出”，队列的操作特征是“先进先出” 【答案】A 【解析】 【详解】本题考查线性数据结构的基本特征和常见类型。A. 每个数据元素都有且仅有一个前驱和一个后继：这描述的是双向链表的特性，而线性结构不一定是双向链表，单向链表或栈、队列等不符合此特性。B. 常见的线性数据结构有队列和栈：队列和栈确实是常见的线性数据结构。C. 可以使用数组或链表来存储线性数据结构：线性数据结构可以用数组或链表实现。D. 栈的操作特征是“后进先出”，队列的操作特征是“先进先出”：这是对栈和队列操作特征的正确描述。故答案为：A。 10. 有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ） A. 2，9，5 B. 2，5，8 C. 5，8，2 D. 8，3，2 【答案】B 【解析】 【详解】本题考查的是队列操作。队列操作原则是先进先出。经过TTT操作后队首到队尾的元素依次为9,5,8,3,2；再经过Q操作后队首到队尾的元素依次为5,8,3,2；再经过TT操作后队首到队尾的元素依次为3,2,5,8；再经过Q操作后队首到队尾的元素依次为2,5,8。故选项B正确。 11. 列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为（ ） A. t B. n C. i D. r 【答案】D 【解析】 【详解】本题考查列表操作和循环控制能力。初始条件：q[0…4] = ['p','r','i','n','t']，head=0，tail=5。 程序逻辑：当head%3=0时输出q[head]；否则将q[head]赋值给q[tail]并令tail自增。然后head自增，循环持续至head≥tail。 逐步跟踪可得到输出字符依次为：第一次head=0满足0%3=0，输出“p”；第四次head=3满足3%3=0，输出“n”；第七次head=6满足6%3=0，输出“i”；第十次head=9满足9%3=0，输出“t”；第十三次head=12满足12%3=0，输出“r”。因此，最后一个输出的字符为“r”。故答案为：D。 12. 表达式树是包含表达式的数据结构，表达式树对于一些高性能的场景下有较大实用性。如图所示，一个数学表达式可以用一棵表达式树来表示。下列关于该表达式树的描述中不正确的是（　　） A. 表达式树的根节点左右子树的深度差不会超过1 B. 对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理 C. 该表达式树对应的表达式为(6-3)/2+5*(7+2)/8 D. 该表达式树中的内部节点比分支节点少一个 【答案】A 【解析】 【详解】本题主要考查树结构。表达式树的根节点左右子树的深度差可以超过1；对该表达式树进行后序遍历得到的后序表达式，实现了无括号处理和优先级处理；该表达式树对应的表达式为(6-3)/2+5*(7+2)/8；该表达式树中的内部节点比分支节点少一个，故本题选A选项。 13. 有二叉树用数组表示如下表所示，则关于该二叉树说法正确的是（ ） 0 1 2 3 4 5 6 7 8 9 10 11 12 D A H F G C M 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选项。 14. 有如下Python程序段： 执行该程序段后，输出的结果是（ ） A. A-B-D-C-E-F B. D-B-A-E-C-F C. D-B-E-F-C-A D. A-B-C-D-E-F 【答案】A 【解析】 【详解】本题考查二叉树的遍历算法，具体是深度优先遍历（DFS）的非递归实现。初始时栈中仅有根结点下标0（对应“A”），弹出后将结果列表加入“A”； 按代码逻辑，先判断右子结点(c+1)，再判断左子结点c。对于根结点0，右子为2(“C”)、左子为1(“B”)，故依次向栈压入2、1； 栈顶1弹出后结果加入“B”，其右子下标4对应None不压栈，左子下标3(“D”)压栈； 栈顶3弹出后结果加入“D”，无子女； 栈顶2弹出后结果加入“C”，其右子6(“F”)、左子5(“E”)依次入栈； 弹出5后加入“E”，无子女；再弹出6加入“F”，无子女，循环结束； 最终输出顺序为“A-B-D-C-E-F”。故答案为：A。 15. 有如下两个Python程序段，下列关于两个程序段的说法，正确的是（ ） A. 程序段1和程序段2都采用了递归算法 B. 若问题规模为n，程序段1和程序段2的时间复杂度都是O(n) C. 程序段1和程序段2的输出结果不相同 D. 程序段1中，代码（1）和代码（2）两处中的数字1同时修改为0，输出结果不变 【答案】B 【解析】 【详解】本题考查程序段的递归与迭代实现及其时间复杂度分析。程序段1采用递归算法来计算阶乘，递归基条件是n==1时返回1，否则返回n*f(n-1)。程序段2采用迭代算法，通过循环计算阶乘。两者都计算阶乘，输出结果相同。1. 选项A：程序段1采用递归算法，程序段2采用迭代算法，故选项A错误。2. 选项B：程序段1的递归深度为n，时间复杂度为O(n)；程序段2的循环次数为n，时间复杂度也是O(n)，故选项B正确。3. 选项C：程序段1和程序段2都计算阶乘，输出结果相同，故选项C错误。4. 选项D：程序段1中将代码（1）和代码（2）中的数字1修改为0，递归基条件改变，输出结果会改变，故选项D错误。故答案为：B。 16. 在数据序列1，3，4，5，5，7，9，10，11中查找第一个不小于5的元素下标，则下列说法中正确的是（ ） A. 使用顺序查找算法从左向右扫描，需要比较的次数为5次 B. 使用顺序查找算法从右向左扫描，需要比较的次数为6次 C. 使用二分查找算法中间位置左偏，需要比较的次数为4次 D. 使用二分查找算法中间位置右偏，需要比较的次数为3次 【答案】D 【解析】 【详解】本题考查查找算法的效率分析。对于顺序查找算法，从左向右扫描时，序列为1, 3, 4, 5, 5, 7, 9, 10, 11，第一个不小于5的元素是5，位于第4个位置，因此需要比较4次。对于从右向左扫描，第一个不小于5的元素仍然是5，但需要扫描到第3个位置才能确认，因此需要比较7次。对于二分查找算法，序列已经有序，选择中间位置左偏或右偏，均需要3次比较即可找到第一个不小于5的元素。故答案为：D。 17. 有如下Python程序段： 下列关于该程序的说法，正确的是（ ） A. 程序执行结束后，a[0]的值为6 B. 程序的算法时间复杂度为O(n) C. 程序的算法时间复杂度为O(n2) D. 程序的算法空间复杂度为O(n2) 【答案】C 【解析】 【详解】本题考查插入排序算法的时间复杂度和空间复杂度。详细的解析过程：1. 该程序实现的是插入排序算法。插入排序的基本思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。2. 时间复杂度分析：插入排序的时间复杂度在最坏情况下（即数组是逆序的）为O(n²)，因为需要进行n次插入操作，每次插入操作可能需要移动n个元素。3. 空间复杂度分析：插入排序是就地排序算法，空间复杂度为O(1)，因为只需要常数个额外空间。故答案为：C。 18. 有如下Python程序段： 执行该程序段后，数组a的值是（ ） A. [7,7,6,5,5,4] B. [7,6,5,4] C. [4,5,5,6,7,7] D. [4,5,6,7] 【答案】A 【解析】 【详解】本题考查数组排序和计数排序的实现。程序中 b 用来记录各数值出现的次数，然后按从大到小的顺序将数组 a 中的元素依次填充。数组 a=[7,5,6,7,4,5] 中，7 出现 2 次，6 出现 1 次，5 出现 2 次，4 出现 1 次，程序执行后最终得到 [7,7,6,5,5,4]。故答案为：A。 19. 下列关于实时查询数据系统中数据结构的说法，不正确的是（ ） A. 在实时查询系统中使用数组结构，插入数据信息的时效性较差 B. 在链表中查找数据时效性较高，插入数据时效性较低 C. 跳跃表基于有序链表，通过索引表跳跃着进行查找 D. 跳跃表通过跨区间、跳跃性的比较，减少了数据比较的次数，提高了效率 【答案】B 【解析】 【详解】本题考查数据结构在实时查询系统中的应用及其性能特点。选项A正确描述了数组结构在插入数据时的时效性问题，因为数组需要移动元素来插入新数据，时效性较差。选项B错误，因为链表在查找数据时效性较低，而插入数据时效性较高，因为链表插入数据只需调整指针。选项C正确描述了跳跃表的结构和查找方式，跳跃表通过索引表进行跳跃查找。选项D正确描述了跳跃表的效率优势，通过减少数据比较次数提高查找效率。因此，选项B的描述不正确。故答案为：B。 20. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。下列GeoHash字符串中，表示区域最大的是（ ） A. wtw B. wtw37 C. wtw37q D. wtw37j 【答案】A 【解析】 【详解】本题考查GeoHash字符串长度与区域大小的关系。GeoHash的字符串越短，表示的区域越大，因为短字符串代表的区域覆盖范围更广。题目要求选择表示区域最大的GeoHash字符串，因此需要选择长度最短的字符串。选项中，A选项“wtw”的长度最短，表示的区域最大。故答案为：A。 21. 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。 22. GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。GeoHash广泛应用于空间索引，尤其是POI数据查询的算法，根据材料，GeoHash算法涉及的空间索引技术主要是（ ） A. R树索引的空间索引技术 B. 四叉树编码索引的空间索引技术 C. 多级索引的空间索引技术 D. 网格索引的空间索引技术 【答案】D 【解析】 【详解】本题考查空间索引技术的应用。GeoHash是一种用于地理位置编码的算法，它通过将地理坐标转换为字符串来实现空间索引。GeoHash的字符串长度决定了划分区域的大小，字符串的公共前缀可以用于快速查找邻近的点和区域。根据题目材料，GeoHash算法涉及的空间索引技术主要是网格索引的空间索引技术。网格索引通过将空间划分为固定大小的网格来实现快速查询和邻近点搜索，这与GeoHash的工作原理相符。故答案为：D。 23. 在如图所示的跳跃表中删除原链表中的元素10，则下列删除元素10之后的状态正确的是（ ） A. B. C. D. 【答案】D 【解析】 【详解】本题考查跳跃表的删除操作。跳跃表是一种多级索引结构，删除元素时需要更新各级索引的指针。“10”应当在原链表及其各级索引中同时删除，并相应更新指针。删除后：原链表从“1→3→4→10→13→15→20”变为“1→3→4→13→15→20”；由于“10”在一级和二级索引中都出现，需将它从索引中去掉，跳表的索引层是 “有用才留”，删除后二级索引层只有单独的1完全没用，将一级索引中“4”直接指向“15”。 据此可判断，正确的删除后结构应是选项D所示。故答案为：D。 24. 下面有关数据结构的说法不正确的是（ ） A. 在程序设计中，数据结构设计时主要考虑对象之间逻辑关系的实现 B. 链表结构适用于初始规模确定但在处理过程中频繁进行插入、删除操作的数据 C. 数组结构中采用下标访问数据，访问效率要高于链表结构 D. 大多数软件中都有“撤销”功能，实现此功能应采用队列结构 【答案】D 【解析】 【详解】本题考查的是数据结构。队列先进先出，栈先进后出，故大多数软件中都有“撤销”功能，实现此功能应采用栈结构。故本题应选D。 25. 定义如下函数： 已知自定义函数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。 二、非选择题：本大题共3小题，共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. 一款智力玩具，有x种颜色的n个不同直径的同心圆盘（x＜n）。将圆盘串在倒T字型支架上，垂直俯视，直径不大于上方的圆盘将被遮挡，现从上方依次取走一片圆盘，记下能看到的颜色。最后说出取走几片圆盘后看到颜色种数最多，并说出颜色。某人取了6片5种颜色的圆盘随机叠放，如图a所示。他编写了如下程序来验证自己的结果是否正确，程序运行结果如图b所示。 请回答下列问题： （1）函数pop的功能是____。 （2）实现上述功能的部分程序如下页所示，请在划线处填入合适的代码。 ①____、②____、③____ 【答案】 ①. 出栈 ②. f[color[z[top]]]==0 ③. z[top]=i ④. n-i-1 【解析】 【详解】本题考查栈的应用及程序填空能力。 （1）关于pop函数的功能是模拟出栈操作。在栈的模拟过程中，出栈表示取走一个圆盘，因此函数pop的任务是从栈中移除元素，同时更新颜色数量信息。故答案为：出栈。 （2）①在出栈的过程中，首先要判断栈是否为空（top!=-1），并且新取到的圆盘半径是否大于或等于栈顶圆盘半径（rad>=r[z[top]]）。如果满足条件，表示栈顶圆盘被遮挡，需要将其出栈。在出栈的同时，更新颜色数量信息，即f[color[z[top]]] -= 1。而在这个过程中，需要额外判断颜色数量是否为零。因此，第一个填空的条件应该是 f[color[z[top]]] ==0。故答案为：f[color[z[top]]]==0。②这个填空表示将当前取到的圆盘编号i入栈。在栈中，z数组存储了圆盘的编号，top表示栈顶的索引。在程序中，top是一个指向栈顶元素的指针。每当取走一个圆盘后，需要将新的圆盘编号i入栈，即z[top]=i。故答案为：z[top]=i。③这个填空表示剩余可见的颜色种类数。在取走第i个圆盘后，还有n-i-1个圆盘可见。这是因为在整个过程中，共有n个圆盘，而已经取走i个，剩下的是n-i个圆盘，再减去当前取走的这个，即n-i-1。故答案为：n-i-1。 28. 正则表达式是用一些特定的字符组成的一个“规则字符串”。它可以实现检查一个字符串中是否包含有某种子串、将匹配的子串替换或者从字符串中取出符合某个条件的子串等操作。现规定2个符号规则： ①“.”可以匹配任意单个字符，例如a="wer"，b=".e."，则字符串a与b匹配。 ②“*”匹配0个或多个前一位字符，例如a="aadbc"，b="a*b*c，c="aaaaabc"，则字符串a与b不匹配，字符串b与c匹配。因为此时b匹配的字符串是"abc"或"aabbc"或"aaabbbbbbbc"等。 请回答下列问题： （1）若字符串a="edffffgn"，b=".d*g."，则a与b____（选填：匹配/不匹配）。 （2）现有一个规则字符串p，包含规定的规则符号，编写如下Python程序，判断一个常规字符串s是否与p匹配，请在划线处填入合适的代码。 ①____、②____、③____ 【答案】 ①. 不匹配 ②. p[j]══"." ③. s[i]══s[i-1] ④. i!=m or j!=n 【解析】 【详解】本题考查正则表达式的匹配规则及其在编程中的实现。 （1）根据题意，模式 b=“.dg.” 的含义是： 第 1 个“.”可以匹配任意单个字符， d 表示可以匹配零个或若干个 ‘d’， 接下来必须有一个 ‘g’， 最后一个“.”再匹配任意单个字符。 对于 a=“edffffgn”，由于在 ‘d*’ 后出现的是一连串的 ‘f’ 而非 ‘g’，无法与模式中的 ‘g’ 对齐，故二者不匹配。 （2）给定的Python程序用于实现正则表达式的匹配。需要填入合适的代码以完成匹配逻辑。① 代码应判断当前字符是否为“.”，即可以匹配任意字符。故填入：p[j]=="."；② 代码应判断当前字符是否与前一个字符相同，以便在“*”的情况下继续匹配。故填入：s[i]==s[i-1]；③ 处在退出 while 循环后，如字符串或模式还未同步到末尾，则匹配失败，故可写成：i!=m or j!=n。 第1页/共1页 学科网（北京）股份有限公司 $