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

《信息技术 选择性必修1 数据与数据结构》（教科版2019） 期末考试模拟卷 三 出题人： 审题人：教务处 题号装 订 线 班级_____________________姓名______________________学号_____________________ 总分 一 二 三 四 一、选择题 1．已知列表p1＝[1，2，3]，p2＝[3，2，1]，p3＝[1，2，3，″1″，″2″，″3″]，则表达式p1＝＝p2 and p1<＝p3的值为(　　) A．0 B．1 C．True D．False 2．已知6个节点的二叉树的先序遍历是abdcef，中序遍历是dbaecf，则该二叉树的后序遍历为（   ） A．dbaefc B．dbacef C．dbefca D．bdefca 3．如果函数int(X)表示取出X的整数部分，则int(68/10)的值为（   ）。 A．5 B．6 C．7 D．8 4．迭代法也称（ ），是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的（ ）称为一次“迭代”，而每一次迭代得到的（ ）会被用来作为下一次迭代的（ ）。（  ） A．辗转法；重复；结果；初始值 B．重复；结果；辗转法；初始值 C．辗转法；结果；重复；初始值 D．结果；初始值；辗转法；重复 5．数学表达式(7-5)*(1+2)可用二叉树表示，如图所示。则下列说法错误的是（   ） A．该二叉树是满二叉树 B．该二叉树的高度为3 C．通过后序遍历可求出该表达式的逆波兰式为7512-+* D．用列表方式存储该二叉树的具体结构为：['*',['-',[7,None,None],[5,None,None]],['+',[1,None,None],[2,None,None]]] 6．数字1,2,3依次进栈，则不可能的出栈顺序是 (　　) A．3,2,1 B．3,1,2 C．1,2,3 D．2,1,3 7．二分查找又称折半直找，是种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（  ） A．1，4，7，15，13 B．15，14，12，7，2，3 C．34，25，17，9，10，3 D．6，9，12，14，23，25 8．假设栈S的最大长度为3，其初始状态和终止状态均为空，经过一系列入栈和出栈的操作，若元素最后的出栈序列为F，E，D，C，B，A，则可能的入栈顺序为（   ） A．ABCDEF B．ACDFEB C．BEFACD D．BFDECA 9．判断a是否能被b整除，以下语句正确的是（    ） A．if a/b=0: B．if a//b=0: C．if a%b= =0: D．if a//b= =0: 10．下列python语句中，执行结果一定不是“10”的为（  ） A．x+10 B．x-10 C．x*10 D．x%10 11．小华玩猜价格游戏，已知价格的范围在 1 元到 200 元之间。他第一次猜 100 元，太低；第二次猜 150元，太高；第三次猜 125 元，又太低；……，小明在猜价格时采用的方法是（ ）。 A．顺序查找 B．随机查找 C．对分查找 D．排序查找 12．设栈S 的初始状态为空，元素a,b,c,d,e,f依次入栈，出栈顺序为b,d,c,f,e,a,则栈S的容量至少是（   ） A．2 B．3 C．4 D．5 13．下面程序运行结果是：（  ） c=0 for i in range(1,26):      if i%2==0:        c=c+1 print(c) A．10 B．11 C．12 D．13 14．已知一棵完全二叉树共有200个节点，下列说法正确的是（    ） A．该完全二叉树的高度为7 B．该完全二叉树有99个叶子节点 C．该完全二叉树有100个度为2的节点 D．该完全二叉树有1个度为1的节点 15．有如下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] 16．有如下 Python程序段: def f(s):     if len(s)==1:         return True     elif len(s)==2:         return s[0]==s[1]     elif s[0]==s[-1]:         return f(s[1: -1])     else:         return False print(f("1234321")) 执行该程序段后，下列说法正确的是（   ） A．输出结果为False B．函数f 运用了迭代算法 C．函数 f 的调用次数为4 D．函数f的时间夏杂度为O(n²) 17．下列表达式的值最大的是（   ） A．Val (Str(10) + Str(0)) B．Val (Str(10)) + Val(Str(1)) C．Int(Rnd * 100) D．Sqr (Len("10000")) 18．递归算法是一种（   ）的算法。 A．非线性 B．迭代 C．自我调用 D．无法预测 19．使用升序排序算法对列表[130,20,98,15,67,3 ]进行排序后结果为（    ） A．[130,20,98,15,67,3 ] B．[3,15,20,67,98,130 ] C．[15,20,98,67,3, 130] D．[130,98,67,20,15,3 ] 20．已知 x=2，语句 x*=x+1 执行后，x的值是(    )。 A．2 B．3 C．5 D．6 二、填空题 21．快速排序的基本思想是通过选取一个基准元素，将数组分为两部分，一部分的元素都小于基准元素，另一部分的元素都大于基准元素，然后对这两部分分别进行排序。其平均时间复杂度为 。 22．已知 x = [3, 5, 7] ，那么执行语句 x[1:] = [2] 之后，x 的值为 。 23．python输出的函数是 。 24．在哈希表中，负载因子是指已存储元素数量与哈希表容量的比值。当负载因子过大时，会发生 现象。 25．在数据结构中，栈是一种 的数据结构，遵循后进先出（LIFO）原则。 26．尾递归是一种特殊的递归形式，可以被优化为 结构。 27．递归算法是一种通过 来解决问题的算法。 28．快速排序是一种基于分治思想的排序算法，它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序的平均时间复杂度为 。 29．请将数学表达式 写成计算机程序设计语言表达式 __________________ 。 30．计算机中数据的存储结构主要分为 和 。 31．将数学表达式：x2＋5x＋3写成VisualBasic表达式： 32．在Python程序设计语言中，运行以下程序，显示的运行结果是( ) a=3 b=4 if a+b>8：     print（a） if a+b<=8：     print（b） 33．在实现递归算法时，将递归算法转换为非递归形式可以 栈溢出的问题。 34．在数据结构中， 是一种特殊的线性表，只允许在表的两端进行插入和删除操作。 35．冒泡排序的基本思想是通过 来逐步将元素按照升序排列。冒泡排序的平均时间复杂度是O(n^2)。 三、判断题 36．在 Python语言环境下，表达式13%2+7//2的值为4.5。   ( ) 37．尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。( ) 38．递归方法是一种显式的控制结构。( ) 39．递归方法的核心思想是将一个问题分解为更小的子问题，这些子问题与原问题具有相同的结构。( ) 40．算术运算符中*、/的运算优先级高于//和%。( ) 41．用栈来存储数据时，可以快速地通过下标精确地访问序列中的某个数据元素。( ) 42．递归方法可以用于解决排序和搜索等问题。( ) 43．递归方法适用于解决那些可以通过分解为更小规模的相同问题来解决的问题。( ) 44．递归方法是一种隐式的控制结构，通过函数调用自身来实现循环。( ) 45．递归方法在处理具有重复子问题的问题时特别有效。( ) 四、简答题 46．描述什么是二叉树，并解释二叉搜索树的特点。 试题第2页，共3页 试题第3页，共3页 学科网（北京）股份有限公司 $$考填标记 信息技术答题卡 8号 ■D 口D 口 甲D 口 3是笔。 1T 口D 铅用改流, 17 甲p口 口 3. 不得内,涂 出出 阳1 4. 面洁。不折夜,不要数 ■ ■D图DDD 口口口口口阳口口 t题() □回D [ 17C□ :□□□□口 □□1□□□ 10□□14□□ 1□□1□ 3]□ 7□□ 1 11 □ 8D□□ 11□□□□1□□□D20□□□□ 二.填空题) _.80题(20分) 图.简答题(10) 短.10分) 在的区的 请品各题的位的答是(时 参考答案： 题号 1 2 3 4 5 6 7 8 9 10 答案 D C B A C B D D C D 题号 11 12 13 14 15 16 17 18 19 20 答案 C B C D D C A C B D 1．D 【详解】本题考查的是表达式的计算。本题主要考查的是列表操作。列表中的元素和位置有关，因此表达式p1＝＝p2的值为False，列表p3中的元素包含列表p1中的元素，因此表达式p1<＝p3的值为True，and运算时，只有两边同时为True时，结果才为True，其他情况均为False，故选项D正确。 2．C 【详解】本题考查二叉树相关内容。根据二叉树的先序遍历“abdcef”，可知树根是a，中序遍历“dbaecf”中db为左子树序列，ecf为右子树序列，节点b又是节点d父节点，同理可得，e是c节点的左孩子节点，f是c节点的右孩子节点，画出二叉树如下图所示： 该二叉树的后序遍历为dbefca，故本题答案为C选项。 3．B 【详解】本题考查的是Python函数。/表示除，int(68/10)=int(6.8)=6。故本题应选B。 4．A 【详解】本题主要考查迭代算法。迭代法也称辗转法，是用计算机解决问题的一种基本方法。迭代通常是为了接近并达到所需的目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值，故本题选A选项。 5．C 【详解】本题考查二叉树。后序遍历的顺序是左子树-右子树-根节点。对于该二叉树，后序遍历的结果是 75-12+*。故答案为：C。 6．B 【详解】本题主要考查栈的操作。数字1,2,3依次进栈，若3先出栈，接着只能是2出栈，不可能是3、1、2，故本题选B选项。 7．D 【详解】本题主要考查二分查找算法。二分查找又称折半直找，是种应用于有序数列的高效查找算法，6，9，12，14，23，25是升序序列，适合二分查找算法，故本题选D选项。 8．D 【详解】本题考查栈。ABCDEF依次入栈再依次出栈，第一个出栈为F，需要栈的最大长度为6，A选项错误；ACDFEB依次入栈，第一个出栈为F，需要栈的最大长度为4，B选项错误；BEFACD依次入栈再依次出栈，当F，E出栈后，ACD入栈，D出栈，此时需要栈的最大长度为4，C选项错误；故答案为：D。 9．C 【详解】本题考查的是Python表达式。判断a是否能被b整除，只要判断a除以b的余数是否为0，在Python中用==表示相等。故本题应选C。 10．D 【详解】本题考查Python表达式。A选项：这是对x加上10，结果可能是10，具体取决于x的值。B选项：这是对x减去10，结果可能是10，具体取决于x的值。C选项：这是对x乘以10，结果可能是10，具体取决于x的值。D选项：这是对x取余数，结果不一定是10，具体取决于x的值。如果x是10的倍数，结果是0；否则，结果是不等于10的余数。故答案为：D。 11．C 【详解】本题考查的是查找算法。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找;在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。故本题应选C。 12．B 【详解】本题考查的是栈相关知识。栈是先入后出。栈S 的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a，则先入栈a、b，出栈b；再入栈c、d，出栈d、c；再入栈e、f，出栈f、e、a。整个过程栈中最多元素为3个，故栈S的容量至少是3，选项B正确 13．C 【详解】本题主要考查Python程序的执行。变量i的范围是1-25，当i是偶数时，c递增，满足if条件的i有：2、4、6、8、10、12、14、16、18、20、22、24，故程序运行完，c的值为12，故本题选C选项。 14．D 【详解】本题主要考查二叉树的描述。该完全二叉树的高度为h=log2n + 1=8；该完全二叉树有200/2=100个叶子节点；由n0=n2+1，因此该完全二叉树有100-1=99个度为2的节点；由n=n0+n1+n2，得到该完全二叉树有200-100-99=1个度为1的节点，故本题选D选项。 15．D 【详解】本题考查的是插入排序。阅读程序可知，比较的是abs (a[j]-2)>abs(k-2)，即最终是按abs (a[i]-2)升序排列，即最后每个数据项减2后求绝对值应为升序，4个选项结果如下表： A B C D 原始值 -5，-2，4，0，1 3，-1，0，2，-3 1，2，3，4，5 0，4，0，-2，-4 -2 -7，-4，2，-2，-1 1，-3，-2，0，-5 -1，0，1，2，3 -2，2，-2，-4，-6 求绝对值 7，4，2，2，1 1，3，2，0，5 1，0，1，2，3 2，2，2，4，6 故本题应选D。 16．C 【详解】本题考查程序分析。根据代码，这是利用递归判断一个字符串是否是“回文串”；选项A，"1234321"是“回文串”应该输出True，错误；选项B，运用了递归算法，错误；选项C，第一次，f("1234321")；第二次f("23432")；第三次f("343")；第四次f("4")。故选择C。选项D，根据以上分析，算法复杂度是O(n) 17．A 【详解】本题主要考查表达式的计算。Val()是将字符串转为整型，Int是取整数部分，Rnd是随机生成[0,1)之间的数，Sqr()是开方函数，Len()是求字符串的长度，故Val (Str(10) + Str(0))=Val(Str(100))=100，Val (Str(10)) + Val(Str(1))=10+1=11，Int(Rnd * 100)生成[0,99]之间的整数，Sqr (Len("10000"))=Sqr(5)，故表达式最大的是Val (Str(10) + Str(0))，故本题选A选项。 18．C 【详解】本题考查的是递归算法。递归是一种通过函数直接或间接调用自身来解决问题的方法。它通常将一个大问题分解为与原问题相似的较小问题，直到达到可以直接解决的基本情况（或称为递归出口），然后再逐级返回，逐步解决整个问题。递归的核心思想是“自己调用自己”。故选C。 19．B 【详解】本题主要考查升序排序算法。使用升序排序算法对列表[130,20,98,15,67,3 ]进行排序后结果为[3,15,20,67,98,130 ]，故本题选B选项。 20．D 【详解】本题考查的是Python赋值语句。x*=x+1等价于赋值语句x=x*(x+1)。执行后x的值为：2*（2+1）=6。故本题应选D。 21．O(nlogn) 【详解】本题考查快速排序。快速排序的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n^2)。故答案为：O(nlogn)。 22．[3,2] 【详解】本题主要考查Python列表。x = [3, 5, 7] ，语句 x[1:] = [2] 是将列表x索引1及之后的值赋值为2，即5、7赋值替换为2，故执行语句 x[1:] = [2] 之后，x 的值为[3,2]。 23． print() 【详解】本题主要考查Python函数。用来接收键盘输入的函数是input()，python输出的函数是print()。 24．哈希冲突增多 【详解】本题考查哈希表的描述。在哈希表中，负载因子是已存储元素数量与哈希表容量的比值。当负载因子过大时，哈希表中的元素数量接近或超过其容量，导致多个元素被映射到相同的哈希位置，从而发生哈希冲突增多现象。这会降低哈希表的查找效率。为了避免这种情况，通常会在负载因子达到某个阈值时进行扩容操作。 25．线性 【详解】本题考查栈。在数据结构领域，栈是一种重要的结构。本题重点在于对栈的类型进行考查，明确其为线性数据结构。线性数据结构的特点是元素之间存在一对一的线性关系。栈遵循后进先出原则，即最后进入栈的元素最先出栈。这种特性使得栈在很多场景中发挥重要作用，比如函数调用时保存现场、表达式求值等。由于栈的操作只在一端进行，其元素的排列呈现线性特点，所以被归类为线性数据结构。故答案为：线性。 26．循环 【详解】本题考查的是递归。尾递归是一种特殊的递归形式，其特点在于递归调用是函数执行的最后一步，即函数调用出现在调用者函数的尾部，并且没有其他操作跟随在递归调用之后。由于这种特性，尾递归可以被优化为循环结构，从而减少递归调用带来的开销，特别是避免递归调用过深导致的栈溢出问题。 27．自我调用 【详解】本题考查递归算法。递归算法的核心在于通过自身函数或方法的自我调用，将复杂问题不断分解为规模更小、结构相似的子问题，并通过子问题的解逐步求得原问题的解。故答案为：自我调用。 28．O(nlogn) 【详解】本题考查快速排序。快速排序的平均时间复杂度为O(nlogn)，但在最坏情况下，其时间复杂度为O(n^2)。 29．（x^2+y^2）/（x*y） 【详解】本题主要考查程序语句。数学表达式中的平方用“^”号表示，除用“/”，乘用“*”，故该表达式写成计算机程序设计语言表达式（x^2+y^2）/（x*y）。 30． 顺序存储结构 非顺序存储结构 【详解】本题考查数据存储结构。计算机中数据的存储结构主要分为顺序存储结构和非顺序存储结构。顺序存储结构是指数据元素在存储器中按其逻辑顺序依次存放，相邻元素的存储位置也相邻。非顺序存储结构则不要求数据元素的存储位置相邻，常见的有链式存储结构等。例如，数组通常采用顺序存储结构，而链表则属于非顺序存储结构。故答案为：顺序存储结构、非顺序存储结构。 31．x^2+5*x+3 【详解】本题主要考查VB程序表达式。上述数学表达式写成VisualBasic表达式：x^2+5*x+3。 32．4 【详解】本题主要考查Python程序的执行。a=3，b=4，a+b<8，故输出b的值4。 33．避免 【详解】本题考查递归算法。递归算法在执行过程中会不断地调用自身，每次调用都会在栈中分配新的空间。如果递归深度过大，可能会导致栈溢出。将递归算法转换为非递归形式，可以通过显式地使用栈数据结构来管理函数调用，从而避免栈溢出的问题。 34．队列 【详解】本题考查队列。在数据结构中，一种特殊的线性表，只允许在表的两端进行插入和删除操作的表称为队列（Queue）。故答案为：队列。 35．相邻元素之间的比较和交换 【详解】本题考查冒泡排序。冒泡排序的基本思想是通过相邻元素之间的比较和交换来逐步将元素按照升序排列。故答案为：相邻元素之间的比较和交换。 36．错误 【详解】本题考查的是Python表达式。在Python中“∥”表示整除，%表示求余。表达式13%2+7∥2的值为4。故题干中的说法错误。 37．正确 【详解】本题考查尾递归。尾递归指的就是在函数的最后一步进行递归调用。这样的结构使得在某些支持优化的编程语言中，可以对其进行特殊处理，避免不断地创建新的栈帧，从而节省栈空间，提高程序的性能和避免栈溢出。故说法正确。 38．错误 【详解】本题考查递归。递归方法不是一种显式的控制结构，而是一种通过函数自身调用自身来解决问题的方法。在递归中，函数的执行流程相对较为隐晦和复杂，需要通过函数调用栈来管理和实现。它依赖于系统在运行时自动处理函数的调用和返回，而不是像循环等显式控制结构那样，程序员可以直接清晰地看到控制的流程和条件。故说法错误。 39．正确 【详解】本题考查递归方法。递归方法确实是通过将问题分解为更小的、结构相同的子问题来解决原始问题的。这是递归方法的基本思想。故说法正确。 40．错误 【详解】本题考查的是Python算术符。在Python中算术运算符*、/、//和%运算优先级一样，故题干中的说法是错误的。 41．错误 【详解】本题考查栈。用数组来存储数据时，可以快速地通过下标精确地访问序列中的某个数据元素，而栈只能从访问栈顶元素开始访问。故说法错误。 42．正确 【详解】本题考查递归方法。递归方法确实可以用于解决排序（如快速排序、归并排序）和搜索（如二分查找）等问题。故说法正确。 43．正确 【详解】本题考查递归方法。递归的核心思想就是将一个复杂的大问题不断分解为规模更小的、与原问题具有相同形式的子问题，并通过解决这些子问题来最终解决原问题。故说法正确。 44．正确 【详解】本题考查递归。递归是一种编程技术，其中一个函数通过调用自身来解决问题。递归方法是一种隐式的控制结构，通常用于解决具有重复性质的问题。通过递归调用，函数可以在每次调用时处理问题的一部分，直到达到基准条件（也称为递归终止条件），此时递归停止，函数开始返回并完成所有的递归调用。故说法正确。 45．正确 【详解】本题考查递归方法。递归方法非常适合处理具有重复子问题的问题，因为它可以避免重复计算相同子问题，从而提高效率。故说法正确。 46．二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。 【详解】本题考查二叉树。 二叉树（Binary Tree）是树形结构的一个重要类型，在计算机科学中广泛应用。二叉树的特点是每个节点最多只能有两棵子树，且有左右之分。具体来说，二叉树是n（n≥0）个有限元素的集合，该集合或者为空（称为空二叉树），或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。这种结构使得二叉树在存储和算法实现上相对简单，因此在实际问题中经常被采用。 二叉树的基本形态包括空二叉树、只有一个根节点的二叉树、只有左子树的二叉树、只有右子树的二叉树以及完全二叉树等。其中，完全二叉树是一种特殊的二叉树，其深度为k，有n个节点，且这些节点与深度为k的满二叉树中编号从1到n的节点一一对应。 二叉搜索树的特点 二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它除了具有二叉树的一般特点外，还具有以下特点： 有序性：在二叉搜索树中，对于树中的任意节点X，其左子树上所有节点的值都小于X的值，而其右子树上所有节点的值都大于X的值。这一特性使得二叉搜索树在查找、插入和删除操作上具有高效性。 递归性：二叉搜索树的左子树和右子树也都是二叉搜索树，这保证了整个树结构的一致性。 快速查找：由于二叉搜索树的有序性，可以通过递归的方式快速定位到目标节点，查找效率较高。在最坏情况下（树退化为链表），查找效率为O(n)，但在平均情况下，查找效率接近O(logn)。 动态集合操作：二叉搜索树支持动态集合上的各种操作，如插入、删除和查找等。这些操作的时间复杂度都与树的高度成正比，因此在平衡的二叉搜索树中，这些操作都能保持较高的效率。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$