数据结构复习题3：栈与队列

秒速五厘米 2024-03-16 23:02 18阅读 0赞

> 1.[栈的介绍及基本运算（出栈、入栈、销毁栈等）][Link 1]  
> 2.[栈（中缀表达式的计算）][Link 2]  
> 3.[栈相关习题及详解(选择题和综合题) ][Link 3]  
> 4.[《数据结构》-第三章 栈和队列（习题）][-_]  
> 5.[栈的应用之括号匹配问题][Link 4]  
> 6.[栈结构之链栈详解（C语言版）注：博主有汇总][C]  
> 7.[【数据结构】栈与队列经典选择题][Link 5]  
> 8.[第三章 栈和队列（答案）][Link 6]  
> 9.[【考研】栈在表达式求值中的应用（真题分析）][Link 7]  
> 10.[数据结构课后习题–错题集][Link 8]  
> 11.[栈求表达式的值（超级详细）注：含汇总][Link 9]

> 非常优秀的讲解，学栈和队列必看视频！！！！  
> [【栈和队列练习题讲解-哔哩哔哩】 ][-_ 1]

#### 练习题3：栈和队列 ####

*   *  1.栈
     *  2.队列
     *  3.综合

### 1.栈 ###

1.设链表不带头结点且所有操作均在表头进行，则下列最不是和作为链栈的是（）  
A. 只有表头结点指针，没有表尾指针的双向循环链表  
B. 只有表尾结点指针，没有表头指针的双向循环链表  
C. 只有表头结点指针，没有表尾指针的单向循环链表  
D. 只有表尾结点指针，没有表头指针的单向循环链表

对于双向循环链表，不管是表头指针还是表尾指针，都可以很方便地找到表头结点，方便在表头做插入或删除操作。  
单循环链表通过尾指针可以很方便地找到表头结点，但通过头指针找尾结点则需要遍历一次链表。

2.向一个栈顶指针为top的链栈中插入一个x结点，则执行（）  
A. top->next=x B. x->next=top->next;top->next=x

C. x-next=top;top=x D. x->top->data;top=top->next

3.若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列为p1, p2，p3，…，pn，  
若p1=n，则pi为 ( )  
A．i B．n=i C．n-i+1 D．不确定

4.一个栈的输入序列为1,2,3…\*,n, 输出序列的第一个元素是i,则第j个输出元素是( )。  
A. i-j- 1 B. i-j C. j-i+ 1 D.不确定

5.若一个栈的输入序列是P1,P2.\*.,Pn输出序列是1,2,3,.,n,若P3=1,则P1的值( ).  
A. .可能是2 B.一定是2 C.不可能是2 D.不可能是3

6.设栈的初始状态为空，当字符序列“n1\_ ”作为栈的输入时，输出长度为3，且可用做  
C语言标识符的序列有()个。  
A.4 B. 5 C.3 D. 6

C语言的标识符不能以数字开头

7.采用共享栈的好处是( )。  
A.减少存取时间，降低发生上溢的可能 B.节省存储空间，降低发生上溢的可能  
C.减少存取时间，降低发生下溢的可能 D.节省存储空间，降低发生下溢的可能

存取栈中的元素都只需要0(1)的时间，所以减少存取时间无从谈起,排除A、C。另外，栈的插入和删除操作都是在栈顶进行的，只可能发生上溢(栈顶指针超出了最大范围)，而下溢是指当缓冲器空，还往外读。因此本题答案为B。

8.利用栈求表达式的值时，设立运算数栈OPEN.假设OPEN只有两个存储单元，则在下列  
表达式中，不会发生溢出的是( )。  
A. A-B\*(C-D) B. (A-B)*C-D C. (A-B*C)-D D. (A-B)\*(C-D)

9.链栈与顺序栈相比，比较明显的优点是（）  
A.插入操作更加方便  
B.删除操作更加方便  
C.入栈时不需要扩容

10.链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。  
A．x=top->data;top=top->link； B．top=top->link;x=top->link；  
C．x=top;top=top->link； D．x=top->link；  
答案：A  
top=top->link栈顶指针指向栈顶下一结点

typedef struct LinkStackNode {
        		//链栈类型定义
    	ElemType data;					//数据域
    	struct LinkStackNode* next;		//指针域
    }SNode,*LiStack;

11.若一个栈以向量V\[1…n\]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。

A．top++; V\[top\]=x; B．V\[top\]=x; top++;  
C．top–; V\[top\]=x; D．V\[top\]=x; top–;  
答案：C  
答案解析：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V\[1…n\]中，所以进栈时top指针先下移变为n，之后将元素x存储在V\[n\]。

附加：  
①.设栈的顺序存储空间为S（1：m)，初始状态为top=m+1，现经过一系列正常的入栈与退栈操作后，top=0，则栈中的元素个数为（C）。  
A 1 B m+1 C 不可能 D m  
②.设栈的顺序存储空间为S（1：m)，初始状态为top=m+1，现经过一系列正常的入栈与退栈操作后，top=1，则栈中的元素个数为（C）  
A 0 B m-1 C m D 1  
![在这里插入图片描述][c970703ef1794a0aa8d719901ef360c9.png]  
如图，top=0时，溢出，top=1时，新增了m个元素。  
关于top=0是上溢，初始状态中top=m+1不是下溢的问题，top=0发生在入栈操作中，是溢出，同理，top=m+1发生在出栈时才算下溢，此处只是以top=m+1来表明这是一个空栈。  
[栈的上溢和下溢问题][Link 10]

1-5 C C C D C 6-10 C B B C A

### 2.队列 ###

> 应用：树的遍历，图的广度优遍历，CPU资源分配，打印数据缓冲区  
> 标循环队列判断队满和队空的条件：  
> 队满：front=(rear+1)%size  
> 队空：front = rear

1.最不适合用作链式队列的链表是( )。  
A.只带队首指针的非循环双链表  
B.只带队首指针的循环双链表  
C.只带队尾指针的循环双链表  
D.只带队尾指针的循环单链表

由于非循环双链表只带队首指针，在执行入队操作时需要修改队尾结点的指针域，而查找队尾结点需要0(n)的时间。B、C和D均可在0(1)的时间内找到队首和队尾。

附加类似题目：  
①下列更合适表示队列的链表结构(B) A.单向链表 B.单向循环链表 C.双向链表 D.双向循环链表？

2.循环队列存储在数组A\[0…m\]中，则入队时的操作为（ ）。  
A. rear=rear+1 B. rear=(rear+1) mod (m-1)  
C. rear=(rear+1) mod m D. rear=(rear+1) mod (m+1)

3.用链接方式存储的队列，在进行删除运算时（ ）。  
A. 仅修改头指针 B. 仅修改尾指针  
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

【答案】D。一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也会丢失，因此需对队尾指针重新赋值。

4.已知循环队列的存储空间为数组A\[21\]，front 指向队头元案的前一一个位置，rear 指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为( )  
A.5 B. 6 C.16 D.17  
(3-8+21)%21=16  
循环队列：L=(n+r-f）%n 非循环队列：L=r-f  
从头结点开始数，一直数到尾巴结点(如果到来21 就回到0)  
9 10 11 12 13 14 15 16 17 18 19 20 0 1 2 3  
头结点指向的地方是空。（实现的时候也可以是尾结点指向是空）  
所以16个。

5.若用数组A\[0…5\]来实现循环队列，且当前rear和front的值分别为1和5，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（　）。  
A. 3和4 B.3和0 C.5和0 D.5和1

front=5 循环队列，当出队列（删除）时front=(front+1)%6=0  
rear=1,每次入队列（加入）时 rear=(rear+1)%6=2 ,每二次再加入元素时rear=(2+1)%6=3

6.下列关于顺序结构实现循环队列的说法，正确的是（)  
A.循环队列的长度通常都不固定  
B.直接用队头和队尾在同一个位置可以判断循环队列是否为满  
C.通过设置计数的方式可以判断队列空或者满  
D.循环队列是一种非线性数据结构

队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的  
A错误：循环队列的长度都是固定的  
B错误：队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断  
C正确：设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空  
D错误：循环队列也是队列的一种，是一种特殊的线性数据结构

7.队列的先进先出特性是指( AD )。  
A.最后插入队列中的元素总是最后被删除  
B.当同时进行插入、删除操作时，总是插入操作优先  
C.每当有删除操作时，总要先做一次插入操作  
D.每次从队中删除的总是最早插入的元素

8.循环队列的存储空间为Q(1:40)，初始状态为front=rear=40，经过一系列正常的入队和出队操作后，front=rear=15，此后又退出一个元素，则循环队列中的元素个数为（A）  
A 39或0且产生下溢错误 B 14 C 40 D 15

元素个数 =（队尾-对头+容量）%容量  
第一种：通过计算，为0，说明为空，空队出队下溢。  
第二种：从16开始插入，绕一圈再到15，插入40个元素，退一个，39个元素。  
![在这里插入图片描述][97f234b10b894d7a8004ae795f15eeee.png]

附加：  
循环队列的存储空间为Q(1:100)，初始状态为front=rear=100，经过一系列正常的入队和出队操作后，front=rear=99，则循环队列中的元素个数为（D）  
A 1 B 2 C 99 D 0或100

实际做题过程中，类似的题直接带公式计算即可，不用考虑太多。（疑点：这两道题没有考虑留出空位的问题）

1- 5 A D D D C B 6-8 C AD A

### 3.综合 ###

1.设有一个递归算法如下：

int fact(int n) {
         //n大于等于 0
       if(n<=0)    return 1;
       else      return n*fact(n-1);
     }

则计算 fact(n) 需要调用该函数的次数为（ A ）。  
A.n+1 B. n-1 C. n D. n+2

特殊值法。设 n=0，易知仅调用一次 fact(n) 函数，故选 A 。

2.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机 将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ A ）。  
A.队列 B .栈 C.线性表 D.有序

解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。而**递归调用、函数调用、表达式求值均用到了栈的后进先出性质。**  
3.链栈(不带头结点)执行Pop操作，并将出栈的元素存在x中，应该执行  
【答案】x=top ->data; top=top- >next

4.向一个栈顶指针为top的链栈(不带头结点)中插入一个x结点，则执行  
【答案】x->next=top; top=x

5.下面关于栈和队列的说法中错误的是（AB）  
A.队列和栈通常都使用链表实现  
B.队列和栈都只能从两端插入、删除数据  
C.队列和栈都不支持随机访问和随机插入  
D.队列是“先入先出”，栈是“先入后出”

A错误：栈是尾部插入和删除，一般使用顺序表实现，队列是头部删除尾部插入，一般使用链表实现  
B错误：栈是后进先出，尾部插入和删除；队列是先进先出，尾部插入头部删除  
C正确：栈只能访问栈顶元素，不支持随机访问，队列也不支持  
D正确：栈和队列的特性

[Link 1]: https://blog.csdn.net/weixin_53161762/article/details/123567365
[Link 2]: https://blog.csdn.net/waldeinNJU/article/details/108446855
[Link 3]: https://blog.csdn.net/qq_22073849/article/details/78355247
[-_]: https://blog.csdn.net/weixin_41831593/article/details/119146378
[Link 4]: https://blog.csdn.net/weixin_40243308/article/details/89301391
[C]: https://blog.csdn.net/qq_44075108/article/details/109333557
[Link 5]: https://blog.csdn.net/qq_74310471/article/details/129844542
[Link 6]: https://blog.csdn.net/qq_41998273/article/details/89349393
[Link 7]: https://blog.csdn.net/qq_34438969/article/details/126834528
[Link 8]: https://blog.csdn.net/weixin_43102407/article/details/94297143
[Link 9]: http://data.biancheng.net/view/288.html
[-_ 1]: https://b23.tv/SDX6IZd
[c970703ef1794a0aa8d719901ef360c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a7beb4cdb1a04a67b2a62341a11899bc.png
[Link 10]: https://blog.csdn.net/qq_51184727/article/details/131422320
[97f234b10b894d7a8004ae795f15eeee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b3eb579b097245b7859b836e46fef09e.png