第3章 栈和队列(期末复习含习题)

第二章栈和队列

考点一：栈的定义

只允许在表的末端进行插入和删除的线性表。

考点二：进栈、退栈（重点：P.90.只考顺序栈，链式栈不考）

（1）动态顺序存储表示：

◆结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top 指向栈顶的下一个存储位置;

◆结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。（2）静态顺序存储表示：

◆结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top 所指的当前位置)。

◆结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。

若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。

例题：设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有E个。

供选择的答案：

A～D：①a1 ②a2 ③a3 ④a4

E：①1 ②2 ③3 ④0

答：ABCDE＝2, 4, 1, 2, 2

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

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n，则出栈的序列是n，…，3，2，1。（若不要求顺序出栈，则输出序列不确定）

考点三、四：递归过程和递归栈（重点：P105（请结合P。106的图3.12理解以下文字））递归调用：一个函数(或过程)直接或间接地调用自己本身。

◆为保证递归调用正确执行，系统设立一个“递归工作栈”，作为整个递归调用过程期间使用的数据存储区。

◆每一层递归包含的信息如：参数、局部变量、上一层的返回地址构成一个“工作记录” 。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。

考点五：队列定义与操作

队列：只允许在表的一端进行插入，而在另一端进行删除。

队首：允许进行删除的一端称为队首。

队尾：允许进行插入的一端称为队尾。

考点六：顺序队列（重点：队列操作：插入与删除）

设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。

◆初始化：front=rear=0。

◆入队：将新元素插入rear所指的位置，然后rear加1。

◆出队：删去front所指的元素，然后加1并返回被删元素。

◆队列为空：front=rear。

◆队满：rear=MAX_QUEUE_SIZE-1或front=rear。

顺序队列中存在“假溢出”现象。

考点七：循环队列（重点：P116.图3.20和判断队满）

◆rear所指的单元始终为空。

◆循环队列为空：front=rear 。

◆循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

入队操作：

Status Insert_CirQueue(SqQueue Q , ElemType e)

/* 将数据元素e插入到循环队列Q的队尾*/

{ if ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)

return ERROR; /* 队满，返回错误标志*/

Q.Queue_array[Q.rear]=e ; /* 元素e入队*/

Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;

/* 队尾指针向前移动*/

return OK; /* 入队成功*/

}

出队操作：

Status Delete_CirQueue(SqQueue Q, ElemType *x )

/* 将循环队列Q的队首元素出队*/

{ if (Q.front+1== Q.rear)

return ERROR ; /* 队空，返回错误标志*/

*x=Q.Queue_array[Q.front] ; /* 取队首元素*/

Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;

/* 队首指针向前移动*/

return OK ;

}

例题：

1. 栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元

素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。

3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的前一个位置。

5. 在具有n个单元的循环队列中，队满时共有n-1 个元素。

6. 向栈中压入元素的操作是先移动栈顶指针，后存入元素。

7. 从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。

8.带表头结点的空循环双向链表的长度等于0。

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

（√）10. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（×）11. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。（×）12. 栈和队列是一种非线性数据结构。

错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。（√）13. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（×）14. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

错，后半句不对。

（×）15. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

错，有可能。

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

PTA第三章栈与队列练习题

1-1 通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出得序列为:123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示得循环队列中,front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈得输入序列为{1, 2, 3, 4, 5},则不可能得到{3, 4, 1, 2, 5}这样得出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}、(2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”就是指用单向循环链表或者循环数组表示得队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols、(1分) T F 2-1 设栈S与队列Q得初始状态均为空,元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队得顺序就是b、d、c、f、e、 a、g,则栈S得容量至少就是: (2分) 1. 1 2. 2 3. 3 4. 4 作者: DS课程组

实验三 栈和队列的应用

实验三栈和队列的应用 1、实验目的 （1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。 （2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法； （3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈和队列的应用； 2、实验内容 1）栈和队列基本操作实现 （1）栈的基本操作：采用顺序存储或链式存储结构（数据类型自定义），实现初始化栈、判栈是否为空、入栈、出栈、读取栈顶元素等基本操作，栈的存储结构自定义。 （2）队列的基本操作：实现循环队列或链队列的初始化、入队列、出队列、求队列中元素个数、判队列空等操作，队列的存储结构自定义。 2）栈和队列的应用 （1）利用栈的基本操作将一个十进制的正整数转换成二进制数据，并将其转换结果输出。 提示：利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为： 十进制整数X和R作为形参 初始化栈 只要Ｘ不为0重复做下列动作 将x%R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 (2) 利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Right”，否则输出“Wrong”。

(3) 假设循环队列中只设rear（队尾）和quelen（元素个数据）来分别表示队尾元素的位置和队中元素的个数，写出相应的入队和出队程序。 （4）选作题：编写程序实现对一个输入表达式的括号配对。 3、实验步骤 （1）理解栈的基本工作原理； （2）仔细分析实验内容，给出其算法和流程图； （3）用C语言实现该算法； （4）给出测试数据，并分析其结果； （5）在实验报告册上写出实验过程。 4、实验帮助 算法为： 1) 定义栈的顺序存取结构 2) 分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等） 3) 定义一个函数用来实现上面问题： 十进制整数X和R作为形参 初始化栈 只要X不为0重复做下列动作 将X % R入栈 X=X/R 只要栈不为空重复做下列动作 栈顶出栈 输出栈顶元素 5、算法描述 （1））初始化栈S (创建一个空栈S) void initstack(sqstack *S) { S->base=(ElemType *) malloc(INITSIZE*sizeof(ElemType)); if(!S->base) exit (-1); S->top=0; /*空栈标志*/ S->stacksize = INITSIZE; } (2) 获取栈顶元素 int gettop(sqstack S,ElemType *e) //顺序钱 { if ( S.top==0 ) /* 栈空 */

第三章栈和队列习题_数据结构电子教案

习题三栈和队列 一单项选择题 1. 在作进栈运算时,应先判别栈是否(① ),在作退栈运算时应先判别栈是否(② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(③ )。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 2．若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。 A 可能是2 B 一定是2 C 可能是1 D 一定是1 3. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 4.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6, s5,s1,则栈的容量至少应该是（） A.2 B. 3 C. 5 D.6 5. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 6. 执行完下列语句段后，i值为：（） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1)); A．2 B. 4 C. 8 D. 无限递归 7. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(- 8. 用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 10．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为（） A.front=front+1 B. front=（front+1）% m C.rear=(rear+1)%(m+1) D. front=(front+1)%(m+1) 11.循环队列的队满条件为 ( ) A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize; B. (sq.front+1) % maxsize ==sq.rear C. (sq.rear+1) % maxsize ==sq.front D.sq.rear ==sq.front

数据结构第3章栈和队列自测题答案

一、填空题 二、1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n个单元的循环队列中，队满时共有n-1 个元素。 6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。 7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 8. 带表头结点的空循环双向链表的长度等于0。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。） 三、（×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （×）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。

（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （×）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同 类项。 （×）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （B）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出

数据结构练习题 第三章 栈、队列和数组 习题及答案

第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);

第三章栈和队列练习题

第三章栈和队列练习题 一、单项选择题 1．一个顺序栈一旦被声明，其占用空间的大小（）。 A．已固定B．可以改变C．不能固定D．动态变化 2．链栈和顺序栈相比，有一个比较明显的缺点，即（）。 A．插入操作更加方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 3．用单链表表示的链式队列的队头在链表的（）位置。 A．链头B．链尾C．链中D．任意位置 4．在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入缓冲区中，而打印机则从缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A．堆栈B．队列C．数组D．先性表 5．若已知一个栈的入栈序列是1，2，3，…，30，其输出序列是p1,p2,p3,…p n，若p1=30，则p10为（）。 A．11 B．20 C．19 D．21 6．循环队列A[m] 存放其元素，用front和rear分别表示队头及队尾，则循环队列满的条件是（）。 A．（rear+1)%m=front B．rear =front+1 C．rear=front D．（rear+1)%m-1=front 7．在一个栈顶指针为top的链栈中，将一个p指针所指的结点入栈，应执行（）。 A．top->next=p; B．p->next=top->next; top->next=p; C．p->next=top; top=p; D．p->next=top->next; top=top->next; 8．在一个栈顶指针为top的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。 A．x=top;top=top->next; B．x=top->data;

数据结构第3章栈和队列自测卷答案(供参考)

head 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。） （每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （ B ）1.栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 （ C ）2.若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n ，即n 是最先出栈的，根据栈的原理，n 必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，…，n ，则出栈的序列是n ，…，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （ B ）3.判定一个栈ST （最多元素为m0）为空的条件是

数据结构第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 班级 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是方式。 （ √ ）8. 两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别 设在这片存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （ B ）1.栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 （ C ）2.若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，

第3章-栈与队列习题参考答案

习题三参考答案 备注: 红色字体标明的是与书本内容有改动的内容。 一、选择题 1.在栈中存取数据的原则是（ B ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2．若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A．1234 B. 1324 C. 4321 D. 1423 3．在链栈中，进行出栈操作时（B ）。 A．需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素的类型 D. 无需对栈作任何差别 4．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（ A ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 5．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top==0 B.top==-1 C. top==maxSize D.top==maxSize-1 6．在队列中存取数据元素的原则是（ A ）。 A．先进先出 B. 先进后出 C. 后进后出 D. 没有限制 7．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 8．在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。 A．front==rear B. front!=rear C. front==rear+1 D. front==(rear+1)% maxSize 9.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首 和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（C ）。 A．rear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize 10.设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度 为（ B ）。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 二、填空题 1.栈是一种操作受限的特殊线性表，其特殊性体现在其插入和删除操作都限制在表尾进行。允许插入和删除 操作的一端称为栈顶，而另一端称为栈底。栈具有后进先出的特点。 2.栈也有两种存储结构，一种是顺序存储，另一种是链式存储；以这两种存储结构存储的栈分别称为顺序 栈和链栈。 3.在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top==0 ; 栈顶

第三章+栈和队列(参考答案)

第三章栈和队列 一、判断题 1、链栈的初始化是指开辟足够多的结点，然后置栈顶指针为 NULL。（×） 2、递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（×） 二、填空题 1、向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给___栈顶指针_____。 2、迷宫问题是一个回溯控制的问题，最好使用____栈______的方法来解决。 3、有如下递归过程： Void Print(int w) { int i; if (w!=0) { Print(w?1); for (i=1;i<=w;i++) printf(“%3d”,w); printf(“\n”); } } 调用语句print(4)的结果是__________。 1 2 2 3 3 3 4 4 4 4 4、假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句：_ S->next=R->next _________；___ R->next=S _______；R=S； 三、选择题 1、设有4个数据元素a1、a 2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a 3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A 2，第二次出栈得到的元素是 B 4；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C 1，第二次出队得到的元素是 D 2。经操作后，最后在栈中或队中的元素还有 E 2个。 供选择的答案： A～D：①a1 ②a2 ③ a3 ④a4 E：①1 ②2 ③ 3 ④ 0 2、栈是一种线性表，它的特点是 A 2。设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B 2；从栈中弹出（POP）一个元素时，变量T的值 C 1。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 6，变量T的值是 E 4。 供选择的答案： A：①先进先出②后进先出③进优于出④出优于进⑤随机进出 B，C：①加1 ②减1 ③不变④清⑤加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥a,c E：① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 3、在做进栈运算时，应先判别栈是否 A 2；在做退栈运算时，应先判别栈是否 B 1。当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的最大容量为 C 2。

栈和队列答案

栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A)。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j 个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是n，则pi 是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为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

第三章栈与队列 练习题

第三章栈与队列练习题 一、选择题 1、栈结构通常采用的两种存储结构是（ A ）。 A、顺序存储结构和链表存储结构 B、散列和索引 C、链表存储结构和数组 D、线性链表和非线性存储 2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（B） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3、向一个栈顶指针为HS的链栈中插入一个s结点时，则执行（） A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4、从一个栈顶指针为HS的链栈中删除一个结点，用x保存被删除结点的值，则执行（C） A、x=HS;HS=HS->next; B、HS=HS->next;x=HS->data; C、 x=HS->data;HS=HS->next; D、s->next=Hs;Hs=HS->next; 7、一个队列的入列序列是1，2，3，4，则队列的输出序列是（B ）//尾插入元素，头删除元素。 A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 9、循环队列SQ采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front和rear，则判定此循环队列为满的条件是（C）//不懂啊！！！ A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 11、用单链表表示的链式队列的队头在链表的（A）位置 A、链头 B、链尾 C、链中 12、判定一个链队列Q（最多元素为n个）为空的条件是（ A） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 14、在一个链队列Q中，删除一个结点需要执行的指令是（C） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、 Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next; 15、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（D） A、仅修改队头指针 B、仅修改队尾指针 C、队头尾指针都要修改 D、队头尾指针都可能要修改。 16、栈和队列的共同点是（C） A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 18、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是（B） A、2 B、 3 C、 5 D、 6 20、设有一顺序栈已经含有3个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（A） 0 maxsize-1

数据结构-第3章栈和队列自测卷答案

head 第3章 栈和队列 自测卷答案 姓名 班级 一、填空题（每空1分，共15分） 1. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 8.带表头结点的空循环双向链表的长度等于 0 。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU 中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ × ）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底 分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分）

数据结构 第3章 栈和队列练习题

第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为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 （2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX

数据结构第3章栈与队列习题

第3章栈与队列 一、单项选择题 1．元素A、Ｂ、C、D依次进顺序栈后，栈顶元素是，栈底元素是。 A．A B．B C．C D．D 2．经过以下栈运算后，x的值是。 InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x); A．a B．b C．1 D．0 3．已知一个栈的进栈序列是ABC，出栈序列为CBA，经过的栈操作是。 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 4．设一个栈的输入序列为A、B、C、D，则借助一个栈所得到的序列是。 A．A,B,C,D B．D,C,B,A C．A,C,D,B D．D,A,B,C 5．一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是。 A．edcba B．decba C．dceab D．abcde 6．已知一个栈的进栈序列是1，2，3，……,n，其输出序列的第一个元素是i，则第j个出栈元素是。 A．i B．n-i C．j-i+1 D．不确定 7．已知一个栈的进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,Pn，若p1=n，则pi的值。 A．i B．n-i C．n-i+1 D．不确定 8．设n个元素进栈序列是1，2，3，……，n，其输出序列是p1,p2,…,p n，若p1=3,则p2的值。 A．一定是2 B．一定是1

C．不可能是1 D．以上都不对 9．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=1,则p1的值。 A．可能是2 B．一定是1 C．不可能是2 D．不可能是3 10．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p3=3,则p1的值。 A．可能是2 B．一定是2 C．不可能是1 D．一定是1 11．设n个元素进栈序列是p1,p2,…,p n，其输出序列是1，2，3，……，n，若p n=1,则p i(1≤i≤n-1)的值。 A．n-i+1 B．n-i C．i D．有多种可能 12．判定一个顺序栈S为空的条件为。 A．S.top= =S.base B．S.top!= S.base C．S.top!= S.base+S.stacksize D．S.top= = S.base+S.stacksize 13．判定一个顺序栈S为栈满的条件是。 A．S.top-S.base= =S.stacksize B．S.top= = S.base C．S.top-S.base!=S.stacksize D．S.top!= S.base 14．链栈与顺序栈相比有一个明显的优点，即。 A．插入操作方便B．通常不会出现栈满的情况 C．不会出现栈空的情况D．删除操作更加方便 15．最不适合用作链栈的链表是。 A．只有表头指针没有表尾指针的循环双链表 B．只有表尾指针没有表头指针的循环双链表 C．只有表尾指针没有表头指针的循环单链表 D．只有表头指针没有表尾指针的循环单链表 16．如果以链表作为栈的存储结构，则退链栈操作时。 A．必须判别链栈是否满B．判别链栈元素的类型 C．必须判别链栈是否空D．对链栈不作任何判别