内容发布更新时间 : 2025/6/24 18:20:18星期一 下面是文章的全部内容请认真阅读。
出队算法如下：
⑵ 设顺序栈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
3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）。
A x=top; top=top->next; B x=top->data;
C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D
4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。 【解答】PA321, P3A21, P32A1, P321A, AP321
5.设S=\，其长度为（ ）。 【解答】15
6．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（ ）。 【解答】Ｏ(1)
7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？
答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA 8．简述队列和栈这两种数据结构的相同点和不同点。
【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。
不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而
队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。
9. 利用两个栈S1和S2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。
【解答】利用两个栈S1和S2模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已输入的元素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S1中元素全部送入到S2中，再从S2中删除栈顶元素，最后再将S2中元素全部送入到S1中；判断队空的条件是：栈S1和S2同时为空。
10. 设计算法把一个十进制整数