资源简介

浙教版（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出队后入栈，栈中元素为2，1；T-->3出队后入栈，栈中元素为3，2，1；执行PPP，连续三次出栈，栈为空，出栈顺序为3，2，1。
C选项，操作序列为THTTPPP，T-->3出队后入栈，栈中元素为3；H-->1出队后入队，队列元素为2，1；T-->2出队后入栈，栈中元素为2，3；T-->1出队后入栈，栈中元素为1，2，3；执行PPP，连续三次出栈，栈为空，出栈顺序为1，2，3。
D选项，操作序列为HΤΡΤΡΤΡ，H-->3出队后入队，队列元素为1，2，3；T-->1出队后入栈，栈中元素为1；P-->1出栈，出栈顺序为1，栈空；T-->2出队后入栈，栈中元素为2；。P-->2出栈，出栈顺序为1，2，栈空；T-->3出队后入栈，栈中元素为3，P-->3出栈，出栈顺序为1，2，3。
故本题答案是B选项。
2．B
【详解】本题考查栈操作相关内容。栈的特点是：先进后出。题干中限定条件栈s的最大长度为3：A选项，若d先出栈，说明c，b，a均在栈内，栈的容量至少为4，超出最大长度，选项错误。B选项，若b先出栈，说明a在栈内，a可以出栈，此时栈空，c，d先后入栈，再依次出栈，可得出栈序列：b，a，d，c，选项正确。CD选项中，a不应先于b出栈，选项错误。故本题答案是B选项。
3．C
【详解】本题考查算法时间复杂度相关内容。该函数采用了递归算法，执行过程为：f (x, n)-->x*f (x, n-1)-->x*f (x, n-2)-->...-->x*f (x, 0)，时间复杂度是O(n)。故本题答案是C选项。
4．C
【详解】本题考查数据结构链表操作相关内容。要删除头节点后面的节点，只需将头节点的next指针指向下一个节点的下一个节点即可。link[p][1] = - 1操作使得指针p所指向的节点变为尾节点，不能实现删除操作。head = link[p][1]操作使得指针p所指向的节点变为头节点，不能实现删除操作。link[head][1] = q、link[head][1] = link[p][1] 可以实现删除指针p所指向的节点。故本题答案是C选项。
5．C
【详解】本题考查图数据结构的描述。图是最为复杂的数据结构，如果数据元素之间存在一对多或者多对多的关系，那么这种数据的组织结构就叫作图结构。全国航运图存在多对多的关系，属于图结构。线性结构和树结构不存在多对多的关系。故选C。
6．D
【详解】本题考查线性数据结构的描述。在线性数据结构中，当前元素的后一位元素被称为后记元素，当前元素的前一位元素被称为前趋元素。故选D。
7．A
【详解】本题考查数据结构。线性数据结构就是数据元素之间是一对一的关系。故选A。
8．C
【详解】本题考查线性表相关内容。
1.顺序表存储（典型的数组）原理：顺序表存储是将数据元素放到一块连续的内存存储空间，相邻数据元素的存放地址也相邻（逻辑与物理统一）。优点：（1）空间利用率高。（局部性原理，连续存放，命中率高）（2）存取速度高效，通过下标来直接存储。缺点：（1）插入和删除比较慢，比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序。（2）不可以增长长度，有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现“溢出”问题，当元素个数远少于预先分配的空间时，空间浪费巨大。
2.链表存储原理：链表存储是在程序运行过程中动态的分配空间，只要存储器还有空间，就不会发生存储溢出问题，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点关系间的指针。优点：（1）存取某个元素速度慢。（2）插入和删除速度快，保留原有的物理顺序，比如：插入或者删除一个元素时，只需要改变指针指向即可。（3）没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关。缺点：（1）占用额外的空间以存储指针（浪费空间，不连续存放，malloc开辟，空间碎片多）（2）查找速度慢，因为查找时，需要循环链表访问，需要从开始节点一个一个节点去查找元素访问。频繁的查找却很少的插入和删除操作可以用顺序表存储，堆排序，二分查找适宜用顺序表。如果频繁的插入和删除操作很少的查询就可以使用链表存储；顺序表适宜于做查找这样的静态操作；链表适宜于做插入、删除这样的动态操作。
故本题答案是C选项。
9．C
【详解】本题考查数据结构相关内容。数据结构也称逻辑结构，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。从逻辑上可以把数据结构分成线性结构和非性结构。故本题答案是C选项。
10．C
【详解】本题考查顺序查找相关内容。122不存在于数组a中，数组a中共有10个元素，当与a数组中所有元素全部比较完结束，因此共查找10次，故本题答案为C选项。
11．C
【详解】本题考查数据结构栈的相关内容。计算机在执行递归程序时，是通过栈的调用来实现的，故本题答案为C选项。
12．B
【详解】本题考查递归算法相关内容。递归算法的执行过程分为两个阶段：递推和回归。在递推阶段，把较复杂的问题的求解递推到一些简单的问题的求解；在回归阶段，当获得简单问题的解后，逐级返回依次得到复杂问题的解。故本题答案为B选项。
13．B
【详解】本题考查数据结构算法相关内容。题中求3n的值，采用“大事化小，小事化了”的方法，符合递归算法的基本思想，故本题答案为B选项。
14．C
【详解】本题考查数据结构相关内容。迭代算法和递归算法是两种不同的算法，A选项错误。递归中一定有迭代，但迭代中不一定有递归，B选项错误。一般情况下，迭代算法和递归算法是可以相互转换的，C选项正确。迭代算法效率较高，而递归算法比较占用空间，程序运行效率较低，D选项错误。故本题答案为C选项。
15．B
【详解】本题考查数据结构相关内容。栈的操作有删除栈顶元素、判断栈是否为空、将栈置为空等。栈的插入和删除操作只能在栈顶进行，故本题答案为B选项。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑