第 三部分 栈 队列 带答案精品参考资料.doc

第三部分 栈 队列 一、选择题 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,b 3. 链式栈与顺序栈相比，一个比较明显的优点是 (?B )。 ???? A. 插入操作更加方便??????????? B. 通常不会出现栈满的情况 C. 不会出现栈空的情况???????? D. 删除操作更加方便 4. 在一个顺序存储的循环队列中，队头指针指向队头元素的 (?A )。 ???? A. 前一个位置???????? ?? B. 后一个位置 C. 队头元素位置???? ??? D. 队尾元素的前一位置 5. 若一个栈的输入序列是1，2，3……n，则输出序列的第一个元素是n，则第i个输出元素是（ C ）。 A? n-i?????????? B? i??????????? C? n-i+1???????? D? n-i-1 6. 栈的数组表示中，top为栈顶指针，栈空的条件是( D )。 （A） top=0 （B）top=maxSize （C）top=maxSize（D）top=-1 7. 在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。 （A） front=maxSize （B）(rear+1)%maxSize=front （C） rear=maxSize （D）rear=front 8. 栈和队列的共同特点是( C )。 （A） 都是先进后出 （B）都是先进先出 （C） 只允许在端点处插入和删除 （D）没有共同点 9．与中缀表达式a+b*c-d等价的前缀表达式是( C )。 A.+a-*bcd B.*+-abcd C.-+a*bcd D.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←front，( D )，call RET(P)。 A.front←link(rear) B.rear←link(p) C.rear←link(front) D.front←link(p) 12．由两个栈共享一个向量空间的好处是：（?B?） ?? A．减少存取时间，降低下溢发生的机率 ?? B．节省存储空间，降低上溢发生的机率 ?? C．减少存取时间，降低上溢发生的机率 ?? D．节省存储空间，降低下溢发生的机率 13．数组data[m]为循环队列的存储空间, front为队头指针, rare为队尾指针,则执行入队的操作为（ D ）。 A rare=rare+1 B rare=(rare+1)%(m-1) C rare=(rare-1)%m D rare=(rare+1)%m 14. 将递归算法转换成对应的非递归算法时，通常需要使用( A )。 （a）栈 （b）队列? （c）链表 （d）数组 15．下列关于栈的叙述中正确的是( D )。 A. 在栈中只能插入数据 B. 在栈中只能删除数据 C. 栈是先进先出的线性表 D. 栈是先进后出的线性表 16．下列关于队列的叙述中正确的是( C )。 A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 17．栈和队列的共同点是( C )。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 18．栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈之前，栈中元素可以出栈，则出栈序列可能是（??D ）。 A. ABCED B. DBCEA C. CDABE D. DCBEA 19．表达式a*(b+c)-d的后缀表达式是( B )。 A. abcd*+1 B. abc+*d- C. abc*+d- D. -+*abcd 20．设依次进入一个栈的元素序列为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,b 21．当需要随机查找线性表的元素时，宜采用（??C ）