《数据结构》习题集第3章栈和队列.doc

第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=n3. 向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ）A、HS-next=s; B、s-next=HS-next；HS-next=s; C、s-next=HS；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、-+*abcd6. 中缀表达式A-（B+C/D）*E 的后缀形式是（ D ）A、AB-C+D/E* B、ABC+D/E* C、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，18. 循环队列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+19. 循环队列SQ 采用数组空间SQ.base0,n-1存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（ ）A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n10. 若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（ ）A、1，5 B、2, 4 C、4，2 D、5，111. 用单链表表示的链式队列的队头在链表的（ ）位置A、链头 B、链尾 C、链中12. 判定一个链队列Q（最多元素为n 个）为空的条件是（ ）A、Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n13. 在链队列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-next-next; C、Q.front-next=Q.front-next-next; D、Q.front=Q.rear-next;15. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。16. 栈和队列的共同点是（ ）A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点17. 消除递归（ ）需要使用栈。A、一定 B、不一定18. 设有一顺序栈S，元素s1，s2，s3，s4，s5，s6 依次进栈，如果6 个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是（ ）A、2 B、3 C、 5 D、 619. 若一个栈的输入序列是a，b，c，则通过入、出栈操作可能得到a,b,c 的不同排列个数为（ ）A、 4 B、 5 C、 6 D、 720. 设有一顺序栈已经含有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.121. 链栈和顺序栈相比，有一个比较明显的优势是（ ）A、通常不会出现栈满的情况 B、通常不会出现栈空的情况C、插入操作更容易实现 D、删除操作更加容易实现22. 若一个栈的输入序列是1，2，3，4，n，输出序列的第一个元素是n，则第i 个输出元素是（ C ）A、不确定 B、 n-i C、 n-i+1 D、n-i-123. 以下说法正确的是( )A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、 判断题1. 在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。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，则在栈的输出序列中可以得到1,2,3,4。9. 若以链表作为栈的存储结构，则进栈需要判断栈是否满。10. 若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、 填空题1. 栈的特点是（先进后出 ），队列的特点是（ 先进先出 ）。2. 线性表、栈、队列都是（ ）结构，可以在线性表的（ ）位置插入和删除元素；对于栈只能在（ ）插入和删除元素；对于队列只能在（ ）插入元素和在（ ）位置删除元素。3. 有程序如下，则此程序的输出结果（栈的元素类型是SelemType 为char）是（ ）。void main()stack s; char x,y; initstack (s); x=c;y=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，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）；若只设尾指针，则出队和入队的时间复杂度分别是（ ）和（ ）。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=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);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);的结果是（ ）。四、 简答题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;I=n;I+)push(s,aI);(2) status algo2(stack s,int e)stack t;int d;initstack(t);while(!stackempty(s)pop(s,d);if(d!=e)push(t,d);while(!stackempty(t)pop(t,d);push(s,d);3. 内存中一片连续空间（不妨假设地址从0 到m-1）提供给两个栈s1 和s2 使用，怎样分配这部分存储空间，使得对任一栈仅当这部分空间全满时才发生溢出。4. 有递归过程如下：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)的结果是什么？5. 简述以下算法的功能（栈和队列的元素类型均为 int）void algo(queue &q)stack s;int d;initstack(s);while(!queueempty(q)dequeue(q,d);push(s,d);while(!stackempty(s)pop(s,d);enqueue(q,d);6. 假设 Q0，9是一个非循环线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，如果不能入队，请指出其元素，并说明理由。d,e,b,g,h 入队 d,e 出队 I,j,k,l,m入队 b 出队 n,o,p,q,r 入队。7. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：9-2*4+(8+1)/3。8. 设栈S（1，2，3，4，5，6，7），其中7 为栈顶元素。写出调用algo 后栈S 的状态。void algo(Stack *S)int i=0;Queue Q; Stack T;InitQueue(Q); InitStack(T);while(!StackEmpty(S)if(i%2=0) Push(T,Pop(S);else EnQueue(Q,Pop(S);i+;while(!QueueEmpty(Q)Push(S,DeQueue(Q);while(!StackEmpty(T)Push(S,Pop(T);五、 设计题1. 回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)2. 设从键盘输入一整数的序列：a1, a2, a3，an，试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。3. 从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。4. 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。下面所示的序列中哪些是合法的？A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。5. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。6. 假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。7. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： 写出循环队列的类型定义； 写出“从队尾删除”和“从队头插入”的算法。8. 已知Ackermann函数定义如下:a) 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 写出计算Ack(m,n)的非递归算法。9. 已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： 求链表中的最大整数； 求链表的结点个数； 求所有整数的平均值。（2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)根据提示，算法可设计为：/以下为顺序栈的存储结构定义#define StackSize 100 /假定预分配的栈空间最多为100个元素typedef char DataType;/假定栈元素的数据类型为字符typedef structDataType dataStackSize;int top;SeqStack;int IsHuiwen( char *t)/判断t字符向量是否为回文，若是，返回1，否则返回0SeqStack s;int i , len;char temp;InitStack( &s);len=strlen(t); /求向量长度for ( i=0; ilen/2; i+)/将一半字符入栈Push( &s, ti);while( !EmptyStack( &s)/ 每弹出一个字符与相应字符比较temp=Pop (&s);if( temp!=Si) return 0 ;/ 不等则返回0else i+;return 1 ; / 比较完毕均相等则返回 1（3）设从键盘输入一整数的序列：a1, a2, a3，an，试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。#define maxsize 栈空间容量 void InOutS(int smaxsize) /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(“出栈元素是%dn”,stop-)； /算法结束。（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。 题目分析逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 float expr( )/从键盘输入逆波兰表达式，以$表示输入结束，本算法求逆波兰式表达式的值。float OPND30; / OPND是操作数栈。init(OPND); /两栈初始化。 float num=0.0; /数字初始化。 scanf (“%c”,&x);/x是字符型变量。 while(x!=$) switch case0=x=0&x=0&xj)printf(“序列非法n”)；exit(0); i+; /不论Ai是I或O，指针i均后移。 if(j!=k) printf(“序列非法n”)；return(false); else printf(“序列合法n”)；return(true); /算法结束。 算法讨论在入栈出栈序列（即由I和O组成的字符串）的任一位置，入栈次数（I的个数）都必须大于等于出栈次数（即O的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记0），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。算法如下：/先定义链队结构:typedef struct queuenodeDatatype data;struct queuenode *next;QueueNode; /以上是结点类型的定义typedef structqueuenode *rear;LinkQueue; /只设一个指向队尾元素的指针(1)置空队void InitQueue( LinkQueue *Q) /置空队：就是使头结点成为队尾元素QueueNode *s;Q-rear = Q-rear-next;/将队尾指针指向头结点while (Q-rear!=Q-rear-next)/当队列非空，将队中元素逐个出队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-next=Q-rear-next;/初始化新结点并链入Q-rear-next=p;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 = Q-rear-next; Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下结点pfree(p);/释放被删结点return x;（7）假设以数组Qm存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。【解答】循环队列类定义#include template class Queue /循环队列的类定义public: Queue ( int=10 ); Queue ( ) delete Q; void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( ); void MakeEmpty ( ) front = rear = tag = 0; /置空队列 int IsEmpty ( ) const return front = rear & tag = 0; /判队列空否 int IsFull ( ) const return front = rear & tag = 1; /判队列满否private: int rear, front, tag;/队尾指针、队头指针和队满标志 Type *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 &item ) assert ( ! IsFull ( ) );/判队列是否不满，满则出错处理rear = ( rear + 1 ) % m;/队尾位置进1, 队尾指针指示实际队尾位置Qrear = 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 ( ) );/判断队列是否不空，空则出错处理return Q(front + 1) % m;/返回队头元素的值(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求： 写出循环队列的类型定义； 写出“从队尾删除”和“从队头插入”的算法。题目分析 用一维数组 v0.M-1实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。（1）#define M 队列可能达到的最大长度typedef struct elemtp dataM; 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.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!=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) /因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,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;jN;j+) akm0j;=j+1; for(i=1;im;i+) akmi0=akmi-11; for(j=1;jN;j+) akmij=akmi-1akmij-1; return(akmmn); /算法结束（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： 求链表中的最大整数； 求链表的结点个数； 求所有整数的平均值。#include /定义在头文件RecurveList.h中class List;class ListNode /链表结点类friend class List;private:int data;/结点数据ListNode *link;/结点指针ListNode ( const int item ) : data(item), link(NULL) /构造函数;class List /链表类private:ListNode *first, current;int Max ( ListNode *f );int Num ( ListNode *f );float Avg ( ListNode *f, int& n );public:List ( ) : first(NULL), current (NULL) /构造函数List ( ) /析构函数ListNode* NewNode ( const int item );/创建链表结点, 其值为itemvoid NewList ( const int retvalue );/建立链表, 以输入retvalue结束void PrintList ( );/输出链表所有结点数据int GetMax ( ) return Max ( first ); /求链表所有数据的最大值int GetNum ( ) return Num ( first ); /求链表中数据个数float GetAvg ( ) return Avg ( first ); /求链表所有数据的平均值;ListNode* List : NewNode ( const int item ) /