数据结构

1.时间复杂度是算法执行语句的次数。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

2. 循环队列的顺序表中，为什么要空一个位置？ 这是为了用来区分队空与队满的情况。如果不空一个位置，则判断队空和队满的条件是一样的。

（1）另设一个标志位以区别队列是空还是满。（2）少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:队空时: front=rear队满时: (rear+1)%maxsize=front

3.什么是二叉排序树？以及它的原理，算法。（二叉排序树的查找过程） 二叉排序树又称二叉查找树，它或者是一颗空树，或者满足一下性质的二叉树:

① 若左子树不空，则左子树上所有结点的值均小于根节点的值；

② 若右子树不空，则右子树上所有结点的值均大于根节点的值；

③ 左右子树也分别是二叉排序树。

原理步骤: 若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，递归查左子树。 若大于根结点的关键字值，递归查右子树。 若子树为空，查找不成功。

4.哈夫曼树 定义: 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二 叉树，也称为哈夫曼树(huffman tree)。 构造方法: 假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn，则哈夫 曼树的构造规则为: (1) 将 w1、w2、…，wn 看成是有 n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其 左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

特点: ① 权值越大的结点，距离根节点越近； ② 树中没有度为一的结点。

应用: 哈夫曼编码，减少编码的长度。哈夫曼编码就是长度最短的前缀编码。

5. 什么是哈希冲突？以及如何解决。 散列（哈希）表: 根据关键码值(key value)而直接进行访问的数据结构。根据给定的关键字来计算出关键字在表中的地址，加快查找的速度。 冲突:指的是多个关键字映射同一个地址的情况。 解决办法:

（1） 开放定址法 ① 线性探查法（产生堆积问题）； ② 平方探查法（不能探查到哈希表上所有的地址，但至少能探查到一半的地址）

（2） 链地址法 把所有的同义词用单链表连接起来。

补充（常见的哈希函数构造方法），除留余数法， 直接定址法，数字分析法，平方取中法

6.

———深度优先搜索遍历和广度优先搜索遍历的过程

深度优先搜索遍历

基本思想:首先访问出发点 v，并将其标记为已访问；然后选取与 v 邻接的未被访问的邻接顶点 w，访问 w；再选取与 w 邻接的未被访问的顶点访问，以此类推。当一个顶点所有的邻接顶点都被访问过时，则依 次退回最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些顶点中去一个顶点进行上述 的过程，直至图中所有顶点都被访问过为止。 广度优先搜索遍历 基本思想:首先访问起始顶点 v，然后选取与 v 邻接的全部顶点 w1，w2，….，wn 进行访问，再一次访 问与 w1，w2，… ，wn 邻接的全部顶点（不包括已访问过的顶点），以此类推，直至所有顶点都被访问过为止。

———-迪杰斯特拉算法的过程 该算法可以求得某一顶点到其余各顶点的最短路径。 算法思想:设有两个顶点集合 s 和 t，其中集合 s 中存放的是图中已找到最短路径的顶点，集合 t 中存放 的是图中的剩余顶点。 初始状态时，集合 s 中只包含源点 v0，然后不断从集合 t 中选取到顶点 v0 路径最短的顶点 vu 并加入集 合 s 中。集合 s 每加入一个新的顶点 vu，都要修改 v0 到集合 t 中各个顶点的最短路径的长度值。不断重 复这个过程，直至集合 t 中的顶点全部并入到 s 中为止。

7. 链表查找某个元素，平均的时间复杂度是多少？

o(n) 链表是顺序存储，故（1+n）/2。

8. 图的存储方式

① 邻接矩阵:是图的顺序存储结构，用两个数组分别存储数据元素（顶点）信息和数据元 素之间的关系（边/弧）的信息。图的邻接矩阵表示是唯一的，无向图的邻接矩阵是对称 的。

② 邻接表:是图的链式存储结构，由单链表的表头形成的顶点表和单链表其余结点所形成 的边表两部分组成。

③ 十字链表:有向图的另一种链式存储结构。

④ 邻接多重表:无向图的链式存储结构。

9.. 图的深度遍历是否唯一？

不一定是唯一的。我们可以取图中任一顶点进行深度遍历。某个顶点有多个邻接未访问顶点时，原则上讲，选哪个都可以的。

深度优先搜索和广度优先搜索都是图遍历的算法。

——-图的相关概念

图:由结点的有穷集合 v 和边的集合 e 组成。

类别:有向图和无向图。 顶点的度:出度和入度。

有向完全图和无向完全图: 若有向图有 n 个顶点，则最多有 n(n-1)条边，则称为有向完全图； 若无向图有 n 个顶点，则最多有 n(n-1)/2 条边，则称为无向完全图。

路径:相邻顶点序偶所构成的序列。

简单路径:序列中的顶点和路径不重复出现的路径。

回路:路径中第一个顶点和最后一个顶点相同的路径。

连通:

无向图中，如果 vi 到 vj 有路径，则称这两个顶点连通。如果图中任意两个顶点之间都连通，则 称该图为连通图。

有向图中，如果 vi 到 vj 有路径，则称这两个顶点连通。如果图中每一对顶点 vi 和 vj，从 vi 到 vj 和 vj 到 vi 都有路径，则称该图为强连通图。

10. 最小生成树的概念 （边的权值最短）

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持 图连通的最少的边。如果在最小生成树中添加一条边，必定成一个环。

相关算法: ① 普里姆算法（prim） ② 克鲁斯卡尔算法（kruskal）

一个带权无向图的最小生成树不一定是唯一的。

从kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，对这些边的选择可能会产生不同的最小生成树。

prim算法:在当前顶点集所可以连接到的边中选择最小的边，要判断该边是否已经在最小生成树中。时间复杂度是o（n2）kruskal算法:把所有的

边按照权值从小到大排列，按照顺序选择边，不构成回路，直到所有的顶点都被访问过。时间复杂度是 o（nlogn）

prim算法适合求解边稠密的最小生成树，kruskal算法适合求解边稀疏的最小生成树。

n 个结点的最小生成树有几个结点，几条边:n 个结点，n-1 条边。——最短路径dijkstra算法:是求某个原点到其余各个顶点的最短路径。o（n2）floyd算法: 是求每对顶点之间的最短路径。o（n3）

dijkstra算法不适用于负权边的情况(如 e[i][j]=-n 就不适合),floyd算法适用于该类问题

——–关键路径

使用e（i）表示活动ai最早发生时间，除此之外，我们还定义了一个活动最迟发生时间，使用l（i）表示，

不推迟工期的最晚开工时间。我们把e（i）=l（i）的活动ai称为关键活动，因此，这个条件就是我们求一个aoe-网的关键路径的关键所在了。

11. 平衡二叉树 又称 avl 树，是一种特殊的二叉排序树，其左右子树都是平衡二叉树，且左右子树的高度差的 绝对值不超过 1.

平衡因子: 左子树高度减去右子树高度的差的绝对值。

平衡调整: 先找到失去平衡的最小子树，即以距离插入结点最近，且平衡因子绝对值大于 1 的结点为根节点的子树，分为 ll,lr,rl,rr 四中调节方式。

12. 二叉树的存储

① 顺序存储结构:用一个数组来存储一颗二叉树，二叉树中的结点值按照编号依次存入一个一维数组中。 适用于完全二叉树，若用于一般的二叉树则会浪 费大量 存储空间。

② 链式存储结构:二叉树中的每一个结点用一个链结点来存放。

14. 折半查找，又称二分查找，

基本思路: 在当前的查找区间[low…high]中，首先确定 mid=(low+high)/2，然后拿关键字与 mid 比较，若相等则查 找成功，返回该位置，否则确定新的查找区间， mid>k，[low…mid-1] mid

直至查找自区间长度小于 1 时查找结束。

适用范围:顺序结构存储并按照关键字大小有序排列。 时间复杂度:o(log2n)

15. 完全二叉树 若一棵二叉树至多只有最下面的两层上的结点的度数可以小于 2，并且最下层上的结点都集中在该层最左 边的若干位置上，则此二叉树成为完全二叉树。

完全二叉树特点: 叶子结点只可能在最大的两层上出现， 对任意结点， 若其右分支下的子孙最大层次为 l，则其左分支下的 子孙的最大层次必为 l 或 l+1；

16. 什么是堆？有什么作用？

堆是一种数据结构，可以把堆看成一个完全二叉树，并且这个完全二叉树满足: 父节点的值大于子节点的值，则为大顶堆

作用:应用于堆排序。

17. 如何实现循环队列？有何好处？

如何实现:把数组弄成一个环，让 rear 和 front 指针沿着环走，这样就可以产生循环队列。

好处:循环队列是顺序队列的改进，在顺序队列中，在元素进队的时候，rear 要向后移动，元素出队的时 候，front 也要向后移动，

这样经过一系列的出队和入队操作之后，两个指针最后会达到数组的末端，此时 虽然队中已经没有元素了，但是还是不能让元素入队，

即出现了“假溢出”的现象。循环队列就能避免出 现这个现象。

18. 深度优先搜索形成的是什么？森林唯一么？ （森林，不能说树）（不唯一，因为邻接表可能不唯一）

19. 满二叉树的结点个数（n 层） 2 的 n 次方减一（2n-1）

20. 二叉查找树查找的时间复杂度以及中序遍历后得到什么样的序列 递增有序序列

21. 什么图可以进行拓扑排序？ 有向无环图（dag）

aov网—-用顶点表示活动，边表示活动发生的先后顺序。

aoe网—-用边表示活动的网，aoe网是带权有向无环图。

22. 顺序队列的特征、栈

队列是一种操作受限的线性表，只允许队尾入队，在队头进行出队。最大的特点是先进先出。

栈只允许在一端进行插入和删除数据。

23.一级缓存和二级缓存

l1 cache(一级缓存)是cpu第一层高速缓存，分为数据缓存和指令缓存。
l2 cache＝二级缓存
二级缓存是比一级缓存速度更慢，容量更大的内存，主要就是做一级缓存和内存之间数据临时交换的地方用。

现在，为了适应速度更快的处理器p4ee，已经出现了三级缓存了，它的容量更大，速度相对二级缓存也要慢一些，

但是比内存可快多了。 缓存的出现使得cpu处理器的运行效率得到了大幅度的提升，这个区域中存放的都是

cpu频繁要使用的数据，所以缓存越大处理器效率就越高，同时由于缓存的物理结构比内存复杂很多，所以其成本也很高。

24.树的存储结构:双亲表示法 、孩子表示法、 孩子兄弟表示法

树的存储方法及其优点
l 双亲表示法:
采用一组连续空间来存储每个节点，同时在每个节点中增设一个伪指针，指示双亲节点的位置。
可以很快地找到双亲节点，但求孩子节点需遍历整个结构。
l 孩子表示法:
将每个节点的孩子节点都用单链表链接起来形成一个线性结构。
可以很快地找到孩子节点，但求双亲节点需遍历整个结构。
l 孩子兄弟表示法:
左孩子右兄弟
优点:可以很方便实现从树到二叉树的转换以及查找孩子节点。
缺点:查找双亲节点比较麻烦。

25.树的遍历方式 先序遍历 中序遍历（递增序列） 后序遍历

26.数组和链表的区别 :

数组vs链表:

数组:具有相同数据类型的元素按一定顺序排列的集合。

①数据顺序存储，存储空间是连续的。

②数组中的元素都是相同类型的。

③数组的长度是固定的。

④数组的空间是从栈分配的。

⑤查找快，增删慢。

链表:链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

①链表的元素是通过指针进行连接的，不是顺序存储的，内存空间不一定连续。

②元素可以是不同类型的。

③链表的长度是可变的。

④链表的空间是从堆中分配的。

⑤增删快，查找慢。

二叉排序树的插入、删除、查找
二叉排序树:空二叉树；左子树上所有节点的关键字小于根节点的关键字，右子树上的所有结点的关键字大于根节点的关键字，且左右子树又各是一个二叉排序树。

插入:
若原二叉排序树非空，则直接插入；否则，插入关键字与根节点比较，若小于根节点，则插入到左子树中，若大于根节点，则插入到右子树中，插入的节点一定是某个叶节点。
删除:
l 叶节点，直接删除
l 只有左子树或右子树，则让左子树或右子树代替被删除的节点。
l 有左子树和右子树，让它的直接后继（中序遍历的后一个元素）代替它
若在二叉排序树中删除并插入某节点，得到的二叉树是否与原来相同？
叶节点，则相同。
非叶节点，不完全相同。

28.各种排序算法的时间复杂度和空间复杂度 以及稳定性