浙教版（2019）选修一5.1数据结构与算法的关系同步练习（含解析）

浙教版（2019）选修一5.1数据结构与算法的关系同步练习 学校:_____姓名：_____班级：_____考号：_____ 一、选择题 1．队列Q从队首到队尾的元素依次为3，1，2，栈S初始为空。约定以下操作：H操作是指元素出队后再入队，T操作是指元素出队后入栈，P操作是指元素出栈。经过一系列操作后，最终出栈顺序为1，2，3，以下操作不可能的是（ ） A．TTPTPP B．HTTTPPP C．THTTPPP D．HΤΡΤΡΤΡ 2．栈S最大长度为3，若元素a，b，c，d依次入栈，则可能的出栈序列为（ ） A．d，c，b，a B．b，a，d，c C．c，a，b，d D．c，d，a，b 3．定义如下函数： 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) 4．由n个节点链接成的单链表如图所示，其中head为头指针。 使用列表link模拟该链表结构，每个节点包含数据域和指针域，如图中最后一个节点可以表示为［98，-1］。现要删除指针p所指向的节点，可以实现该操作的语句有（ ） ① link[p][1] = - 1 ② link[head][1] = q ③ link[head][1] = link[p][1] ④ head = link[p][1] A．①② B．①③ C．②③ D．②④ 5．全国航运图属于（ ） A．线性结构 B．树结构 C．图结构 D．以上均不是 6．在线性数据结构中，当前元素的后一位元素被称为（ ） A．首元素 B．前趋元素 C．尾元素 D．后继元素 7．线性结构数据之间的关系是（ ） A．一对一 B．多对多 C．一对多 D．多对一 8．在以下的叙述中，正确的是（ ） A．线性表的顺序存储结构优于链表存储结构 B．线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C．线性表的链表存储适用于频繁插入/删除数据元素的情况 D．线性表的链表存储结构优于顺序存储结构 9．在数据结构中，从逻辑上可以把数据结构分成（ ） A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非性结构 D．内部结构和外部结构 10．在数组a中存储的数据依次为“12，56，37，18，19，22，28，26，31，33”。现使用顺序查找算法在数组a中查找数据122，则共需查找的次数为（ ） A．8次 B．9次 C．10次 D．11次 11．递归算法的函数调用时，处理参数和返回地址通常使用的数据结构是（ ） A．数组 B．队列 C．栈 D．链表 12．递归过程的实现过程分为两个阶段，分别是（ ） A．枚举和回归 B．递推和回归 C．递推和递归 D．试探和回归 13．小王设计了一个算法求3n的值，算法思想是：先把3n转换为3*3n-1，而3n-1又可以转换为3*3n-1-1，如此继续，直到3*30，已知30=1，然后通过30的值又可以求出31的值，如此继续，最终求出了3n的值。小杰采用的算法是（ ） A．迭代算法 B．递归算法 C．枚举算法 D．解析算法 14．下列有关迭代算法和递归算法的描述，正确的是（ ） A．迭代算法和递归算法本质上没有什么区别 B．递归中一定有迭代，迭代中也一定有递归 C．通常情况下，迭代算法和递归算法可以相互转换 D．迭代算法效率较低，而递归算法效率较高 15．下列不是栈的基本运算的是（ ） A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．将栈置为空 试卷第1页，共3页 试卷第1页，共3页 参考答案： 1．B 【详解】本题考查数据结构栈和队列操作相关内容。栈的特点是先进后出，队列的特点是先进先出。结合题目，推知： A选项，操作序列为TTPTPP，T-->3出队后入栈，栈中元素为3；T-->1出队后入栈，栈中元素为1，3；P-->1出栈，栈中元素为3，出栈顺序为1；T-->2出队后入栈，栈中元素为2，3；P-->2出栈，栈中元素为3，出栈顺序为1，2；P-->3出栈，栈为空，出栈顺序为1，2，3。 B选项，操作序列为HTTTPPP，H-->3出队后入队，队列元素为1，2，3；T-->1出队后入栈，栈中元素为1；T-->2出队后入栈，栈中 ... ...