1、1/15 第 3 章 栈和队列 一、 选择题 1. 栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2. 设栈ST 用顺序存储结构表示，则栈 ST 为空的条件是（ B ） A、ST.top-ST.base0 B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n 3. 向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS-next=s; B、s-next=HS-next；HS-next=s; C、s-next=H
2、S；HS=s; D、s-next=HS；HS=HS-next; 4. 从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS ；HS=HS-next; B 、HS=HS-next；x=HS-data; C 、x=HS-data；HS=HS-next; D 、s-next=Hs ；Hs=HS-next; 5. 表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6. 中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C
3、、ABCD/E*+- D、ABCD/+E*- 7. 一个队列的入列序列是1，2，3，4， 则队列的输出序列是（ B ） A、4，3，2，1 B、1， 2，3，4 C、1，4，3，2 D、3，2，4，1 8. 循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为空的条件是（ ） A、Q.rear-Q.front=n B、Q.rear-Q.front-1=n C、Q.front=Q.rear D、Q.front=Q.rear+1 9. 循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是fr
4、ont 和rear，则判定此循环队 列为满的条件是（ ） A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素， 再加入两个元素后，rear 和front 的值分别为（ ） A、1，5 B、2, 4 C、4，2 D、5，1 11. 用单链表表示的链式队列的队头在链表的（ ）位置 A、链头 B、链尾 C、链中 12. 判定一个链队列Q（最多元素为 n 个）为空的条件是
5、（ ） A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13. 在链队列Q 中，插入s 所指结点需顺序执行的指令是（ ） A 、Q.front-next=s；f=s; B 、Q.rear-next=s；Q.rear=s; C 、s-next=Q.rear；Q.rear=s; D 、s-next=Q.front；Q.front=s; 14. 在一个链队列Q 中，删除一个结点需要执行的指令是（ ） A、Q.rear=Q.front-next; B、Q.rear-next=Q.rear
6、-next-next; C、Q.front-next=Q.front-next-next; D、Q.front=Q.rear-next; 2/15 15. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时 （ ） A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16. 栈和队列的共同点是（ ） A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 17. 消除递归（ ）需要使用栈。 A、一定 B、不一定 18. 设有一顺序栈S，元素s1，s2，s3 ，s4，s5，s6 依
7、次进栈，如果 6 个元素出栈的顺序是 s2，s3 ，s4 ，s6 ，s5，s1 ，则栈的容量至少应该是（ ） A、2 B、3 C、 5 D、 6 19. 若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为（ ） A、 4 B、 5 C、 6 D、 7 20. 设有一顺序栈已经含有3 个元素，如图3.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是（ ） A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1 图3.1 21. 链栈和顺序栈相比，有一个比较明显的优势是（ ） A、通常不会出现
8、栈满的情况 B、通常不会出现栈空的情况 C、插入操作更容易实现 D、删除操作更加容易实现 22. 若一个栈的输入序列是1，2，3，4，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ） A、不确定 B、 n-i C、 n-i+1 D、n-i-1 23. 以下说法正确的是( ) A、因链栈本身没有容量限制 ,故在用户内存空间的范围内不会出现栈满情况 B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 C、对于链栈而言,在栈满状态下 ,如果此时再作进栈运算，则会发生“上溢” D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。 二、 判断题 1. 在
9、顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 2. 链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。 3. 若一个栈的输入序列为 1，2，3，n，其输出序列的第一个元素为 n，则其输出序列的每个元素一定满足 ai=i+1(i=1,2, ,n)。 4. 在链队列中，即使不设置尾指针也能进行入队操作。 5. 在对链队列（带头指针）做出队操作时，不会改变 front 指针的值。 6. 循环队列中元素个数为 rear-front。 7. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得到 4,3,1,2。 8. 一个栈的输入序列是 1,2,3,4，则在栈的输出序列中可以得
10、到 1,2,3,4。 9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。 3/15 10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。 三、 填空题 1. 栈的特点是（先进后出 ），队列的特点是（ 先进先出 ）。 2. 线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插 入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。 3. 有程序如下，则此程序的输出结果（栈的元素类型是 SelemType 为 char）是（ ）。 void main() stack s; char x,y; initstack (s); x=c; y
11、=k; push(s,x); push(s,a); push(s,y); pop(s,x); push(s,t); push(s,x); pop(s,x); push(s,s); while(!stackempty(s) pop(s,y); printf(y); printf(x); 4. 在栈顶指针为 HS 的链栈中，判定栈空的条件是（ ）。 5. 向栈中压入元素的操作是先（ ）后（ ）。 6. 对栈进行退栈操作是先（ ）后（ ）。 7. 用循环链表表示的队列长度为 n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只 设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。
12、 8. 从循环队列中删除一个元素时，其操作是（ ）。 9. 在一个循环队列中，队首指针指向队首元素的（ ）。 10. 在具有 n 个单元的循环队列中，队满时共有（ ）个元素。 11. 在 HQ 的链队列中，判断只有一个结点的条件是（ ）。 12. 设栈 S 和队列 Q 的初始状态为空，元素 a、b、c、d、e、f 依次通过栈 S，一个元素出栈后即进入队列 Q。若 这 6 个元素出队列的顺序是 b、d、c、f、e、a 则栈 S 的容量至少应该是（ ）。 13. 有程序如下，则此程序的输出结果（队列的元素类型是 QSelemType 为 char）是（ ）。 void main() char x=
13、e,y=c; enqueue(q,h);enqueue(q,r);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x); enqueue(q,a); while(!queueempty(q) dequeue(q,y);printf(y); 4/15 printf(x); 14. 有如下递归函数： int dunno(int m) int value; if(m=0) value=3; else value=dunno(m-1)+5; return(value); 执行语句 printf(“%dn”,dunno(3);的结果是（ ）。 四、 简答
14、题 1. 对于堆栈，给出三个输入项 A，B，C，如果输入项序列为 ABC，试给出全部可能的输出序列，并写 出每种序列对应的操作。例如：A 进 B 进 C 进 C 出 B 出 A 出，产生的序列为 CBA。 2. 简述以下算法的功能（栈的元素类型是 SelemType 为 int）。 （1 ） status algo1(stack s) int I,n,a255; n=0; while(!stackempty(s) n+; pop(s,an); for(I=1;Irear = Q-rear-next;/将队尾指针指向头结点 while (Q-rear!=Q-rear-next)/当队列非空，将队
15、中元素逐个出队 s=Q-rear-next; Q-rear-next=s-next; free(s); /回收结点空间 (2)判队空 int EmptyQueue( LinkQueue *Q) /判队空 /当头结点的 next 指针指向自己时为空队 return Q-rear-next-next=Q-rear-next; (3)入队 void EnQueue( LinkQueue *Q, Datatype x) /入队 /也就是在尾结点处插入元素 QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode);/申请新结点 p-data=x; p-ne
16、xt=Q-rear-next;/初始化新结点并链入 Q-rear-next=p; 11/15 Q-rear=p;/将尾指针移至新结点 (4)出队 Datatype DeQueue( LinkQueue *Q) /出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q ) Error(“Queue underflow“); p=Q-rear-next-next; /p 指向将要摘下的结点 x=p-data; /保存结点中数据 if (p=Q-rear) /当队列中只有一个结点时，p 结点出队后，要将队尾指针指向头结点 Q-rear =
17、Q-rear-next; Q-rear-next=p-next; else Q-rear-next-next=p-next;/摘下结点 p free(p);/释放被删结点 return x; （7 ） 假设以数组 Qm存放循环队列中的元素, 同时设置一个标志 tag，以 tag = 0 和 tag = 1 来区别在队头指 针(front) 和队尾指针( rear)相等时，队列状态为“空”还是“满” 。试编写与此结构相应的插入(enqueue) 和删除(dlqueue) 算法。 【解答】 循环队列类定义 #include template class Queue /循环队列的类定义 public
18、: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = tag = 0; /置空队列 int IsEmpty ( ) const return front = rear /判队列空否 12/15 int IsFull ( ) const return front = rear /判队列满否 private: int rear, front, tag; /队尾指针、队头指针和队满标志 Type
19、 *Q; /存放队列元素的数组 int m; /队列最大可容纳元素个数 构造函数 template Queue: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) /建立一个最大具有 m 个元素的空队列。 Q = new Typem; /创建队列空间 assert ( Q != 0 ); /断言: 动态存储分配成功与否 插入函数 template void Queue : EnQueue ( Type /判队列是否不满，满则出错处理 rear = ( rear + 1 ) % m; /队尾位置进 1, 队尾指针指示实际队尾位置 Qre
20、ar = item; /进队列 tag = 1; /标志改 1，表示队列不空 删除函数 template Type Queue : DeQueue ( ) assert ( ! IsEmpty ( ) ); /判断队列是否不空，空则出错处理 front = ( front + 1 ) % m; /队头位置进 1, 队头指针指示实际队头的前一位置 tag = 0; /标志改 0, 表示栈不满 return Qfront; /返回原队头元素的值 读取队头元素函数 template Type Queue : GetFront ( ) assert ( ! IsEmpty ( ) ); /判断队列是否
21、不空，空则出错处理 return Q(front + 1) % m; /返回队头元素的值 (8）如果允许在循环队列的两端都可以进行插入和删除操作。要求： 写出循环队列的类型定义； 写出“从队尾删除”和“从队头插入”的算法。 题目分析 用一维数组 v0M-1实现循环队列，其中 M 是队列长度。设队头指针 front 和队尾指针 rear，约定 front 指向队头元素的前一位置，rear 指向队尾元素。定义 front=rear 时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。 （1）#define M 队列可能达到的最大长度
22、typedef struct elemtp dataM; int front,rear; 13/15 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, elemt
23、p x) / Q 是顺序存储的循环队列，本算法实现“从队头插入”元素 x。 if (Q.rear=(Q.front-1+M)%M) printf(“队满”; exit(0);) Q.dataQ.front=x; /x 入队列 Q.front=(Q.front-1+M)%M; /修改队头指针。 / 结束从队头插入算法。 （9 ）已知 Ackermann 函数定义如下 : 写出计算 Ack(m,n)的递归算法，并根据此算法给出出 Ack(2,1)的计算过程。 写出计算 Ack(m,n)的非递归算法。 int Ack(int m,n) if (m=0) return(n+1); else if(m!
24、=0 else return(Ack(m-1,Ack(m,m-1); /算法结束 （1）Ack(2,1)的计算过程 Ack(2,1)=Ack(1,Ack(2,0) /因 m0,n0 而得 =Ack(1,Ack(1,1) /因 m0,n=0 而得 =Ack(1,Ack(0,Ack(1,0) / 因 m0,n0 而得 = Ack(1,Ack(0,Ack(0,1) / 因 m0,n=0 而得 =Ack(1,Ack(0,2) / 因 m=0 而得 =Ack(1,3) / 因 m=0 而得 =Ack(0,Ack(1,2) /因 m0,n0 而得 = Ack(0,Ack(0,Ack(1,1) /因 m0,
25、n0 而得 = Ack(0,Ack(0,Ack(0,Ack(1,0) /因 m0,n0 而得 = Ack(0,Ack(0,Ack(0,Ack(0,1) /因 m0,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 akmMN;int i,j; for(j=0;j value; /输入 while ( value != retvalue ) /输入有效 q = NewNode
26、( value ); /建立包含 value 的新结点 15/15 if ( first = NULL ) first = current = q; /空表时, 新结点成为链表第一个结点 else current-link = q; current = q; /非空表时, 新结点链入链尾 cin value; /再输入 current-link = NULL; /链尾封闭 void List : PrintList ( ) /输出链表 cout data; /递归结束条件 int temp = Max ( f -link ); /在当前结点的后继链表中求最大值 if ( f -data tem
27、p ) return f -data; /如果当前结点的值还要大, 返回当前检点值 else return temp; /否则返回后继链表中的最大值 int List : Num ( ListNode *f ) /递归算法 : 求链表中结点个数 if ( f = NULL ) return 0; /空表, 返回 0 return 1+ Num ( f -link ); /否则, 返回后继链表结点个数加 1 float List : Avg ( ListNode *f , int return ( float ) (f -data ); else float Sum = Avg ( f -lin
28、k, n ) * n; n+; return ( f -data + Sum ) / n; #include “RecurveList.h“ /定义在主文件中 int main ( int argc, char* argv ) List test; int finished; cout finished; /输入建表结束标志数据 test.NewList ( finished ); /建立链表 test.PrintList ( ); /打印链表 cout “nThe Max is : “ test.GetMax ( ); cout “nThe Num is : “ test.GetNum ( ); cout “nThe Ave is : “ test.GetAve () n; printf ( “Hello World!n“ ); return 0;
