2023-2024学年高二上学期浙教版(2019)选修一5.1 数据结构与算法的关系 同步练习（含答案）

2023-2024学年高二上学期浙教版(2019)选修一5.1 数据结构与算法的关系 一、选择题 1．有1个队列，队首指针head=2，队尾指针tail=3，经过一系列出队入队后，队首指针head=3，队尾指针tail=6，则该队列经历的出队和入队操作次数分别为（ ） A．1 3 B．1 4 C．2 3 D．2 4 2．定义如下函数： def f (x, n): if n == 0: return 1 return x * f (x, n - 1) 该函数的时间复杂度为（ ） A．0(1) B．0(log2n) C．0(n) D．0(xn) 3．递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是（ ） A．数组 B．队列 C．栈 D．链表 4．在二次探测的哈希表中，当发生哈希冲突时，我们会（ ） A．停止查找 B．重新选择哈希函数 C．以二次函数的形式探测新的位置 D．删除冲突的元素 5．有如下 Python程序，用于判断链表是否为回文链表（回文链表是指正序遍历和逆序遍历得到的结点顺序一致的链表），则划线处代码是（ ） a=[[1,1],[2,2],[8,3],[2,4],[1,-1]] st=[];head=0;flag=True slow, fast=head, head while ① : st.append (a[slow][o]) slow=a[slow][1] fast=a[a[fast][1]][1] if ② : slow=a[slow][1] while slow!=-1: if st.pop () !=a[slow][0]: flag=False slow=a[slow][1] if flag: print("是回文链表!") else: print("不是回文链表!") A．①fast!=-1 or a[fast][1]!=-1 ②fast!=-1 B．①fast!=-1 or a[fast][1]!=-1 ②a[fast][1]!=-1 C．①fast!=-1 and a[fast][1]!=-1 ②fast!=-1 D．①fast!=-1 and a[fast][1]!=-1 ②a[fast][1]!=-1 6．树结构是一种具有层次关系的非线性结构。树是由n(n≥0)个节点组成的有限集合，如图所示，下列说法错误的是( ) A．任何一个非空树均仅有一个称为根的节点，如图中A,n=0时为空树 B．当n>0时，其余节点可分为m ( m≥0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树 C．节点A为根节点，B、C、D为A的子树的根节点，同理，E、F、G是B的子树的根节点，B是E、F、G的父节点 D．在树结构中，数据元素之间是一对一的关系 7．数据结构中栈和队列的共同特点是（ ） A．处理数据时满足先进后出 B．处理数据时满足先进先出 C．只允许在端点处插入和删除数据 D．没有共同点 8．用对分查找法从列表[2、4、6、8、15、16、27、33、55]中找到数据16的最少查找次数是（ ）次。 A．2 B．3 C．4 D．6 9．什么是时间复杂度（ ） A．程序执行所需的时间 B．程序执行所需的内存 C．描述算法运行时间随输入大小增长的趋势 D．程序的输出结果 10．数据结构在程序设计中的作用不包括（ ） A．提高程序运行效率 B．方便数据的存储和检索 C．增加代码的复杂度 D．有助于算法设计 11．队列Q从队首到队尾的元素依次为0，1，2，3，约定：A操作是指队首元素出队，P操作是指队首元素出队后立即从队尾入队，经过APA系列操作后，队列中队首到队尾的元素依次为（ ） A．3，0，2 B．2，0 C．3，1 D．1，3，0 12．线性结构数据之间的关系是（ ） A．一对一 B．多对多 C．一对多 D．多对一 13．全国航运图属于（ ） A．线性结构 B．树结构 C．图结构 D．以上均不是 14．下列有关数组的描述，错误的是（ ） A．数组是由相同数据类型的变量组成的一个序列 B．数组中的每个元素按照下标顺序依次存储 C．二维数组中的元素在内存中的存储方式有行优先存储和列优先存储两种 D．在数组中进行插入、删除操作时无需移动数据元素 15．关于数据结构的描述，以下选项中错误的是( ) A．数据结构指相互有关联的数据元素的集合 B．数据的存储结构有顺序存储、链接存储、索引存储和散列存储 C．数据结构不可以直观地用图形表示 D．数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型 二、填空题 16．下列查找算法中 ... ...