第二单元栈和队列答案.doc
《第二单元栈和队列答案.doc》由会员分享,可在线阅读,更多相关《第二单元栈和队列答案.doc(8页珍藏版)》请在三一文库上搜索。
1、第二单元课后练习题知识点范围:第3章栈和队列一、选择题(每小题1分,共28分)1栈的特点是 B ,简称C的线性表;队列的特点是 A ,简称D的线性表。A先进先出 B后进先出CLIFO DFIFO2栈和队列的共同点是 C 。A都是先进后出 B都是先进先出C只允许在端点处插入和删除元素 D没有共同点3一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是 C 。Aedcba Bdecba Cdceab Dabcde4设有一个栈,元素依次进栈的顺序为A、B、C、D、E。下列 B 是可能的出栈序列。 AD,B,C,A,E BB,C,D,E,A CE,A,B,C,D DE,D,C,A,B5以下
2、B 不是队列的基本运算?A从队尾插入一个新元素 B从队列中删除第i个元素C判断一个队列是否为空 D读取队头元素的值6若已知一个栈的进栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1n,则pi为 C 。Ai Bni Cni1 D不确定7设计一个判别表达式中左、右括号是否配对出现的算法,采用 D 数据结构最佳。 A线性表的顺序存储结构 B队列 C线性表的链式存储结构 D栈 8判定一个顺序栈st(最多元素为MaxSize)为满的条件是 D 。Ast-top != -1 Bst-top = -1 Cst-top != MaxSize Dst-top = MaxSize 9一个队列的入
3、队序列是1,2,3,4,则队列的输出序列是 B 。A4,3,2,1 B1,2,3,4C1,4,3,2 D3,2,4,110判定一个循环队列qu(最多元素为MaxSize)为空的条件是 C 。Aqu-rear qu-front =MaxSize Bqu-rear qu-front -1=MaxSize Cqu-rear =qu-front D qu-rear =qu-front -111若用一个循环队列空间大小为6,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为 B 。 A1和5 B2和4 C4和2 D5和112向一个栈顶指针
4、为h的带头结点的链栈中插入指针s所指的结点时,应执行 D 操作。Ah-next=s; Bs-next=h;Cs-next=h;h =s; Ds-next=h-next;h-next=s;13输入序列为ABC,若用S表示入栈,X表示出栈操作,则得到CBA输出序列要经过的栈操作序列为 B 。A SXSXSX B SSSXXXC SSXSX D SXSSXX14和顺序栈相比,链栈有一个比较明显的优势是 A 。 A通常不会出现栈满的情况 B 通常不会出现栈空的情况 C插入操作更容易实现 D删除操作更容易实现15若一个顺序栈中元素为n个,做进栈运算时发生上溢,则说明该栈的最大容量为( B )。A. n-
5、1 B. n C. n+1 D. n/216允许对队列进行的操作有 D 。A对队列中的元素排序 B取出最近进队的元素 C在队头元素之前插入元素 D删除队头元素17对于循环队列 D 。A无法判断队列是否为空 B无法判断队列是否为满 C队列不可能满 D以上说法都不对18若一个带头结点的链栈的栈顶指针用top表示,当p指向的结点进栈时,执行的操作是 C 。Ap-next=top;top=top-next; Btop=p-p; p-next=top;Cp-next=top-next; top-next=p; Dp-next=top; top=p;19队列的“先进先出”特性是指 D 。A最早插入队列中的
6、元素总是最后被删除 B当同时进行插入、删除操作时,总是插入操作优先C每当有删除操作时,总是要先做一次插入操作D每次从队列中删除的总是最早插入的元素20若一个循环队列,其最多元素个数为MAXSIZE,front为头指针,rear为尾指针,则判定满队列的条件是 A 。A(rear+1)%MAXSIZE=front B rear+1=frontCrear=front D(front+1)%MAXSIZE=rear21队列是一种A的线性表。A先进先出B先进后出C只能插入D只能删除22设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为B。A5,3,4,6,1,2B3,2,5,6,4
7、,1C 3,1,2,5,4,6D1,5,4,6,2,323设顺序循环队列Q0:M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为C。AR-FB F-RC (R-F+M)MD (F-R+M)M24设用链表作为栈的存储结构则退栈操作B。A必须判别栈是否为满B必须判别栈是否为空C判别栈元素的类型D对栈不作任何判别25在链队列Q 中,front指向链队列的头结点,rear指和队尾元素,若让s 所指结点入队需执行的指令是( B )A Q.front-next=s;f=s; BQ.rear-next=s;Q.rear=s;
8、 C s-next=Q.rear;Q.rear=s; Ds-next=Q.front;Q.front=s;26设栈ST 用顺序存储结构表示,若top、base分别为指向栈顶和栈底的指针,则栈ST 为空的条件是 B A、ST.top-ST.base0 B、ST.top-ST.base=0 C、ST.top-ST.basen D、ST.top-ST.base=n27设有一顺序栈已经含有3 个元素,如图2.1 所示元素a4 正等待进栈。下列不可能出现的出栈序列是 A A、a3,a1,a4,a2 B、 a3,a2,a4,a1 C、 a3,a4,a2,a1 D、 a4,a3,a2,a1图2.128设有一
9、顺序栈S,若有6个元素按s1,s2,s3,s4,s5,s6 的顺序依次进栈,如果6 个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少需要的单元空间个数应该是 B A、2 B、3 C、 5 D、 6二、填空题(每空1分,共25分)1 栈 是限定仅在表的一端进行插入或删除操作的线性表,其运算遵循 后进先出 的原则。2下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句。#define MAXSIZE 100typedef struct int sMAXSIZE; int top; sqstack;void push(sqstack *stack , int x)if (
10、stack-top=MAXSIZE) printf(“overflow”);else stack-sstack-top=x ; stack-top+ ;3设输入序列为1、2、3,则经过栈的作用后可以得到 5 种不同的输出序列。4不论是顺序存储结构的栈还是链式存储结构的栈,其入栈和出栈操作的时间复杂度均为 O(1) 。5设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储_ M-1_个队列元素;当前实际存储 (R-F+M)%M 个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。6栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 单元 队列 答案
链接地址:https://www.31doc.com/p-2717959.html