【数据结构】总结面试最常用的55道填空题

1. 树是由n个结点所构成的有限集合，当n=0时，称为空树
2. 树的表示法有4种，分别为：文氏图表示法、凹入图表示法、广义表表示法以及树形表示法
3. 结点的度是指结点所拥有子树的数目
4. 二叉树是一种特殊的树，它的每个结点最多只有两颗子树，并且这两课子树也是二叉树
5. 在一棵二叉树中，若其所有结点或叶结点，或左、右子树都非空，且所有叶结点都在同一层，则称这棵二叉树为满二叉树
6. 在二叉树的第i层上至多有2i个结点(i≥0)
7. 深度为h(h≥0)的二叉树上至多含2h-1个结点
8. 对于任何一棵二叉树，若其叶结点的个数为n0,度为2的结点个数为n2,则有n0=n2+1
9. 具有n个结点的完全二叉树的深度为log2n+1或log2(n+1)
10. 若某完全二叉含n个结点，从上到下从左到右进行0至n-1的编号，则：
    1. 若i=0,则该节点是二叉树的根，无双亲，否则，编号为(i-1)/2的结点为其双亲结点
    2. 若(2i+1)≥n，则该节点无左孩子，否则，编号为2i+1的结点为其左孩子结点
    3. 若(2i+2)≥n，则该节点无右孩子，否则，编号为2i+2的结点为其右孩子结点
11. 先根遍历的实现步骤是：①、访问根节点，②、先根遍历左子树，③、先根遍历右子树
12. 由二叉树的前序和后序不可以唯一确定一颗树
13. 结点间的路径是指从一个结点到另一个结点所经历的结点和分支序列
14. 结点的路径长度是指从根结点到该结点的路径上分支的数目
15. 树的带权路径长度是指树中所有叶结点的带权路径长度之和
16. 给定n个权值并作为n个叶结点按一定规则构造一棵二叉树，使其带权路径长度达到最小值，则这棵二叉树被称为最优二叉树，也称哈夫曼树
17. 完全无向图中的每两个顶点之间都存在着一条边
18. 完全有向图中的每两个顶点之间都存在着方向相反的两条边
19. 假设图中有n个顶点，e条边，则：
    1. 完全无向图含有e=n(n-1)/2条边；
    2. 完全有向图含有e=n(n-1)条边；
20. 在一个无向图中，若存在一条边(u,v),则称顶点u与v互为邻接点
21. 顶点的度是指图中与该顶点相关联的边的数目
22. 有向图顶点的度
    1. 顶点v的入边数目是该顶点的入度，记为ID(v);
    2. 顶点v的出边数目是该顶点的出度，记为OD(v);
    3. 顶点v的度等于它的入度和出度之和，即D(v)=ID(v)+OD(v)
23. 若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图
24. 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量
25. 若有向图中任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图
26. 常见的图的存储结构有两种，分别为：邻接矩阵和邻接表
27. 无向图的邻接矩阵是对称的(可采用压缩存储)，顶点vi的度是第i行或第i列中“1”的元素个数
28. 有向图的邻接矩阵不一定为对称矩阵，每行中“1”的个数为该顶点的出度，每列中“1”的个数为该顶点的入度
29. 对于稀疏图，邻接表比邻接矩阵节省存储空间
30. 图的遍历方式通常有两种，分别是广度优先搜索和深度优先搜索
31. 图的广度优先搜索遍历类似于树的层次遍历过程
32. 在一个网的所有生成树中，权值之和最小的生成树称为最小代价生成树
33. 求图的最小生成树的典型算法有两种，分别是克鲁斯卡尔算法和普里姆算法
34. 克鲁斯卡尔算法的基本思想是，先构造一个只含有n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止
35. 最小生成树不是唯一的，因为同一时候可能有多种选择
36. 克鲁斯卡尔算法的时间复杂度为O(eloge),执行时间主要取决于图的边数
37. 克鲁斯卡尔算法适用于针对稀疏图的操作
38. 普里姆算法的时间复杂度为O(n2),执行时间主要取决于图的顶点数，与边数无关
39. 普里姆算法适用于针对稠密图的操作
40. 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序
41. 一个无环的有向图称为有向无环图，简称为DAG图
42. 排序是将一组无序的记录序列调整为有序的记录序列的一种操作
43. 按排序过程中所涉及到的存储器不同分为内部排序和外部排序
44. 按相同关键字在排序前后的位置不同分为稳定排序和不稳定排序
45. 内部排序的过程是一个逐步扩大记录的有序序列长度的过程
46. 内部排序的方法大致可以分为5种类型，分别是插入类、交换类、选择类、归并类和其它方法
47. 直接插入排序的位置查找方法是基于顺序查找
48. 希尔排序的位置查找方法是基于逐趟缩小增量
49. 希尔排序是不稳定的排序方法，它的时间复杂度是不确定的，但在插入排序中，希尔排序的效能最高，最好的情况可达O(nlog2n)
50. 冒泡排序是稳定的排序方法，它的时间复杂度为O(n2)
51. 快速排序是不稳定的排序方法，它的时间复杂度为O(nlog2n)，是内部排序中性能最好的一种
52. 直接选择排序是不稳定的排序方法，它的时间复杂度为O(n2)
53. 树形选择排序是稳定的排序方法，它的时间复杂度为O(nlog2n)
54. 堆排序是不稳定的排序方法，它的时间复杂度为O(nlog2n)
55. 归并排序是稳定的排序方法，它的时间复杂度为O(nlog2n)

热点资讯