栈专项练习_栈 练习

栈按照后进先出原则存储数据

1. 在栈中，（栈的底）保持不变。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

2. 递归先序遍历一个节点为n，深度为d的二叉树，需要栈空间的大小为O(d) 

在从根向下遍历中，每次先转移到左子树上，而右边则需要暂存起来。

因为二叉树并不一定是平衡的，也就是深度d！=logn，有可能d>>logn。。所以栈大小应该是O（d）

3. 下列关于堆和栈（以 C++ 语言来说）的区别描述错误的有？ A

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

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

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

D.堆的使用容易产生碎片，但是用起来最方便

栈是系统自动分配的，堆是人为分配的；

栈的地址是自上向下，朝内存地址递减，堆则相反；

其次，栈的内存分配是由系统自动管理，而堆需要人为通过new、delete等形式分配、释放内存，容易产生碎片化严重的问题；

栈一般用于临时变量的创建，而堆用于数据更改等方面

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

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

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

C.堆栈是一种 LIFO 的数据结构

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

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

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

A. LRU的过程如下（简单理解，访问的频率越高越不该丢弃）

   1.新数据插入到链表头部；

   2.每当缓存命中（即缓存数据被访问），则将数据移到链表头部；

   3.当链表满的时候，将链表尾部的数据丢弃。

   A恰好说反了

B.简单方法：

   1.先将中缀表达式加括号：(A+((B+C)*D));

   2.再把运算符移到括号后面（前缀移到前面）: (A((B C)+D)*)+;

   3.把括号去掉：ABC+D*+。

C. LIFO：Last In First Out（后进先出）

D.汇编语言也并不能被机器执行，机器可以执行的是二进制的机器语言。

E. TCP建立通信需要三次握手，而UDP,在传送数据前不需要先建立连接，远地的主机在收到UDP报文后也不需要给出任何确认。

F.程序员是可以通过调用fork()函数的方式进行切换的。

5. 便于插入和删除的容器是（ACD）

A. list

B. vector  ×

C. map

D. set 

vector 底层数据结构为数组，支持快速随机访问

list 底层数据结构为双向链表，支持快速增删

map、set、都是STL关联容器，支持快速增删

6. 栈和队列是一种非线性数据结构（×）

数据元素间有线性关系——线性结构（所谓线性关系：除第一个元素外，其他元素有且只有一个前驱；除最后一个元素外，其他元素有且只有一个后继）

常用的线性结构：线性表、栈、队列、双队列、数组、串

常用的非线性结构：二维数组、多维数组、树（二叉树等）、图、广义表

7. 栈应用的典型实例是（用“算符优先法进行表达式求值”） 

栈的典型应用：表达式求值，括号匹配，递归函数调用，数制转换等

队列的典型应用：打印队列，事件排队

8. 已知算术表达式的中缀表达式为a-(b+c/d)*e,其后缀形式为( abcd/+e*- )

9. 某表达式的前缀形式为"+-*^ABCD/E/F+GH",它的中缀形式为( A^B*C-D+E/(F/(G+H)) )

中缀表达式转后缀表达式转换技巧：加括号，移符号，去括号； eg：前缀：A+(B+C)*D

1. 先将中缀表达式加括号：(A + ((B + C) * D))；

2. 再把运算符移到括号后面（前缀移到前面）：(A ((B C)+ D)*)+；

3. 把括号去掉：ABC+D*+。

而且这种方法也适合于中缀转前缀。

10. 线性表的顺序存储方式具有哪些优点（ABC）

A.可以用结点的物理次序反映结点之间的逻辑关系

B.存储密度高，节省存储空间

C.在结点等长时可以随机存取

D.插入删除比较灵活 ×

顺序存储：在一块连续的存储区域一个接着一个的存放数据。顺序存储方式把逻辑上相邻的节点存储在物理位置放在相邻的存储单元里，节点间的逻辑关系由存储单元的邻接关系来体现。顺序存储方式也称为顺序存储结构，一般采用数组或结构数组来描述。

优点：

在结点等长时可以随机存取

存储密度高节省存储空间

用结点的物理次序反映结点之间的逻辑关系

缺点：

插入和删除结点时要移动大量的结点

必须静态分配连续空间

链接存储：链接存储方式比较灵活，不要求逻辑上相邻的节点在物理位置上相邻，节点间的逻辑关系由附加的引用字段来表示。一个节点的引用字段往往指向下一个节点的存放位置。链接存储方式也成为链式存储结构。

优点：

插入和删除比较灵活，不需要大量移动结点

动态分配空间比较灵活，不需要预先申请最大的连续空间

缺点：

增加指针的空间开销

检索必须沿链进行，不能随机存取

因此D不是顺序存储的优点，而是链接存储的优点。