牛客刷题笔记--(栈专项练习)_若采用带头、尾指针的单向链表表示一个堆栈,那么该堆栈的栈顶指针top应该如何设置

知识点

对于栈用栈顶指针表示栈顶，而栈的插入和删除操作均在栈顶进行。对于队列用队头和队尾指针分别表示允许插入和删除的一端。因此对于顺序存储和链式存储的栈和队列，进行插入和删除运算的时间复杂度均为O(1)。
链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况，顺序栈先要预定空间，而链式栈不需要预定空间，采用链栈不必预先估计栈的最大容量，只要系统有可用空间，就不会溢出
在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化.
在n个有序顺序表中插入一个新元素，并保持原来的顺序不变，平均要移动的元素次数是n/2
设计一个算法时，考虑的因素很多。首先要满足算法的五个基本特性：确定性，可行性，有穷性，输入，输出。其次，再从可读性，健壮性，低耦合高效率，低存储等方面进行优化。
由栈的定义可得：它只能在栈顶进行插入和删除操作，只能在栈顶进栈、入栈、压栈，是把新元素放在现在栈顶的上面，删除是把当前的栈顶弹出栈，当前栈顶的下一个元素变成新的栈顶。根据栈的定义可知，栈只可以访问栈顶元素，不可以访问栈底元素

对于符号栈来说，如果当前符号优先级要小于栈顶元素，那么就弹出栈顶元素及对应的操作数，计算结果入操作数栈，然后再把当前符号压入栈中。
栈要是能插入就违背了栈的设计原则

在CPU执行程序的过程中，会执行有关的堆栈操作指令。执行这样的指令，无论是压入堆栈还是弹出堆栈，堆栈指针和栈顶将随着指令的执行而发生改变。同时，堆栈中的数据也会随着压入数据的不同而改变。唯一不会改变的就是在堆栈初始化时设置的堆栈的底。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
在函数调用过程中形成嵌套时，则应使最后被调用的函数最先返回，后进先出，栈。

前中后缀表达式的特点，以及相互转换的规则及例子:

题型

元素的出栈顺序
共享栈判断栈满
栈中元素个数
栈的最大容量
中缀表达式 操作数栈 符号栈
根据出栈序列判断栈的最小容量

1两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端（√）。
使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸

2 下列关于栈的叙述中，错误的是 。（I、Ⅲ、Ⅳ）

Ⅰ．采用非递归方式重写递归程序时必须使用栈

Ⅱ．函数调用时，系统要用栈保存必要的信息

Ⅲ．只要确定了入桟次序，即可确定出栈次序

Ⅳ．栈是一种受限的线性表，允许在其两端进行操作

I的反例：计算斐波拉契数列迭代实现只需要一个循环即可实现。Ⅲ的反例：入栈序列为1、2，进行如下操作PUSH、PUSH、POP、POP，出栈次序为2、1；进行如下操作PUSH、POP、PUSH、POP，出栈次序为1、2。Ⅳ，栈是一种受限的线性表，只允许在一端进行操作。Ⅱ正确。

1.一直递归下去，在最深层返回值
4.只允许在一端进行操作

3 若用数组S[0…n]作为两个栈S1和S2的存储结构，对任何一个栈只有当S全满时才不能做入栈操作。为这两个栈分配空间的最佳方案是 A

S1的栈底位置为0，S2的栈底位置为n

S1的栈底位置为0，S2的栈底位置为n/2

S1的栈底位置为1，S2的栈底位置为n/2

答案：A
两个栈的栈底一个在数组第一个元素，朝着数组正方向增长
另一个在数组最后一个元素，朝着数组索引减小的方向增长。
当两个栈的栈顶相等是，表明数组满了，不能继续入栈

4 若一序列进栈顺序为e1,e2,e3,e4,e5,问存在多少种可能的出栈序列（42）


5 请问刚进入func函数时，参数在栈中的形式可能为 （左侧为地址，右侧为数据—） D

0x0013FCF0 0x61616161
0x0013FCF4 0x22222222
0x0013FCF8 0x00000000

0x0013FCF0 0x22222222
0x0013FCF4 0x0013FCF8
0x0013FCF8 0x61616161

0x0013FCF0 0x22222222
0x0013FCF4 0x61616161
0x0013FCF8 0x00000000

0x0013FCF0 0x0013FCF8
0x0013FCF4 0x22222222
0x0013FCF8 0x61616161

选D。 1，对于x86，栈的增长方向是从大地址到小地址
2，对于函数调用，参数的入栈顺序是从右向左
3，函数调用入栈顺序是 右边参数–>左边参数–>函数返回地址
符合的只有D
C明显不对，即使栈增长方向是从小地址到大地址，0x00000000也明显不是函数返回地址

答案：D
需要注意两点：
第一是函数参数的入栈顺序，从右到左；
第二是栈的存储是从高地址到低地址。

---

0x0013FCF0 0x0013FCF8
0x0013FCF4 0x22222222
0x0013FCF8 0x61616161
看选项D。
AC很容易排除掉，因为函数返回的地址是不正确的~

6 以下那种结构，平均来讲获取任意一个指定值最快？(D)

二叉排序树

队列

栈

哈希表
1
2
3
4
5
6
7

二叉排序树中，查找的平均时间复杂度是O(logn)；
对于栈和队列来说，查找就意味着把元素挨个出栈或者出队，故平均时间复杂度是O(n)；
而哈希表，直接通过关键码查找元素，平均为O(1)；
故哈希表速度是最快的

7 用俩个栈模拟实现一个队列，如果栈的容量分别是O和P(O>P),那么模拟实现的队列最大容量是多少？C

O+P

2O+1

2P+1

2O-1

解释：
大概就是用容量小的栈作为缓冲，先从大栈出n个元素到小栈，在压入n+1个元素到大栈
https://www.cnblogs.com/eniac12/p/4865158.html
容量指的是，同一时间，两个栈里面，能存放的最多的元素的个数（要求能够满足按队列顺序出栈）。是同一个时间，某一个固定的时刻。不是累计可以放多少个元素，如果是累计可以放多少个元素的话，那么一次放一个出一个，无限次之后，容量岂不是 无限大了
第二步进n 个，也是可以的。但是如果第二步只进n个的话，你计算出来的 最大容量结果就是 2n。没有进 n+1 个结果好，也可以进 n+2个，容易知道，如果第二步 进 n+2 个的话，就怎么出也没法正常出栈了，因为限压出大栈剩下的n+2，才能压出n+1,这不符合队列的先进先出的要求。所以，综上，最多就能进 （n+1） +（n） 个元素。左侧进栈深度为 n+1 右侧出栈深度是 n
https://blog.csdn.net/SCS199411/article/details/91443928

8 下列情况中，不能使用栈（stack）来解决问题的是？D

将数学表达式转换为后辍形式

实现递归算法

高级编程语言的过程调用

操作系统分配资源（如CPU）
1
2
3
4
5
6
7

资源分配有多种分配策略，简单的可以是任务先到先执行，可以使用队列来完成
资源的调度与分配用到了多种分配方式，其中最简单的就是，先来先服务，后面又根据实际情况在此基础上综合了优先权和短进程等方面的考虑。所以像栈这种后进先出的就不合适了，所以D是不能的
栈是FILO
对于操作系统中CPU的资源分配是根据时间片来轮流分配的

9 下列关于堆和栈的区别描述错误的有？ A

申请方式的不同，堆是系统自动分配，栈是自己申请

栈的大小是固定的，堆的大小受限于系统中有效的虚拟内存

栈的空间由系统决定何时释放，堆需要自己决定何时去释放

堆的使用容易产生碎片，但是用起来最方便
1
2
3
4
5
6
7

堆：自己做菜自己吃，什么时候收盘子自己知道，但是可能会浪费（产生碎片），因为可能自己一个人吃不完。 桟：公司食堂，你吃饭由食堂工作人员帮你打饭和分配位置，吃完了工作人员帮你收盘子。你浪费粮食（碎片）那是不可能的，因为食堂会把碎片拿去喂猪。

1.栈内存操作系统来分配，堆内存由程序员自己来分配。
2.栈由系统自动分配，只要栈剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

操作系统中所说的堆内存和 栈内存 ，在操作上有上述的特点，这里的堆内存实际上指的就是（满足堆内存性质的） 优先队列 的一种数据结构，第1个元素有最高的优先权 ；栈内存实际上就是满足先进后出的性质的数学或数据结构

10 若栈采用链式存储结构,则下列说法中正确的是(D)

需要判断栈满但不需要判断栈空

不需要判断栈满也不需要判断栈空

需要判断栈满且需要判断栈空

不需要判断栈满但需要判断栈空
链栈由于采用了链表的方式作为存储方式，入栈时，使用malloc申请空间后，用指针相连接，所以节点个数没有限制，但是出栈时，如果栈中的元素个数为0，则不能继续出栈，所以需要判断当前栈是否为空

11 表达式3*2^{(4+2*2-6*3)-5，求值过程中当扫描到6时，对象栈和算符栈为（D），其中}为乘幂。

3，2，8;*^-

3，2，4，2，2;*^+*-

3，2，4，2，2,;*^(+*-

3，2，8;*^(-
1
2
3
4
5
6
7

12 下面的一些说法哪些是正确的：( BC)

缓存策略中基于LRU的淘汰策略，在缓存满时，会把最近进入缓存的数据先淘汰，以保持高的命中率

中缀表达式A+(B+C)*D的后缀表但式为:ABC+D*+

堆栈是一种LIFO的数据结构

高级语言通过编译或者即时编译(JIT)后成为汇编语言被机器装载执行

TCP协议和UDP协议都在IP协议之上，TCP是面向连接的,UDP是面向非连接的，但无论TCP还是UDP建立通信都需要一次握手，以确保对方的端口已经打开

现代的操作系统一般都分为用户态和内核态，用户态和内核态的切换是经常发生的，程序员不需要对内核态和用户态的切换进行编程关注


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

13 以下哪个不是分配在栈上的？C

函数内局部变量

函数内局部指针变量

函数内动态申请的对象

函数内指向动态申请的对象的局部指针变量
1
2
3
4
5
6
7

内存分为堆和栈，简单来说：栈保存变量和对象的引用，堆保存对象

首先不同数据类型储存方式不一样，数据类型分为简单数据类型和复杂数据类型，string，number，boolean，undefined，null是简单类型变量，对象是复杂类型变量；内存存储分为栈和堆，简单类型变量储存在栈中，而对象的内容储存在堆中，只是指向对象的内存地址储存在栈中。

14 设栈的顺序存储空间为 S(1:m) ，初始状态为 top=0 。现经过一系列正常的入栈与退栈操作后， top=m+1 ，则栈中的元素个数为（ A）

不可能

m+1

0

m
1
2
3
4
5
6
7

此栈为顺序栈，存储空间为S(1:m)，栈顶指针初始状态为top=0，即栈空状态；当栈内有一个元素时，top=1,；当处于栈满状态时，top=m。由此可见，栈顶指针top的取值范围是[0,m]之间的整数，因此top=m+1是不可能事件。

应注意的是，如果用一维数组来作为顺序栈的存储结构，则存储空间为S(0:m-1) ，易与题述混淆，此时栈顶指针初始状态为top=-1，即栈空状态；当栈内有一个元素时，top=0,；当处于栈满状态时，top=m-1。由此可见，当栈非空时，栈顶指针top与数组下标相对应。栈顶指针top的取值范围是[-1,m-1]之间的整数。

15 下列叙述中正确的是（ A）

在栈中，栈顶指针的动态变化决定栈中元素的个数

在循环队列中，队尾指针的动态变化决定队列的长度

在循环链表中，头指针和链尾指针的动态变化决定链表的长度

在线性链表中，头指针和链尾指针的动态变化决定链表的长度
1
2
3
4
5
6
7

在栈中，栈底指针保持不变，有元素入栈，栈顶指名增加，有元素出栈，栈顶指针减少。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的。线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入或删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度。故本题答案为 A 选项。

16 递归式的先序遍历一个n节点，深度为d的二叉树，需要栈空间的大小为______。B

O（n）

O（d）

O（logn）

O（nlogn）
1
2
3
4
5
6
7

因为二叉树并不一定是平衡的，也就是深度d！=logn，有可能d > > logn(远大于)，所以栈大小应该是O（d）
在从根向下遍历中，每次先转移到左子树上，而右边则需要暂存起来，因此，最多需要的暂存空间需要d个
从第1层到第d-1层，每次都要压一个有孩子结点入栈，所以要d-1次，因此O（d）

17 若采用带头、尾指针的单向链表表示一个栈，那么该堆栈的栈顶指针top应该如何设置（A）

将表头项设置为top

将链表尾设置为top

随便哪端作为top都可以

链表头、尾都不适合作为top
1
2
3
4
5
6
7

这里头尾指针是链表的，和栈没关系，即头指针≠栈底，尾指针≠栈顶。
出栈入栈都是针对栈顶元素进行的操作，考虑到这个链表是单向的（从前往后不能从后往前），所以把头指针设成top，这样出栈入栈就是对表头操作，时间上快很多。

表尾为top 删除的时候复杂度太大

18 两个顺序栈共享数组S【0…n-1】，其中第一个栈的栈顶指针top1的初始值为-1，第二个栈的栈顶指针top2的初始值为n，则判断该共享栈满的条件是（ B ）

top2+2=top1

top1+1=top2

top1+2=top2

top2+1=top1

简单概括为：两个栈顶指针相邻时栈满。
栈底放两端，分别为-1和maxsize,入栈方向由两端延伸至相遇，左栈+1=右栈表示栈满。

这道题要理解 “第一个栈的栈顶指针top1的初始值为-1，第二个栈的栈顶指针top2的初始值为n“，这句话表明一个栈从头开始，另一个栈则是从尾开始，随着两栈的增加，栈顶指针不断的接近，当top1+1= top2时就代表满了

19 若栈采用顺序存储方式存储，现两栈共享空间V[1…m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B ）。

top[1]+top[2]=m

top[1]+1=top[2]

top[2]-top[1]|=0

top[1]=top[2]

两栈相对压栈，如图所示，由于空间为1~m，所以B就出来了，D呢，我觉得 如果top[1]=top[2]的时候，这是不成立的，这样必有一个栈已经是满的，无法实现

20 设栈的存储空间为 S(1:50) ，初始状态为 top=51 。现经过一系列正常的入栈与退栈操作后， top=50 ，则栈中的元素个数为（ 1）

栈的顺序存储空间为S(1: 50)，初始状态top=51，所以这个栈是50在栈底，1是开口向上的。经过一系列入栈、出栈之后，Top=50。那么此时栈中元素=51-50=1，因此这题选择A。

栈的所谓“初始状态”，即为空栈时的状态。空栈时top指向51，且栈s的最大容量为50，则此栈的1是开口向上的。现在top指向50，则说明栈中有一个元素

栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行。入栈运算即在栈顶位置插入一个新元素，退栈运算即取出栈顶元素赋予指定变量。栈为空时，栈顶指针 top=0 ，经过入栈和退栈运算，指针始终指向栈顶元素。初始状态为 top=51 ，当 top=50 时，则栈中 S(50:51) 存储着元素， 51-50=1 ，元素个数为 1 。故本题答案为 A 选项。

21 在Windows中，下列关于堆和栈的说法中错误的是? B

堆都是动态分配的，没有静态分配的堆;栈有静态分配和动态分配2种分配方式。

堆的生长方向是向下的，即向着内存地址减小的方向增长；栈的生长方向是向上的，即向着内存地址增加的方向增长。

对堆的频繁new/delete会造成内存空间的不连续，从而造成大量的碎片;栈则不会存在这个问题

栈是由编译器自动治理；堆的释放工作由程序员控制，轻易产生内存泄露。
1
2
3
4
5
6
7

堆是不连续的，生长方向是向上的，即向着内存地址增大的方向增长；栈是连续的，生长方向是向下的，即向着内存地址减小的方向增长

栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。

1、栈区（stack）由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap）一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事。
区别：

1. 管理方式：对于栈来讲，是由编译器自动管理，无需我们手工控制；对于堆来说，释放工作由程序员控制，容易产生内存溢出。
2. 空间大小：堆内存几乎是没有什么限制。栈一般都是有一定的空间大小。
3. 碎片问题：对于堆来讲，频繁的new/delete会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题。
4. 分配方式：堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。
5. 分配效率：栈的效率比较高。堆的效率比栈要低得多。
6. 增长方向：堆的增长方向是从程序低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况可能不是这样的，与CPU的体系结构有关）

注意：这里的堆和数据结构中的堆没啥关系。

22 假设栈初始为空，将中缀表达式转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是 （B）

+(*-

+(-*

/+(*-*

/+-*
1
2
3
4
5
6
7

一共俩栈，操作数栈和符号栈。
对于符号栈来说，
如果当前符号优先级要小于栈顶元素，那么就弹出栈顶元素及对应的操作数，计算结果入操作数栈，然后再把当前符号压入栈中。就比如栈顶现在是*，当前符号是+，那么就先弹出两个操作数a和b，然后把a*b的结果再压回操作数栈，再把+入符号栈。
如果当前符号优先级要大于栈顶元素，那么就直接符号入栈。就比如栈顶现在是+，当前符号是*，那就直接把*压入符号栈。
回到本题，除了加减乘除还有个左括号，其优先级要大于其他的符号，如果栈顶是*，当前符号是(，那么就压入(，不过这个题还没出这种情况。当遇到)时，不断从符号栈弹出运算符，并弹出操作数依次计算，直到符号栈栈顶是左括号，弹出左括号，并把括号里计算的结果压入操作数栈。
1
2
3
4
5

23 下列说法错误的是 (BD)

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,这种形式的栈也称为顺序栈

top=0 时为空栈,元素进栈时指针 top 不断地减 1

当top等于数组的最大下标值时则栈满

栈不能对输入序列部分或全局起求逆作用
1
2
3
4
5
6
7

A正确，虽然链栈也可以实现地址连续，但无法做到依次存放数据元素，因为除了元素域还需要存放指针域。因此满足条件的只有顺序栈。
B错误，top= -1时为空栈，top=0只能说明栈中只有一个元素，并且元素进栈时top应该自增
C正确，top所指向的对象永远是栈顶元素
D错误，栈的特性（先进后出）就决定了可以作为求逆元素的辅助空间。所谓求逆运算就是ABC依次入栈，输出CBA。

对于C选项，当用数组来存储栈时，栈空时top = -1，top每次指向栈顶的下一个位置，故栈满时top指向的位置就是数组的最大下标值。

24 下面的一些说法哪些是正确的：( BC )

缓存策略中基于LRU的淘汰策略，在缓存满时，会把最近进入缓存的数据先淘汰，以保持高的命中率

中缀表达式A+(B+C)*D的后缀表达式为: ABC+D*+

堆栈是一种LIFO的数据结构

高级语言通过编译或者即时编译(JIT)后成为汇编语言被机器装载执行

TCP协议和UDP协议都在IP协议之上，TCP是面向连接的,UDP是面向非连接的，但无论TCP还是UDP建立通信都需要一次握手，以确保对方的端口已经打开

现代的操作系统一般都分为用户态和内核态，用户态和内核态的切换是经常发生的，程序员不需要对内核态和用户态的切换进行编程关注
1
2
3
4
5
6
7
8
9
10
11

LRU全程应该是last recent used，即会删除最近一段时间访问少的内容

一般的编译器，是先将高级语言转换成汇编语言（中间代码），然后在汇编的基础上优化生成OBJ目标代码，最后Link成可执行文件

我们知道内核态和用户态的区别就是对于资源的访问权限不一样。那么我们如何实现这样的权限？这需要对程序执行的每一条指令进行检查才能完成, 这种检查就是地址翻译。程序发出一条指令都需要经过这个地址翻译过程，从而我们通过控制翻译，就可以限制程序对资源的访问。2.而内核态对所有资源都有特权, 所以内核程序都是直接绕过内存地址翻译而直接执行特权指令。

25 从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( D )命令。

x=top;top=top->next;

top=top->next;x=top->data;

x=top->data;

x=top->data;top=top->next;
1
2
3
4
5
6
7

AD有争议，不过都选的D

26 后缀式 ab+cd+/可用表达式（D ）来表示

a+b/c+d

(a+b)/c+d

a+b/(c+d)

(a+b)/(c+d)

后缀表达式不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行，不再考虑运算符的优先规则。
最后一个操作是’/’，而且前面是一个+操作，后面没有操作，可知/操作最后进行，由此可得，另外两个操作数是a+b和c+d，因此表达式为D (a+b)/(c+d)

过程如下：
a入栈
b入栈
遇到+号，取栈里的两个操作数，即a和b，计算a+b，结果入栈
c入栈
d入栈
遇到+号，取栈里的两个操作数，即c和d，计算c+d，结果入栈
遇到/，取栈里的两个操作数，即（a+b）和（c+d），计算（ a+b）/（c+d）

第一个的后缀 abc/+d+
第二个的后缀 ab+c/d+
第三个的后缀 abcd+/+

27 利用栈完成数制转换，将十进制的169转换为八进制，出栈序列为（A）

251

521

215

152

169/8 = 21 余1
21/8 = 2 余5
2/8 = 0 余 2
余数倒过来 251
每次求余后余数依次进栈，顺序为152，结果从依次从栈中弹出为251

169转化8进制：169=2*8^2+5*8^1+1*8^0，栈是先进后出，那么出来的数则为251 
1

28 若一个栈以向量V…存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是©。

top=top+1; V[top]=x

V[top]=x; top=top+1

top=top-1; V[top]=x

V[top]=x; top=top-1

1.如果初始化top=-1，则栈底地址到栈顶是由小到大的，这样top=-1的时候才表示栈为空
2.如果初始化top=n+1，（n是表示栈的容量），则栈底地址到栈顶是由大到小的，这样top=n+1的时候才表示栈为空
题目显然符合2情况，所以top - -才符合栈顶指针向上移动

29 单链表实现的栈，栈顶指针为Top(仅仅是一个指针)，入栈一个P节点时，其操作步骤为：B

Top->next=p;

p->next=Top->next;Top->next=p;

p->next=Top;Top=p->next;

p->next=Top;Top=Top->next;

单链表的栈，栈顶就是第一个节点，这里可以有两种实现：
1、top节点表示真实的栈顶节点；
2、top节点只是一个标识，其next才是栈顶节点。
对于1，入栈操作是在top前插入节点：p->next = top; top = p;
对于2，入栈操作是在top后插入节点：p->next = top->next; top->next = p;
所以，选B。

30 某表达式的前缀形式为"±*^ABCD/E/F+GH",它的中缀形式为©

A^B*C-D+E/F/G+H

A^B*(C-D)+(E/F)/G+H

A^B*C-D+E/(F/(G+H))

A^B*(C-D)+E/(F/(G+H))
1
2
3
4
5
6
7

前缀表达式的计算机求值特点：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

根据前序遍历（±^ABCD/E/F+GH）和表达式的性质得到二叉树如下：

中序遍历为：A^BC-D+E/F/(G+H)
注意：遍历是要考虑运算符的优先级

31 堆栈溢出一般是由什么原因导致的？BC

函数代码长度过长

循环的递归调用

大数据结构的局部变量

代码运行时错误
1
2
3
4
5
6
7

1 代码存储在程序区，与栈没有关系。
2 递归涉及到压栈入栈。
3 局部变量存在栈区。
4 栈的大小是固定的。
1、内存泄露，比如某一数组原先已定义好大小，但是在后续操作中存放的个数超出这一既定长度，会导致堆栈溢出
2、由于程序员动态申请的内存块使用后未立即释放，导致内存区不够用，也会导致堆栈溢出
3、程序陷入死循环，往内存写数据，不断地消耗内存空间
4、程序本身运行起来就要消耗一定大小的内存，但是系统提供的实际内存不够，比如JVM虚拟内存不够让程序使用

32 以下哪个选项中可能应用到栈。ABCD

递归

快速排序（非递归程序用栈实现）

表达式求值

树的遍历
1
2
3
4
5
6
7

A，递归肯定用到栈的，存放局部变量，返回地址等，不过该栈是操作系统提供的栈。
B，快速排序的非递归实现，栈中存放要进行一遍快排的起始位置，利用栈先进后出的方式，模拟递归的过程。
C，表达式求值，将中序表达式转换为前序或后序时，需要用栈存放符号。
D，树的深度优先遍历，用栈记录遍历过的元素，以便进行回溯。

33 a - (b * c + d) / e的后缀表达式是（C）

abcde-*+/

abcd*+e/-

abc*d+e/-

abc*de+/-
1
2
3
4
5
6
7

后缀表达式就是将运算符号移到两个运算对象后面，但不影响原有计算顺序
后缀表达式是方便计算机运行的，所以这么考虑，每个运算符号前面两个变量就是运算表达式，该运算表达式满足原式的运算人为习惯，如括号内先运算这些，同时，每一个表达式运算后可视为一个新变量。结合该规律，很容易选择c~

34 下列叙述中正确的是（AD）

在循环队列中，队头指针和队尾指针的动态变化决定队列的长度

在循环队列中，队尾指针的动态变化决定队列的长度

在带链的队列中，队头指针与队尾指针的动态变化决定队列的长度

在带链的栈中，栈顶指针的动态变化决定栈中元素的个数
1
2
3
4
5
6
7

在栈中，栈底保持不变，有元素入栈，栈顶指针增加；有元素出栈，栈顶指针减小。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。在循环链表中，前一个结点指向后一个结点，而最后一个结点指向头结点，只有头结点是固定的。线性链表中，由于前一个结点包含下一个结点的指针，尾结点指针为空，要插入删除元素，只需要改变相应位置的结点指针即可，头指针和尾指针无法决定链表长度。

C中，带链的队列中，队头指针始终指向头结点，头结点中的指针指向队头，所以队头指针实际上是固定的，删除队员只会修改头结点中的指针。而队尾插入队员，则需要先创建一个结点，插入到队列后，然后让队尾指针指向它，所以队尾指针会动态变化。(所以队头指针应该是固定不变的，C错. )

35 已知栈s允许在两端出栈，但只允许在一端入栈;队列Q只允许在一 端入队列，在另一端出队列。设栈s和队列Q的初始状态为空, el,e2,e3, e4,e5,e6依次通过栈S,一个元素出栈后即进队列Q，则不可能得到的出队列的顺序是( C）

e2,e4,e3,e5,e1,e6

e2,e5,el,e3,e4,e6

e5,e1,e6,e3,e2 ,e4

e4,el,e3,e5,e2,e6
1
2
3
4
5
6
7

选C
以下假设栈的内容为e1,e2,e3时，e1为栈底，e3为栈顶。
出队序列和入队序列相同，所以只求入队序列就可以了。

选项A：e2,e4,e3,e5,e1,e6
1、入栈e1，e2，出栈e2，然后e2入队列Q，此时栈S内容为e1
2、入栈e3，e4，分别出栈e4，e3，然后e4，e3依次入队列Q，此时栈内容为e1
3、入栈e5，分别出栈e5，e1，然后e5，e1依次入队列Q，此时栈内容为空
4、入栈e6，出栈e6，然后e6入队列Q，此时栈内容为空

选项B：e2,e5,el,e3,e4,e6
1、入栈e1，e2，出栈e2，然后e2入队列Q，此时栈S内容为e1
2、入栈e3，e4，e5，分别出栈e5，e1，e3，e4，然后e5，e1，e3，e4依次入队列Q，此时队列为空
3、入栈e6，出栈e6，然后e6入队列Q，此时栈内容为空

选项C：e5,e1,e6,e3,e2,e4
1、入栈e1，e2，e3，e4，e5，分别出栈e5，e1，然后e5，e1入队列Q，此时栈S内容为e2，e3，e4
2、入栈e6，出栈e6，然后e6入队列Q，此时栈内容为e2，e3，e4
3、栈内容为e2，e3，e4，此时想让e3出栈是不可能的，所以C不对

选项D：e4,el,e3,e5,e2,e6
1、入栈e1，e2，e3，e4，分别出栈e4，e1，e3，然后e4，e1，e3依次入队列Q，此时栈内容为e2
2、入栈e5，分别出栈e5，e2，然后e5，e2依次入队列Q，此时栈内容为空
3、入栈e6，出栈e6，然后e6入队列Q，此时栈内容为空

选项一个个的套就可以了，遵守题目规定的入栈出栈、入队出队顺序即可，想让谁入队，就得先让他出栈，他要想出栈，一定要在栈的两端