数据结构（宁夏大学） 第三章_智慧树知到答案2021年

第三章 栈和队列：栈和队列是两种重要的抽象数据类型，是一类插入和删除的位置受限的线性表。从数据逻辑结构角度年，它们都是线性结构，应用非常广泛，本章将讨论栈与队列的概念、存储结构和基本运算的实现。3.1栈:栈是限定仅在一端进行插入或删除的线性表。本节将讲解栈的逻辑结构、和基本运算。栈的顺序存储结构是用一个数组向量来实现栈，通常习惯以数组下标大的一端做栈顶，本节首先讲解了顺序栈的入栈、出栈等基本运算的实现，然后分析了多个顺序栈共享存储空间的问题，并提出了两个共用栈的解决方案。由于插入、删除都在top位置进行，所以链栈实际就是一个用top指针表示的单链表，本节主要讲解了链栈的基本运算。本节主要通过多个链栈的管理、多行文本编辑器纠错、栈实现递归调用三个例题的讲解，说明了栈在计算机中的应用非常广泛。
3.2队列:队列(Queue)是一种运算受限的线性表。它只允许在表的一端进行 插入，而在另一端进行删除。本节主要介绍了队列的逻辑结构和基本运算。本节首先分析了用向量存储队列，所产生假上溢和假下溢现象，引出了循环队列的概念，然后讲解了循环队列的结构及基本运算的实现。由于队列规定了必须在队尾插入、队头删除，所以一个链队列显然需要队头、队尾两个指针才能唯一确定，本节主要讲解了链队列的基本运算及改进算法。本节用队列来实现了迷宫求解问题，讲解了迷宫的数据建模和搜索路径的实现两个关键问题的具体解决方案。

[单选题]设用链表作为栈的存储结构则退栈操作（  ）。

选项:[必须判别栈是否为满, 判别栈元素的类型, 必须判别栈是否为空, 对栈不作任何判别]
[单选题]栈结构通常采用的两种存储结构是（  ）。

选项:[散列方式和索引方式, 线性存储结构和链表存储结构, 线性存储结构和非线性存储结构, 链表存储结构和数组]
[单选题]设循环队列Q[N]的头尾指针为F、R，头指针F总是指在队列中的第一个元素的前一位置，则队列中元素计数为（ ）。

选项:[(R-F+N)%N , R-F, (F-R+N)%N, N-(R-F)]
[单选题]一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（  ）。

选项:[2 3 4 1 5, 1 5 4 3 2, 5 4 1 3 2, 2 3 1 4 5]
[单选题]设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（  ）。

选项:[2, 6, 3, 4]
[单选题]队列操作的原则是（  ）。

选项:[先进先出, 后进先出, 只能进行插入, 只能进行删除]
[单选题]以下属于队列的基本运算的是（  ）。

选项:[删除队头元素, 取出最近进队元素, 对队列中的元素排序, 在队列中某元素之后插入元素]
[单选题]设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（  ）。

选项:[O(log₂n), O(n²), O(1), O(n)]
[单选题]设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（  ）。

选项:[top->next=top;, top=top+1;, top=top->next;, top=top-1;]
[单选题]以下各种不带头结点的链表中最不适合用作链队的（  ）。

选项:[只带队首指针的循环双链表, 只带队首指针的非循环双链表, 只带队尾指针的循环双链表, 只带队尾指针的非循环双链表]
[判断题]在链队列中，即使不设置尾指针也能进行入队操作。

选项:[错, 对]
[判断题]走迷宫问题只能用队列来求解。

选项:[对, 错]
[判断题]非空的双向循环链表中任何结点的前驱指针均不为空。

选项:[错, 对]