资源简介

定远育才学校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,]，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操作是指队列中1个元素出队。则经过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操作是指队列中1个元素出队。则经过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. 使用二分查找算法中间位置左偏，需要比较的次数为3次
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. 跳跃表通过跨区间、跳跃性的比较，减少了数据比较的次数，提高了效率
GeoHash的字符串长短可以决定要划分区域的大小，GeoHash能够提供任意精度的分段级别，一般分级为1～12级，一旦选定区域的宽和高，GeoHash字符串的长度就确定了，这样就把地图分成一个个的矩形区域。把地图区域划分好之后，如何快速的查找一个点邻近的点和区域呢？一个点邻近的点的GeoHash字符串有公共前缀，并且公共前缀的长度越长，这两个点距离越近。利用这个特性，可以快速地进行邻近点的搜索，越接近的点通常和目标点的GeoHash字符串公共前缀越长（也有特殊情况，需要单独处理）。
20.下列GeoHash字符串中，表示区域最大的是（）
A. wtw B. wtw37 C. wtw37q D. wtw37j
21.下列GeoHash字符串表示的区域中，与"wx4g0ec1"表示的区域最邻近的是（）
A. "wz15j7f9" B. "wx4g0ebc" C. "wx4f8995" D. "wx451gbc"
22.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.（14分）某校高二段n个班级举行飞镖比赛，初赛每位学生投掷飞镖并记录总成绩，每班录取前3名学生（成绩相同也被录取）。用Python程序实现各班按成绩降序输出，输出内容为班级、序号、总成绩，运行结果如图所示，请回答下列问题：
（1）定义如下insert(h，info)函数，指针h指向该班的头节点，列表info的4个数据项依次为班级编号、学生序号、总成绩、后一节点的指针（初值为-1）。函数的功能是将学生信息info插入到指定班级的链表中，并确保链表中的节点按总成绩从高到低排序，返回该班级的头指针。请在划线处填入合适的代码
（2）实现按照总成绩从高到低输出指定班级前3名学生信息的Python程序如下，请在划线处填入合适的代码
（3）程序中加框处代码有错，请改正。
27.（18分）一款智力玩具，有x种颜色的n个不同直径的同心圆盘(x＜n)。将圆盘串在倒T字型支架上，垂直俯视，直径不大于上方的圆盘将被遮挡，现从上方依次取走一片圆盘，记下能看到的颜色。最后说出取走几片圆盘后看到颜色种数最多，并说出颜色。某人取了6片5种颜色的圆盘随机叠放，如图a所示。他编写了如下程序来验证自己的结果是否正确，程序运行结果如图b所示。
请回答下列问题：
（1）函数pop的功能是________。
（2）实现上述功能的部分程序如下页所示，请在划线处填入合适的代码。
28.（18分）正则表达式是用一些特定的字符组成的一个“规则字符串”。它可以实现检查一个字符串中是否包含有某种子串、将匹配的子串替换或者从字符串中取出符合某个条件的子串等操作。现规定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.B 2.D 3.B 4.C 5.B 6.C 7.A 8.B 9.A 10.B 11.D 12.A 13.C 14.A 15.B 16.D 17.C 18.A
19.B 20.A 21.B 22.D 23.D 24.D 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）出栈
（2）①f[color[z[top]]]==0
②z[top]=i
③n-i-1
28.（1）不匹配（ 2）①p[j]══"." ②s[i]══s[i-1] ③i!=m or j!=n

展开更多......

收起↑