• 推导 n = n 0 n 1 n 2 ， n 0 = n 2 1 , n 1 = 0 n = n_0 n_1 n_2， n_0 = n_2 1 , n_1 = 0 n= n0​+n1​+n2​，n0​=n2​+1,n1​=0 。

• 少一个条件，左右子树高度之差小于等于1。

6T，

• 链式结构线性表的存储空间比顺序结构多，而且链表结点的存储空间利用率比顺序表稍低（存储密度不够大）。
• 元素的物理顺序与逻辑顺序不一致，顺序存储结构的物理顺序和逻辑顺序一致。

7T，邻接表，计算所有顶点入度，时间复杂度为 O(n+e)。

13T，子链兄弟链法存储一颗树（孩子兄弟存储：即二叉链表），根结点右指针为空。

14T， 。下三角压缩存储方式，是**自然序列的求和**。

• 三角行列式的求和是：
• 注意矩阵从0开始，并且第一次存储地址为0。

16T,

• B：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。

18T，排序算法：比较次数与初始序列无关的是简单选择排序

• 排序躺数与初始序列有关的是 起泡排序和快速排序。

25T，$\lceil log_2(n+1) \rceil $。

27T，m阶B-树是

• 一颗m叉平衡排序树。√

• A选项说 m叉排序树 ×，why,A就是原因。

29T，最短路径求法，如何快速求呢。

39T，二叉树存的一个中缀表达式。前序遍历。

43T，$n_0 = 1 + n_2 + 2n_3 +3n_4… $。

44T。

• 链表的物理顺序和逻辑顺序无关。

• 有向图的邻接表结构比邻接矩阵结构要节省空间。不一定，图为稀疏图，邻接表好，稠密图时，邻接矩阵好。
• ==AOE（activity on edge）==网 是权值在弧上的带权图。 AOV（activity on vertex）

• 所有结点只有右子的二叉树。 √
• 根结点没有左子的二叉树。× 因为仅根结点符合 是不可以的，还有右子树的所有左子树也得符合。
• 只有根结点的二叉树。×，why。

• 堆，√
• 哈夫曼树，× 关键字只出现在叶结点上。

8T，有点别扭

10T，最小生成树是图的极小连通图，包含图中所有顶点。

• 最小生成树有n-1条边。

20T，完全二叉树的层次遍历序列 与 结点间的 父子关系 存在对应关系。

23T，大于100000的待排序序列为有序序列，效率最快的是 直接插入。

26T，存储矩阵的三元组表示法

• 按照行列有序排列。
• 矩阵计算速度更快。不需要进行查找。
• 同行非零元素排列在一起。

29T，最小生成树的应用：城市之间道路问题。

33T，哈夫曼树

• 哈夫曼树上权值最小的结点层数最大。这样才能保证哈夫曼树带权路径长度最小。
• 根据哈夫曼树构造的哈夫曼编码属于变长编码。
  • 若允许对不同字符用不等长的二进制位表示，则称为可变长编码，哈夫曼编码属于变长编码。

36T

• A 快速排序的性能优于 归并排序。

38T，最短路径dijkstra描述

• Dijkstra 算法是求 有向带权图 中单源点到其余各顶点的最短路径，目标解是一个最短路径集合。
• 以0 为起点的最短弧 属于目标解集。
• 最先求得的是目标解集中最短的最短路径。

40T，先根序列。

45T ，散列表

• 散列表采用顺序表作为容器

• 通过散列函数来定位元素

• 适合于 动态查找

• 散列表的装载因子越大冲突几率越小。×，关键字不变，len越小，装载因子越大，则冲突几率越大。

2T，顺序结构线性表是指元素顺序存放在 预先分配 的缓冲区中。

4T，删除单链表上指定结点的后序结点的最坏时间复杂度为 O(1)。

7T，联系二叉树的确定。

9T，n个结点的二叉树链表的空链有 n+1 个。

21T，Dijkstra算法，最先确定的最短路径是：以起点为弧尾的权值最小的弧。

22T，图的邻接表存储结构上，顶点为n，弧边为e，**e>n，计算所有顶点入度最快的快速算法，时间复杂度**为：

• O(e)

25T，

28T，二叉平衡树的平衡因子，经典题。有推理逻辑，图和公式写在课本上了。

29T，二叉平衡树的调整，本质上就是，左孩子<父结点<右孩子。

35T，题有问题，哪一种排序方法的排序躺数与初始序列有关？

38T，深度越小的二叉排序树平均查找性能最好

45T，消除递归形式不一定要通过栈，比如斐波那契数列 。

• 二叉树的度为2。×，有五种形态。
• 二叉树是**无向树。×，是有向树**
  • 有向树满足如下条件：
  • 1、有且仅有一个结点入度为0.
  • 2、除树根外的结点入度为1.
  • 3、从树根到任一结点有一条有向通路。
• 二叉树有且只有一个根结点。×。

• 无向图的边数等于顶点度数之和。×，还要再除2。
• 有向图中的顶点入度之和等于顶点出度之和。√
• 有向图是特殊的无向图。×，
  • 无向图可以看作每条边都有两个方向的有向图。所以，无向图是特殊的有向图。
• 有向图中的弧在无向图中称为边。×，弧和边不可混淆。
• 无向图邻接矩阵：
  • 1、邻接矩阵是对称的
  • 2、矩阵 1 的个数 为图中总边数 的两倍。
  • 3、矩阵中 1行 或者 第 1列的元素之和即为 顶点 i 的度
• 有向图邻接矩阵：
  • 1、矩阵1 的个数 为 图中的边数。
  • 2、矩阵中 第 i 行的元素之和 即为顶点的出度，第 i 列的元素之和为顶点的入度。

• 就是求叶子结点。
• n 1 = 0 n_1 = 0 n1​=0 。
• n = 2 n 0 − 1 n = 2n_0 - 1 n=2n0​−1 。

• B：支持随机存取。
• C：只在表尾增删数据。
• D：支持折半查找。

• 因为边表的结点个数就是出度个数。
• 入度个数的统计可以联想到 拓扑排序中 第一步 就是统计入度个数，进行遍历。

41T，平衡二叉树。

• 平衡二叉树是完全二叉树。×
• 完全二叉树是平衡二叉树。×
• 两颗平衡二叉树合并到根结点可得到一颗新的平衡二叉树。×（肯定错）
• 平衡二叉树的左右子树肯定是平衡二叉树。

43T，折半查找一个存在的数。画判定树。

44T。

45T，图的邻接矩阵的下三角都是0，则图是

• 有向无环图。

• 注意 上句话 中的 删除操作 确实为 O(1)。
• 扩展：静态链表可以通过下标访问。

• D：三元组表示法适合按行进行访问。

• 图根据 关系特征 可以分为有向图和无向图两大类。错，有无方向
• **图的深度优先遍历和广度优先遍历可以确定该图。**错
• 数据既可以部署在图的顶点上也可以部署在弧上。对

• A有向无环图，拓扑排序，想想特性
• B生成树
• C无向图
• D完全图。
• 何为偏序关系 。
  • ssss

• i和j的位置可能互换了。

• 一条最短路径必是由另一条最短路径构成。错
• 以V0为起点的最短的弧必为一条最短路径。对
• 以V0为起点的最长的弧必不是一条最短路径，错

• A 算法A的速度 比算法 B快 ×
• B 算法B的速度比算法 A快 ×
• C 算法B比算法A更复杂 ×
• D，以上都不对
• 回顾，北化资料，13页 5T。
  • 某算法的时间复杂度为O($ n^2 ) ， 表 明 该 算 法 ： 执 行 时 间 与 )，表明该算法：执行时间与 )，表明该算法：执行时间与 n^2$ 成正比。
  • 时间复杂度为O($ n^2 ) , 说 明 算 法 的 时 间 复 杂 度 T ( O ) 满 足 T ( n ) < = c ∗ ) ,说明算法的时间复杂度T(O) 满足 T(n) <= c* ),说明算法的时间复杂度T(O)满足T(n)<=c∗ n^2$
  • 问题规模 就是 n，时间复杂度T(O) 是关于问题规模 n 的函数。

• D：串的存储结构 类似于但不是 顺序存储结构。
• A

• D：链式存储结构不需要预先分配存储缓冲空间。√

• 三元组表由非零元素值、行数、列数 组成。×，按定义来。
• 三元组表中的非零元素要求按先行后列的顺序有序存储。√
• 三元组表可以节省存储空间，但需要更多的矩阵计算时间。×。从时间复杂复杂度上来看，然而并没有需要更多时间

• 试试，有趣
• 第一步： n 0 = n 2 + 1 ， 所 以 n 2 = 17 n_0 = n_2 + 1，所以n_2 = 17 n0​=n2​+1，所以n2​=17 。
• 第二步：$ n = n_0 + n_1 + n_2, 因为求最少，所以 n_1 = 0, 则 n = 35$ 。、
• 第三步：$\lfloor log_2(n+1) \rfloor $ 为6。

• A，
• B，

• 简单排序算法虽然排序速度较慢，但实现较为容易。×。（我觉得挺对的）

1T，

• A，数据元素的数据项中可以有多个次关键字，只能有一个主关键字。×，

• C，主关键字是数据元素中具有唯一标识作用的数据项。√

• D，数据元素是构成数据集合的数据对象，由多个数据项组成。×

  • 数据元素是数据的基本单位。

3T，

• B， 逻辑结构决定了算法的设计，物理结构决定算法的实现。√
• D，同一种物理结构可以用多种逻辑结构来实现。×，
  • 说反了。

5T，

• A，线性表中有且只有唯一的表头元素和唯一的表尾元素。× 空表
  • 这是性质，没有错，但是不能这样说，空表就没有。
• B，线性表中，每个元素有且只有唯一的前驱和惟一的后继。×。空表。

13T，串的暴力破解法，源串为m，模式串为n，则最坏时间复杂度为O(m*n)。

15T

• D，带行向量的三元组表上元素访问的最坏时间复杂度 是 O(m*n），×
  • 知道咧，三元组表数据结构为一元数组。存储的是稀疏数组，非零个数小于m*m。

19题计算指针利用率（非空利用率）：

• n 0 = 1000 , 所 以 n 2 = 999 n_0 = 1000, 所以 n_2 = 999 n0​=1000,所以n2​=999。
• n个结点的总链数为2n： n = n 0 + n 1 + n 2 = 1000 + n 1 + 999 n = n_0 + n_1 + n_2 = 1000 + n_1 + 999 n=n0​+n1​+n2​=1000+n1​+999 。
• 所以 ( 2 n 2 + n 1 ) / 2 n = ( 2 ∗ 999 + n 1 ) / 2 ( 1999 + n 1 ) = 1 / 2 (2n_2 +n_1)/2n = (2*999+n_1)/2(1999+n_1) = 1/2 (2n2​+n1​)/2n=(2∗999+n1​)/2(1999+n1​)=1/2。
• 推论：因为 n0 约等于为 n2，所以上式 ( 2 n 2 + n 1 ) / 2 n = ( 2 n 0 + n 1 ) / 2 ( 2 n 0 + n 1 ) = 1 / 2 (2n_2 +n_1)/2n = (2n_0 + n1)/2(2n_0 + n_1) = 1/2 (2n2​+n1​)/2n=(2n0​+n1)/2(2n0​+n1​)=1/2。

22T，23T，画图题.。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

• 二叉树 转 树 转森林，，回顾课本，给忘了------一句话：左孩子、右兄弟。

24T

• A，图的邻接表结构计算 所有顶点 的入度 只需要遍历一遍整个邻接表。√。
  • 拓扑排序第一步：统计入度个数。
• B，图的邻接表结构计算 指定顶点 的出度 只需要遍历一遍整个邻接表。×。只遍历边表即可
  • 指定顶点的边表的结点个数 就是 指定顶点的入度。

26T

• B，有向图上的一条路径必属于某一个深度优先遍历序列。√
• C，无向图的一次深度优先遍历可以遍历完所有顶点。×
  • 图包含连通图和连通分量。

27T，

31T，

• A，Dijkstra和Floyd都利用了最短路径的局部最优特性。√。
• B，Dijkstra通过穷举起点和终点的所有路径来确定最短路径。×
  • 不是的。
• C，Floyd改善了Dijkstra算法在最坏情况下的时间复杂特性。×
  • 改善额是Dijkstra不能求权值为负值的单源起点最短路径问题。
• D，Dijkstra只适合于单源起点最短路径问题的求解。×
  • 任意两点间路径也可以。

34T，D选型

36T，

• B，先进排序法中，快速排序法平均时间性能最好，堆排序法空间复杂度最低。√
  • 为什么快速排序的平均性能最好？
• C，先进排序法的平均时间复杂度优于简单排序法，是更快的排序算法。×

40T，考到了很少考的归并排序。

1T，抠字眼，紧扣定义。

• A，数据元素是数据项中的数据内容，×，说反了，数据项是数据元素的数据内容。也就是B选项了
• C，数据元素是不可再拆分的数据，×，数据元素由若干个数据项组成。
• 数据项是不可再拆分的数据，×
  • 数据肯定可以拆分。课本定义：数据项是构成数据元素的不可分割的最小单位。

2T，关键字是特殊的数据项。

• D，关键字是数据项的类型。×。

4T，定义细节题。

• A，物理结构是逻辑结构的代码表示，×，
  • 分清逻辑结构和物理结构的定义
• B，逻辑结构与物理结构相互对应，×
• C，逻辑结构决定了物理结构，× 物理结构和逻辑结构无关系。
• D，物理结构与算法的实现相关。√。

5T，复杂度。

• A，时间复杂度不代表算法的速度。√
• B，时间复杂度越高，算法执行时间越长。×
• C，O(logn) 的阶高于 O(n)，×
• D，算法的时间复杂度只与问题规模有关，×

北化资料 13页5T。某算法的时间复杂度为O($ n^2 ) ， 表 明 该 算 法 ： 执 行 时 间 与 )，表明该算法：执行时间与 )，表明该算法：执行时间与 n^2$ 成正比。

6T，细节题，正确的是 A

• A，线性表的关系集合满足非对称性。√
• B，线性表的关系集合是全序关系。×
• C，线性表中的每个元素都有唯一前驱。×，表头没有
• D，线性表中的每个元素有唯一后继。×

7T，

8T，单链表的空间开销高于顺序表。×，目前我