精品解析：《信息技术 选择性必修1 数据与数据结构》（教科版2019）期末考试模拟卷 二

《信息技术 选择性必修1 数据与数据结构》（教科版2019） 期末考试模拟卷 二 一、选择题 1. 在信息加工中，经常要对被处理的数据进行排序，在排序时经常要进行数据的交换。下列四个选项中，不能将x和y两个变量中的数据进行交换的是（ ） A. B. C. D. 2. 若x是整型变量，下列选项中，与表达式Not（x > 1 And x <= 6）等价的是（ ） A. x <= 1 And x> 6 B. Not x > 1 And Not x<= 6 C. x > 1 Or x<= 6 D. x<=1 Or x > 6 3. 设栈S和队列Q的初始状态为空，元素w1、w2、w3、w4、w5依次通过栈S，一个元素出栈后即进入队列Q，下列不可能是出队序列的是（ ） A. w5、w4、w3、w2、w1 B. w3、w2、w1、w4、w5 C. w4、w2、w1、w3、w5 D. w1、w2、w3、w4、w5 4. 如图所示二叉树，根节点为0，每个节点的左子节点为0，右子节点为1，每一条从根到叶子的路径都组成一个二进制数。例如：从根到叶子a的路径组成二进制数011，转换为十进制数是3。若某完全二叉树共有13个节点，则它能表示的最大十进制数是（ ） A. 3 B. 4 C. 5 D. 6 5. 用数组表示二叉树的示意图如下所示，则该二叉树的中序遍历序列为（ ） A. BEDFAC B. ABDEFC C. DBEAFC D. BDAECF 6. 利用冒泡排序给数组[15,78,88,23,69,71,20,53]升序排序，第三遍冒泡加工之后的数据结果是（ ） A. [15,20,23,78,88,69,71,53] B. [15,20,23,53,78,88,69,71] C. [15,78,23,69,71,20,53,88] D. [15,23,69,71,20,53,78,88] 7. 有1个队列，队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为（ ） A. 23 B. 6,2,3 C. 9,4,5 D. 9,4,5,6 8. 栈和队列的共同点是（ ） A. 只允许在端点处插入和删除数据 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 9. 有如下Python程序： def fun(x,n): if x == n: return 1 if n % x == 0: return fun(x,n//x)+1 else: return fun(x+1,n) print(fun(2,100)) 执行上述程序后，输出的结果是（ ） A 2 B. 3 C. 4 D. 5 10. 下列Python表达式用于表示“一棵n个节点的二叉树的叶子节点最大可能数量”正确的是（ ） A. n-1 B. (n-1)//2 C. (n+1)//2 D. n/2 11. 在Python编程中，判断一个学生是否是一名体重（weight）大于55千克或者身高（height）小于170厘米男生（gender:Male），条件表达式可以表示为（ ） A. gender＝＝"Male" and （weight＞55 or height<170） B. gender＝＝ "Male" or weight＞55 or height<170） C. gender＝＝"Male" or （weight＞55 and height<170） D. gender＝＝ "Male" and weight＞55 and height<170） 12. 若已知元素的入栈顺序是a,b,c,d,其出栈序列为Q1,Q2,Q3,Q4,则Q2,Q4不可能是（ ） A. a和c B. a和b C. b和d D. c和d 13. 在python程序中，表达式10-5//2*2＋4%5的结果是（ ） A. 0 B. 6 C. 10 D. 15 14. 某学校举行校园歌手比赛，数组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) 15. 某完全二叉树，中序遍历结果为“甲乙丙丁”，则后序遍历结果是（ ） A. 甲乙丁丙 B. 丙乙甲丁 C. 甲丁丙乙 D. 乙丁丙甲 16. 下面代码的输出结果是（ ）。 def add(x): if x>0: return x＋add(x-l) else: return 0 result＝add(10) print(result) A. 0 B. 10 C. 55 D. 45 17. 某食品连锁店5位顾客贵宾消费卡的积分依次为810，512，613，700，900。采用选择排序算法对其排序，若完成第一遍时的结果为：512，810，613，700，900，则完成第二遍的结果是( ) A. 512，613，700，900，810 B. 512，810，613，900，700 C. 512，900，613，700，810 D. 512，613，810，700，900 18. 某二叉树的中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（ ） A. 前序遍历序列为DBACGFE B. 节点G为节点E的父节点 C. 该二叉树有两个叶子节点 D. 节点A与节点F为同一层 19. 19世纪末，在欧洲商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。玩家要将最左边杆上的盘子全部移到最右边的杆子上，要求一次只能移动一个盘，且不允许大盘放在小盘的上面。如果最左边杆子上只有3个盘子，则最少需要移动（ ）步才能将所有的盘子移至最右边杆。（ ） A. 15 B. 31 C. 7 D. 8 20. 在计算机科学中，数据具有如下特征的是（ ） A. 语义性 B. 传递性 C. 时效性 D. 共享性 二、填空题 21. 二叉树是一种每个节点最多有____个子节点的树结构。 22. 设树T有17条边，12片树叶，4个4度内部节点，1个3度内部节点。则T的树根的度数为_____。 23. 递归算法中的递归式是指______。 24. 以下程序引入Python的math模块，使用math模块下的floor函数对命令行输入的实数进行取整 n=input（“请输入一个实数：”） n2= math. floor（float（n）） print（n2） 该程序段划线处应填入的代码为________。 25. 冒泡排序的基本思想是通过不断比较相邻元素并交换顺序错误的元素来实现排序，其时间复杂度为____。 26. 在计算机编程中，______ 是一种用于存储和管理数据的集合，它允许数据项以有序的方式添加和删除。 27. 将数学表达式改写成VB表达式：_____________________________ 28. 将数学表达式：x2＋5x＋3写成VisualBasic表达式：________________________ 29. 递归算法的时间复杂度通常与问题的______有关。 30. 快速排序的基本思想是通过选取一个基准元素，将数组分为两部分，一部分的元素都小于基准元素，另一部分的元素都大于基准元素，然后对这两部分分别进行排序。其平均时间复杂度为____。 31. 递归算法的适用场景包括阶乘计算、斐波那契数列计算和______等。 32. 队列是一种有限制的____结构。特点是数据元素只能在队尾依次添加（称为进队），在另一端依次删除（称为出队）。 33. 计数排序是一种____算法，它的适用范围是整数且范围不大。 34. 请在Python中新建文件，输入以下代码并运行出结果，end=‘ ’的语句作用是：______ 35. 在Python程序中，已知x=2，y=3，当执行语句y+=x*2，y的值是____。 三、判断题 36. 在 Python语言环境下，表达式13%2+7//2的值为4.5。 （ ） 37. 递归方法是一种隐式的控制结构，通过函数调用自身来实现循环。（ ） 38. 在递归方法中，必须有一个明确的终止条件，以防止无限递归。（ ） 39. 在程序设计常用的数据结构中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为栈。（ ） 40. 如果变量a=5，那么表达式10>a and a<3的结果为False。（ ） 41. 递归方法是一种显式的控制结构。（ ） 42. 递归程序必须有一个明确的结束条件， 否则会陷入无限递归的状态，无法结束调用。（ ） 43. 尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。（ ） 44. 递归方法可能导致栈溢出，特别是在处理大规模问题时。（ ） 45. 在递归方法中，递归调用可以是尾递归。（ ） 四、简答题 46. 论述堆排序的基本思想和实现步骤。 第1页/共1页 学科网（北京）股份有限公司 $$ 《信息技术 选择性必修1 数据与数据结构》（教科版2019） 期末考试模拟卷 二 一、选择题 1. 在信息加工中，经常要对被处理的数据进行排序，在排序时经常要进行数据的交换。下列四个选项中，不能将x和y两个变量中的数据进行交换的是（ ） A B. C. D. 【答案】A 【解析】 【详解】本题考查的是数据的交换。假设x=3，y=4， 选项A，x=4，y=4，没实现两数交换 选项B，t=3，x=4，y=3，实现两数互换 选项C，x=3+4=7，y=7-4=3，x=7-3=4，实现两数互换 选项D，x=3-4=-1，y=-1+4=3，x=3-（-1）=4，实现两数互换 故选项BCD均可以实现两数互换，答案为A。 2. 若x是整型变量，下列选项中，与表达式Not（x > 1 And x <= 6）等价的是（ ） A. x <= 1 And x> 6 B. Not x > 1 And Not x<= 6 C. x > 1 Or x<= 6 D. x<=1 Or x > 6 【答案】D 【解析】 【详解】本题主要考查表达式的运算。表达式Not（x > 1 And x <= 6）等价于Not x>1 Or Not x<=6 等价于x<=1 Or x>6，故本题选D选项。 3. 设栈S和队列Q的初始状态为空，元素w1、w2、w3、w4、w5依次通过栈S，一个元素出栈后即进入队列Q，下列不可能是出队序列的是（ ） A. w5、w4、w3、w2、w1 B. w3、w2、w1、w4、w5 C. w4、w2、w1、w3、w5 D. w1、w2、w3、w4、w5 【答案】C 【解析】 【详解】本题考查数据结构栈、队列相关操作。栈的特点是：后进先出；队列的特点是：先进先出。结合栈、队列的特点，分析题意可得，元素w1、w2、w3、w4、w5的出栈序列即为队列的出队序列。 A选项，w5、w4、w3、w2、w1，w5第一个出队，即第一个出栈，说明w4、w3、w2、w1均在栈内，其出栈序列只能是一种：w4、w3、w2、w1，故其入队序列是w5、w4、w3、w2、w1，出队序列为w5、w4、w3、w2、w1，选项正确。 B选项，w3、w2、w1、w4、w5，w3第一个出队，即第一个出栈，说明w2、w1均在栈内，w2、w1依次出栈再入队，其出栈序列是w2、w1，出队序列是w2、w1；w4、w5依次入栈、出栈再入队，其出栈序列是w4、w5，其出栈序列是：w4、w5，故其入队序列是w3、w2、w1、w4、w5，出队序列为w3、w2、w1、w4、w5，选项正确。 C选项，w4、w2、w1、w3、w5，w4第一个出队，即第一个出栈，说明w3、w2、w1均在栈内，w3、w2、w1依次出栈再入队，其出栈序列是w3、w2、w1，出队序列是w3、w2、w1；此时与选项中出队序列：w2、w1、w3不同，选项错误。 D选项，w1、w2、w3、w4、w5，w1第一个出队，即第一个出栈，说明栈内无其他元素，w2、w3、w4、w5可以依次出栈再入队，其出栈序列是w2、w3、w4、w5，出队序列是w2、w3、w4、w5；故其入队序列是w1、w2、w3、w4、w5，出队序列为w1、w2、w3、w4、w5，选项正确。故本题答案是C选项。 4. 如图所示的二叉树，根节点为0，每个节点的左子节点为0，右子节点为1，每一条从根到叶子的路径都组成一个二进制数。例如：从根到叶子a的路径组成二进制数011，转换为十进制数是3。若某完全二叉树共有13个节点，则它能表示的最大十进制数是（ ） A. 3 B. 4 C. 5 D. 6 【答案】C 【解析】 【详解】本题考查二叉树相关内容。若某完全二叉树共有13个节点，构建完全二叉树，如图所示：其表示的最大数为：0101，转换为十进制是5，故本题答案为C选项。 5. 用数组表示二叉树的示意图如下所示，则该二叉树的中序遍历序列为（ ） A. BEDFAC B. ABDEFC C. DBEAFC D. BDAECF 【答案】A 【解析】 【详解】本题考查二叉树相关内容。由二叉树存储可推知该二叉树结构，如图所示： 该二叉树的中序遍历结果为：BEDFAC。故本题答案是A选项。 6. 利用冒泡排序给数组[15,78,88,23,69,71,20,53]升序排序，第三遍冒泡加工之后的数据结果是（ ） A. [15,20,23,78,88,69,71,53] B. [15,20,23,53,78,88,69,71] C. [15,78,23,69,71,20,53,88] D. [15,23,69,71,20,53,78,88] 【答案】B 【解析】 【详解】本题主要考查冒泡排序。利用冒泡排序给数组[15,78,88,23,69,71,20,53]升序排序，第一遍冒泡加工之后的数据结果是[15,20,78,88,23,69,71,53]，第二遍冒泡加工之后的数据结果是[15,20,23,78,88,53,69,71]，第三遍冒泡加工之后的数据结果是[15,20,23,53,78,88,69,71]，故本题选B选项。 7. 有1个队列，队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为（ ） A. 2,3 B. 6,2,3 C. 9,4,5 D. 9,4,5,6 【答案】D 【解析】 【详解】本题考查队列相关内容。队列的特点是先进先出。队首到队尾的元素依次为8、10、12、9。第一次操作8出队，第二次操作8//2的结果4入队，第三次操作10出队，第四次操作10//2的结果5入队，第五次操作12出队，第六次操作12//2的结果6入队，故此时队列中的元素依次为9、4、5、6，D选项正确。故本题答案是D选项。 8. 栈和队列的共同点是（ ） A. 只允许在端点处插入和删除数据 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 【答案】A 【解析】 【详解】本题考查了栈和队列的基本特性。栈和队列的共同点是都只允许在端点处插入和删除数据。具体来说：栈（Stack）是先进后出（LIFO）的数据结构，只允许在一端（称为栈顶）插入和删除数据。队列（Queue）是先进先出（FIFO）的数据结构，只允许在一端（称为队尾）插入数据，在另一端（称为队头）删除数据。因此，A选项是正确的。B和C选项分别描述了栈和队列的不同特性，而D选项显然是不正确的。故答案为：A。 9. 有如下Python程序： def fun(x,n): if x == n: return 1 if n % x == 0: return fun(x,n//x)+1 else: return fun(x+1,n) print(fun(2,100)) 执行上述程序后，输出的结果是（ ） A. 2 B. 3 C. 4 D. 5 【答案】C 【解析】 【详解】本题考查的是Python递归。fun(2,100)=fun(2,50)+1=fun(2,25)+1+1=fun(5,5)+1+1+1=1+1+1+1=4。故本题应选C。 【分析】 【点睛】 10. 下列Python表达式用于表示“一棵n个节点的二叉树的叶子节点最大可能数量”正确的是（ ） A. n-1 B. (n-1)//2 C. (n+1)//2 D. n/2 【答案】C 【解析】 【详解】本题主要考查二叉树的描述。n个结点的二叉树，最少有一个叶子结点，最多有⌈n/2⌉ 个叶子节点。 当二叉树每一层都只有一个结点，也即每一个分支结点都只有一个孩子时，只有树最底层有1个叶子结点。 当二叉树是完全二叉树时，叶子最多。完全二叉树只有0或1个度为1的结点，而根据任意二叉树中度为0的结点(叶子)总是比度为2的结点多1的规律，可知当结点总数n是偶数时，叶子有n/2个，当结点总数n是奇数时，叶子有n/2取整加1个。即叶子最多有⌈n/2⌉ 个 ，用Python表示是(n+1)//2，故本题选C选项。 11. 在Python编程中，判断一个学生是否是一名体重（weight）大于55千克或者身高（height）小于170厘米的男生（gender:Male），条件表达式可以表示为（ ） A. gender＝＝"Male" and （weight＞55 or height<170） B. gender＝＝ "Male" or weight＞55 or height<170） C. gender＝＝"Male" or （weight＞55 and height<170） D. gender＝＝ "Male" and weight＞55 and height<170） 【答案】A 【解析】 【详解】本题考查的是Python逻辑表达式。and表示同时满足，or表示或者的关系，判断一个学生是否是一名体重（weight）大于55千克或者身高（height）小于170厘米的男生（gender:Male），条件表达式可以表示为：gender＝＝"Male" and （weight＞55 or height<170）。故本题应选A。 12. 若已知元素的入栈顺序是a,b,c,d,其出栈序列为Q1,Q2,Q3,Q4,则Q2,Q4不可能是（ ） A. a和c B. a和b C. b和d D. c和d 【答案】B 【解析】 【详解】本题考查栈结构相关内容。入栈顺序是a、b、c、d，其出栈序列共14种，分别是：abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba。对比四个选项，B选项不可能出现，故本题答案是B选项。 13. 在python程序中，表达式10-5//2*2＋4%5的结果是（ ） A. 0 B. 6 C. 10 D. 15 【答案】C 【解析】 【详解】本题考查表达式。在Python中，先计算除法和取整除法，再计算乘法，然后计算加法和减法，最后计算取余运算。5//2结果为2，2*2结果为4，10-4结果为6，4%5结果为4，6+4结果为10。所以表达式10-5//2*2+4%5的结果是10，答案为C。 14. 某学校举行校园歌手比赛，数组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) 【答案】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选项。 15. 某完全二叉树，中序遍历结果为“甲乙丙丁”，则后序遍历结果是（ ） A. 甲乙丁丙 B. 丙乙甲丁 C. 甲丁丙乙 D. 乙丁丙甲 【答案】A 【解析】 【详解】本题考查的是二叉树的遍历。依据题意可知二叉树如下： 故后序遍历结果是：甲乙丁丙。本题应选A。 16. 下面代码的输出结果是（ ）。 def add(x): if x>0: return x＋add(x-l) else: return 0 result＝add(10) print(result) A. 0 B. 10 C. 55 D. 45 【答案】C 【解析】 【分析】 【详解】本题主要考查递归算法及Python程序实现。add(x)函数是一个递归函数，如果x>0，则返回x+add(x-1)，所以result=add(10)=10+9+8+7+6+5+4+3+2+1=55，故本题选C选项。 17. 某食品连锁店5位顾客贵宾消费卡的积分依次为810，512，613，700，900。采用选择排序算法对其排序，若完成第一遍时的结果为：512，810，613，700，900，则完成第二遍的结果是( ) A. 512，613，700，900，810 B. 512，810，613，900，700 C. 512，900，613，700，810 D. 512，613，810，700，900 【答案】D 【解析】 【详解】本题主要考查选择排序算法。选择排序法实现的步骤：首先找出一个最小数交换到最前面；然后在剩下的数中找个最小的交换到剩下数最前面；最后一直重复此步骤，直到所有数排好即可。若完成第一遍时的结果为：512，810，613，700，900，可知完成的升序排序，故完成第二遍的结果是512，613，810，700，900，故本题选D选项。 18. 某二叉树中序遍历序列为ABCDEFG，后序遍历序列为ACBFEGD，下列说法正确的是（ ） A. 前序遍历序列为DBACGFE B. 节点G为节点E的父节点 C. 该二叉树有两个叶子节点 D. 节点A与节点F为同一层 【答案】B 【解析】 【详解】本题考查的是二叉树。依据题意可画出如下的数： 由图可知，前序遍历序列为DBACGEF，节点G为节点E的父节点，该二叉树有3个叶子节点，节点A与节点F不在同一层。故本题应选B。 19. 19世纪末，在欧洲的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。玩家要将最左边杆上的盘子全部移到最右边的杆子上，要求一次只能移动一个盘，且不允许大盘放在小盘的上面。如果最左边杆子上只有3个盘子，则最少需要移动（ ）步才能将所有的盘子移至最右边杆。（ ） A. 15 B. 31 C. 7 D. 8 【答案】C 【解析】 【详解】本题主要考查递归算法。已知最左边有三个盘子，所以先想办法移动前两个，第一个放在最右边，第二个放中间，然后将第一个移动到中间，然后将最左边的最大的移动到最右边，然后将中间的最小的移动至最左边，将中间部分的中间那个移动至最右端，然后将最小的移动到最右端，完成，共进行了7次移动，故本题选C选项。 20. 在计算机科学中，数据具有如下特征的是（ ） A. 语义性 B. 传递性 C. 时效性 D. 共享性 【答案】A 【解析】 【详解】本题主要考查数据的特征。在计算机科学中，数据具有语义性，指数据的表现形式还不能完全表达其内容，需要经过解释，数据和关于数据的解释是不可分的，故本题选A选项。 二、填空题 21. 二叉树是一种每个节点最多有____个子节点的树结构。 【答案】两 【解析】 【详解】本题考查二叉树。二叉树是一种重要的数据结构，其特点是每个节点最多有两个子节点，分别称为左子节点和右子节点。这是二叉树的核心定义和显著特征，通过这个限制，使得二叉树在数据存储、搜索、排序等操作中具有特定的性质和优势。故答案为：两。 22. 设树T有17条边，12片树叶，4个4度内部节点，1个3度内部节点。则T的树根的度数为_____。 【答案】3 【解析】 【详解】本题考查树结构相关内容。已知17条边，可知节点为18个，设根的度为x，则所有节点的度之和为:x+4*4+3*1+12，总度数应是边的两倍，则有x+4*4+3*1+12=17*2，求得x=3，因此T的树根的度数为3。故本题答案为：3。 23. 递归算法中递归式是指______。 【答案】递归调用的形式化描述 【解析】 【详解】本题考查递归算法。递归式是对递归调用的形式化描述，用于指导如何将原问题分解为更小的子问题。故答案为：递归调用的形式化描述。 24. 以下程序引入Python的math模块，使用math模块下的floor函数对命令行输入的实数进行取整 n=input（“请输入一个实数：”） n2= math. floor（float（n）） print（n2） 该程序段划线处应填入的代码为________。 【答案】import math 【解析】 【详解】本题主要考查Python程序的执行。空处需要使用import关键字导入math模块，故填import math。 25. 冒泡排序的基本思想是通过不断比较相邻元素并交换顺序错误的元素来实现排序，其时间复杂度为____。 【答案】O(n^2) 【解析】 【详解】本题考查冒泡排序。冒泡排序的平均和最坏情况下的时间复杂度都是O(n^2)，最好情况下的时间复杂度是O(n)。故答案为：O(n^2)。 26. 在计算机编程中，______ 是一种用于存储和管理数据的集合，它允许数据项以有序的方式添加和删除。 【答案】队列 【解析】 【详解】本题考查队列。在计算机编程中，队列是一种用于存储和管理数据的集合，它遵循先进先出（FIFO）的原则，允许数据项在一端添加（入队）和在另一端删除（出队）。故正确答案为：队列。 27. 将数学表达式改写成VB表达式：_____________________________ 【答案】(x^3+1)/(abs(x)+sqrt(x)) 【解析】 【详解】本题主要考查VB表达式。绝对值用abs()表示，根号用sqrt()表示，故上式数学表达式改写成VB表达式(x^3+1)/(abs(x)+sqrt(x))。 28. 将数学表达式：x2＋5x＋3写成VisualBasic表达式：________________________ 【答案】x^2+5*x+3 【解析】 【详解】本题主要考查VB程序表达式。上述数学表达式写成VisualBasic表达式：x^2+5*x+3。 29. 递归算法的时间复杂度通常与问题的______有关。 【答案】规模和分解方式 【解析】 【详解】本题考查递归算法。递归算法的时间复杂度通常与问题的规模和分解方式有关，因为不同的分解方式可能导致不同的时间复杂度。故答案为：规模和分解方式。 30. 快速排序的基本思想是通过选取一个基准元素，将数组分为两部分，一部分的元素都小于基准元素，另一部分的元素都大于基准元素，然后对这两部分分别进行排序。其平均时间复杂度为____。 【答案】O(nlogn) 【解析】 【详解】本题考查快速排序。快速排序的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n^2)。故答案为：O(nlogn)。 31. 递归算法的适用场景包括阶乘计算、斐波那契数列计算和______等。 【答案】树的遍历 【解析】 【详解】本题考查递归。递归算法的适用场景包括阶乘计算、斐波那契数列计算和树的遍历等，这些场景都可以将问题分解为更小的子问题。故答案为：树的遍历。 32. 队列是一种有限制的____结构。特点是数据元素只能在队尾依次添加（称为进队），在另一端依次删除（称为出队）。 【答案】线性数据 【解析】 【详解】本题考查队列。队列是一种限制的线性数据结构，只允许在表的一端进行插入操作，称为队尾（rear），而在另一端进行删除操作，称为出队。这种特性使得队列具有先进先出（FIFO—first in first out）的特性。故答案是线性数据。 33. 计数排序是一种____算法，它的适用范围是整数且范围不大。 【答案】非比较 【解析】 【详解】本题考查的是计数排序。计数排序是一种非比较算法，它的适用范围是整数且范围不大的情况。它通过计数每个元素的出现次数来进行排序。 34. 请在Python中新建文件，输入以下代码并运行出结果，end=‘ ’的语句作用是：______ 【答案】end属性值为空字符串，表示不换行；end属性值为 字符，表示换行 【解析】 【详解】本题主要考查Python程序的执行。end属性值为空字符串，表示不换行；end属性值为 字符，表示换行。 35. 在Python程序中，已知x=2，y=3，当执行语句y+=x*2，y的值是____。 【答案】7 【解析】 【详解】本题考查Python表达式。已知x=2，y=3，当执行语句y+=x2时，首先计算x2，得到4，然后将y的当前值3与计算结果4相加，最后将结果赋值给y。因此，y的值为3+4，即7。故答案为：7。 三、判断题 36. 在 Python语言环境下，表达式13%2+7//2的值为4.5。 （ ） 【答案】错误 【解析】 【详解】本题考查的是Python表达式。在Python中“∥”表示整除，%表示求余。表达式13%2+7∥2的值为4。故题干中的说法错误。 37. 递归方法是一种隐式的控制结构，通过函数调用自身来实现循环。（ ） 【答案】正确 【解析】 【详解】本题考查递归。递归是一种编程技术，其中一个函数通过调用自身来解决问题。递归方法是一种隐式的控制结构，通常用于解决具有重复性质的问题。通过递归调用，函数可以在每次调用时处理问题的一部分，直到达到基准条件（也称为递归终止条件），此时递归停止，函数开始返回并完成所有的递归调用。故说法正确。 38. 在递归方法中，必须有一个明确的终止条件，以防止无限递归。（ ） 【答案】正确 【解析】 【详解】本题考查递归。在递归方法中，明确的终止条件是必不可少的。如果没有终止条件，递归函数会无限制地自我调用，导致无限递归，最终可能造成栈溢出等错误，使程序崩溃。故说法正确。 39. 在程序设计常用的数据结构中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为栈。（ ） 【答案】错误 【解析】 【详解】本题考查数据结构队列相关内容。在程序设计中，与食堂排队打饭、公交排队上车处理方式类似的数据结构通常称为队列（Queue）。队列是一种先进先出（FIFO，First-In-First-Out）的数据结构，在队列中，新的元素被添加到队列的末尾，而从队列中移除元素时，总是从队列的头部开始移除。故本题答案是：错误。 40. 如果变量a=5，那么表达式10>a and a<3的结果为False。（ ） 【答案】正确 【解析】 【详解】本题考查的是表达式的运算。10>5为真，5<3为假，所以10>5 and 5<3为假，题干描述正确。 41. 递归方法是一种显式控制结构。（ ） 【答案】错误 【解析】 【详解】本题考查递归。递归方法不是一种显式的控制结构，而是一种通过函数自身调用自身来解决问题的方法。在递归中，函数的执行流程相对较为隐晦和复杂，需要通过函数调用栈来管理和实现。它依赖于系统在运行时自动处理函数的调用和返回，而不是像循环等显式控制结构那样，程序员可以直接清晰地看到控制的流程和条件。故说法错误。 42. 递归程序必须有一个明确的结束条件， 否则会陷入无限递归的状态，无法结束调用。（ ） 【答案】正确 【解析】 【详解】本题考查程序设计相关内容。递归程序必须有一个明确的结束条件，如果没有明确的结束条件，递归函数可能会陷入无限递归的状态，导致无法结束调用。这种情况称为递归无限循环或递归死循环。故本题答案是：正确。 43. 尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。（ ） 【答案】正确 【解析】 【详解】本题考查尾递归。尾递归指的就是在函数的最后一步进行递归调用。这样的结构使得在某些支持优化的编程语言中，可以对其进行特殊处理，避免不断地创建新的栈帧，从而节省栈空间，提高程序的性能和避免栈溢出。故说法正确。 44. 递归方法可能导致栈溢出，特别是在处理大规模问题时。（ ） 【答案】正确 【解析】 【详解】本题考查递归。在递归调用过程中，每次调用都会在系统的栈中分配内存来存储函数的参数、局部变量等信息。如果递归的深度过大，即递归调用的次数过多，会导致栈空间被大量占用。特别是在处理大规模问题时，可能需要极深的递归调用层次，从而超出系统栈的容量限制，引发栈溢出错误。故说法正确。 45. 在递归方法中，递归调用可以是尾递归。（ ） 【答案】正确 【解析】 【详解】本题考查递归。尾递归是一种特殊的递归形式，其中递归调用是函数体中的最后一个操作。尾递归在某些编程语言中可以被优化为迭代形式，从而避免栈溢出的问题。故说法正确。 四、简答题 46. 论述堆排序的基本思想和实现步骤。 【答案】堆排序的基本思想是通过构建一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再调整堆结构，重复这个过程直到整个序列变得有序。实现步骤包括构建最大堆、交换堆顶元素和最后一个元素、调整堆结构等。堆排序的平均时间复杂度为O(nlogn)。 【解析】 【详解】本题考查堆排序。堆排序的基本思想是通过构建一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再调整堆结构，重复这个过程直到整个序列变得有序。实现步骤包括构建最大堆、交换堆顶元素和最后一个元素、调整堆结构等。堆排序的平均时间复杂度为O(nlogn)。 第1页/共1页 学科网（北京）股份有限公司 $$