栈与队列习题与答案

一 选择题 1. 对于栈操作数据的原则是（ ）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2

④: A. 长度 B. 深度 C. 栈顶 D. 栈底

⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】

4. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】

5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】

6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】

7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。【中科院计算所2000一、10(2分)】

A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，

8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】

9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。

A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 【北京航空航天大学 2000 一、3（2分）】【北京邮电大学 1999 一、3（2分）】 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面

得不到的序列为（ ）。 A．fedcba B. bcafed C. dcefba D. cabdef 【南京理工大学 1996 一、9（2分）】

12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX

【南京理工大学 1997 一、5（2分）】 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）【中山大学 1999 一、8(1分)】 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1 【南京理工大学 1998 一、13（2分）】

15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 【南京理工大学 1999 一、14（1分）】 16. 栈在（ ）中应用。【中山大学 1998 二、3（2分）】 A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ ）。【武汉大学 2000 二、2】

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 18. 执行完下列语句段后，i值为：（ ）【浙江大学 2000 一 、6 (3分)】 int f(int x)

{ return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归

19. 表达式a*(b+c)-d的后缀表达式是( )。【南京理工大学 2001 一、2（1.5分）】 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

20. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂 。

A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 【青岛大学 2000 五、5（2分）】

21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 【西安电子科技大学 1996 一、6（2分）】

22. 用链接方式存储的队列，在进行删除运算时（ ）。【北方交通大学 2001 一、12（2分）】 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。【北京理工大学 2001 六、3（2分）】 A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数

组 C．栈 D. 线性表 【福州大学 1998 一、1（2分）】

25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。【北京工商大学 2001 一、2（3分）】

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。【南京理工大学 2001 一、5（1.5分）】

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。【中山大学 1999 一、6（1分）】

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )【浙江大学1999 四、1(4分)】

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 【西安交通大学 1996 三、3 (3分)】 30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。【西安电子科技大学 1996 一、5（2分）】 A. 1234 B. 4132 C. 4231 D. 4213

31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 【南京理工大学 1999 一、16（2分）】 32. 栈和队列的共同点是（ ）。【燕山大学 2001 一、1（2分）】 A. 都是先进先出 B. 都是先进后出

C. 只允许在端点处插入和删除元素 D. 没有共同点 33. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若进栈序列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。【北方交通大学 1999 一、1（5分）】 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构

④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 34. 栈和队都是（ ）【南京理工大学 1997 一、3（2分）】 A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构

35. 设栈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

【南京理工大学 2000 一、6（1.5分）】

36. 用单链表表示的链式队列的队头在链表的（ ）位置。【清华大学 1998 一、1（2分）】 A．链头 B．链尾 C．链中

37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？【哈尔滨工业大学 2000 七（8分）】

A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b} C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g}

二 判断题

1. 消除递归不一定需要使用栈，此说法（ ） 【中科院计算所 1998 二、2（2分）】【中国科技大学 1998 二、2（2分）】 2. 栈是实现过程和函数等子程序所必需的结构。（ ）【合肥工业大学 2000 二、2（1分）】 3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。（ ）【青岛大学 2000 四、2（1分）】

4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ）【上海海运学院 1998 一、4（1分）】

5. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）【北京邮电大学 1999 二、4（2分）】

6. 有n个数顺序（依次）进栈，出栈序列有Cn种，Cn=[1/（n+1）]*（2n）!/[(n!)*(n!)]。（ ）

【北京邮电大学 1998 一、3（2分）】 7. 栈与队列是一种特殊操作的线性表。（ ）【青岛大学 2001 四、3 （1分）】 8. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （ ） 【上海海运学院1995 一、2（1分） 1997 一、3（1分）】 9. 栈和队列都是限制存取点的线性结构。（ ）【中科院软件所 1999 六、(5)（2分）】 10．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。（ ） 【上海海运学院 1999 一、3（1分）】

11. 任何一个递归过程都可以转换成非递归过程。（ ）【上海交通大学 1998一、3（1分）】 12. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（ ） 【上海交通大学 1998 一、4（1分）】

13. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ） 【上海海运学院 1998 一、3（1分）】

14. 通常使用队列来处理函数或过程的调用。（ ）【南京航空航天大学 1997 一、5（1分）】 15. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ 【）上海交通大学 1998 一、2】

16. 循环队列通常用指针来实现队列的头尾相接。（ ）【南京

航空航天大学 1996 六、1（1分）】 17. 循环队列也存在空间溢出问题。（ ）【青岛大学 2002 一、2 （1分）】 18. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）【长沙铁道学院1997一、5(1分)】

19. 栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ）【北京邮电大学2002一、3(1分)】

20. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ） 【上海海运学院 1996 一、2（1分） 1999 一、2（1分）】

三 填空题

1．栈是_______的线性表，其运算遵循_______的原则。【北京科技大学 1997 一、3】 2．_______是限定仅在表尾进行插入或删除操作的线性表。【燕山大学 1998 一、3 （1分）】 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。【中国人民大学2001一、1(2分)】

4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。【西安电子科技大学 1998 二、1（4分）】

5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。 【南京理工大学 1997 三、1（3分）】 6．两个栈共享空间时栈满的条件_______。【中山大学 1998 一、3（1分）】

7．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。【山东工业大学 1994 一、1（5分）】

8. 多个栈共存时，最好用_______作为存储结构。【南京理工大学 2001 二、7（2分）】 9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。【西南交通大学 2000 一、5】 10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。 【合肥工业大学 2001 三、2 （2分）】

11．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。【中山大学 1998 一、4（1分）】

12. 循环队列的引入，目的是为了克服_______。【厦门大学 2001 一、1 （14/8分）】 13．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M：=_______（填PASCAL语言，C语言的考生不填）； M= _______（填C语

学 1999 一、1 （7分）】 34．一个循环队列的数据结构描述如下： TYPE sequeuetp=RECORD

elem：ARRAY[1..MAXSIZE] OF elemtp； front，rear：0..MAXSIZE； END；

给出循环队列的队空和队满的判断条件，并且分析一下该条件对队列实际存储空间大小的影响，如果为了不损失存储空间，你如何改进循环队列的队空和队满的判断条件？【西北工业大学 1999 三 (8分)】

35. 如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 （1）编写实现队列的三个基本运算：判空、入队、出队（3分） （2）队列中能容纳元素的最多个数是多少？（1分）【东北大学 2002 一、1】 36. 给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR) 【西北大学 2000 二、7 (5分)】

37. 顺序队列一般应该组织成为环状队列的形式，而且一般队列头或尾其中之一应该特殊处理。例如，队列为listarray[0..n-1]，队列头指针为 front，队列尾指针为 rear， 则listarray [rear]表示下一个可以插入队列的位置。请解释其原因。【北京大学 1999 一、3 （20/3分）】

38. 设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学 1999 一、4 （3分）】 39. 若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列： （1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； （2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； （3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。 【山东科技大学 2001 一、3 （6分）】

40. 假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r指向队尾元素，如用A和D分别表示入队和出队操作，请给出： （1） 队空的初始条件; （2） 执行操作序列A3D1A5D2A1D2A4时的状态,并作必要的说明。【北方交通大学 1993 四（12分）】

41、设输入元素为1、2、3、P和A，输入次序为123PA，如图（编者略）。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名。【中山大学 1997】

五 算法设计题

1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。

【哈尔滨工业大学 2001 七 （12分）】 2. 设从键盘输入

一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 【南京航空航天大学 1998 六 （10分）】 3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)

【北京科技大学 2001 九、1 （10分）】

4. 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$

【山东师范大学 1999 七 （10分）】

5. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？

A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。【武汉大学 2000 五、2】 6.设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。【南京邮电大学 2000五】

7. 请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 【西安电子科技大学2001软件五(10分)】【上海交通大学1999 二(12分)【】河海大学1998 三(12分)】

类似本题的另外叙述有：

（1）有两个长度相同的栈S1,S2，已知以下入栈、出栈、判栈满和判栈空操作： PROCEDURE push(Stack:Stacktype;x:Datatype); FUNCTION Pop(Stack:Stacktype ):Datatype; FUNCTION Full (Stack:Stacktype):Boolean; FUNCTION Empty(Stack:Stacktype)Boolean;

现用此二栈构成一个队列，试写出下面入队列、出队列操作算法： PROCEDURE EnQueue(x:Datatype);

FUNCTION DeQueue: Datatype;【北京邮电大学 2000 六（10分）】 8. 设结点结构为(data,link)，试用一个全局指针p和某种链接结构实现一个队列,画出示意图,并给出入队addq和出队deleteq过程,要求它们的时间复杂性都是O(l)（不计new和dispose时

间）

【东南大学 1996 二 （10分）】

9. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。【西安电子科技大学 1999计应用 六 （10分）】

10. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；

（2）写出“从队尾删除”和“从队头插入”的算法。【北方交通大学 1994 三 （12分）】 11. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。【山东科技大学 2002 一、2 （6分）】

12. 双端队列（duque）是一个可以在任一端进行插入和删除的线性表。现采用一个一维数组作为双端队列的数据存储结构，使用类PASCAL语言描述如下： CONST maxsize=32; {数组中可容纳的元素个数} TYPE duque=RECORD

elem: ARRAY[0..MAXSIZE-1] OF datatype; {环形队列的存放数组} end1,end2:0..MAXSIZE; {环形数组的两端} END;

试编写两个算法add(Qu:duque;x:datatype;tag:0..1)和delete（Qu:duque; var x:datatype; tag:0..1）用以在此双端队列的任一端进行插入和删除。当tag=0时在左端endl端操作，当tag=1时在右端end2端操作。【清华大学 1998 二（10分）】 13. 一个双端队列deque是限定在两端end1，end2都可进行插入和删除的线性表。队空条件是end1=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端i（i=1，2）的插入enq和删除deq操作的实现。 （1） 当队满时，最多只能有一个元素空间可以是空的。 （2） 在做两端的插入和删除时，队列中其它元素一律不动。【清华大学 1999 六（12分）】 14. 已知Q是一个非空队列，S是一个空栈。仅用队列和栈的ADT函数和少量工作变量，使用Pascal或C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有： makeEmpty(s:stack); 置空栈

push(s:stack;value:datatype); 新元素value进栈 pop(s:stack):datatype; 出栈，返回栈顶值 isEmpty(s:stack):Boolean; 判栈空否 队列的 ADT函数有：

enqueue(q:queue:value:datatype); 元素value进队 deQueue(q:queue):datatype; 出队列，返回队头值

isEmpty(q:queue):boolean; 判队列空否 【清华大学 2000 六（12分）】

15. 将n个队列顺序映射到数组v[l..m]中，每一队列在v中表示为一循环队列。试画出其示意图并写出对应这种表示的addq和deleteq过程。【东南大学 1993 二（20分）】 16. 设整数序列a1,a2,?,an，给出求解最大值的递归程序。【南京航空航天大学 2000 六】 17．线性表中元素存放在向量A（1,?,n）中，元素是整型数。试写出递归算法求出A中的最大和最小

元素。【北京邮电大学 1994 八 （10分）】

18. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：

第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。

（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五（15分）】 19. 写出和下列递归过程等价的非递归过程。 PROCEDURE test(VAR sum:integer); VAR a:integer, BEGIN read(a);

IF a=0 THEN sum:=1

ELSE BEGIN test(sum); sum:=sum*a；END; write(sum)；

END; 【清华大学 1996 二】

20. 试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)；

if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)；

} 【北京轻工业学院 2000 三 （15分）】 21. 已知Ackermann函数定义如下:

（1） 写出Ack(2,1)的计算过程。

（2） 写出计算Ack(m,n)的非递归算法。 【北京航空航天大学 1999 六 （15分）】 22．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 【合肥工业大学 2000 五、5（8分）】

习题答案 一、选择题

1.B 2.1B 2.2A 2.3B 2.4D 2.5.C 3.B 4.D 5.D 6.C 7.D 8.B

9.D 10.D 11.D 12.C 13.B 14.C 15.B 16.D 17.B 18.B 19.B 20.D 21.D 22.D 23.D 24.C 25.A 26.A 27.D 28.B 29.BD 30.C 31.B 32.C

33.1B 33.2A 33.3C 33.4C 33.5F 34.C 35.C 36.A 37.AD

二、判断题

21、（1）sum=21。当x为局部变量时，每次递归调用，都要给局部变量分配存储单元，故x数值4，9，6和2均保留，其递归过程示意图如下： sum（4） 21

sum（3）+4 （x=4） 17

sum（2）+9 （x=9） 8

sum（1）+6 （x=6） 2

sum（0）+2 （x=2） 0 (2) sum=8,当x为全局变量时，在程序的整个执行期间，x只占一个存储单元，先后读入的4个数(4,9,6,2),仅最后一个起作用。当递归调用结束，逐层返回时sum:=sum(n-1)+x表达式中，x就是2，所以结果为sum=8。

22、设操作数栈是opnd，操作符栈是optr，对算术表达式A-B*C/D-E↑F求值，过程如下：

步骤 opnd栈 optr栈 输入字符 主要操作

初始 #

A-B*C/D-E↑F# PUSH(OPTR,’#’) 1 A #

A-B*C/D-E↑F# PUSH(OPND,A)

2 A # -

-B*C/D-E↑F# PUSH(OPTR,’-’) 3 AB # -

B*C/D-E↑F# PUSH(OPND,B) 4 AB # - *

*C/D-E↑F#

PUSH(OPTR,’*’) 5 ABC # - * C/D-E↑F# PUSH(OPND,C) 6

AT(T=B*C) # - / /D-E↑F#

PUSH(OPND,POP(OPND)*POP(OPND)) PUSH(OPTR,’/’) 7 ATD # - / D-E↑F#

PUSH(OPND,D) 8

AT(T=T/D) T(T=A-T) # - # - -E↑F#

x=POP(OPND);y=POP(OPND)

PUSH(OPND,y/x); x

=POP(OPND);y=POP(OPND); PUSH(OPND,y-x) PUSH(OPTR,’-’) 9 TE # - E↑F#

PUSH(OPND,E) 10 TE # -↑ ↑F#

PUSH(OPTR, ‘↑’) 11 TEF # -↑ F#

PUSH(OPND,F) 12 TE

TS(S=E↑F)

R(R=T-S) #- # #

X=POP(OPND) Y=POP(OPND) POP(OPTR) PUSH(OPND,y↑x) x=POP(OPND) y=POP(OPND) POP(OPTR) PUSH(OPND,y-x)

23、

步骤 栈S1 栈S2

输入的算术表达式（按字符读入）

初始

A-B*C/D+E/F 1 A

A-B*C/D+E/F 2 A -

-B*C/D+E/F 3 AB -

B*C/D+E/F 4 AB -*

*C/D+E/F 5 ABC -*

C/D+E/F 6

AT1（注：T1=B*C）

-/ /D+E/F 7 AT1D -/ D+E/F 8

AT2（注：T2=T1/D） T3 （注：T3=A-T2） - + +E/F 9 T3E + E/F 10 T3E +/ /F 11 T3EF +/ F 12

T3T4（注：T4=E/F） T5（注：T5= T3+ T4） +

24、XSXXXSSSXXSXXSXXSSSS

25、S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。

26、设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top[0]=0，栈S2的栈顶

指针top[1]=m+1，当top[0]=0为左栈空，top[1]=m+1为右栈空；当top[0]=0并且top[1]=m+1时为全栈空。当top[1]-top[0]=1时为栈满。 27、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

（2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。

（3）多个链栈一般不考虑栈的溢出（仅受用户内存空间限制），缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。

28、设top1和top2分别为栈1和2的栈顶指针 （1）入栈主要语句

if(top2-top1==1) {printf(“栈满\\n”); exit(0);} case1:top1++；SPACE[top1]=x; //设x为入栈元素。 case2:top2--；SPACE[top2]=x; 出栈主要语句

case1：if（top1==-1） {printf（“栈空\\n”）；exit（0）；} top1--；return（SPACE[top1+1]）； //返回出栈元素。 case2：if（top2==N）{printf（“栈空\\n”）；exit（0）；} top2++；return（SPACE[top2-1]）； //返回出栈元素。 （2）栈满条件：top2-top1=1

栈空条件：top1=-1并且top2=N //top1=-1为左栈空，top2=N为右栈空 29、设顺序存储队列用一维数组q[m]表示，其中m为

队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front指向队头元素的前一位置，rear指向队尾元素。当front等于-1时队空，rear等于m-1时为队满。由于队列的性质（“删除”在队头而“插入”在队尾），所以当队尾指针rear等于m-1时，若front不等于-1，则队列中仍有空闲单元，所以队列并不是真满。这时若再有入队操作，会造成假“溢出”。其解决办法有二，一是将队列元素向前“平移”（占用0至rear-front-1）；二是将队列看成首尾相连，即循环队列（0..m-1）。在循环队列下，仍定义front=rear时为队空，而判断队满则用两种办法，一是用“牺牲一个单元”，即rear+1=front（准确记是（rear+1）%m=front，m是队列容量）时为队满。另一种解法是“设标记”方法，如设标记tag，tag等于0情况下，若删除时导致front=rear为队空；tag=1情况下，若因插入导致front=rear则为队满。 30、见上题29的解答。 31、参见上面29题。 32、typedef struct node

{elemtype elemcq[m]; //m为队列最大可能的容量。

int front ,rear; //front和rear分别为队头和队尾指针。 }cqnode; cqnode cq;

初始状态

cq.front=cq.rear=0;

队列空

cq.front==cq.rear;

队列满

(cq.rear+1)%m==cq.front;

33、栈的特点是后进先出，队列的特点是先进先出。初始时设栈s1和栈s2均为空。 （1）用栈s1和s2模拟一个队列的输入：设s1和s2容量相等。分以下三种情况讨论：若s1未满，则元素入s1栈；若s1满，s2空，则将s1全部元素退栈，再压栈入s2，之后元素入s1栈；若s1满，s2不空（已有出队列元素），则不能入队。 （2）用栈s1和s2模拟队列出队（删除）：若栈s2不空，退栈，即是队列的出队；若s2为空且s1不空，则将s1栈中全部元素退栈，并依次压入s2中，s2栈顶元素退栈，这就是相当于队列的出队。若栈s1为空并且s2也为空，队列空，不能出队。 （3）判队空 若栈s1为空并且s2也为空，才是队列空。 讨论：s1和s2容量之和是队列的最大容量。其操作是，s1栈满后，全部退栈并压栈入s2（设s1和s2容量相等）。再入栈s1直至s1满。这相当队列元素“入队”完毕。出队时，s2退栈完毕后，s1栈中元素依次退栈到s2，s2退栈完毕，相当于队列中全部元素出队。

在栈s2不空情况下，若要求入队操作，只要s1不满，就可压入s1中。若s1满和s2不空状态下要求队列的入队时，按出错处理。 34、（1）队空s.front=s.rear； //设s是sequeuetp类型变量 （2）队满：（s.rear+1）MOD MAXSIZE=s.front //数组下标为0.. MAXSIZE-1 具体参见本章应用题第29题 35、typedef struct {elemtp q[m];

int front,count; //front是队首指针，count是队列中元素个数。 }cqnode;

//定义类型标识符。

(1)判空：int Empty(cqnode cq) //cq是cqnode类型的变量 {if(cq.count==0) return(1)；else return(0); //空队列} 入队: int EnQueue(cqnode cq，elemtp x)

{if(count==m){printf(“队满\\n”)；exit(0); } cq.q[(cq.front+count)%m]=x; //x入队

count++; return(1); //队列中元素个数增加1,入队成功。 }

出队: int DelQueue(cqnode cq)

{if (count==0){printf(“队空\\n”)；return(0);} printf(“出队元素”，cq.q[cq.front]); x=cq.q[cq.front];

cq.front=(cq.front+1)%m; //计算新的队头指针。 return(x)

}

(2) 队列中能容纳的元素的个数为m。队头指针front指向队头元素。

36、循环队列中元素个数为（REAR-FRONT+N）%N。其中FRONT是队首指针，指向队首元素的前一位置；REAR是队尾指针，指向队尾元素；N是队列最大长度。

37、循环队列解决了用向量表示队列所出现的“假溢出”问题，但同时又出现了如何判断队列的满与空问题。例如：在队列长10的循环队列中，若假定队头指针front指向队头元素的前一位置，而队尾指针指向队尾元素，则front=3，rear=7的情况下，连续出队4个元素，则front==rear为队空；如果连续入队6个元素，则front==rear为队满。如何判断这种情况下的队满与队空，一般采取牺牲一个单元的做法或设标记法。即假设front==rear为队空，而（rear+1）%表长==front为队满，或通过设标记tag。若tag=0，front==rear则为队空；若tag=1，因入队而使得front==rear，则为队满。 本题中队列尾指针rear，指向队尾元素的下一位置,listarray[rear]表示下一个入队的元素。在这种情况下，我们可规定，队头指针front指向队首元素。当front==rear时为队空，当（rear+1）%n=front时为队满。出队操作（在队列不空情况下）队头指针是front=（front+1）%n， 38、既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是dbca。 39、（1）4132 （2）4213 （3）4231 40、（1）队空的初始条件：f=r=0；

（2）执行操作A3后，r=3；// A3表示三次入队操作 执行操作D1后，f=1；//D1表示一次出队操作 执行操作A5后，r=0； 执行操作D2后，f=3； 执行操作A1后，r=1； 执行操作D2后，f=5；

执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。 41．一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。

五、算法设计题

1、[题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。

#define maxsize 两栈共享顺序存储空间所能达到的最多元素数 #define elemtp i

nt //假设元素类型为整型 typedef struct

{elemtp stack[maxsize]; //栈空间 int top[2]; //top为两个栈顶指针 }stk;

stk s; //s是如上定义的结构类型变量，为全局变量。 (1)入栈操作：

int push(int i,int x)

//入栈操作。i为栈号，i=0表示左边的栈s1，i=1表示右边的栈s2，x是入栈元素。入栈成功返回1，否则返回0。

{if(i<0||i>1){printf(“栈号输入不对”);exit(0);} if(s.top[1]-s.top[0]==1) {printf(“栈已满\\n”);return(0);} switch(i)

{case 0: s.stack[++s.top[0]]=x; return(1); break; case 1: s.stack[--s.top[1]]=x; return(1); }

}//push

（2） 退栈操作 elemtp pop(int i)

//退栈算法。i代表栈号，i=0时为s1栈，i=1时为s2栈。退栈成功返回退栈元素，否则返回-1。

{if(i<0 || i>1){printf(“栈号输入错误\\n”)；exit(0);} switch(i)

{case 0: if(s.top[0]==-1) {printf(“栈空\\n”)；return（-1）；} else return(s.stack[s.top[0]--]);

case 1: if(s.top[1]==maxsize {printf(“栈空\\n”); return(-1);} else return(s.stack[s.top[1]++]); }

}//算法结束

[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算。两栈共享空间示意图略，s1栈是通常意义下的栈，而s2栈入栈操作时，其栈顶指针左移（减1），退栈时，栈顶指针右移（加1）。

2、#define maxsize 栈空间容量 void InOutS(int s[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。 {int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。 if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\\n”);exit(0);}else s[++top]=x; //x入栈。 else //读入的整数等于-1时退栈。 {if(top==0){printf(“栈空\\n”);exit(0);} else printf(“出栈元素是%d\\n”,s[top--])；}} }//算法结束。

3、[题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 int EXYX(char E[],int n)

//E[]是有n字符的字符数组，存放字符串表达式，以‘#’结束。本算法判断表达式中圆括号是否匹配。

{char s[30]; //s是一维数组，容量足够大，用作存放括号的栈。 int top=0; //top用作栈顶指针。

s[top]= ‘#’; //‘#’先入栈，用于和表达式结束符号‘#’匹配。 int i=0; //字符数组E的工作指针。

while(E[i]!= ‘#’) //逐字符处理字符表达式的数组。 switch(E[i])

{case‘(’: s[++top]=‘(’; i++ ; break ;

case‘)’: if(s[top]==‘(’{top--; i++; break;} else{printf(“括号不配对”);exit(0);}

case‘#’: if(s[top]==‘#’){printf(“括号配对\\n”);return

(1);}

else {printf(“ 括号不配对\\n”);return (0);} //括号不配对 default : i++; //读入其它字符，不作处理。 }

}//算法结束。

[算法讨论]本题是用栈判断括号匹配的特例：只检查圆括号的配对。一般情况是检查花括号（‘{’，‘}’）、方括号（‘[’，‘]’）和圆括号（‘（’，‘）’）的配对问题。编写算法中如遇左括号（‘{’，‘[’，或‘（’）就压入栈中，如遇右括号（‘}’，‘]’，或‘）’），则与栈顶元素比较，如是与其配对的括号（左花括号，左方括号或左圆括号），则弹出栈顶元素；否则，就结论括号不配对。在读入表达式结束符‘#’时，栈中若应只剩‘#’，表示括号全部配对成功；否则表示括号不匹配。

另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。

4、[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 float expr( )

//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。 ｛float OPND[30]; // OPND是操作数栈。 init(OPND); //两栈初始化。 float num=0.0; //数字初始化。

scanf (“%c”,&x);//x是字符型变量。 while(x!=’$’) {switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);} else //处理小数部分。

{scale=10.0; scanf(“%c”,&x); while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(‘0’)/scale;

scale=scale*10; scanf(“%c”,&x); } }//else

push(OPND,num); num=0.0;//数压入栈，下个数初始化 case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while（x！=‘$’）

printf(“后缀表达式的值为%f”,pop(OPND)); }//算法结束。

[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字

字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。 5、（1）A和D是合法序列，B和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A中。 int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\\n”)；exit(0);} }

i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {printf(“序列非法\\n”)；return(false);} else {printf(“序列合法\\n”)；return(true);} }//算法结束。

[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈

次数（题目中要求栈的初态和终态都为空），否则视为非法序列。 6、[题目分析]表达式中的括号有以下三对：‘（’、‘）’、‘[’、‘]’、‘{’、‘}’，使用栈，当为左括号时入栈，右括号时，若栈顶是其对应的左括号，则退栈，若不是其对应的左括号，则结论为括号不配对。当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对。

int Match(LinkedList la)

//算术表达式存储在以la为头结点的单循环链表中，本算法判断括号是否正确配对 {char s[]; //s为字符栈，容量足够大

p=la->link; //p为工作指针，指向待处理结点 StackInit(s); //初始化栈s

while (p!=la) //循环到头结点为止 {switch (p->ch)

{case ‘(’:push(s,p->ch); break;

case ‘)’:if(StackEmpty(s)||StackGetTop(s)!=‘(’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; case ‘[’:push(s,p->ch); break;

case ‘]’: if(StackEmpty(s)||StackGetTop(s)!=‘[’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; case ‘{’:push(s,p->ch); break;

case ‘}’: if(StackEmpty(s)||StackGetTop(s)!=‘{’)

{printf(“括号不配对\\n”); return(0);} else pop(s);break; } p

=p->link; 后移指针 }//while

if (StackEmpty(s)) {printf(“括号配对\\n”); return(1);} else{printf(“括号不配对\\n”); return(0);} }//算法match结束

[算法讨论]算法中对非括号的字符未加讨论。遇到右括号时，若栈空或栈顶元素不是其对应的左圆（方、花）括号，则结论括号不配对，退出运行。最后，若栈不空，仍结论括号不配对。

7、[题目分析]栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。显然，只有栈s2为空且s1也为空，才算是队列空。 (1) int enqueue(stack s1,elemtp x)

//s1是容量为n的栈，栈中元素类型是elemtp。本算法将x入栈，若入栈成功返回1，否则返回0。

{if(top1==n && !Sempty(s2)) //top1是栈s1的栈顶指针，是全局变量。 {printf(“栈满”);return(0);} //s1满s2非空,这时s1不能再入栈。

if(top1==n && Sempty(s2)) //若s2为空，先将s1退栈,元素再压栈到s2。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);}

PUSH(s1,x); return(1); //x入栈，实现了队列元素的入队。 }

(2) void dequeue(stack s2,s1)

//s2是输出栈，本算法将s2栈顶元素退栈，实现队列元素的出队。 {if(!Sempty(s2)) //栈s2不空，则直接出队。 {POP(s2,x); printf(“出队元素为”,x); } else //处理s2空栈。

if(Sempty(s1)) {printf(“队列空”);exit(0);}//若输入栈也为空，则判定队空。 else //先将栈s1倒入s2中，再作出队操作。 {while(!Sempty(s1)) {POP(s1,x);PUSH(s2,x);} POP(s2,x); //s2退栈相当队列出队。 printf(“出队元素”，x); }

}//结束算法dequue。 (3) int queue_empty()

//本算法判用栈s1和s2模拟的队列是否为空。

{if(Sempty(s1)&&Sempty(s2)) return(1);//队列空。 else return(0); //队列不空。 }

[算法讨论]算法中假定栈s1和栈s2容量相同。出队从栈s2出，当s2为空时，若s1不空，则将s1倒入s2再出栈。入队在s1，当s1满后，若s2空，则将s1倒入s2，之后再入队。因此队列的容量为两栈容量之和。元素从栈s1倒入s2，必须在s2空的情况下才能进行，即在要求出队操作时，若s2空，则不论s1元素多少（只要不空），就要全部倒入s2中。 类似本题叙述的其它题的解答：

该题同上面题本质相同，只有叙述不同，请参考上题答案。

8、[题目分析]本题要求用链接结构实现一个队列，我们可用链表结构来实现。一般说，由于队列的先进先出性质，所以队列常设队头指针和队尾指针。但题目中仅给出一个“全局指针p”，且要求入队和出队操作的时间复杂性是O（1），因此

我们用只设尾指针的循环链表来实现队列。

PROC addq(VAR p:linkedlist,x:elemtp);

//p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法是入队操作。 new(s); //申请新结点。假设有内存空间，否则系统给出出错信息。 s↑.data:=x; s↑.link:=p↑.link;//将s结点入队。 p↑.link:=s; p:=s; //尾指针p移至新的队尾。 ENDP;

PROC deleq(VAR p:linkedlist,VAR x:elemtp);

// p是数据域为data、链域为link的用循环链表表示的队列的尾指针，本算法实现队列元素的出队，若出队成功，返回出队元素，否则给出失败信息。

IF （p↑.link=p）THEN[writeln(“空队列”);return(0);]//带头结点的循环队列。 ELSE[s:=p↑.link↑.link; //找到队头元素。 p↑.link↑.link:=s↑.link; //删队头元素。 x:=s↑.data; //返回出队元素。

IF (p=s) THEN p:=p↑.link; //队列中只有一个结点，出队后成为空队列。 dispose(s); //回收出队元素所占存储空间。 ] ENDP;

[算法讨论]上述入队算法中，因链表结构，一般不必考虑空间溢出问题，算法简单。在出队算法中，首先要判断队列是否为空，另外，对出队元素，要判断是否因出队而成为空队列。否则，可能导致因删除出队结点而将尾指针删掉成为“悬挂变量”。 9、本题与上题本质上相同，现用类C语言编写入队和出队算法。 （1）void EnQueue (LinkedList rear, ElemType x)

// rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。 { s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间 s->data=x; s->next=rear->next; //将s结点链入队尾 rear->next=s; rear=s; //rear指向新队尾 }

（2）void DeQueue (LinkedList rear) // rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。

{ if (rear->next==rear) { printf(“队空\\n”); exit(0);} s=rear->next->next; //s指向队头元素，

rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”，s->data);

if (s==rear) rear=rear->next; //空队列 free(s); } 10、[题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。

（1）#define M 队列可能达到的最大长度 typedef struct { elemtp data[M]; int front,rear; } cycqueue;

（2）elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则给出出错信息。

{ if (Q.front==Q.rear) {printf(“队列空”); exit(0);} Q.rear=(Q.rear-1+M)%M; //

修改队尾指针。

return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束

void enqueue (cycqueue Q, elemtp x)

// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);) Q.data[Q.front]=x; //x 入队列

Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。

11、参见9。

12、[题目分析] 双端队列示意图如下（设maxsize =12） 0 1 2 3 4 5 6 7 8 9 10 11

↑ ↑ end1 end2

用上述一维数组作存储结构，把它看作首尾相接的循环队列。可以在任一端（end1或end2）进行插入或删除。初始状态end1+1=end2被认为是队空状态；end1=end2被认为是队满状态。（左端队列）end1指向队尾元素的前一位置。end2指向（右端队列）队尾元素的后一位置。入队时判队满，出队（删除）时判队空。删除一个元素时，首先查找该元素，然后，从队尾将该元素前的元素依次向后或向前（视end1端或end2端而异）移动。 FUNC add (Qu:deque; var x:datatype;tag 0..1):integer;

//在双端队列Qu中插入元素x，若插入成功，返回插入元素在Qu中的下标；插入失败返回-1。tag=0表示在end1端插入；tag=1表示在end2端插入。 IF Qu.end1=Qu.end2 THEN [writeln(“队满”);return(-1);] CASE tag OF

0: //在end1端插入 [Qu.end1:=x; //插入x

Qu.end1:=(Qu.end1-1) MOD maxsize; //修改end1

RETURN(Qu.end1+1) MOD maxsize); //返回插入元素的下标。 1: //在end2端插入 [Qu.end2:=x;

Qu.end2:=(Qu.end2+1) MOD maxsize; RETURN(Qu.end2-1) MOD maxsize); ]

ENDC; //结束CASE语句 ENDF; //结束算法add

FUNC delete (Qu: deque; VAR x:datatype; tag:0..1):integer;

//本算法在双端队列Qu中删除元素x，tag=0时从end1端删除，tag=1时从end2端删除。删除成功返回1，否则返回0。

IF (Qu.end1+1) MOD maxsize=Qu.end2 THEN [writeln(“队空”);return(0);] CASE tag OF

0: //从end1端删除

[i:=(Qu.end1+1) MOD maxsize; //i是end1端最后插入的元素下标。 WHILE(i<>Qu.end2) AND (Qu.elem[i]<>x) DO i=(i+1) MOD maxsize;//查找被删除元素x的位置 IF (Qu.elem[i]=x) AND (i<>Qu.end2) THEN [ j:=i;

WHILE((j-1+maxsize) MOD maxsize <>Qu.end1) DO [Qu.elem[j]:=Qu.elem[(j-1+maxsize) MOD maxsize]; j:=(j-1+maxsize) MOD maxsize; ]//移动元素，覆盖达到删除

Qu.end1:=(Qu.end1+1) MOD maxsize; //修改end1指针 RETURN(1); ]

ELSE RETURN(0);

]//结束从end1端删除。 1: //从end2端删除

[i:=(Qu.end2-1+maxsize) MOD maxsize; //i是end2端最后插入的元素下标。 WHILE(i<>Qu.end1) AND (Qu.elem[i]<>x) DO i=(i-1+maxsize) MOD maxsize;//查找被删除元素x的下标

IF (Qu.elem[i]=x) AND (i<>Qu.end1) THEN //被删除元素找到 [ j:=i;

WHILE((j+1) MOD maxsize <>Qu.end2) DO [Qu.elem[j]:=Qu.elem[(j+1) MOD maxsize]; j:=(j

+1) MOD maxsize; ]//移动元素，覆盖达到删除

Qu.end2:=(Qu.end2-1+maxsize) MOD maxsize; //修改end2指针

RETURN(1);//返回删除成功的信息 ]

ELSE RETURN(0);//删除失败 ]//结束在end2端删除。 ENDC;//结束CASE语句 ENDF;//结束delete

[算法讨论]请注意下标运算。(i+1) MOD maxsize容易理解，考虑到i-1可能为负的情况，所以求下个i时用了(i-1+maxsize) MOD maxsize。

13、[题目分析] 本题与上面12题基本相同，现用类C语言给出该双端队列的定义。 #define maxsize 32 typedef struct

{datatype elem[maxsize];

int end1,end2; //end1和end2取值范围是0..maxsize-1 } deque;

14、[题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 void Invert(queue Q)

//Q是一个非空队列，本算法利用空栈S和已给的几个栈和队列的ADT函数，将队列Q中的元素逆置。

{makempty(S); //置空栈

while (!isEmpty(Q)) // 队列Q中元素出队

{value=deQueue(Q); push(S,value); }// 将出队元素压入栈中 while(!isEmpty(S)) //栈中元素退栈

{value=pop(S); enQueue(Q,value); }//将出栈元素入队列 Q }//算法invert 结束

15、为运算方便，设数组下标从0开始，即数组v[0..m-1]。设每个循环队列长度（容量）为L，则循环队列的个数为n=ém/Lù。为了指示每个循环队列的队头和队尾，设如下结构类型 typedef struct {int f,r; }scq; scq q[n];

（1）初始化的核心语句

for(i=1;i<=n;i++) q[i].f=q[i].r=(i-1)*L; //q[i]是全局变量 （2）入队 int addq(int i;elemtp x)

//n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将元素插入到第i个循环队列中。若入队成功，返回1，否则返回队满标记0（入队失败）。

{ if (i<1||i>n) {printf(“队列号错误”);exit(0);}

if (q[i].r+1)%L+(i-1)*L==q[i].f) {printf(“队满\\n”);exit(0);} q[i].r=(q[i].r+1)%L+(i-1)*L; // 计算入队位置 v[q[i].r]=x; return(1);//元素x入队 }

（3）出队 int deleteq (int i) // n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将第i个循环队列出队。若出队成功，打印出队列元素，并返回1表示成功；若该循环队列为空，返回0表示出队失败。 {if (<1||>n) {printf(“队列号错误\\n”);exit(0);} if (q[i].r==q[i].f) {printf(“队空\\n”); return(0);} q[i].f=(q[i].f+1)%L+(i-1)*L;

printf(“出队元素”,q[i].f); return(1); }

（4）讨论，上述算法假定最后一个循环队列的长度也是L，否则要对最后一个循环队列作特殊处理。另外，未讨论一个循环队列满而相邻循环队列不满时，需修改个循环队列首尾指针的情况（即各循环队列长度不等）。 n个循环队列共享数组v[0..m-1]的示意图如下： 0 L-1 2L-1 3L-1 (n-1)L-1 ?

第i个循环队列从下标 (i-1)L 开始，到iL-1为止。设每个循环队列均用牺牲一个单元的办法来判断队满，即为（q[i].r+1）%L+(i-1)*L=q[i].f时，判定为队满。 16、int MaxValue (int a[],int n)

//设整数序列存于数组a中，共有n个，本算法求解其最大值。 {if (n==1) max=a[1];

else if a[n]>MaxValue(a,n-1) max=a[n]; else max=MaxValue(a,n-1); return(max); }

17、本题与上题类似，只是这里是同时求n个数中的最大值和最小值的递归算法。 int MinMaxValue(int A[],int n,int *max,int *min)

//一维数组A中存放有n个整型数，本算法递归的求出其中的最小数。 {if (n>0)

{if(*max<A[n]) *max=A[n]; if(*min>A[n]) *min=A[n]; MinMaxValue(A,n-1,max,min); }//算法结束

[算法讨论]调用本算法的格式是MinMaxValue(arr,n,&max,&min);其中，arr是具有n个整数的一维数组，max=-32768是最大数的初值,min=32767是最小数的初值。

18、[题目分析] 求两个正整数m和n的最大公因子，本题叙述的运算方法叫辗转相除法，也称欧几里德定理。其函数定义为： gcd(m,n)=

int gcd (int m,n)

//求正整数m和n的最大公因子的递归算法

{if(m<n) return(gcd(n,m))； //若m<n，则m和n互换 if(n==0) return(m); else return(gcd(n,m%n)); }//算法结束

使用栈，消除递归的非递归算法如下： int gcd(int m,n)

{int s[max][2]; //s是栈，容量max足够大 top=1; s[top][0]=m; s[top][1]=n; while (s[top][1]!=0)

if (s[top][0]<s[top][1]) //若m<n，则交换两数 {t=s[top][0]; s[top][0]=s[top][1]; s[top][1]=t;}

else{t=s[top][0]%s[top][1]; top++; s[top][0]=s[top-1][1]; s[top][1]=t; } return(s[top][0]); }//算法结束

由于是尾递归，可以不使用栈，其非递归算法如下 int gcd (int m,n)

//求正整数m和n的最大公因子

{if (m<n){t=m;m=n;n=t;}// 若m<n，则m和n互换 while (n!=0) {t=m; m=n; n=t%n;} return(m); } //算法结束

19、[题目分析]这是以读入数据的顺序为相反顺序进行累乘问题，可将读入数据放入栈中，到输入结束，将栈中数据退出进行累乘。累乘的初值为1。 PROC test;

CONST maxsize=32;

VAR s:ARRAY[1..maxsize] OF integer, top,sum,a:integer; [top:=0; sum:=1;// read(a);

WHILE a<>0 DO

[top:=top+1; s[top]:=a; read(a); ] write(sum:5); WHILE top>0 DO

[sum:=sum*s[top]; top:=top-1; write(sum:5);] ENDP;

20、[题目分析] 本题与第19题基本相同，不同之处就是求和，另外用C描述。 int test;

{int x,sum=0,top=0,s[]; scanf(“%d”,&x) while (x<>0)

{s[++top]:=a; scanf(“%d”,&x); } printf(sum:5); while (top)

{sum+=s[top--]; printf(sum:5); } };

21、int Ack(int m,n) {if (m==0) return(n+1);

else if(m!=0&&n==0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束

（1）Ack(2,1)的计算过程

Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得 =Ack(1,Ack(1,1)) //因m<>0,n=0而得

=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 =Ack(1,Ack(0,2)) // 因m=0而得 =Ack(1,3) // 因m=0而得

=Ack(0,Ack(1,2)) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得

（2）int Ackerman( int m, int n) {int akm[M][N];int i,j;

for(j=0;j<N;j++) akm[0][j];=j+1; for(i=1;i<m;i++) {akm[i][0]=akm[i-1][1]; for(j=1;j<N;j++)

akm[i][j]=akm[i-1][akm[i][j-1]]; }

return(akm[m][n]); }//算法结束

22、[题目分析]从集合（1..n）中选出k(本题中k=2)个元素，为了避免重复和漏选，可分别求出包括1和不包括1的所有组合。即包括1时，求出集合（2..n）中取出k-1个元素的所有组合；不包括1 时，求出集合（2..n）中取出k个元素的所有组合。，将这两种情况合到一起，就是题目的解。

int A[],n; //设集合已存于数组A中。 void comb(int P[],int i,int k)

//从集合（1..n）中选取k（k<=n）个元素的所有组合

{if (k==0) printf(P);

else if(k<=n) {P[i]=A[i]; comb(P,i+1,k-1); comb(P,i+1,k); }

}//算法结束

本文来源：https://www.bwwdw.com/article/8q93.html