(栈和队列)(复习题).doc

栈和队列一、选择题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以下 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一个队列的入队序列是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向一个栈顶指针为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-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最早插入队列中的元素总是最后被删除 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，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; 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设有一顺序栈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 栈 是限定仅在表的一端进行插入或删除操作的线性表，其运算遵循 后进先出 的原则。5设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_ M-1_个队列元素。6栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_ LIFO 表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_ FIFO _表。7设F和R分别表示顺序循环队列的头指针和尾指针，或F指向队头元素的前一个位置，R指向队尾元素则判断该循环队列为空的条件为 F=R 。9.若addQ(n)表示元素n入队列Q的入队运算，delQ( )表示队列Q的出队运算，当前队列状态为空，则经过addQ(1)，addQ(2)， delQ( )，addQ(5)，addQ(7)， delQ( )，addQ(9)操作后，队头元素为5，队尾元素为9；若使队列中剩余元素全部出队，还需经过3次delQ( )操作。10.栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。12. 设顺序循环队列Q0：M-1的头指针和尾指针分别为F