栈队列和数组

第三章 栈、队列

一、名词解释：

1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队

二、填空题：

1、栈修改的原则是_________。在栈顶进行插入运算，被称为________，在栈顶进行删除运

算，被称为________。

2、对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 3、对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 4、一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 5、实现在顺序栈上的进栈，主要语句为_____________________________________。 6、实现在顺序栈上的退栈，主要语句为____________________________________。 7、实现在顺序栈上判栈空的条件为________________。

8、实现在顺序栈上取栈顶元素，主要语句为_____________________。

9、设一个链栈的栈顶指针为top，栈中结点的格式为 info， next,栈空的条件是

_____________；如果栈不为空，则取栈顶操作为______________；退栈操作为______________,______________,______________；p进栈操作为______________，______________。

10、在队列中，新插入的结点只能添加到________，被删除的只能是排在______的结点。 11、实现在循环队上的入队列，主要语句为____________________________________。 12、实现在循环队上的出队列，主要语句为____________________________________。 13、实现在循环队上判队空的条件为____________________________________。 14、实现在循环队上取队头，主要语句为____________________________________。 15、链队在一定范围内不会出现___________的情况。当lq.front==lq.rear试，队中无元素。

16、实现在链队上的入队列，主要语句为____________________________________。 17、实现在链队上的出队列，主要语句为____________________________________。 18、实现在链队上判队空的条件为____________________________________。 19、实现在链队上读队头元素，主要语句为____________________________________。 20、栈和队列都是 结构；对于栈只能在 插入和删除元素；对于队列只能在

插入和 删除元素。

21、 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性

表。

22、在具有n个单元的循环队列中，队满时共有 个元素。 23、向顺序栈中压入元素的操作是 ， 。

24、从循环队列中删除一个元素时， ， 。 三、判断

（ ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （ ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出

型结构。

（ ）5. 栈和链表是两种不同的数据结构。

（ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个

栈的栈底分别设在这片内存空间的两端。

（ ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

四、单项选择题

1.以下说法正确的是 ( )

①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 2.顺序队列的人队操作应为 ( )

①sq.rear=sq.rear+1；sq.data[sq.rear]=x ②sq.data[sq.rear]=x；sq.rear=sq.rear+1

③sq.rear=(sq.rear+1)% maxsize； sq.data[sq.rear]=x ④sq.data[sqrear]=x； sq.rear=(sq.rear+1)% maxsize 3.循环队列的人队操作应为 ( )

①sq.rear=sq.rear+1； sq.data[sq.rear]=x ②sq.data[sq.rear]=x； sq.rear=sq.rear+1

③sq.rear=(sq.rear+1)% maxsize； sq.data[sq.rear]=x ④sq.data[sq.rear]=x； sq.rear=(sq.rear+1)% maxsize 4. 顺序队列的出队操作为 ( )

①sq.front=(sq.front+1)% maxsize ②sq.front=sq.front+1

③sq.rear=(sq.rear+1)% maxsize ④sq.rear=sq.rear+1 5. 循环队列的出队操作为 ( )

①sq.front=(sq.ftont+1)% maxsize ②sq.front=sq.front+1 ③sq.rear=(sq.rear+)% maxsize ④sq.rear=sq.rear+1 6.循环队列的队满条件为 ( )

①(sq.rear+1) % mazsize ==(sq.front+1) % maxsize; ②(sq.rear+1 % maxsize ==sq.front+1 ③sq.(rear+1) % maxsize ==sq.front ④sq.rear ==sq.front 7.循环队列的队空条件为 ( )

①(sq.rear+1) % maxsize ==(sq.front+1) % maxsize ②(sq.rear+) % maxsize ==sq.front+1 ③(sp.rear+1) % maxsize ==sq.front ④sq.rear == sq.front

8．如果以链表作为栈的存储结构，则退栈操作是 ( )

①必须判别栈是否满 ②必须判别栈是否空 ③判别栈元素的类型 ④对栈不做任何操作

9．基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（ ）唯一确定。

①非零元素 ②三元组(i,j,aij) ③ aij ④ i,j

10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队为指针，则执行出队操作的语句为 （ ）

①front=front+1 ② front=（front+1）%m ③rear=(rear+1)%m ④ front=(front+1)%(m+1)

11.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是 （ ）

①2 ② 3 ③ 5 ④6

12．设有一顺序栈已含3个元素，a1，a2，a3，a1在栈底，元素a4正等待进栈。那么下列

4个序列中不可能出现的出栈序列是 （ ）

①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1 13.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ）

①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next

14.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤

为（ ）

①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data ③x=Top;Top=Top->next ④ x=Top->data

15.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ ）

①f->next=c;f=s ②r->next=s;r=s ③s->next=r;r=s ④ s->next=f;f=s 16．链栈与顺序栈相比，有一个比较明显的优点即 （ ）

①插入操作更方便 ② 通常不会出现栈满的情况 ③不会出现栈空的情况 ④ 删除操作更方便

17.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ）

① e d c b a ②d e c b a ③d c e a b ④a b c d e 18.一个队列的人列序是1，2，3，4，则队列的输出系列是（ ）

① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2 ④ 3，2，4，1 19．设计一个判别表达式中左、右括号是否配对出线的算法，采用（ ）数据结构最佳。

①线性标的顺序存储结构 ②栈

③ 队列 ④ 线性表的链式存储结构 20．以下说法正确的是（ ）

①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构

③插人和删除是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用 ④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件front=rear。 21. 栈中元素的进出原则是（ ）

Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出

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

p1=n，则pi为（ ）

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 23. 判定一个栈ST（最多元素为m0）为空的条件是

Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0 24. 判定一个队列QU（最多元素为m0）为满队列的条件是（ ）

Ａ．QU->rear － QU->front = = m0 Ｂ．QU->rear － QU->front －1= = m0 Ｃ．QU->front = = QU->rear Ｄ．QU->front = = QU->rear+1

25．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素

的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ ）

（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n 26. 设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队

操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈