发布时间 : 星期日 文章清华大学出版社数据结构(C++版)(第2版)课后习题答案最全整理更新完毕开始阅读7f427edcafaad1f34693daef5ef7ba0d4a736d92
⑸ 空串与空格串是相同的。
【解答】错。空串的长度为零，而空格串的长度不为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。
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．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？
【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。
9. 算法设计
⑴ 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。
【解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。
入队算法如下：
出队算法如下：
⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。 【解答】操作步骤为： ① 将所有元素出栈并入队；
② 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③ 将奇数结点出栈并入队； ④ 将偶数结点出队并入栈； ⑤ 将所有元素出栈并入队； ⑥ 将所有元素出队并入栈即为所求。
⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。
【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：
⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。
【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下：
⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。 【解答】参见3.2.5
学习自测及答案
1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A 不变 B top=0; C top=top-1; D top=top+1; 【解答】C
2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C