数据结构练习 第三章 栈和队列
数据结构练习第三章栈和队列
一、选择题
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．队列的插入操作是在（）进行。
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；
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指针。
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．允许对队列进行的操作有( )。
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
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;
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______。
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
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,…,a n）,其出栈的次序为(a p1,a p2…,a pn) 现已知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%10
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
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．什么是循环队列？
用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和
队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再入队，然而队列中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。应该指出，除特别说明，循环队列通常是指顺序存储结构，而不是链式存储结构。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塔的移动次数。
设H n为n个盘子的Hanoi塔的移动次数。(假定n个盘子从钢针X移到钢针Z，可借助钢针Y)
则 H n =2H n-1+1
∥先将n-1个盘子从X移到Y，第n个盘子移到Z，再将那n-1个移到Z
=2（2H n-2+1）+1
=22 H n-2+2+1
=22（2H n-3+1）+2+1
=23 H n-3+22+2+1
·
·
·
= 2k H n-k+2k-1 +2k-2 +…+21 +20
=2n-1 H1+2n-2+2n-3+…+21+20
因为H1=1，所以原式H n=2n-1+2n-2+…+21+20=2n-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扫描完毕。
（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的变化过程。
16．简述顺序存储队列的假溢出的避免方法及队列满和空的条件。
设顺序存储队列用一维数组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则为队满。
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作为双端队列的输入序列，试分别求出以下条件的输出序列：
能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序
列。
（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 两栈共享顺序存储空间所能达到的最多元素数
#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)
{case0: if(s.top[0]==-1) {printf(“栈空\n”)；return（-1）；}
else return(s.stack[s.top[0]--]);
case1: 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的工作指针
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);}
}∥算法结束
[算法讨论]在入栈出栈序列（即由‘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); ∥队列不空
}
[算法讨论]算法中假定栈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）
↑↑
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。
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 if(n==0) return(m); else return(gcd(n,m%n)); }∥算法结束 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; 第三章栈和队列习题答案 一、基础知识题 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈) (2)能否得到出栈序列1423和1432并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 链栈中为何不设置头结点 答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 循环队列的优点是什么如何判别它的空和满 答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何若只设尾指针呢答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 指出下述程序段的功能是什么 (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } .. // 设Q1已有内容，Q2已初始化过 while ( ! QueueEmpty( &Q1) ) { x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++) { x=DeQueue(&Q2) ; EnQueue( &Q1, x) ; EnQueue( &Q2, x);} 答： (1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的 第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0); 实验编号：3四川师大《数据结构》实验报告2016年10月29日 实验三栈和队列及其应用_ 一．实验目的及要求 （1）掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们； （2）本实验训练的要点是“栈”的观点及其典型用法； （3）掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。 二．实验内容 （1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； （2）应用栈的基本操作，实现数制转换（任意进制）； （3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）； （4）利用栈实现任一个表达式中的语法检查（括号的匹配）。 （5）利用栈实现表达式的求值。 注：（1）～（3）必做，（4）～（5）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）； A.顺序储存： 代码部分： 栈" << endl; cout << " 2.出栈" << endl; cout << " 3.判栈空" << endl; cout << " 4.返回栈顶部数据" << endl; cout << " 5.栈长" << endl; cout << " 0.退出系统" << endl; cout << "你的选择是：" ; } 链式储存： 代码部分： 栈"< 习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素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 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间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] 6. 执行完下列语句段后，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. 无限递归 7. 表达式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；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front 第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（B ）。【青岛大学 2001】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ② A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③B)。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ C )分别设在这片内存空间的两端,这样,当( ⑤ D )时，才产生上溢。【上海海运学院 1997】【上海海运学院 1999】①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B ）。【中山大学 1999】 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ C ）。【武汉大学 2000】 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2 ,p 3 ，…，p N ,若 p N 是n，则p i 是( C )。【南京理工大学 2001】 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈 序列？（）【北方交通大学 2001】 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.熟悉栈这种特殊线性结构的特性； 2.熟练并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 3.熟练掌握队列在链表存储结构下的基本运算。 实验原理： 堆栈顺序存储结构下的基本算法； 堆栈链式存储结构下的基本算法； 队列顺序存储结构下的基本算法； 队列链式存储结构下的基本算法； 实验内容： 第一题链式堆栈设计。要求 （1）用链式堆栈设计实现堆栈，堆栈的操作集合要求包括：初始化StackInitiate（S）,非空否StackNotEmpty(S)，入栈StackiPush(S,x),出栈StackPop（S,d）,取栈顶数据元素StackTop(S,d); （2）设计一个主函数对链式堆栈进行测试。测试方法为：依次把数据元素1，2，3，4，5入栈，然后出栈并在屏幕上显示出栈的数据元素； （3）定义数据元素的数据类型为如下形式的结构体， Typedef struct { char taskName[10]; int taskNo; }DataType; 首先设计一个包含5个数据元素的测试数据，然后设计一个主函数对链式堆栈进行测试，测试方法为：依次吧5个数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。 第二题对顺序循环队列，常规的设计方法是使用対尾指针和对头指针，对尾指针用于指示当前的対尾位置下标，对头指针用于指示当前的対头位置下标。现要求： （1）设计一个使用对头指针和计数器的顺序循环队列抽象数据类型，其中操作包括：初始化，入队列，出队列，取对头元素和判断队列是否为空； （2）编写主函数进行测试。 程序代码： 第一题： （1）源程序"LinStack.h"如下： #define NULL 0 typedef struct snode { DataType data; struct snode *next; } LSNode; /*（1）初始化StackInitiate(LSNode ** head) */ void StackInitiate(LSNode ** head) /*初始化带头结点链式堆栈*/ 第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data; 栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是n，则pi 是( )。 A. i B. n-i C. n-i+1 D. 不确定 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 7. 设栈的输入序列是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， 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 学号_______ 姓名_______ 班级_______ 成绩_______ 第三章栈和队列习题 一、判断 1.队列中所有地插入操作都发生在表地一端，删除则发生在表地另 一端（） 2.栈具有先进先出地特性（） 3.队列为先进后出地结构（） 4.栈用于实现子程序调用（） 5.栈、队列必须用数组来表示（） 6.队列用于操作系统中地作业调度（） 7.线性表地每个结点只能是一个简单类型，而链表地每个结点可以 是一个复杂类型.（） 8.栈和链表是两种不同地数据结构.（） 9.栈和队列地存储方式既可是顺序方式，也可是链接方式.（） 二、单项选择 1．循环队列用数组A[maxsize] 表示，下面哪个选项表示该循环队列队满 (A) rear==maxsize-1 (B) front==(rear+1)%maxsize (C) rear-front==maxsize (D) rear-front==maxsize-1 2．元素地入栈序列是a,b,c,d，则栈地不可能地输出序列是 (A) dcba (B)abcd (C) dcab (D) cbad 3．在用数组queue[maxsize]仿真队列时(temp为int型变量)，假设队列中至少有一个元素，出队列操作应执行以下 (A) temp=queue[rear]；rear--；(B) rear++； temp=queue[rear]； (C) temp=queue[front]；front--；(D) front++；temp=queue[front]； 4．下列哪种数据结构常用于函数调用 (A) 堆栈 (B) 队列 (C) 链表 (D) 数组 5．编译器中通常以哪种数据结构处理递归程序调用 （A）队列（B）数组（C）堆栈（D）记录 6．下列哪些数据结构可用来实现堆栈 （1）链表（2）数组（3）树（4）图 （A）（2），（3）（B）（2），（4）（C）（1），（4）（D）（1），（2）7．下列哪种数据结构常用于系统程序地作业调度 （A）栈（B）队列（C）链表（D）数组 8．栈和队列地共同点是 （A）都是先进后出（B）都是先进先出 （C）只允许在端点处插入和删除元素（D）没有共同点 9．若已知一个栈地入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为______ 南京信息工程大学实验（实习）报告 实验（实习）名称栈和队列日期2017.11.8 得分指导老师崔萌萌 系计算机系专业软件工程年级2016 班次(1) 姓名学号 一、实验目的 1、学习栈的顺序存储和实现，会进行栈的基本操作 2、掌握递归 3、学习队列的顺序存储、链式存储，会进行队列的基本操作 4、掌握循环队列的表示和基本操作 二、实验内容 1、用栈解决以下问题： （1）对于输入的任意一个非负十进制数，显示输出与其等值的八进制数，写出程序。（2）表达式求值，写出程序。 2、用递归写出以下程序： （1）求n！。 （2）汉诺塔程序，并截图显示3、4、5个盘子的移动步骤,写出移动6个盘子的移动次数。 3、编程实现：（1）创建队列，将asdfghjkl依次入队。（2）将队列asdfghjkl依次出队。 4、编程实现创建一个最多6个元素的循环队列、将ABCDEF依次入队，判断循环队列是否队满。 三、实验步骤 1.栈的使用 1.1 用栈实现进制的转换： 代码如下： #include printf("转换为%d进制： ",radix); while(n) { s.push(n%radix); n /= radix; } while(!s.empty()) { //非空 printf("%d",s.top()); s.pop(); } printf("\n"); return 0; } 运行结果如下： 2.2 求表达式的值 代码如下： #include 第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。 习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 第3章栈和队列练习题答案 一、填空题 1. 线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 二、判断正误 （√）1. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）2. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （×）3. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （√）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）6. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）7. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题 （B）1.栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出 （C）2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为 Ａ．i Ｂ．n-i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （D）3．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 （Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n E：①1 ②2 ③3 ④0 四、阅读理解 1.【严题集3.3②】写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 void main( ){ Stack S; Char x,y; InitStack(S); x=’c’;y=’k’; 《数据结构》课程实验报告 实验名称栈和队列实验序号实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)理解栈和队列的特征以及它们之间的差异，知道在何时使用那种数据结构。 (2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3)重点掌握在顺序队上和链队上实现队列的基本运算算法，注意循环队队列满和队空的条件。 (4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。 二、实验项目摘要 编写一个程序algo3-1.cpp，实现顺序栈的各种基本运算，并在此基础上设计一个主程序并完成如下功能：（1）初始化栈s； （2）判断栈s是否非空； （3）依次进栈元素a,b,c,d,e； （4）判断栈s是否非空； （5）输出栈长度； （6）输出从栈顶到栈底元素； （7）输出出栈序列； （8）判断栈s是否非空； （9）释放栈。 编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算，并在此基础上设计一个主程序并完成如下功能： （1）初始化队列q； （2）判断队列q是否非空； （3）依次进队列a,b,c； （4）出队一个元素，输出该元素； （5）输出队列q的元素个数； （6）依次进队列元素d,e,f； （7）输出队列q的元素个数； （8）输出出队序列； （9）释放队列。 三、实验预习内容 栈的顺序存储结构及其基本运算实现（初始化栈，销毁栈，求栈的长度，判断栈是否为空，进栈，取栈顶元素，显示栈中元素） 队列的顺序存储结构及其基本运算实现（初始化队列，销毁队列，判断队列是否为空，入队列，出队列） 三、实验结果与分析 3-1 #define maxsize 100 #include 第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 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 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,p n，若p1=3,则p2的值。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p n=1,则p i(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base B．S.top!= S.base C．S.top!= S.base+S.stacksize D．S.top= = S.base+S.stacksize 13．判定一个顺序栈S为栈满的条件是。 A．S.top-S.base= =S.stacksize B．S.top= = S.base C．S.top-S.base!=S.stacksize D．S.top!= S.base 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 B．只有表尾指针没有表头指针的循环双链表 C．只有表尾指针没有表头指针的循环单链表 D．只有表头指针没有表尾指针的循环单链表 16．如果以链表作为栈的存储结构，则退链栈操作时。 A．必须判别链栈是否满B．判别链栈元素的类型 C．必须判别链栈是否空D．对链栈不作任何判别 栈和队列 1 简述栈和线性表的区别。 2 简述栈和队列这两种数据结构的相同点和不同点。 3 如果进栈的元素序列为A，B，C，D，则可能得到的出栈序列有多少种？写出全部的可能序列。 4 如果进栈的元素序列为1，2，3，4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。 5 写出下列程序段的运行结果（栈中的元素类型是char）： main( ) { SEQSTACK s,*p; char x, y; p = &s; initstack(p); x = ′c′; y = ′k′; push(p,x); push(p,′a′); push(p,y); x = pop(p); push(p,′t′); push(p,x); x = pop(p); push(p,′s′); while(!empty(p)) { y = pop(p); printf(″%c″,y);} printf(″%c＼n″,x); } 6 将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。 7 写一算法将一顺序栈中的元素依次取出，并打印元素值。 8 设单链表中存放着n个字符，试编一算法，判断该字符串是否有中心对称关系，例如xyzzyx，xyzyx都算是中心对称的字符串。 9 写出下列程序段的运行结果（队列中的元素类型是char）： main( ) { SEQQUEUE a, *q; char x, y; q = &a; x=′e′; y=′c′; initqueue(q); enqueue(q,′h′); enqueue(q,′r′); enqueue(q,y); x = dequeue(q);数据结构第三章栈和队列3习题
栈和队列习题答案
数据结构练习题 第三章 栈、队列和数组 习题及答案
数据结构_实验三_栈和队列及其应用
第三章栈和队列习题_数据结构电子教案
《栈和队列》练习题
数据结构堆栈与队列实验报告
第三章栈和队列练习题
栈和队列答案
栈与队列练习测验题
数据结构栈和队列实验报告.doc
第三章+栈和队列(参考答案)
第3章栈与队列习题参考答案
栈和队列练习题答案
数据结构栈和队列实验报告
数据结构第3章栈与队列习题
《数据结构练习题》栈和队列
- 数据结构-栈和队列-实验
- 数据结构栈和队列实验报告
- 数据结构实验3栈和队列
- 数据结构栈和队列实验报告
- 数据结构堆栈与队列实验报告
- 第三章栈和队列习题_数据结构
- 数据结构详细讲解(栈和队列)
- 数据结构第3章栈和队列
- 数据结构 C语言版 第二版(严蔚敏) 第3章 栈和队列 答案
- 数据结构_实验三_栈和队列及其应用
- 《数据结构》习题集：第3章 栈和队列
- 数据结构_实验三_栈和队列及其应用
- 数据结构之栈和队列应用
- 完整版数据结构习题集第3章栈和队列
- 数据结构(C语言版) 清华大学 严蔚敏 栈和队列
- 数据结构栈和队列实验报告
- 数据结构与算法 栈和队列
- 数据结构栈和队列的应用
- 数据结构--栈和队列 ppt课件
- 数据结构练习 第三章 栈和队列