第三章 栈和队列 （答案版）

第三章 栈和队列 一、填空题 1、 线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队头 删除元素。 2、 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3、 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4、在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5、在具有n个单元的循环队列中，队满时共有 n-1 个元素。 6、 向栈中压入元素的操作是先 移动栈顶指针 后 插入元素 。 7、从循环队列中删除一个元素时，其操作是 先 判断是否队空 ，后 移动队头指针 。 8、 带表头结点的空循环双向链表的长度等于 1 。 二、判断正误 （ F ）1、 在表结构中最常用的是线性表，栈和队列不太常用。 （ T ）2、 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （ F ）3、 栈和链表是两种不同的数据结构。 （ F ）4、 栈和队列是一种非线性数据结构。 （ T ）5、 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ T ）6、 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ F ）7、 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ F ）8、 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 三、单项选择题（每小题1分，共20分） 1、判定一个顺序栈ST（最多元素为m0）为空的条件是 A A、ST->top<0 B、ST->top=0 C、ST->top<>m0 D、ST->top=m0 2、判定一个队列QU（最多元素为m0）为满队列的条件是 A A、QU->rear － QU->front == m0 B、QU->rear － QU->front －1 == m0 C、QU->front == QU->rear D、QU->front == QU->rear+1 3、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 D A、r－f; B、（n＋f－r）% n; C、n＋r－f; D、（n＋r－f）% n 4、向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行： C A、 top->next = S; B、S->next = top->next; top->next = S; C、 S->next = top; top = S; D、S->next = top; top = top->next; 5、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为： C A、i B、n=i C、n-i+1 D、不确定 6、向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行： C A、top->next = S; B、S->next = top->next; top->next = S; C、S->next = top; top = S; D、S->next = top; top = top->next; 7、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ C A、1和 5 B、2和4 C、4和2 D、5和1 四、简答题 1、 说明线性表、栈与队的异同点。 答：线性表元素之间存在一对一的关系，除了第一个元素外，每一个元素都有一个唯一的前驱，除了最后一个元素外，每一个元素都有一个唯一的后续。线性表可以在任意位置插入和删除元素。 栈和队列是运算受到限制的线性表，具体而言，栈只能在表的一段插入、删除元素，该端称之为栈顶，对应的，插入删除称之为入栈和出栈，队列只能在表的一段删除，该端成为队头，在另一端插入元素，该端成为队尾。 2、 顺序队的“假溢出”是怎样产生