2024年全国高一《信息技术选择性必修1数据与数据结构》（教科版2019）期末考试模拟卷一

这是一份2024年全国高一《信息技术选择性必修1数据与数据结构》（教科版2019）期末考试模拟卷一，共15页。试卷主要包含了选择题，填空题，判断题，简答题等内容，欢迎下载使用。

一、选择题
1．下列关于队列和栈的说法，不正确的是（ ）
A．队列是一种先进先出的线性表，可在队尾进行插入操作
B．栈的特性是″先进后出，后进先出″
C．某栈的入栈的顺序为″abc″，出栈顺序只有3种
D．队列和栈都是线性数据结构，都可以用数组来实现
2．依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是（ ）
A．aB．bC．cD．d
3．下列VB表达式中，值最小的是（ ）。
A．Abs(-3) + Len("NBXIAOSHI")
B．Val(Mid("Ningb2222", 8, 1))
C．Int(Sqr(36) + 5) \ 2
D．10^2 Md 100 \ 3 ^ 2
4．某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（ ）
A．前序遍历序列为DBACGFEB．节点G为节点E的父节点C．该二叉树有两个叶子节点D．节点A与节点F为同一层
5．递归算法可以用三个字来概括，但不包括下列选项中的（ ）
A．解B．分C．治D．合
6．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（ ）
A．2B．4C．5D．6
7．约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP 系列操作后，队首指针head和队尾指针tail的值分别为（ ）
A．3 4B．3 5C．4 5D．4 6
8．某二叉树的树形结构如图所示，其后序遍历结果为DBGEFCA，前序遍历的结果为（ ）
A．ABCDEFGB．ABDCEGFC．DBEGCFAD．ABDCGFE
9．有如下 Pythn 程序段：
def tra(head,a):
if head==- 1:
return " "
tra(a[head][1],a)
print(a[head][0],end=" ")
a=[["A",3],["C",2],["D",4],["B", 1],["E",- 1]]
head=0
tra(head,a)
运行该程序段后，输出的结果是（ ）
A．E D C B AB．A B C D EC．E B D C AD．A C D B E
10．若有一批元素的出栈顺序为“i,n,p,u,t”，其入栈顺序不可能是（ ）
A．n,i,t,u,pB．n,i,u,t,pC．t,u,p,n,iD．i,n,p,u,t
11．某学校举行校园歌手比赛，数组a存放歌手的得分，数组mc存放名次。名次计算规则为：先对数组a中的元素按高到低的排序，分值最高为第1名，分值相同则名次相同。VB程序段的部分代码如下：
Fr i = 1 T 19
Fr j = 20 T i + 1 Step -1
If① Then t =a(j): a(j)=a(i): a(i)=t
Next j
Next i
mc(1) =②
Fr i = 2 T 20
If a(i) < > a(i - 1) Then③ Else④
Next i
下列①②③④代码正确的是（ ）
A．①处代码为 a(j) < a(i)
B．②处代码为 i
C．③处代码为 mc(i) = mc(i + 1)
D．④处代码为 mc(i) = mc(i - 1)
12．将十进制正整数转化为二进制数，对应的Pythn程序如下：
def tStr(n,base):
s = "01"
if n < base:
return s[n]
else:
return ①
n = int(input('请输入正整数:'))
result = tStr(n,2)
print(result)
则代码中①处的语句可为（ ）
A．tStr(n // base, base) + s[n % base]B．s[n % base] + tStr(n // base, base)
C．tStr(n % base, base) + s[n // base]D．s[n // base] + tStr(n % base, base)
13．若采用冒泡排序对数据1，19，6，7，2，8，23，15进行排序处理，则第二遍加工后的结果是（ ）
A．23，19，1，15，8，6，7，2B．23，19，1，15，6，7，2，8
C．23，19，15，1，6，7，2，8D．23，19，15，8，1，6，7，2
14．已知一个栈的入栈顺序是1，2，3，4，…，n，其输出序列为R1，R2，R3，…，Rn，若Rn是1，则Ri是（ ）
A．iB．n-1C．n-i+1D．不确定
15．栈S1从栈底到栈顶的元素顺序由1，2，3改为3，2，1，可借助初始均为空、长度均为3的栈S2、栈S3出入栈操作来实现，则需要出栈操作的总次数至少是（ ）
A．6B．7C．8D．9
16．栈和队列的顺序存储结构通常使用哪种数据结构（ ）
A．链表B．数组C．树D．图
17．下列有关查找的说法中，正确的是（ ）
A．顺序查找时，被查找的数据必须有序B．对分查找时，被查找的数据不一定有序
C．顺序查找总能找到要查找的关键字D．—般情况下，对分查找的效率较高
18．有1个队列，队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为（ ）
A．2,3B．6,2,3C．9,4,5D．9,4,5,6
19．运行下列 Pythn程序，结果正确的是( )
a=18
b=7
c=a%b
b=a%b
print(a,b)
A．18 5B．5 18C．18 4D．4 18
20．某对分查找算法的VB程序段如下
Key =Val(Text1. Text)
i=1:j=10:n=0
D While i Key Then
j=m-1
Else
i=m+1
End If
Lp
Text2. Text = str(n)
数组元素a(1)到a(10)的值依次为“2，3，5，8，9，10，13，17，19，25”，在文本框Text1中入待查找的整数，执行该程序段，则文本框Text2中显示3，待查找数不可能是（ ）
A．2B．4C．9D．19
二、填空题
21．在计算机编程中， 是一种用于描述程序中数据的组织方式。
22．递归算法必须有一个 ，以防止无限递归。
23．递归算法的时间复杂度通常与问题的 有关。
24．程序代码如下，则其中\n的作用是( )
25．栈是一种特殊的数据结构，遵循 的原则。
26．选择排序的主要思想是在未排序的序列中找到最小（或最大）的元素，将其存放到已排序序列的末尾。选择排序的平均时间复杂度为 。
27．归并排序是一种基于分治思想的排序算法，它的基本思想是将两个有序的子序列合并成一个有序序列。归并排序的平均时间复杂度为 。
28．二叉树是一种每个节点最多有 个子节点的树结构。
29．使用递归算法解决汉诺塔问题时，递归调用的次数为 。
30．计数排序是一种 算法，它的适用范围是整数且范围不大。
31．用来接收键盘输入的函数是 。
32．在数据结构中， 是一种特殊的线性表，只允许在表的两端进行插入和删除操作。
33．冒泡排序的基本思想是通过不断比较相邻元素并交换顺序错误的元素来实现排序，其时间复杂度为 。
34．使用( )关键字来创建pythn自定义函数。
35．递归算法的缺点之一是需要额外的空间来存储函数调用的 。
三、判断题
36．尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。( )
37．递归方法适用于所有类型的问题。( )
38．递归方法适用于解决那些可以通过分解为更小规模的相同问题来解决的问题。( )
39．在程序设计常用的数据结构中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为栈。( )
40．在递归方法中，必须有一个明确的终止条件，以防止无限递归。( )
41．递归程序必须有一个明确的结束条件， 否则会陷入无限递归的状态，无法结束调用。( )
42．在使用递归方法时，应该尽量使递归调用尽可能浅，以减少栈空间的使用。( )
43．递归方法是一种隐式的控制结构，通过函数调用自身来实现循环。( )
44．在Pythn中，s＝s＋5是错误的赋值语句。( )
45．在 Pythn语言环境下，表达式13%2+7//2的值为4.5。 ( )
四、简答题
46．队列和栈有什么共同点？
原始数据
1
19
6
7
2
8
23
15
第一遍加工后
23
1
19
6
7
2
8
15
第二遍加工后
…
参考答案：
1．C
【详解】本题主要考查栈和队列的相关知识。栈的特点是先进后出（后进先出），队列的特点是先进先出；队列只允在一端（队尾）进行插入，在另一端（队头）进行删除；栈限定仅能在一端（栈顶）进行插入和删除操作；栈和队列均为操作受限的线性表，可以用数组来实现；入栈的顺序为″abc″，其出栈序列共有5中：abc、acb、bac、bca、cba。故本题答案是C选项。
2．C
【详解】本题主要考查队列的操作。队列的特点是在队尾插入元素，在队头删除元素。依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是c，下一个元素是d，故本题选C选项。
3．D
【详解】本题主要考查VB表达式。Abs()求绝对值函数，Len()求字符串长度，Val()将字符串转换为整数，Mid()截取字符串函数，Int()取整数部分，Sqr()求根函数，Md取余，Abs(-3) + Len("NBXIAOSHI")=3+9=12，Val(Mid("Ningb2222", 8, 1))=2，Int(Sqr(36) + 5) \ 2=5，10^2 Md 100 \ 3 ^ 2=100 Md 100\9=100 Md 11=1，故本题选D选项。
4．B
【详解】本题考查的是二叉树。依据题意可画出如下的数：
由图可知，前序遍历序列为DBACGEF，节点G为节点E的父节点，该二叉树有3个叶子节点，节点A与节点F不在同一层。故本题应选B。
5．A
【详解】本题主要考查递归算法。递归算法即在程序中不断反复调用自身来达到求解问题的方法。此处的重点是调用自身，这就要求待解决的问题能够分解为相同问题的一个子问题，每个子问题分别解决，这样通过多次调用，将所有的子问题合在一起就可以完成求解。递归算法可以用三个字来概括，即分、治、合，故本题选A选项。
6．B
【详解】本题考查队列相关内容。队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，则队首元素位置是2，队尾元素位置是5，共有5-2+1=4个元素。故本题答案是B选项。
7．D
【详解】本题考查队列操作相关内容。根据题目规定，T表示出队后入队，E表示入队，P表示出队，操作过程中指针变化情况如下所示：
此队列共进行入队6次，出队4次，入队移动队尾指针及tail+6，出队移动head指针，即head+4，执行EETPETEP后（E入队，T（出队+入队），P出队）head=4，tail=6，故本题答案为D选项。
8．D
【详解】本题考查二叉树的遍历。根据后序遍历结果以及该二叉树的树形结构，可以画出该二叉树如下，由二叉树可知前序遍历的结果是ABDCGFE。故选D。
9．A
【详解】本题考查的是迭代程序。可以把该程序看成链表，a是二维列表，a里面的列表第一个位置是要输出的内容，第二位置是指向下一个列表，“-1”表示链表结尾。a=[["A",3],["C",2],["D",4],["B", 1],["E",- 1]]，故输出内容构成的链表是：ABCDE，因为迭代，所以逆序输出：E D C B A，选项A正确。
10．B
【详解】本题考查栈。栈的特点是先进后出。对于选项A，入栈顺序为n,i,t,u,p，可能的进出栈过程为：n进栈，i进栈，i出栈，n出栈，t进栈，u进栈，p进栈，p出栈，u出栈，t出栈，符合出栈顺序“i,n,p,u,t”；对于选项B，入栈顺序为n,i,u,t,p，若先入栈n和i，i出栈，n出栈，接着入栈u，入栈t，入栈p，p出栈，此时u要先于t出栈，不符合出栈顺序“i,n,p,u,t”；对于选项C，入栈顺序为t,u,p,n,i，可能的进出栈过程为：t进栈，u进栈，p进栈，n进栈，i进栈，i出栈，n出栈，p出栈，u出栈，t出栈，符合出栈顺序；对于选项D，入栈顺序为i,n,p,u,t，可能的进出栈过程为：i进栈，i出栈，n进栈，n出栈，p进栈，p出栈，u进栈，u出栈，t进栈，t出栈，符合出栈顺序。故答案为：B。
11．D
【详解】本题主要考查排序算法知识点。分析程序可知，①处通过嵌套fr循环比较a(i)与a(j)的大小，实现降序排序，若a(i)key成立，故执行j=m-1=4；
第二次查找，i=1，j=4，则m=2，n=2，a（m）>key成立，故执行j=m-1=1；
第三次查找，i=1，j=1，则m=1，n=3，a（m）>key不成立，故执行i=m+1=2，此时i>j，退出循环，故最终n=3，符合题干。
假设Key=4；
第一次查找，i=1，j=10，则m=5，n=1，a（m）>key成立，故执行j=m-1=4；
第二次查找，i=1，j=4，则m=2，n=2，a（m）>key不成立，故执行i=m+1=3；
第三次查找，i=3，j=4，则m=3，n=3，a（m）>key成立，故执行j=m-1=2，此时i>j，退出循环，故最终n=3，符合题干。
假设Key=9；
第一次查找，i=1，j=10，则m=5，n=1，a（m）>key不成立，故执行i=m+1=6；
第二次查找，i=6，j=10，则m=8，n=2，a（m）>key成立，故执行j=m-1=7；
第三次查找，i=6，j=7，则m=6，n=3，a（m）>key成立，故执行j=m-1=5，此时i>j，退出循环，故最终n=3，符合题干。
假设Key=19；
第一次查找，i=1，j=10，则m=5，n=1，a（m）>key不成立，故执行i=m+1=6；
第二次查找，i=6，j=10，则m=8，n=2，a（m）>key不成立，故执行i=m+1=9；
第三次查找，i=9，j=10，则m=9，n=3，a（m）>key不成立，故执行i=m+1=10；
第四次查找，i=10，j=10，则m=10，n=4，a（m）>key成立，故执行j=m-1=9，此时i>j，退出循环，故最终n=4，不符合题干。
故本题待查找数不可能是19，本题选D。
21．数据结构
【详解】本题考查数据结构。在计算机编程中，数据结构是用于描述程序中数据的组织方式。它规定了数据的存储、访问和操作方式，决定了数据的逻辑结构和物理存储结构。不同的数据结构具有不同的特点和适用场景，合理选择和使用数据结构可以提高程序的效率和性能，使程序能够更高效地处理和操作数据。故答案为：数据结构。
22．递归出口
【详解】本题考查递归。递归算法必须有一个递归出口，它是递归结束的条件，用于防止无限递归。故答案为：递归出口。
23．规模和分解方式
【详解】本题考查递归算法。递归算法的时间复杂度通常与问题的规模和分解方式有关，因为不同的分解方式可能导致不同的时间复杂度。故答案为：规模和分解方式。
24．换行
【详解】本题主要考查Pythn转义字符。“\n”表示换行，“\t”表示空四个字符，也称缩进。
25．后进先出
【详解】本题考查栈。栈是一种特殊的数据结构。“后进先出（LIFO）”准确描述了栈的操作特性。这意味着最后进入栈的元素会最先被取出。例如，往栈中依次放入元素1、2、3，那么取出的顺序将是3、2、1。后进先出原则决定了栈在数据存储和取出上的特定顺序。故答案为：后进先出。
26．O(n^2)
【详解】本题考查选择排序。选择排序的平均时间复杂度为O(n^2)，因为它需要进行n次遍历，每次遍历需要进行n-i次比较（i表示当前遍历的次数）。
27．O(nlgn)
【详解】本题考查归并排序。归并排序的平均时间复杂度为O(nlgn)，因为它需要进行lgn次分割操作和n次合并操作。
28．两
【详解】本题考查二叉树。二叉树是一种重要的数据结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。这是二叉树的核心定义和显著特征，通过这个限制，使得二叉树在数据存储、搜索、排序等操作中具有特定的性质和优势。故答案为：两。
29．2^(n-1)
【详解】本题考查递归法的应用。汉诺塔问题的递归算法中，每次递归调用都会将问题规模减半，因此递归调用的次数为2^(n-1)。
30．非比较
【详解】本题考查的是计数排序。计数排序是一种非比较算法，它的适用范围是整数且范围不大的情况。它通过计数每个元素的出现次数来进行排序。
31．input()
【详解】本题主要考查Pythn函数。用来接收键盘输入的函数是input()，pythn输出的函数是print()。
32．队列
【详解】本题考查队列。在数据结构中，一种特殊的线性表，只允许在表的两端进行插入和删除操作的表称为队列（Queue）。故答案为：队列。
33．O(n^2)
【详解】本题考查冒泡排序。冒泡排序的平均和最坏情况下的时间复杂度都是O(n^2)，最好情况下的时间复杂度是O(n)。故答案为：O(n^2)。
34．def
【详解】本题主要考查Pythn函数。使用def关键字来创建pythn自定义函数。
35．信息
【详解】本题考查递归。递归算法的缺点之一是需要额外的空间来存储函数调用的信息，这可能导致较高的空间复杂度。故答案为：信息。
36．正确
【详解】本题考查尾递归。尾递归指的就是在函数的最后一步进行递归调用。这样的结构使得在某些支持优化的编程语言中，可以对其进行特殊处理，避免不断地创建新的栈帧，从而节省栈空间，提高程序的性能和避免栈溢出。故说法正确。
37．错误
【详解】本题考查递归。递归方法虽然在处理某些特定类型的问题时具有优势，但并非适用于所有类型的问题。对于一些简单、直接且不具有明显递归结构的问题，使用迭代或者其他更直接的方法可能更加高效和易于理解。故说法错误。
38．正确
【详解】本题考查递归方法。递归的核心思想就是将一个复杂的大问题不断分解为规模更小的、与原问题具有相同形式的子问题，并通过解决这些子问题来最终解决原问题。故说法正确。
39．错误
【详解】本题考查数据结构队列相关内容。在程序设计中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为队列（Queue）。队列是一种先进先出（FIFO，First-In-First-Out）的数据结构，在队列中，新的元素被添加到队列的末尾，而从队列中移除元素时，总是从队列的头部开始移除。故本题答案是：错误。
40．正确
【详解】本题考查递归。在递归方法中，明确的终止条件是必不可少的。如果没有终止条件，递归函数会无限制地自我调用，导致无限递归，最终可能造成栈溢出等错误，使程序崩溃。故说法正确。
41．正确
【详解】本题考查程序设计相关内容。递归程序必须有一个明确的结束条件，如果没有明确的结束条件，递归函数可能会陷入无限递归的状态，导致无法结束调用。这种情况称为递归无限循环或递归死循环。故本题答案是：正确。
42．正确
【详解】本题考查递归。在递归调用中，每次调用都会消耗一定的栈空间来存储函数的状态和参数等信息。如果递归调用的深度过深，会大量占用栈空间，可能导致栈溢出错误。因此，尽量使递归调用尽可能浅，可以有效地减少栈空间的使用，降低出现栈溢出的风险。故说法正确。
43．正确
【详解】本题考查递归。递归是一种编程技术，其中一个函数通过调用自身来解决问题。递归方法是一种隐式的控制结构，通常用于解决具有重复性质的问题。通过递归调用，函数可以在每次调用时处理问题的一部分，直到达到基准条件（也称为递归终止条件），此时递归停止，函数开始返回并完成所有的递归调用。故说法正确。
44．错误
【详解】本题考查的是Pythn赋值语句。赋值语句格式：变量名=表示，赋值的作用是把“=”右边的表达式的计算结果存储到“=”左边的变量。在Pythn中，s＝s＋5是正确的赋值语句。故题干中的说法错误。
45．错误
【详解】本题考查的是Pythn表达式。在Pythn中“∥”表示整除，%表示求余。表达式13%2+7∥2的值为4。故题干中的说法错误。
46．都是线性关系
【详解】本题考查数据结构。
都属于线性数据结构：队列和栈都是线性数据结构，即数据元素之间存在一对一的线性关系。然而，它们在数据元素的排列顺序和访问规则上有所不同。
有限制性的操作：栈的操作是后进先出（LIFO），只能在栈顶进行元素的插入（push）和删除（pp）操作。队列的操作是先进先出（FIFO），只能在队尾进行元素的插入（enqueue）操作，在队头进行元素的删除（dequeue）操作。
题号
1
2
3
4
5
6
7
8
9
10
答案
C
C
D
B
A
B
D
D
A
B
题号
11
12
13
14
15
16
17
18
19
20
答案
D
A
B
C
B
B
D
D
C
D
操作序列EETPETEP
队列中指针初值head=tail=0
EETPETEP
head=0;tail=1
EETPETEP
head=0;tail=2
EETPETEP
head=1;tail=3
EETPETEP
head=2;tail=3
EETPETEP
head=2;tail=4
EETPETEP
head=3;tail=5
EETPETEP
head=3;tail=6
EETPETEP
head=4;tail=6