第一章 选择题专项-浙江高中信息技术高三复习作业本

陶小波编写 1 第一章 选择题专项 1.1 栈 1.栈 S 最大长度为 3,若元素 a,b,c,d 依次入栈，则可能的出栈序列为( ) A.d,c,b,a B.b,a,d,c C.c,a,b,d D.c,d,a,b 2.有“甲乙丙丁戊”5位小朋友按序沿着一条仅容一人通过的小道行走，途中有一个单向出 口的山洞，可容纳 2人前后站位休息，如图所示，则 5 人走出小道的顺序不可能的( ) A.甲乙丁戊丙 C.乙甲丁戊丙 B.丁戊甲丙乙 D.乙丙甲戊丁 3. 有如下程序段 s=["A","B","C","D"] m=[1,3,0,2 ]st=[""]*4 top=-1 j=0 for i in range(len(s)): top+=1 st[top]=s[i] while top!=-1 and ord(st[top])-ord("A")==m[j]: top-=1 j+=1 print(st[:top+1]) 执行该程序段后，输出内容是（ ） A.[] B.[’A'] C.[’A',’C'] D.[’A','C','E'] 4. 有如下 Python 程序： 陶小波编写 2 1.2 队列 1.给一个队列如下约定：T操作是指队列中 1个元素出队后再入队，P 操作是指 1个元素入 队。原始队列经过 TTPTP 系列操作后，队列中队首到队尾的元素依次为 ABCDE,则原始队列 中队首到队尾的元素依次为( ) A.ABC B.ABD C.BAE D.BADEC 2.队列 Q 从队首到队尾的元素依次是 1,2,3,栈 S 初始为空。约定：P 操作是指 Q 中 1 个元素 出队后入栈，J 操作是指 Q中 1个元素出队后再入队。经过 JPJPP 系列操作后，栈 S 中栈顶 到栈底的元素依次为( ) A.2,1,3 B.1,3,2 C.3,1,2 D.2,3,1 3.队列 q中队首至队尾元素依次为“A,B,C,D,E,F”,约定：S 为出队操作，U 为出队再入队 操作，若要使队列 q队首至队尾元素依次为“B,D,E”,下列操作可实现的是（ ） A.USUSSU B.SUSUUS C.SSSUU D.SUUSUS 4. 队列 Q 从队首到队尾的元素依次为 1,2,3,4,栈 S 初始为空。约定：H 操作是指元素出队 后入队，T操作是指元素出队后入栈。经过 HTTHT 操作后，栈 S 中从栈底到栈顶的元素依次 为 A.1,2,4 B.2,3,1 C.3,1,2 D.4,2,1 5.有 2 个队列 a和 b,队首到队尾的元素依次分别为“5,7,9”和“6,4,8”。约定： T操作 是指队列 a中 1个元素先出队，若大于队列 b 的队首元素则再入 b 队列，否则不入；Q 操作 是指队列 b中 1个元素先出队，若大于队列 b 的队尾元素则再入 b队列，否则不入。则经过 TTQQQQT 系列操作后，队列 b中的元素个数为 A.1 B.2 C.3 D,4 6. 队列Q从队首到队尾的元素依次是1,3,5,栈S从栈底到栈顶的元素依次是2,4,6,现约定： A操作是指元素出队后入栈，B 操作是指元素出栈后入队。经过 BAAB 系列操作后，队列中队 首到队尾的元素依次为(▲) A.5,2,1 B.5,2,4 C.5,6,1 D.5,6,3 陶小波编写 3 1.3 链表 1.使用列表 flink 模拟链表结构(节点数大于 1),每个节点包含起始数值、连续长度、指针 区域，h为头指针。链表中各节点已按起始数值由小到大排列，各个节点表示的数值区间不 重叠，例如链表 flink 为[[20,100,3],[150,50,2],[250,60,-1],[120,30,1]],h=0,其中节 点[20,100,3]表示从数值 20开始有长度为 100 的连续值(20到 119),3代表后继节点索引为 3, 现 要 合 并 链 表 各 节 点 连 续 的 数 值 区 间 ， 合 并 后 链 表 flink 的 数 据 修 改 为 [[20,180,2],[150,50,2],[250,60,-1],[120,30,1]], h=0。实现该功能的程序段如下： 2.使用列表a模拟链表结构(节点数大于2),每个节点包含数据区域和指针区域，h为头指针， 如图 a所示。现修改该链表各节点的链接关系，移除链表中值重复的节点，保留最开始出现 的节点，结果如图 b所示。实现该功能的程序段如下，方框中应填入的正确代码为( ) p=-1 q=head vis =[] while q!=-1: 图 a 图 b 陶小波编写 4 3. 使用列表 da和 db模拟 2个链表结构(节点数均大于 0),每个节点包含数据区域和指针区 域，ha 和 hb 分别为链表 da 和 db 的头指针。链表中各节点已按数据区域中数值由小到大排 列，且链表 da 头节点值小于链表 db 头节点值。现要将链表 db 中数据合并到链表 da 中，且 保持升序排列。实现该功能的程序段如下，方框中应填入的正确代码为( ) q=ha while hb!=-1: p=da[q][1] 4. 列表 a 存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为 ha、hb,且 a[ha][0]<a[hb][0],如第 4-1 图所示。现要将其合并为一个升序链表，头指针为 h, 结果如第 4-2 图所示，实现功能的程序段如下： 陶小波编写 5 5. 使用列表 d 模拟链表结构(节点数大于 0),每个节点包含数据区域和指针区域，head 为头 指针。现要删除链表中数据值在[begin,end]范围的节点，实现该功能的部分程序段如下， 方框中应填入的正确代码为：（ ） 6. 用链表模拟队列操作(队列长度大于 1),链表的每个节点包含数据区域和指针区域。指针 head 指向队列的第一个元素，指针 tail 指向队列的最后一个元素，如图所示。现执行 n 次 “出队后立即入队”操作，实现该功能的 Python 程序段如下： 7.使用列表 a模拟链表结构(节点数大于 0),每个节点包含数据区域和指针区域，head 为头 指针，链表中各节点已按数据区域中数值的由小到大排列。现要修改该链表各节点的链接关 系，删除链表中数据区域数值相同的节点，使得链表各节点的数据区域值不重复。实现该功 能 的 程 序 段 如 下 ， 方 框 中 应 填 入 的 代 码 段 可 行 的 是 陶小波编写 6 1.4 二叉树 1.某二叉树对应的一维数组表示如下图所示： A.该二叉树的度为 3 C.该二叉树是一棵完全二叉树 B.该二叉树有2个叶子节点 D.该二叉树前序遍历结果为ABCDE 2.某二叉树的部分树形结构如第 2题图所示，其前序遍历结果为 ABCDEF,下列说法正确的是 A.该二叉树的深度一定是 3 B.节点 C和节点 D一定都是叶子节点 C.节点 F在该二叉树的左子树中 D.该二叉树的后序遍历可能是 CDBFEA 第 2 题图 3.有一棵 8个节点的二叉树，下列说法正确的是( ) A.叶子节点可能为 4个 B.第 3 层最多 6 个节点 C.度为 1 的节点最多 4 个 D.该树的层数可能为 3 层 4.某完全二叉树共有 300 个节点，该二叉树的高度是( ) A.8 B.9 C.10 D.11 5.某二叉树的前序遍历结果为 ABC,若该二叉树不是满二叉树，则其后序遍历结果为( ) A.ABC B.BCA C.CBA D.CAB 6.某二叉树如第 6 图所示，下列说法正确的是（ ） A.节点 D、F 都是节点 B 的孩子节点 B.该树的度和深度分别为 2 和 3 C.该二叉树中序遍历的结果为 DBEAGCF D.若补全成高度为 5的满二叉树则需增加 24 个节点 陶小波编写 7 1.5 排序 1. 列表 1st 中共有 n 个整数，若下列程序段实现将数组元素 lst[st]至 lst[ed]升序排列， 则划线处的代码为( ) 2. 有如下 Python 代码： #随机产生 5 个整数，存储在列表 a 中 for i in range(1,5): k =a[i] j =i-1 while j>=0 and abs(a[j]-2)>abs(k-2): a[j+1]=a[j] j-=1 a[j+1]=k 执行该程序段后，列表 a的值可能是 A.[-5,-2,4,0,1] B.[3,-1,0,2,-3] C.[1,2,3,4,5] D.[0,4,0,-2,-4] 3.列表 a 中各元素 a[0]到 a[4]的值依次为 9,2,5,1,3,若分别执行如下两段程序，则数据交 换次数分别是（ ） 陶小波编写 8 1.6 查找 1.某二分查找算法的 Python 程序段如下： import random key=random.randint(2,4)*2 a=[2,5,6,8,13,15,20,22] ans=0;i=0;j=len(a)-1 while i<=j: m=(i+j)//2 ans+=m if key==a[m]: break elif key>a[m]: i=m+1 else: j=m-1 执行该程序段后，ans 的值不可能是（ ） A.3 B.4 C.5 D.6 2. 某二分查找算法的 Python 程序段如下： i=0;j=9;c=0 key =int(input()) while i <=j: m =(i+j)//2 if a[m]==key: break if a[m]>key j=m-1 else: i=m +1 c +=1 若 a=[2,13,14,19,23,26,29,31,32,38],运行该程序段后，c的值为 2,则 key 的值不可能是 ( ) A.19 B.29 C.30 D.32 3. 定义如下函数： 陶小波编写 9 1.7 递归 1.定义如下函数： def f(n): if n<=1: return 1 elif n%2==0: return f(n-3)+1 return f(n-1)*2 执行语句 s=f(6)后，s 的值是（ ） A.3 B.4 C.5 D.6 2.定义如下函数： 3.定义如下函数： 陶小波编写 10 4.定义如下函数： 陶小波编写 答案 第一章选择题 12 3 4 5 6 7 8 9 10 11 1213 1415 BB 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 (一)队列 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 B C 6 B D 16 17 18 19 20 21 22 23 24 25 26 27 282930 (二)链表 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 B A A A D 16 17 18 19 20 21 2223 24 25 26 27 282930 (三)二叉树 1 2 3 4 5 6 1 8 9 10 11 12 13 14 15 B D A 16 17 18 19 2021 2223 2425 2627 282930 (四)排序 1 2 3 4 5 6 7 8 9 10 11 1213 1415 D 0 16 17 18 1920 21 22 23 24 25 26 27 28 2930 (五)查找 1 2 3 4 5 6 8 9 10 11 12 13 14 15 c D 16 17 18 192021 2223 2425 26 2728 2930 (六)递归 1 23 4 56 7 8 10 11 12 1314 15 c B c 16 17 18 19202122 2324 25 26 27 28 2930 (七)枚举 1 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 202122 2324 25 2627 28 2930 137 陶小波编写 (九)解析 2 3 4 5 6 8 9 10 11 12 13 14 15 16 17 18 19 202122 23 24 25 26 27 28 29 30 第二章链表 第一题【来源2023年11月温州一模】 (1)B (2)3 (3)①p=i ②k=task[p][3] 3task[p][3]=task [k][3] 第二题【来源2023年11月台州一模】 (1)135 (2)①B ②1st[q][1]=pos (3)Dinfo[cur][0]=pos info[cur][0]=len(1st)-1 ②p ③1st[p][o] 第三题【来源2023年11月绍兴诊新】 (1)2 (2)[3,9][11,7] (3)Dque.append([t[1].h]) 2que[que[p][1]][0]!=t[1]que[p][1]!=-1 and que[que[p][1]][0]!=t[1] 3preHeight=que [h][0] 第四题【来源2023年11月宁波一模】 (1)08:09:00 (2)D (3)t%3600/60 (4)①head=1en(1st)-1 138