《信息技术 选择性必修1 数据与数据结构》（教科版2019）期末考试模拟卷 一 （试题+参考答案+答题卡）

参考答案： 题号 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 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()求根函数，Mod取余，Abs(-3) + Len("NBXIAOSHI")=3+9=12，Val(Mid("Ningbo2222", 8, 1))=2，Int(Sqr(36) + 5) \ 2=5，10^2 Mod 100 \ 3 ^ 2=100 Mod 100\9=100 Mod 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表示出队，操作过程中指针变化情况如下所示： 操作序列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 此队列共进行入队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 【详解】本题考查栈的操作。栈的特点是先进后出，后进先出。选项B中，先入栈n、i再i、n出栈；接着u、t、p入栈，p出栈后接着是t出栈而不是u出栈，与题干不符。故选B。 11．D 【详解】本题主要考查排序算法知识点。分析程序可知，①处通过嵌套for循环比较a(i)与a(j)的大小，实现降序排序，若a(i)<a(j)，就交换，故此处填a(i)<a(j)。②第一名的名次初始化为1，即mc(1)=1。③此处若相邻的分数不相同，则第i位的名次为i-1位的名次加1，故此处填mc(i)=mc(i-1)+1。④如果相邻的分数相同，则名次相同，即mc(i) = mc(i - 1)，故本题选D选项。 12．A 【详解】本题主要考查递归算法及Python程序实现。分析程序可知，当n>=base时，十进制转换为二进制的方法是“除权取余、逆序排列”，该程序采用递归算法，故第一空第一部分继续调用toStr方法，第二部分将余数保存到列表s中，故填toStr(n // base, base) + s[n % base]，故本题选A选项。 13．B 【详解】本题考查冒泡排序。观察第一遍加工后的结果可知，本题的排序方式为降序，并且从后往前进行数据比较和交换，若后面的数据比前面的大则进行互换，因此第二遍加工后的结果为23，19，1，15，6，7，2，8，故答案为B。 14．C 【详解】本题考查栈。由于栈先进后出的特性可知，若Rn为1，则必有R1是n。因此R1是n，R2是n-1，Rn是1，因此可推得Ri为n-i+1，因此答案为C。 15．B 【详解】本题考查的是栈的操作。依据题意，要将栈内3个元素，借助另外两个栈，实现顺序完全颠倒。首先栈中3个元素必须出栈（到其它栈）即3次出栈，3次入栈，也是3次出栈（从其它栈出栈）。由于可借助的栈只有2个，故其中一个元素还要多出1次到其它栈。故出栈操作的总次数至少是：3+3+1=7。选B。 16．B 【详解】本题考查数据结构。栈和队列的顺序存储结构通常使用数组实现，因为数组支持快速的随机访问，可以高效地进行元素的入栈、出栈、入队和出队操作。故答案为：B。 17．D 【详解】本题考查查找算法。顺序查找对被查找的数据是否有序没有要求，而对分查找时被查找的数据必须有序。故 A、B选项错误。顺序查找和对分查找都不能保证一定能找到要查找的关键字，C选项错误。顺序查找是对全部范围内的每个元素依次进行比较，而对分查找每次对一半范围内的数据进行比较，一般来说，对分查找的效率比顺序查找要高，D选项正确。故答案为：D。 18．D 【详解】本题考查队列相关内容。队列的特点是先进先出。队首到队尾的元素依次为8、10、12、9。第一次操作8出队，第二次操作8//2的结果4入队，第三次操作10出队，第四次操作10//2的结果5入队，第五次操作12出队，第六次操作12//2的结果6入队，故此时队列中的元素依次为9、4、5、6，D选项正确。故本题答案是D选项。 19．C 【详解】本题主要考查Python程序的执行。a=18，b=7，c=a%b=4，b=a%b=4，输出a和b的值是18和4，故本题选C选项。 20．D 【详解】本题考查查找算法相关知识。 假设Key=2； 第一次查找，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成立，故执行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．换行 【详解】本题主要考查Python转义字符。“ ”表示换行，“\t”表示空四个字符，也称缩进。 25． 后进先出 【详解】本题考查栈。栈是一种特殊的数据结构。“后进先出（LIFO）”准确描述了栈的操作特性。这意味着最后进入栈的元素会最先被取出。例如，往栈中依次放入元素1、2、3，那么取出的顺序将是3、2、1。后进先出原则决定了栈在数据存储和取出上的特定顺序。故答案为：后进先出。 26．O(n^2) 【详解】本题考查选择排序。选择排序的平均时间复杂度为O(n^2)，因为它需要进行n次遍历，每次遍历需要进行n-i次比较（i表示当前遍历的次数）。 27．O(nlogn) 【详解】本题考查归并排序。归并排序的平均时间复杂度为O(nlogn)，因为它需要进行logn次分割操作和n次合并操作。 28．两 【详解】本题考查二叉树。二叉树是一种重要的数据结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。这是二叉树的核心定义和显著特征，通过这个限制，使得二叉树在数据存储、搜索、排序等操作中具有特定的性质和优势。故答案为：两。 29．2^(n-1) 【详解】本题考查递归法的应用。汉诺塔问题的递归算法中，每次递归调用都会将问题规模减半，因此递归调用的次数为2^(n-1)。 30． 非比较 【详解】本题考查的是计数排序。计数排序是一种非比较算法，它的适用范围是整数且范围不大的情况。它通过计数每个元素的出现次数来进行排序。 31． input() 【详解】本题主要考查Python函数。用来接收键盘输入的函数是input()，python输出的函数是print()。 32．队列 【详解】本题考查队列。在数据结构中，一种特殊的线性表，只允许在表的两端进行插入和删除操作的表称为队列（Queue）。故答案为：队列。 33．O(n^2) 【详解】本题考查冒泡排序。冒泡排序的平均和最坏情况下的时间复杂度都是O(n^2)，最好情况下的时间复杂度是O(n)。故答案为：O(n^2)。 34．def 【详解】本题主要考查Python函数。使用def关键字来创建python自定义函数。 35．信息 【详解】本题考查递归。递归算法的缺点之一是需要额外的空间来存储函数调用的信息，这可能导致较高的空间复杂度。故答案为：信息。 36．正确 【详解】本题考查尾递归。尾递归指的就是在函数的最后一步进行递归调用。这样的结构使得在某些支持优化的编程语言中，可以对其进行特殊处理，避免不断地创建新的栈帧，从而节省栈空间，提高程序的性能和避免栈溢出。故说法正确。 37．错误 【详解】本题考查递归。递归方法虽然在处理某些特定类型的问题时具有优势，但并非适用于所有类型的问题。对于一些简单、直接且不具有明显递归结构的问题，使用迭代或者其他更直接的方法可能更加高效和易于理解。故说法错误。 38．正确 【详解】本题考查递归方法。递归的核心思想就是将一个复杂的大问题不断分解为规模更小的、与原问题具有相同形式的子问题，并通过解决这些子问题来最终解决原问题。故说法正确。 39．错误 【详解】本题考查数据结构队列相关内容。在程序设计中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为队列（Queue）。队列是一种先进先出（FIFO，First-In-First-Out）的数据结构，在队列中，新的元素被添加到队列的末尾，而从队列中移除元素时，总是从队列的头部开始移除。故本题答案是：错误。 40．正确 【详解】本题考查递归。为了避免无限递归，递归方法必须有一个明确的终止条件，当满足这个条件时，递归调用将停止。故说法正确。 41．正确 【详解】本题考查程序设计相关内容。递归程序必须有一个明确的结束条件，如果没有明确的结束条件，递归函数可能会陷入无限递归的状态，导致无法结束调用。这种情况称为递归无限循环或递归死循环。故本题答案是：正确。 42．正确 【详解】本题考查递归。在递归调用中，每次调用都会消耗一定的栈空间来存储函数的状态和参数等信息。如果递归调用的深度过深，会大量占用栈空间，可能导致栈溢出错误。因此，尽量使递归调用尽可能浅，可以有效地减少栈空间的使用，降低出现栈溢出的风险。故说法正确。 43．正确 【详解】本题考查递归。递归是一种编程技术，其中一个函数通过调用自身来解决问题。递归方法是一种隐式的控制结构，通常用于解决具有重复性质的问题。通过递归调用，函数可以在每次调用时处理问题的一部分，直到达到基准条件（也称为递归终止条件），此时递归停止，函数开始返回并完成所有的递归调用。故说法正确。 44．错误 【详解】本题考查的是Python赋值语句。赋值语句格式：变量名=表示，赋值的作用是把“=”右边的表达式的计算结果存储到“=”左边的变量。在Python中，s＝s＋5是正确的赋值语句。故题干中的说法错误。 45．错误 【详解】本题考查的是Python表达式。在Python中“∥”表示整除，%表示求余。表达式13%2+7∥2的值为4。故题干中的说法错误。 46．都是线性关系 【详解】本题考查数据结构。 都属于线性数据结构：队列和栈都是线性数据结构，即数据元素之间存在一对一的线性关系。然而，它们在数据元素的排列顺序和访问规则上有所不同。 有限制性的操作：栈的操作是后进先出（LIFO），只能在栈顶进行元素的插入（push）和删除（pop）操作。队列的操作是先进先出（FIFO），只能在队尾进行元素的插入（enqueue）操作，在队头进行元素的删除（dequeue）操作。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$ 《信息技术 选择性必修1 数据与数据结构》（教科版2019） 期末考试模拟卷 一 出题人： 审题人：教务处 题号装 订 线 班级_____________________姓名______________________学号_____________________ 总分 一 二 三 四 一、选择题 1．下列关于队列和栈的说法，不正确的是（   ） A．队列是一种先进先出的线性表，可在队尾进行插入操作 B．栈的特性是″先进后出，后进先出″ C．某栈的入栈的顺序为″abc″，出栈顺序只有3种 D．队列和栈都是线性数据结构，都可以用数组来实现 2．依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是（   ） A．a B．b C．c D．d 3．下列VB表达式中，值最小的是（    ）。 A．Abs(-3) + Len("NBXIAOSHI") B．Val(Mid("Ningbo2222", 8, 1)) C．Int(Sqr(36) + 5) \ 2 D．10^2 Mod 100 \ 3 ^ 2 4．某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（   ） A．前序遍历序列为DBACGFE B．节点G为节点E的父节点 C．该二叉树有两个叶子节点 D．节点A与节点F为同一层 5．递归算法可以用三个字来概括，但不包括下列选项中的（   ） A．解 B．分 C．治 D．合 6．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（   ） A．2 B．4 C．5 D．6 7．约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP 系列操作后，队首指针head和队尾指针tail的值分别为（   ） A．3 4 B．3 5 C．4 5 D．4 6 8．某二叉树的树形结构如图所示，其后序遍历结果为DBGEFCA，前序遍历的结果为（    ） A．ABCDEFG B．ABDCEGF C．DBEGCFA D．ABDCGFE 9．有如下 Python 程序段： 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 A B．A B C D E C．E B D C A D．A C D B E 10．若有一批元素的出栈顺序为“i, n, p, u, t”，其入栈顺序不可能是（   ） A．n, i, t, u, p B．n, i, u, t, p C．t, u, p, n, i D．i, n, p, u, t 11．某学校举行校园歌手比赛，数组a存放歌手的得分，数组mc存放名次。名次计算规则为：先对数组a中的元素按高到低的排序，分值最高为第1名，分值相同则名次相同。VB程序段的部分代码如下： For i = 1 To 19 For j = 20 To i + 1 Step -1 If① Then t =a(j): a(j)=a(i): a(i)=t Next j Next i mc(1) =② For i = 2 To 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．将十进制正整数转化为二进制数，对应的Python程序如下： def toStr(n,base): s = "01" if n < base: return s[n] else: return ① n = int(input('请输入正整数:')) result = toStr(n,2) print(result) 则代码中①处的语句可为（    ） A．toStr(n // base, base) + s[n % base] B．s[n % base] + toStr(n // base, base) C．toStr(n % base, base) + s[n // base] D．s[n // base] + toStr(n % base, base) 13．若采用冒泡排序对数据1，19，6，7，2，8，23，15进行排序处理，则第二遍加工后的结果是（   ） 原始数据 1 19 6 7 2 8 23 15 第一遍加工后 23 1 19 6 7 2 8 15 第二遍加工后 … A．23，19，1，15，8，6，7，2 B．23，19，1，15，6，7，2，8 C．23，19，15，1，6，7，2，8 D．23，19，15，8，1，6，7，2 14．已知一个栈的入栈顺序是1，2，3，4，…，n，其输出序列为R1，R2，R3，…，Rn，若Rn是1，则Ri是（   ） A．i B．n-1 C．n-i+1 D．不确定 15．栈S1从栈底到栈顶的元素顺序由1，2，3改为3，2，1，可借助初始均为空、长度均为3的栈S2、栈S3出入栈操作来实现，则需要出栈操作的总次数至少是（    ） A．6 B．7 C．8 D．9 16．栈和队列的顺序存储结构通常使用哪种数据结构（     ） A．链表 B．数组 C．树 D．图 17．下列有关查找的说法中，正确的是（   ） A．顺序查找时，被查找的数据必须有序 B．对分查找时，被查找的数据不一定有序 C．顺序查找总能找到要查找的关键字 D．—般情况下，对分查找的效率较高 18．有1个队列，队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为（   ） A．2,3 B．6,2,3 C．9,4,5 D．9,4,5,6 19．运行下列 Python程序，结果正确的是(　) a=18 b=7 c=a%b b=a%b print(a,b) A．18   5 B．5  18 C．18   4 D．4  18 20．某对分查找算法的VB程序段如下 Key =Val(Text1. Text) i=1:j=10:n=0 Do While i <=j   m= (i+j)\2   n=n+1   If a(m)>Key Then     j=m-1   Else     i=m+1   End If Loop Text2. Text = str(n) 数组元素a(1)到a(10)的值依次为“2，3，5，8，9，10，13，17，19，25”，在文本框Text1中入待查找的整数，执行该程序段，则文本框Text2中显示3，待查找数不可能是（    ） A．2 B．4 C．9 D．19 二、填空题 21．在计算机编程中， 是一种用于描述程序中数据的组织方式。 22．递归算法必须有一个 ，以防止无限递归。 23．递归算法的时间复杂度通常与问题的 有关。 24．程序代码如下，则其中 的作用是 。 25．栈是一种特殊的数据结构，遵循 的原则。 26．选择排序的主要思想是在未排序的序列中找到最小（或最大）的元素，将其存放到已排序序列的末尾。选择排序的平均时间复杂度为 。 27．归并排序是一种基于分治思想的排序算法，它的基本思想是将两个有序的子序列合并成一个有序序列。归并排序的平均时间复杂度为 。 28．二叉树是一种每个节点最多有 个子节点的树结构。 29．使用递归算法解决汉诺塔问题时，递归调用的次数为 。 30．计数排序是一种 算法，它的适用范围是整数且范围不大。 31．用来接收键盘输入的函数是 。 32．在数据结构中， 是一种特殊的线性表，只允许在表的两端进行插入和删除操作。 33．冒泡排序的基本思想是通过不断比较相邻元素并交换顺序错误的元素来实现排序，其时间复杂度为 。 34．使用( )关键字来创建python自定义函数。 35．递归算法的缺点之一是需要额外的空间来存储函数调用的 。 三、判断题 36．尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。( ) 37．递归方法适用于所有类型的问题。( ) 38．递归方法适用于解决那些可以通过分解为更小规模的相同问题来解决的问题。( ) 39．在程序设计常用的数据结构中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为栈。( ) 40．在递归方法中，必须有一个明确的终止条件，以防止无限递归。( ) 41．递归程序必须有一个明确的结束条件， 否则会陷入无限递归的状态，无法结束调用。( ) 42．在使用递归方法时，应该尽量使递归调用尽可能浅，以减少栈空间的使用。( ) 43．递归方法是一种隐式的控制结构，通过函数调用自身来实现循环。( ) 44．在Python中，s＝s＋5是错误的赋值语句。( ) 45．在 Python语言环境下，表达式13%2+7//2的值为4.5。   ( ) 四、简答题 46．队列和栈有什么共同点？ 试题第2页，共3页 试题第3页，共3页 学科网（北京）股份有限公司 $$境考填诗标记 信息技木答孤卡 静等过可 名 能周： ■■■ 士配脑冬通性用口桌米型色笔填写 ■ 1.不得春开什榨内相写，除律 。保转丰周的精，缓折叠，不要被 回 ■ 回 回 回 ■ 博箱峰■研议峰回同口刀) ■■▣ ▣▣ ■▣ ■■■■ 这样题40分 ■▣口四四■可衣▣口四四9可卫四可a▣■可■四■可7▣可四可 1■▣四■▣6▣▣四D6可▣圆口M0四■▣M可▣圈■四 3画■四■四下■■D四■四H可可可司仿J■B四四传口口围■四 4■▣■四■四■口8口口▣四？■▣口通口6口四g■可特口口■则口D 空题日0分制 3 3 四，算答厘0冷 运.10什) 有在各意日容超内域内荐.道由的摩的梦家天第绵)气（人 语在各量植首萝道以城为行栋：里他止门养实无效第天（其2期 A