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。

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的元素，能减少移动元素的次数，提高算法的效率。算法如下：

精选