首页 > 《数据结构》中的一些会遇到的面试题
头像
擎宇要努力努力再努力
编辑于 2021-02-15 22:35
+ 关注

《数据结构》中的一些会遇到的面试题

(一)AVL 树

AVL 树是平衡二叉查找树,增加和删除节点后通过旋转重新达到平衡,旋转包括左旋和右旋。左旋是以某节点为中心,将它沉入当前左子节点的位置,而让当前的右子节点作为新树的根节点,称为逆时针旋转,右旋同理。


(二)红黑树

每个节点上有一个颜色属性,是红色或黑色。红黑树通过重新着色和左右旋转,高效地实现了平衡调整。

红黑树本质上是二叉查找树,额外引入了 5 个约束条件:① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的红色节点。⑤ 在任何递归子树中,根节点到叶子节点的所有路径上包含相同数目的黑色节点。这五个条件保证了红黑树增删查的最坏时间复杂度均为 O(log~n~)。红黑树的任何旋转在 3 次之内均可完成。

红黑树的平衡性不如 AVL 树,它维持的只是一种大致的平衡,不严格保证左右子树的高度差不超过 1。节点数相同的情况下,红黑树的高度可能更高,平均查找次数会高于 AVL 树。

在插入时,红黑树和 AVL 树都能在至多两次旋转内恢复平衡,在删除时由于红黑树只追求大致平衡,因此至多三次旋转可以恢复平衡,而 AVL 树最多需要 O(log~n~) 次。面对频繁地插入与删除红黑树更加合适。


(三)B 树

B 树 又叫多路平衡搜索树,一颗 m 叉的 B 树:

  • 树中每个节点最多包含 m 个子节点。

  • 除根节点与叶子节点外,每个节点至少有 ceil(m/2) 个子节点。

  • 所有的叶子节点都在同一层。

  • 每个非叶子节点由 n 个 key 与 n+1 个指针组成,其中 ceil(m/2)-1 <= n <= m-1

B 树和二叉树相比,查询效率更高,因为 B 树的层级结构比二叉树小(深度小,需要遍历的次数少)。


(四)B+ 树

B 树中每个节点同时存储 key 和 data,而 B+ 树中只有叶子节点才存储 data,非叶子节点只存储 key。InnoDB 对 B+ 树进行了优化,在每个叶子节点上增加了一个指向相邻叶子节点的链表指针,形成了带有顺序指针的 B+ 树,提高区间访问的性能。

B+ 树的优点:

  • 由于 B+ 树在非叶子节点上不含数据信息,因此在内存中能够存放更多的 key,数据存放得更紧密,利用率更高。

  • B+ 树的叶子节点都是相连的,对整棵树的遍历只需要对叶子节点进行一次线性遍历,而 B 树则需要每层递归遍历,相邻元素可能在内存中不相邻,缓存命中率没有 B+ 树好。

  • B 树的优点是,由于每个节点都包含 key 和 value,经常访问的元素可能离根节点更近,访问也更迅速。


(五)图

图表示多对多关系,根据边的属性分为有向图和无向图。

存储结构:

  • 邻接矩阵:一个一维数组存储图的顶点信息,一个二维数组存储图的边/弧信息。无向图中 1 表示两个顶点连通,0 表示不连通;有向图中 1 表示存在弧,0 表示不存在弧。

  • 邻接表:邻接表是一种链式存储结构,结合了数组与链表。将顶点存储在一个一维数组中,同时在顶点信息中存储用于指向第一个邻接点的指针。图中每个顶点的所有邻接点构成了一个线性表,由于邻接点个数不定,所以用单向链表存储。

遍历:

  • 广度优先:类似树的层次遍历,在访问某顶点后依次访问该顶点的各个未访问的邻接点。

  • 深度优先:类似树的先序遍历,在访问某顶点后,按深度优先访问其邻接点。
  • 深度优先:类似树的先序遍历,在访问某顶点后,按深度优先访问其邻接点。


(六)排序分类

类别 方法 最好时间 最差时间 平均时间 辅助空间 稳定性
插入排序 直接插入 O(n) O(n²) O(n²) O(1) 稳定
希尔排序 O(n) O(n²) O(n^1.3^) O(1) 不稳定
选择排序 直接选择 O(n²) O(n²) O(n²) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
交换排序 冒泡 O(n) O(n²) O(n²) O(1) 稳定
快速排序 O(nlogn) O(n²) O(nlogn) O(nlogn) 不稳定
归并排序 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定


具体的各种排序算法的代码和特点,网上有各种资料,这里不再写了




全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐