第三部分栈队列带答案

《第三部分栈队列带答案》由会员分享，可在线阅读，更多相关《第三部分栈队列带答案（9页珍藏版）》请在装配图网上搜索。

1、第三部分 栈 队列一、选择题1（ A ） 又称为 FIFO 表。A. 队列 B.散列表 C.栈 D.哈希表2 设依次进入一个栈的元素序列为c,a,b,d, 不可得到出栈的元素序列有 （B D ）A. a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b3. 链式栈与顺序栈相比，一个比较明显的优点是 （ B ） 。A. 插入操作更加方便B. 通常不会出现栈满的情况C. 不会出现栈空的情况D. 删除操作更加方便4. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A ） 。A. 前一个位置B. 后一个位置C. 队头元素位置D. 队尾元素的前一位置i 个输出元5. 若一个

2、栈的输入序列是1 , 2 , 3n,则输出序列的第一个元素是n ,贝U第素是（ C ）。A n-iB iC n-i+1D n-i-16. 栈的数组表示中, top 为栈顶指针,栈空的条件是 （ D ） 。（A） top=0 （ B ）top=maxSize（ C） top=maxSize （ D ） top=-1为数组的7. 在数组表示的循环队列中, front 、rear 分别为队列的头、尾指针, maxSize最大长度,队满的条件是 （ B ）（ A ） front=maxSize（ C ） rear=maxSize8. 栈和队列的共同特点是（ A） 都是先进后出（ B ）（rear+1）

3、%maxSize=front（ D） rear=front（ C ） 。（ B ）都是先进先出（C） 只允许在端点处插入和删除 （ D ）没有共同点9 与中缀表达式 a+b*c-d 等价的前缀表达式是 （ C ） 。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-10中缀表达式 A-（B+C）*D/E 的后缀形式是 （ D ）A.ABC+-D*E/B. ABC+D*-E/C. ABC+D-*E/D. ABC+D*E/-11 若非空队列采用链式存储结构, front 和 rear 分别为队头元素与队列尾元素的指针,删除此时队列的一个元素的操作时依次执行p J front

4、, ( D ) , call RET(P)。A.front jlink(rear)B.rear J link(p)C.rear J link(front)D.front J link(p)12 由两个栈共享一个向量空间的好处是： ( B )A. 减少存取时间，降低下溢发生的机率B. 节省存储空间，降低上溢发生的机率C 减少存取时间，降低上溢发生的机率D 节省存储空间，降低下溢发生的机率13 数组 datam 为循环队列的存储空间 , front 为队头指针 , rare 为队尾指针 ,则执行入 队的操作为( D )。A rare=rare+1B rare=(rare+1)%(m-1)C rar

5、e=(rare-1)%mD rare=(rare+1)%m14. 将递归算法转换成对应的非递归算法时，通常需要使用15下列关于栈的叙述中正确的是( D ) 。A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表16下列关于队列的叙述中正确的是( C ) 。A. 在队列中只能插入数据B.在队列中只能删除数据C. 队列是先进先出的线性表D.队列是先进后出的线性表17栈和队列的共同点是 ( C ) 。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点18栈底至栈顶依次存放元素 A、B、C、D，在第五个兀素 E入栈之前

6、，栈中兀素可以出栈，则出栈序列可能是(D )。A. ABCEDB. DBCEAC.CDABED. DCBEA19表达式 a*(b+c)-d的后缀表达式是 ( B ) 。A. abcd*+1B. abc+*d-C.abc*+d-D. -+*abcd20设依次进入一个栈的元素序列为c,a,b,d，不可得到的出栈的元素序列有(B D )。A. a,b,c,dB. a,d,c,bC.b,a,d,cD. c,d,a,b(c)链表(d)数组(a)栈 (b)队列21 当需要随机查找线性表的元素时，宜采用(C )作存储结构。A.双向链表B.循环链表C.顺序表D.单链表22 .表达式采用逆波兰式表示时可以不用括

7、号，而且可以用基于(A )求值过程进行计算。A.栈B.队列C.符号表D.散列表23 .与逆波兰式ab+cd+* 对应的中缀表达式是( C )。A. a+b+c*dB. (a+b)*c+d24 初始为空的堆栈中依次插入元素f、e、此时的栈顶元素是(B )。A. cB. dC. b25 .某堆栈的输入序列为1 , 2 , 3，的元素为(C )。A. iB. n-iC. n-i+126 .循环单链表表示队列，正确的说法是(C. (a+b)*(c+d)D. a+b*c+dd、c、b、a以后，连续进行了三次删除操作，D. en,输出序列的第一个元素为n,则第i个输出D.哪个元素无所谓B )。A. 可设一

8、个头指针使入队、出队都方便B. 可设一个尾指针使入队、出队都方便C. 必须设头、尾指针才能使入队、出队都方便D. 无论如何，只可能使入队方便27 在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行(D ）。A. s-li nk=p-li nk;p-li nk=s;B. p-li nk=s;s-li nk=q;C. p-li nk=s-li nk;s-li nk=p;D. q-li nk=s;s-li nk=p;、填空题1 .在n(n0)个元素的顺序栈中删除1个元素的时间复杂度为：0(1)2 .设SQ为循环队列，存储在数组 dm中，则SQ出队操作对其队

9、头指针front的修改是 _ front = (front+1)%m 。3 .栈中元素的进出原则为先进后出 。4 .在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个结构，其主要特点是先进先出。条件是 r=f，判满的条件是 (r+1)%m=f。6 .在具有n个单元的循环队列中，队满时共有n-1_个元素。7 操作系统中先来先服务是 _ 队列_数据结构应用的典型例子。8 .设栈S和队列Q的初始状态为空，元素 a、b、c、d、e、f依次通过栈S，一个元 素出栈后即进入队列 Q。若这6个元素

10、出队列的顺序为 b、d、c、f、e、a，则栈S的 容量最少应该是 3 。9 用循环单链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂度分别为_0(1)_和_ O(n)_ ;若只设尾指针，则出队和入队的时间复杂度分别为_0(1)_和0(1)_。10 用向量表示的循环队列的队首和队尾位置分别为1和max_size ，试给出判断队列为满的边界条件为：(max size+1)%MAXSIZE=111 .若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为：2和4。12 .已知链栈的结点结构

11、包括数据域(data)和指向下一个结点的指针域(next)，栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为：1) p-n ext=top:2) top=p:三、判断题1 若某堆栈的输入序列为1,2,3,4 ，则4,3,1,2不可能是堆栈的输出序列之一。(R )2 删除非空链式存储结构的堆栈(设栈顶指针为top)的一个元素的过程是依次执行:p Jtop,top J link(p),call RET(p) 。( R )1 若队列采用链式存储结构，队头指针与指针分别为front和rear ,向队列中插入一个数据信息为item的新元素的过程是依次执行：call GETNODE(p),da

12、ta(P) J item,rear Jp,front J p。( W )四、操作题1 依次输入元素 X,Y,Z,插入到一个初始状态为空的链式栈中，试画出空的链式栈和每插入一个元素之后的链式栈示意图。2指出程序段完成的功能?vode Demo1(SeqStack *S) int i, arr64, n=0;while(!StackEmpty(S) arrn+ =Pop(S);for(i=0; ivn; i+) Push(S, arri);3 .设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后个

13、结点。I 01ra-【解答1】templatevclass Type void List : I nverse ( ) if ( first = NULL )return;ListNode *p = firstf lin k;, *pr = NULL;while ( p != NULL ) first f link = pr;/ 逆转 first 指针pr = first; first = p; p = p f link;/ 指针前移first-li nk=pr;【解答2】templatevclass Type void List : I nverse ( ) ListNode *p, *he

14、ad = new ListNode ();while ( first != NULL ) p = first; first = first f link;/ 摘下 first 链头结点pf link = head f link; head f link = p; / 插入 head 链前端first = head f link; delete head;/ 重置 first4 把A、 B、 C、 D依次进栈(栈初始为空)，任何时刻(只要栈不空)，都可 以出(退)栈，试写出所有可能的出栈序列(如 A B C D )。5用算符优先法求下列算术表达式 12+20/(10-2*3) 的值 ,试简要说明

15、求值过程 ,画出操作数栈和运算符栈的主要变化过程。6 依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中， 试画出所有插入完成之后 的链式栈。7 有5个元素，其入栈次序为 A、B、C、D、E,在各种可能的出栈次序中，以元素C 第一个出栈且 D 第二个出栈的次序有哪几个？CDEBA 、 CDBEA 、 CDBAE五、程序题1 假设以带头结点的循环单链表表示队列，并且只设一个指针rear指向队尾结点，不设头指针，请写出相应的入队和出队算法。入队算法：void Equeue(Slink *tail, ElemType x) Slink *s;s=(Slink *)malloc(sizeof(

16、Slink); s-data = x;s-next=rear-next;rear-next = s;rear = s;出队算法：int Oqueue(Slink *tail, ElemType *e) Slink *p;if(rear-next = rear)return 0;p=rear-next-next;if(p=rear)rear=rear-next;rear-next=rear;elserear-next-next=p-next;*e=p-data;free(p); return 1;2试写一个判别表达式中开、闭括号是否配对出现的算法int match(char *str)/* 判别

17、表达式中小括号是否匹配，若匹配则返回1 ，否则返回 0*/ Stack S;int i=0;S.top=-1;While(stri!=0 )If(stri=( )s.top+;s.datas.top=( ;i+;elseif(stri=) )if(S.top=0) return 0;else return 1;3假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，编写相应的置队空、判队空、入队和出队的算法。算法如下：/ 先定义链队结构 :typedef struct queuenodeDatatype data;struct queuenode *next;Q

18、ueueNode; / 以上是结点类型的定义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( LinkQue

19、ue *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;/ 摘下结点 p free(p);/ 释放被删结点return x;