数据结构练习第三章 栈和队列

一、选择题

1．栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

2．向顺序栈中压入新元素时，应当（ ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 3．允许对队列进行的操作有( )。

A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素 4．用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 5．设用链表作为栈的存储结构则退栈操作（ ）。 A. 必须判别栈是否为满 B. 必须判别栈是否为空 C. 判别栈元素的类型 D.对栈不作任何判别

6．设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的

队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ ）。 A.front->next=s；front=s； B. s->next=rear；rear=s； C. rear->next=s；rear=s； D. s->next=front；front=s； 7．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 A.top=top+1; B. top=top-1; C. top->next=top; D. top=top->next; 8．队列是一种（ ）的线性表。

A. 先进先出 B. 先进后出 C. 只能插入 D. 只能删除

9．设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。

A. n-i B. n-1-i C. n+l -i D.不能确定

10．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。

A. 5，3，4，6，1，2 B. 3，2，5，6，4，1 C. 3，1，2，5，4，6 D. 1，5，4，6，2，3 11．队列的删除操作是在（ ）进行。

A．队首 B．队尾 C．队前 D．队后

12．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。

A．top++; B．top=0; C．top--; D．top=N; 13．队列的插入操作是在（ ）进行。

1

A．队首 B．队尾 C．队前 D．队后 14．若已有一个栈，输入序列为A，B，C，D，E，那么下面哪种序列不可能得到？（ ）

A．ABCDE B．EDCBA C．BAEDC D．ECDBA (d) 注意: 入栈和出栈操作可以交替进行，因此就可能有多种输出序列了。 15．栈和队列共同具有的特点是（ ） A.都是先进后出 B.都是先进先出

C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出

16．若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（ ）

A.1和5 B.2和4 C.4和2 D.5和1 17．一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( ) ．．．A. dceab B. decba C. edcba D. abcde 18．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A. top=top B. top=n-1 C. top=top-1 D. top=top+1 19．设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB

20．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( )

A.top++ B.top-- C.top不变 D.top=0 21. 关于栈和队列的说法中正确的是（ ） A．栈和队列都是线性结构

B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构

22. 设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（ ） A．a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b

23. 在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ） A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front 24. 循环队列存储在数组A[0..m]中，则入队时的操作为( D)。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)

25. 顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（ ） A.s.elem［top］=e； B.s.elem［top+1］=e； s.top=s.top+1； s.top=s.top+1； C.s.top=s.top+1； D.s.top=s.top+1； s.elem［top+1］=e； s.elem［top］=e；

2

26. 循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（ ）

A.8 B.16 C.17 D.18 27. 有关栈的描述，正确的是（ ） A.栈是一种先进先出的特殊的线性表 B.只能从栈顶执行插入、删除操作

C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作

28. 设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ）。

A. R-F B. F-R C. (R-F+M)％M D. (F-R+M)％M 29. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为（ ）。

A．3,2,5,6,4,1 B．1,5,4,6,2,3

C．2,4,3,5,1,6 D．4,5,3,6,2,1

30. 设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。

A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A

31．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。

A．front== rear B．(rear+1)%MAXSIZE==front C．front-rear==1 D．rear%MAXSIZE==front 32．一个元素进入队列的时间复杂度是（ ）。

A．O(1) B．O(n) C．O(n2) D．O(log2n)

33．若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 A.3，2，1 B.2，1，3 C.3，1，2 D.1，3，2

34．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ ）。

A.front==NULL B.front!=NULL C.rear!=NULL D.front==rear

35．若让元素a，b，c依次进栈，则出栈次序不可能出现（ ）种情况。 A．cba B．bac C．cab D．acb

36．在一个链队列中，假定front和rear分别为队头和队尾指针，则插入*s结点的操作应执行（ ）。

A．front->next=s; front=s; B．s->next=rear; rear=s; C． rear->next=s; rear=s; D．s->next=front; front=s; 37．栈的插入与删除操作在（ ）进行。

A.栈顶 B.栈底 C.任意位置 D.指定位置

38．当利用大小为N的一维数组顺序存储一个栈时，假定用top=－1表示栈空，则向这个栈插入一个元素时，首先应执行（ ）语句修改top指针。

3

A．top++； B．top--； C．top=NULL ； D．top； 39．当采用顺序存储方式存储队列时，可能出现存储空间剩余，而不允许继续入队的情况，称为（ ）。

A．溢出 B． 假溢出 C．队列不能用顺序存储方式 D．数组存储空间过小 40．当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为（ ）。

A.N-2 B.N-1 C.N D.N+1 41．从一个循环顺序队列删除元素时，首先需要（ ）。 A.前移一位队首指针 B.后移一位队首指针

C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 42．循环队列存储在数组A[0..m]中，则入队时的操作为( )。 A. rear=rear+1 B. rear=(rear+1) % (m-1) C. rear=(rear+1) % m D. rear=(rear+1) % (m+1) 43．4个园盘的Hahoi塔，总的移动次数为( )。

A.7 B. 8 C.15 D.16 44．对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

45．有六个元素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 46．设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 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，

47．如进栈序列1，2，3，4，5。可能得到的出栈序列为( )

A．1,2,5,3,4 B．3,1,2,5,4 C．3,2,5,4,1 D．1,4,2,3,5 E．都不可能

48．一个栈的入栈序列为A,B,C,D,E，则栈的不可能的出栈序列是( )。 A. ABCDE B. EDCBA C. DECBA D.DCEAB 49．function calc(x,y :integer) : integer; begin

if y=1 then calc :=x

else calc := calc (x,y-1)+x end;

a,b均为正整数，则 calc(a,b)=( )

A.a*(b-1) B. a*b C. a+b D. a+a 50．执行完下列语句段后，i值为：（ ）。 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. 无限递归 51．表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 52．允许对队列进行的操作有( )。

4

A. 对队列中的元素排序 B. 取出最近进队的元素 C. 在队头元素之前插入元素 D. 删除队头元素

53．用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时( )

A．仅修改队头指针 B.仅修改队尾指针

C．队头，队尾指针都可能要修改 D.队头，队尾指针都要修改 54．对于循环队列( )。

A. 无法判断队列是否为空 B. 无法判断队列是否为满 C. 队列不可能满 D. 以上说法都不是

55．循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。

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

56．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1 57．栈和队的共同点是( )。

A. 都是先进后出 B. 都是后进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

58．设栈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 59．4个园盘的Hahoi塔，总的移动次数为( ).

A.7 B.-8 C.15 D.16 60．和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 61．执行（ ）操作时，需要使用队列作辅助存储空间。

A. 查找哈希(Hash)表 B. 广度优先搜索网 C. 先序(根)遍历二叉树 D. 深度优先搜索网

62．设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（ A ）

A.a3,a1,a4,a2 B. a3,a2,a4,a1 C. a3,a4,a2,a1 D. a4,a3,a2,a1 a1 a2 Top a3

63．在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ B）

A.f->next=s;f=s; B.r->next=s;r=s; C.s->next=r;r=s; D.s->next=f;f=s;

5

64．若用一个大小为6的数组来实现循环队列，且当rear和front的值分别是0和3。

当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别是（A ） A. 2和4 B. 1和5 C. 4和2 D. 5和1

65．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）

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

二、填空题

1．后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为___________________________。-1，3 4 X * + 2 Y * 3 / - 2．下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct {int s[100]; int top;} sqstack;

void push(sqstack &stack,int x) {

if (stack.top==m-1) printf(“overflow”);

else {____________________;_________________;} } stack.top++，stack.s[stack.top]=x

3．设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。5

4．不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。O(1)

5．设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。m-1，(R-F+M)%M

6．设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。top1+1=top2

7．栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。FILO，FIFO

8．设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。m-1

9．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。F==R

10．从一个栈删除元素时，首先取出 ，然后再前移一位 。栈顶元素、栈顶指针

11．后缀表达式“2 10 + 5 * 6 – 9 /”的值为 。6

12．中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。3 x 2.4 5 ／6 －*＋

13．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为__SXSSXSXX______。

6

14．在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为__front=rear______。

15．对于栈只能在___栈顶位置_____插入和删除元素。

16．设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为__DCBA_____________。 17．队列中允许进行删除的一端为____队头___________。

18．我们通常把队列中允许插入的一端称为________队尾________。 19．队列的原则是 。先进先出；

20．顺序存储的队列如果不采用循环方式，则会出现 问题。假溢出 21．栈的原则是 。先进后出。

22．对于一个顺序栈作进栈运算时，应先判断栈是否为 ，判断的条件是 ，作出栈运算时，应先判断栈是否为 ，判断的条件是 。满 ;top==MAXSIZE-1 ;空 ;top==-1。

23．在长度为Maxsize的循环队列中，删除一个新元素，修改front队头指针为 。front=(front+1)/Maxsize

24．在链队列中，与入队相关的指针是 、与出队有关的指针是 （头指针或尾指针）。尾指针 、 头指针

25．当用长度为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为 。top = = 0

26．向一个栈顶指针为HS的链栈中插入一个新结点*P果，应执行 和 操作。p->next = HS 、HS = p

27．从一个栈顶指针为HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结点时，应执行 操作。HS = HS->next

28．假定front和rear分别为一个链队的队首和队尾指针，则该链队中只有一个结点的条件为 。( front = = rear ) && ( front <>NULL )

29．中缀算术表达式3+4/(25-(6+15))*8 所对应的后缀算术表达式为 。3 4 25 6 15 + - / 8 * + 30．后缀算术表达式24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为 ，值为 。(24+8)*3/(4*(10-7)) 、8

31．在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top=_____。 top-1

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

为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。 (1)满 (2)空 (3)n (4)栈底 (5)两栈顶指针相邻（即值之差的绝对值为1） 33．多个栈共存时，最好用_______作为存储结构。链式存储结构

34．顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是_______。if(top!=n) data[++top]=x；

35．循环队列的引入，目的是为了克服_______。假溢出时大量移动数据元素。 36．设a=6, b=4, c=2, d=3, e=2, 则后缀表达式abc-/de*+的值为____。9

7

37．在循环队列中，队列长度为n ,存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。 rear=(rear+1)%n

38．已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 s=(LNode *)malloc(sizeof(Lnode))；

s->data=x;s->next=r->next；r->next=s；r=s；

39．区分循环队列的满与空，只有两种方法，它们是______和______。 牺牲一个存储单元 设标记

40．已知一循环队列的存储空间为[m..n]，其中n＞m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是( ) (rear+1)%(n-m+1)==front 41．设有元素序列的入栈次序为：（a1,a2,?,an）,其出栈的次序为(ap1,ap2?,apn) 现已知pl=n,则pi=____。n-i+1

42．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 ____和____；若只设尾指针，则出队和入队的时间复杂度分别是____和____。O(1),O(n),O(1),O(1)

43．下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： #include

void convert(char *a, int n) { int i;

if(i=n/10) convert(______,i); *a=__________; }

main()

{int number; char str[10]=””; scanf(“%d”,&number);

convert(str,number); puts(str); } a+1 n

44．写出下面程序的运行结果 program priout(input，output); procedure print(f1,f2:integer); var f3:integer;

begin if fl<=f2 then

begin if f2 mod fl=0 then f3:=f1+1 else f3:=f1+3； print(f3,f2-1); end

writeln(fl,’’,f2); end

begin print (4,16); end.

(13 11),(12 12),(9 13),(6 14),(5 15),(4 16) ∥输出每组两个数占一行，也没括号

三、判断题

1．（ ）不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。T

8

2．（ ）在循环顺序队列中插入新元素不需要判断队列是否满了。× 3．( )入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。T 4．（ ）栈是一种先进后出的线性表。 √ 5．（ ）消除递归不一定需要使用栈。√

6．（ ）栈是实现过程和函数等子程序所必需的结构。√ 7．（ ）设栈采用顺序存贮结构。若已有i-1 个元素进栈，则将第i个元素进栈时，进栈算法的时间复杂性为O(i)。× 8．（ ）在链队列中，即使不设置尾指针也能进行入队操作。√ 9．（ ）设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。√

10．（ ）栈和队列都是线性表，只是在插入和删除时受到了一些限制。√ 11．（ ）队列在程序调用时必不可少，因此递归离不开队列。×

12．( ) 栈可以作为实现程序设计语言过程调用时的一种数据结构√。 13．（ ）栈又称后进先出表，队列又称为先进先出表。√ 14．（ ）栈和队列都是限制存取点的线性结构。√ 四、简答题

1．简述栈和队列的共同点和不同点。它们与线性表有什么关系？ 2．在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的办法采用循环队列。

3．简述栈和队列这两种数据结构的相同点和不同点。

栈和队列都是操作受限的线性表。栈是先进后出，操作在一端进行；队列是先进先出，插入在一端，删除在另一端进行。

4．如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 ABC；CBA；ACB

5．如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。

DCFEBA可以：

push(A),push(B),push(C),push(D),pop(D),pop(C),pust(E)., Push(F),pop(F),pop(E),pop(B),pop(A)

EDBFCA：根据入栈顺序B不能在C前面出栈。 6．什么是循环队列？

用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和

9

队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。 7．有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列中，第一个出栈元素为C且第二个出栈元素为D的出栈序列有哪几个？ 三个：CDEBA，CDBEA，CDBAE

8．简述递归思想。现有两个正整数M和N，如果采用递归方法解决M×N运算，试结合递归思想，说明其终止条件和递归语句是什么？

递归是程序设计中的重要技术。利用递归技术编写的程序结构清晰、易读、且其正确性容易证明。当问题的定义是递归的、数据结构是递归的和问题的解法是递归的时，最好利用递归。求解递归问题时，要先写出问题求解的递归定义。递归定义由基本项和归纳项组成。基本项描述了一个或几个递归过程的终结状态，即不需要继续递归就可直接求解的状态。归纳项描述了从当前状态向终结状态的转换。递归过程的实质是将复杂问题分解成若干子问题，子问题与原问题具有相同特征，但是简单了。子问题解决了，原问题迎刃而解。

本题求解两个整数M和N相乘，可以利用递归技术变为M个N相加。基本项是M=1,归纳项是(M-1)个N相乘。其递归过程如下： long MultiToAdd(int m,int n) ∥用递归算法求m*n {if(m==1) return (n);

else return (MultiToAdd(m-1,n)+n); }

9．设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。

n个元素的排列有n!种，但借助栈结构，n个入栈元素只可得到1/(n+1)((2n)！/（n!*n!）)种出栈序列，这个数小于n!。本题4个元素，可有14种出栈序列，abcd和dcba就是其中两种；有10(4!-14=10)种排列得不到，其中，dabc和adbc是不可能得到的两种。

10．队列可以用循环单链表来实现，故可以只设置一个头指针或者只设置一个尾指针。请你分析对于循环单链表实现的队列，用哪种方案更合适。

循环单链表若只设头指针，则出队操作时间复杂度是O(1)，而入队操作时间复杂度是O(n)；若只设尾指针，则出队和入队操作时间复杂度都是O(1)。 11．试推导出当总盘数为n的Hanoi塔的移动次数。

设Hn为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y) 则 Hn =2Hn-1+1

∥先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z =2（2Hn-2+1）+1

2

=2 Hn-2+2+1

=22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 · ·

10

·

kk-1k-210

= 2 Hn-k+2 +2 +?+2 +2

=2n-1 H1+2n-2+2n-3+?+21+20

n-1n-210n

因为H1=1，所以原式Hn=2+2+?+2+2=2-1 故总盘数为n的Hanoi塔的移动次数是2n-1。

12． 用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C或PASCAL设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。 两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为-1，另一个栈顶指针为MAX时，栈为空。

用C写的入栈操作push（i，x）如下： const MAX=共享栈可能达到的最大容量 typedef struct node {elemtype s[MAX]； int top[2]； }anode； anode ds;

int push(int I,elemtype x)

∥ds为容量有MAX个类型为elemtype的元素的一维数组，由两个栈共享其空间。I的值为0或1

∥x为类型为elemtype的元素。本算法将x压入栈中。如压栈成功，返回1；否则，返回0

{if（ds.top[1]-ds.top[0]==1）{printf（“栈满\\n”）；return（0）；} switch（i）

{case 0：ds.s[++ds.top[i]]=x；break； case 1：ds.s[--ds.top[i]]=x； return（1）；∥入栈成功 } }

13．用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。

中缀表达式8-(3+5)*(5-6/2)的后缀表达式是： 8 3 5 + 5 6 2 / - * - 栈的变化过程图略，表达式生成过程为：

中缀表达式exp1转为后缀表达式exp2的规则如下：

设操作符栈s，初始化为空栈，压入优先级最低的操作符‘#’。对中缀表达式从左向右扫描，遇操作数，直接写入exp2；若是操作符（记为w），分如下情况处理，直至表达式exp1扫描完毕。

11

（1）w为一般操作符（’+’，’-‘，’*’，’/’等），要与栈顶操作符比较优先级，若w优先级高于栈顶操作符，则入栈；否则，栈顶运算符退栈到exp2，w再与新栈顶操作符作上述比较处理，直至w入栈。 （2）w为左括号（’（’），w入栈。

（3）w为右括号（’）’），操作符栈退栈并进入exp2，直到碰到左括号为止，左括号退栈（不能进入exp2），右括号也丢掉，达到exp2中消除括号的目的。 （4）w为‘#’，表示中缀表达式exp1结束，操作符栈退栈到exp2，直至碰到‘#’，退栈，整个操作结束。

14．有字符串次序为3*-y-a/y^2,利用栈，给出将次序改为3y-*ay2^/-的操作步骤。（可用X代表扫描该字符串过程中顺序取一个字符进栈的操作，用S代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为BCA的操作步骤为XXSXSS）

XSXXXSSSXXSXXSXXSSSS

15．计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式： A-B*C/D+E/F。写出栈S1和S2的变化过程。

步骤 栈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） ?- +E/F? T3 （注：T3=A-T2） ?+ 9 T3E ?+ E/F? 10 T3E ?+/ /F? 11 T3EF ?+/ F? 12 T3T4（注：T4=E/F） ?+ ? T5（注：T5= T3+ T4） ?

16．简述顺序存储队列的假溢出的避免方法及队列满和空的条件。

设顺序存储队列用一维数组q[m]表示，其中m为队列中元素个数，队列中元素在向量中的下标从0到m-1。设队头指针为front，队尾指针是rear，约定front

12

指向队头元素的前一位置，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则为队满。

17．如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 编写实现队列的三个基本运算：判空、入队、出队（3分） 队列中能容纳元素的最多个数是多少？（1分） typedef struct {ElemType 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，ElemType 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指向队头元素。

18．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR)

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

19．若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：

能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列； 既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序

13

列。

（1）4132 （2）4213 （3）4231 五、应用题

1．已知一个中缀算术表达式为： 3+4*(25-(6/15))-8@ ，写出对应的后缀算术表达式。

后缀算术表达式：3 4 25 6 15 / － * ＋ 8 － @

2．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分） （1） d,e,b入队 （2） d,e出队 （3） i,j入队 （4） b出队 （5）n,o,p入队

六、程序填空题（或算法阅读题） 1．void exam1(SeqStack S, int m) { SeqStack T; int i； IniStack(T);

while(!Stackempty (S))

if ((i=pop(S))!=m) push(T,i); while (!Stackempty(T))

{ i=pop（T）; push(S,i); } } //exam1

程序段1 的功能是将一个非空栈中值等于m的元素全部删除；（根据答题情况酌情给分）

七、算法设计题 1． 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。【哈尔滨工业大学 2001 七 （12分）】 [题目分析]两栈共享向量空间，将两栈栈底设在向量两端，初始时，s1栈顶指针为-1，s2栈顶为maxsize。两栈顶指针相邻时为栈满。两栈顶相向，迎面增长，栈顶指针指向栈顶元素。

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

14

#define ElemType int ∥假设元素类型为整型 typedef struct

{ElemType 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(“栈号输入不对\\n”);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）退栈操作

ElemType 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]++]); }∥switch }∥算法结束

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

2．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 【北京科技大学 2001 九.1 （10分）】 [题目分析]判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。 Int EXYX(char E[],int n)

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

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

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

15

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

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

case‘#’: if(s[top]==‘#’){printf(“括号配对\\n”);return (1);} else {printf(“ 括号不配对\\n”);return (0);} ∥括号不配对 default : i++; ∥读入其它字符，不作处理 }∥switch }∥算法结束。

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

另外，由于本题只是检查括号是否匹配，故对从表达式中读入的不是括号的那些字符，一律未作处理。再有，假设栈容量足够大，因此入栈时未判断溢出。 3．假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（1） 下面所示的序列中哪些是合法的？

1. A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2） 通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

【武汉大学 2000 五.2(12分)】

（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);} }∥算法结束

16

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

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

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

(1) int enqueue(stack s1,ElemType x)

∥s1是容量为n的栈，栈中元素类型是ElemType。本算法将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入栈，实现了队列元素的入队 }

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 int queue_empty()

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

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

17

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

5．编程：假设以数组Q[m]存放循环队列中的元素，同时以rear 和 length 分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件，并写出相应的初始化(initqueue), 插入(enqueue)和删除(dlqueue)元素的操作。

【天津大学2002一.5(10分)】

6. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。【山东科技大学 2002 一.2 （6分）】

7. 双端队列（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分）】

[题目分析] 双端队列示意图如下（设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

18

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端删除

19

ENDC;∥结束CASE语句 ENDF;∥结束delete

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

8. 已知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分）】

[题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 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 结束

9. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。 将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。

写出求解该递归函数的非递归算法。【北京航空航天大学 2001 五（15分）】 [题目分析] 求两个正整数m和n的最大公因子，本题叙述的运算方法叫辗转相除法，也称欧几里德定理。其函数定义为： gcd(m,n)= int gcd (int m,n)

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

{if(m

20

使用栈，消除递归的非递归算法如下： 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]

{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

10. 设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。

【合肥工业大学 2000 五.5（8分）】

[题目分析]从集合（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); } }∥算法结束

11. 对于任意的无符号的十进制整数m,写出将其转换为十六进制整数的算法（转换仅要求能够输出正确的十六进制的整数即可。）【兰州大学2000九(10分)】

[题目分析]十进制整数m转换为十六进制整数，进行如下操作：将m被16除，余数是一位十六进制数，将m被16除的商做新的m,继续以上运算，直至商等于0为止。应注意整数10至15，在十六进制中是A至F。 void convert(unsigned int m)

∥本算法将无符号十进制整数m转换为十六进制整数 {while(m/16) {n=m; switch(n)

21

{case 0:case 1: case 2:case 3: case 4:case 5: case 6:case 7: case 8:case 9: printf(“%c”,n+48); break;

case 10: case 11: case 12:case 13: case 14:case 15: printf(“%c”,n+55); }; m=m/16; }; printf(“\\n”); }

本算法的递归描述如下：

void convert(unsigned int m)

∥本算法将无符号十进制整数m转换为十六进制整数 {if(m)

{n=m; switch(n)

{case 0:case 1: case 2:case 3: case 4:case 5: case 6:case 7: case 8:case 9: printf(“%c”,n+48); break;

case 10: case 11: case 12:case 13: case 14:case 15: printf(“%c”,n+55); }

convert(m/16); }//if }//end

12. 已知递归函数F(m)（其中DIV为整除）；

(1) 写出求F(m)递归算法；

(2) 写出求F(m)的非递归算法。【北京师范大学2003五.3(15分)】 递归算法如下：

void recurse(int m, int &s) {if(m<0) return ERROR; if(m==0) s=1;

else {f_recurse(m/2,r); s=m*r; } }

非递归算法如下：

void nonrecure(int m,int &s) {if(m<0) return ERROR; if(m==0) s=1;

else{StackInit(sa);

while(m!=0){a=m;b=m/2; push(sa,{a,b}); m=b; } s=1;

while(!StackEmpty(sa)){pop(sa,t); s=s*t.a; } }//else }//结束

13. 已知有n个元素存放在向量S[1..n]中，其值各不相同，请写一递归算法，生成并输出n个元素的全排列。【中国科学技术大学1992十三(20分)】 【苏州大学2005五(15分)】

[题目分析]n个元素的全排列有n!种。因n!=n*(n-1)! ，而(n-1)!=(n-1)*(n-2)!，故对n个元素，可放到n 个不同位置上，让第一个位置

22

依次取每一个元素，共n种取法，对其后的n-1个位置上的n-1个元素共有(n-1)!种不同排列，??，以此类推，直至第n个位置，将最后一个元素放在此位置上。 利用数组S[n]保存1—n之间的n个自然数，对于i=0到i=n-1，每次使S[0]同S[i]交换(i=0,1,2,?,n-1)后,对S[1]—S[n-1]中的n-1个元素进行全排列，然后再交换其值，使它恢复为此次排列前的状态。

Void Permute(int S[], int j,int n)

∥对S[j]――S[n-1]中的n-j个元素进行全排列，j的初值为0 {int I,temp; if(j==n-1)

{for(i=0;i

for(i=j;i

{temp=S[j]; S[j]=S[i]; S[i]=temp; Permute(S,j+1,n);

temp=S[j]; S[j]=S[i]; S[i]=temp;} }

23