数据结构与算法知识点

知识点整理

● 完全二叉树与满二叉树的区别

满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。

● 已知二叉树的前序遍历和中序遍历求后续遍历

现有二叉搜索树（BST）前序遍历结果序列为abdefgc，中序遍历结果序列为debgfac，请问后序遍历结果序列?

答：前序遍历结果序列为 abdefgc，中序遍历结果序列为 debgfac
以此为条件，根据前序知道a是根，根据中知道debgf为左子树，c为右子树。
根据前知道b为左子树中的根，根据中知道de为b的左，gf为右，根据前和中判断d为根，e为右，f为根，g为左，
树成型，得出后序结果 edgfbca

● 已知啊 a * b = c，求系统进制

如果某系统 15*4=112 成立，则系统采用的是几进制？

将原式转为 X进制：
1 5 * 4 = 1 1 2
（X+5）* 4 = X^2+X+2
解方程即可 x=6

● 栈

1. 设栈 S 和队列 Q 的初始状态均为空，元素啊，a,b,c,d,e,f,g 依次进入栈 S。若每个元素出栈后立即进入推列Q，且7个元素出队的顺序是 b,d,,c,f,e,a,g，则栈 S 的容量至少是？

   栈是先进后出，队列是先进先出，所以元素出队列的顺序就是出栈的顺序。
   出栈的顺序为 b,d,c,f,e,a,g，这意味着

   1. a,b 进入，b 出；

   2. c,d 进入，此时栈中有 a,d,c，出来 d,c；

   3. e,f 进入， 此时栈中有 a,e,f，出来 f,e,a；

   4. g 进入，此时栈中有 g，出来 g；

      由此看出整个过程中栈中存在的元素最多有 3 个，所以栈 S 的容量至少是 3

2. 一个栈的入栈序列是 a,b,c,d,e,f,则栈的不可能的输出序列是（）

   A:fedcba B:defbca C:defcba D:abcdef

   A. 可以全进栈然后依次出栈
   B. 不可以
   C. 先进 adcd 然后 d 出，再进 e，e 出再进 f，f 出剩下的依次 cba出
   D. 一个进，一个出

● 网络延迟

网络延迟是指在传输介质中传输所用的时间，即从报文开始进入网络到它开始离开网络之间的时间。

● 完全二叉树的存储

完全二叉树由于其结构上的特点，通常采用顺序存储方式存储(数组)。