数据结构 第三章(栈与队列) 考试题目

1.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若 p1=n，则pi为( )

A．i B．n-i C．n-i+1 D．不确定 2．栈和队列的共同点是( ) A．都是先进后出 B．都是先进先出

C．只允许在端点处插入和删除元素 D．没有共同点

3．若依次输入数据元素序列{a，b，c，d，e，f，g}进栈，出栈操作可以和入栈操作间隔进行，则下列哪个元素序列可以由出栈序列得到？( ) A．{d，e，c，f，b，g，a} B．{ f，e，g，d，a，c，b} C．{e，f，d，g，b，c，a} D．{ c，d，b，e，g，a，f}

4.一个栈的入栈序列是1,2,3,4,5，则下列序列中不可能的出栈序列是( ) A. 2,3,4,1,5 B. 5,4,1,3,2 C. 2,3,1,4,5 D. 1,5,4,3,2 5. 队列操作的原则是( )

A. 先进先出 B. 后进先出 C. 只能进行插入 D. 只能进行删除 6. 栈的插入与删除是在( )进行。

A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 7.假设顺序栈的定义为： typedef struct {

selemtype *base; /* 栈底指针*/ selemtype *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间,以元素为单位*/ }sqstack;

变量st为sqstack型，则栈st为空的判断条件为（ ）。 A． st.base == NULL B． st.top == st.stacksize

C． st.top-st.base>= st.stacksize D． st.top == st.base

8.假设顺序栈的定义同上题，变量st为sqstack型，则栈st为满的判断条件为（ ）。

A． st.base == NULL B． st.top == st.stacksize

C． st.top-st.base>= st.stacksize D． st.top == st.base

9．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非空时，若插入一个新的数据元素，则其队尾指针rear的变化是( )。

A．QU->rear==(QU->front+1) % m0 B．QU->rear==(QU->rear+1) % m0 C．QU->rear==(QU->front+1) D．QU->rear==(QU->rear+1)

10．在少用一个元素空间的循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 中，当队列非满时，若删除一个数据元素，则其队头指针front的变化是( )。

A．QU->front==(QU->rear+1) % m0 B．QU->front==(QU->front+1) C．QU->front==(QU->rear+1) D．QU->front==(QU->front+1) % m0 二 填空题：

1. 线性表、栈、队列都是线性结构，可以在线性表的__任意___位置插入和删除元素，对于栈只能在__栈顶___位置插入和删除元素，对于队只能在__队尾_位置插入和只能在___队头__位置删除元素。

2. 用下标0开始的N元数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是：m =____m=(m+1)%N_______。

3．设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳__4_个元素。