第1单元 数据与数据结构综合检测 2023-—2024学年教科版（2019）高中信息技术选择性必修1

数据与数据结构 综合检测 一、选择题 1．有如下Python程序段： import random lst=['A'，'B'，'C'，'D'] st=[0]*len（lst） i，top=0，-1 while i<len（lst）：   k=random.randint（0，1）   if k==0：     top+=1     st[top]=lst[i]     i+=1   elif top!=-1：     lst[i]=st[top]     top-=1 执行该程序段后，lst的值不可能是（   ） A．['A'，'B'，'C'，'D'] B．['A'，'B'，'A'，'C'] C．['A'，'A'，'C'，'D'] D．['A'，'A'，'C'，'A'] 2．有如下自定义函数： def fg（n）：    if n<=2：       return n    else：       return fg（n-1）+fg（n-2） 执行语句s=fg（4），下列说法不正确的是（   ） A．s的值为5 B．函数fg被调用的次数是4 C．第二次被调用的函数是fg（3） D．该程序采用了递归算法 3．一条狭长的管道内有3个物体，每个物体可向左或向右移动，也可停在缓冲带上（最多停一个）。经过多次移动，物体状态从a变成c，其中b为移动中某次状态，如图所示，则移动过程中所有物体经过T点的最少总次数是（   ） A．8 B．7 C．5 D．3 4．下列二叉树中，前序和中序遍历结果一样的选项是（   ） A． B． C． D． 5．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（   ） A．5 B．4 C．3 D．2 6．某二叉树前序遍历为ABDFGCEH，后序遍历为FGDBHECA，则下列选项不可能是此二叉树的是（   ） A． B． C． D． 7．有如下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 8．有如下Python程序段： a = [1,2,3,4,5];b = [3,2,5,1,4] stack =[];i = j = 0 while i < len(a):     stack.append(a[i])#将a[i]添加到stack末尾     i += 1     while len(stack)>0 and stack[-1] == b[j]:         stack.pop()#移除stack末尾元素         j +=1 执行该程序段后，stack中的元素个数为（   ） A．0 B．1 C．2 D．3 9．某二叉树对应的一维数组表示如下图所示： 下列关于该二叉树的说法正确的是（   ） A．这是一棵完全二叉树 B．节点F是节点D的孩子节点 C．该二叉树有1个叶子结点 D．该二叉树中序遍历的结果是DBEACF 10．某二叉树的树形结构如下图所示，后序遍历结果为“WUSVTR”，则该二叉树的前序遍历结果为（   ） A．RSTUVW B．RTSVUW C．RTSUWV D．RSUWTV 11．若有一批元素的出栈顺序为“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 12．诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是（   ） A．树 B．栈 C．队列 D．链表 13．用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态），且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是（   ） A．1、2、3、4 B．2、3、4、1 C．4、2、3、1 D．3、2、1、4 14．利用栈求逆波兰表达式（表达式由操作数和运算符组成）的方法是:从左往右扫描该表达式，遇到操作数时入栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时（abcdef表示不同的操作数），所使用的栈的深度至少为（   ） A．3 B．4 C．5 D．6 15．下列二叉树中，后序遍历结果不为CBFEAD