一、基础知识题
3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：
若入、出栈次序为Push， Pop，Push，Push， Pop， Pop，Push， Pop，则出栈的数字序列为何表示i进栈，Pop表示出栈)?
能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。
请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。
3.2 链栈中为何不设置头结点?
3.3 循环队列的优点是什么? 如何判别它的空和满?
3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
3.5 指出下述程序段的功能是什么?
void Demo1 //Demo1
SeqStack S1， S2， tm
DataType x;
...//假设栈tmp和S2已做过初始化
while )
while )
void Demo2
}
void Demo3
while )
}// Demo3
CirQueue Q1， Q2; // 设DataType 为int 型
int x， i ， n= 0;
... // 设Q1已有内容， Q2已初始化过
while )
for
二、算法设计题
3.6 回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。
3.7 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack，并说明S为何要作为指针参数?
3.8 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize，并说明S为何不作为指针参数?
3.9 设计算法判断一个算术表达式的圆括号是否正确配对。 ‘就退掉栈顶的‘ 、入栈Push 和出栈Pop等算法， 其中i为0 或1， 用以表示栈号。
3.11Ackerman 函数定义如下：请写出递归算法。
┌ n+1 当m=0时
AKM = │ AKM 当m≠0 ，n=0时
└ AKM) 当m≠0， n ≠ 0时
3.12用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点 ，试编写相应的置空队、判队空 、入队和出队等算法。
3.14 对于循环向量中的循环队列，写出求队列长度的公式。
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 |
