第 3 章 特殊线性表——栈、队列和串
(2005-07-14) -
第 3 章 特殊线性表——栈、队列和串
课后习题讲解
1. 填空
⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5， 经过
push，push，pop，push，pop，push，push后，输出序列是（ ），栈顶指针为（ ）。
【解答】23，1003H
⑵ 栈通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。
【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，
栈顶指针top等于数
组的长度和内存无可用空间
⑶（ ）可作为实现递归函数调用的一种数据结构。
【解答】栈
【分析】递归函数的调用和返回正好符合后进先出性。
⑷ 表达式a*(b+c)-d的后缀表达式是（ ）。
【解答】abc+*d-
【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面
。
⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队
列的主要区别在于（
）。
【解答】后进先出，先进先出，对插入和删除操作限定的位置不同
⑹ 循环队列的引入是为了克服（ ）。
【解答】假溢出
⑺ 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素
个数的公式为（ ）。
page: 2
The Home of jetmambo - 第 3 章 特殊线性表——栈、队列和串
【解答】（rear-front+n）% n
【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同
的编译器环境下可能会有所不同。
⑻ 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）。
【解答】Ｏ(1)，Ｏ(n)
【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面
插入一个结点，这需要从头指针开始查终端结点的地址。
⑼ 串是一种特殊的线性表，其特殊性体现在（ ）。
【解答】数据元素的类型是一个字符
⑽ 两个串相等的充分必要条件是（ ）。
【解答】长度相同且对应位置的字符相等
【分析】例如"abc"≠"abc "，"abc"≠"bca"。
2. 选择题
⑴ 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。
A 不确定 B n-i C n-i-1 D n-i+1
【解答】D
【分析】此时，输出序列一定是输入序列的逆序。
⑵ 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若
6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（  ）。
A 6    B 4    C 3    D 2
【解答】C
【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。
⑶ 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。
A 54321 B 45321 C 43512 D 12345
【解答】C
【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的
两个元素。
page: 3
The Home of jetmambo - 第 3 章 特殊线性表——栈、队列和串
⑷ 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳
A 顺序表 B 栈 C 队列 D 链表
【解答】B
【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。
⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构
。
A 栈 B队列 C 数组 D线性表
【解答】B
【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。
⑹ 一个队列的入队顺序是1，2数据结构与算法分析答案，3，4，则队列的输出顺序是（ ）。
A 4321 B 1234 C 1432 D 3241
【解答】B
【分析】队列的入队顺序和出队顺序总是一致的。
⑺ 栈和队列的主要区别在于（ ）。
A 它们的逻辑结构不一样 B 它们的存储结构不一样
C 所包含的运算不一样 D 插入、删除运算的限定不一样
【解答】D
【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区
别，任何数据结构在针对具体问题时包含的运算都可能不同。
⑻ 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈
分配空间的最佳方案是（ ）。
A S1的栈底位置为0，S2的栈底位置为n-1
B S1的栈底位置为0，S2的栈底位置为n/2
C S1的栈底位置为0，S2的栈底位置为n
D S1的栈底位置为0，S2的栈底位置为1
【解答】A
【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中
的数组下标是从0开始的。
⑼ 设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）。
A 连接 B 模式匹配 C 求子串 D 求串长
【解答】B
page: 4
The Home of jetmambo - 第 3 章 特殊线性表——栈、队列和串
3. 判断题
⑴ 有n个元素依次进栈，则出栈序列有(n-1)/2种。
【解答】错。应该有 种。
⑵ 栈可以作为实现过程调用的一种数据结构。
【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。
⑶ 在栈满的情况下不能做进栈操作，否则将产生“上溢”。
【解答】对。
⑷ 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。
【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。
⑸ 空串与空格串是相同的。
【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。
4. 设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能
，请说明原因。
⑴ C，E，A，B，D
⑵ C，B，A，D，E
【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为
进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。
5. 举例说明顺序队列的“假溢出”现象。
【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产
生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单
元空闲，其下标分别为0和1。
page: 5
The Home of jetmambo - 第 3 章 特殊线性表——栈、队列和串
6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什
么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）
【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。
7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后
，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。
【解答】队头元素为5，队尾元素为9。其执行过程如图3-8所示。
8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？
【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。