北京化工大学历年真题整理：没考上，换了个学校，但还是在北京~哈哈（总结的算法题，有缘人自取之）

文章目录

• 一、历年选择题真题 总结
• • 1、2008（12.1日一天）
• 2、2012
• 3、2013
• 4、2014
• 5、2015（12.2日二天）
• 6、2016
• 7、2017（12.3日三天）
• 8、2018
• 9、2019
• 10、2020（12.4日四天）
• 11、2021
• 12、22
• 二、历年算法真题题 总结
• • 1、 文本
• 2、表格
• 三、历年算法真题
• • 1、Fibonacci 08/13/14/17√
• • i 递归
  • ii 非递归
• 2、折半查找 12/18/19/20√
• • i 非递归
  • ii 递归
• 3、数组合并 12/14/19
• 4、***扩展(真题)：单链表合并 第24T。
• 5、二叉树结点个数 13/15/19
• 6、快速排序 13/16/18年
• 7、堆排序之堆调整 15/17/20
• 8、中缀表达式括号下标17/18
• 9、中缀表达式括号是否匹配 19
• 10、==***判断有向无环图(拓扑排序) 20/21==
• 11、回文数组 08 12
• 12、数组就地逆转、***==单链表逆转==13 14
• 13、二叉排序树查找，插入13 17
• • i 非递归查找
  • ii 递归查找
  • iii 插入新节点
• 14、==***三元组快速转置 14 17 (第25特殊)==
• 15、逆序数 15 17
• 16、删除零元素，删除重复元素15 16 21
• 17、顺序表插入 18 20
• 18、二叉树叶子结点个数 18 20
  • 19、***==还原带空节点#的前序遍历序列== 21
• • i 官方答案（有 bug）
  • ii 网上正确答案（背这个）
• 20、==二维数组压缩成三元组== 21
• 21、归并排序算法 21
• 22、单链表删除结点 20
• 23、单链表交换指定结点 18
• 24、***==单链表合并并去重== 17
• 25、***==一维数组中的非压缩矩阵压缩到三元组== 19
• 26、==串的暴力破解== 19
• 27、汉诺塔 19
• 28、图的DFS 18
• 29、==图的算法题:求最远距离== 12
• 30、最短路径==Floyd== 13
• 31、数组移动所有偶数 18
• 32、序列最值差值 14
• 33、数组相同元素最多个数 12
• 34、（背）判断二叉树是否相同（内容结构） 17
• 35、二叉树交换子树 16
• 36、（背）二叉树深度 12
• 37、二叉树根结点平衡因子 15
• 38、二叉树第K层结点个数 08
• 39、判断是否为平衡二叉树 14
• 40 、栈基本操作 16
• 41、队列基本操作 15
• 四、扩展必背
• • 1、二叉树的确定
• • i 前序+中序
  • ii 中序+后序
• 2、==最小生成树==（针对无向图，邻接矩阵）
• • i prim(普利姆算法) 针对顶点
  • ii 克鲁斯科尔（可能性不大，因为有排序）
• 3、==最短路径==（针对有向图，邻接矩阵）
• • i 迪杰斯特拉
  • ii Floyd 真题 13年，二、30
• 4、==串的算法==
• • i 暴力破解法 二、26
  • ii kmp算法
  • iii 改进kmp算法
• 5、汉诺塔(27T)、==约瑟夫环==（最后看吧）
• 6、图的 DFS(28T)、==BFS广度优先遍历（层次遍历）==
• 7、==二叉树的层次和深度遍历 递归和非递归（03年之前都考过）==
• • i 二叉树的深度优先 非递归遍历
  • ii 前中后序 递归遍历
  • iii 二叉树的广度优先遍历：层次遍历
• 8、08年之前的代码，需要看一下
• • i 两个单链表交叉合并 2003
• 五、==大纲要求==
• • 1. 排序and 查找：==归并+希尔是重点==
• • i 直接插入排序
  • ii 冒泡排序
  • iii 简单选择排序
  • iv ==希尔排序== **
• 2. 图 前面都有了
• 3 二叉树：真题+下面的北化资料了
• 4 线性表：真题为主
• 5 串+矩阵：二维压缩成三元组，三元组转置，kpm，暴力。
• 六、北化资料必背
• • 1、判断是否是完全二叉树（理解+背）
• 2、判断是否是二叉排序树（理解+背）
• 3、求指定结点在给定二叉排序树中的层次(easy)
• 4、递归求二叉树高度 二、36

一、历年选择题真题 总结

1、2008（12.1日一天）

1、 图的广度优先搜索中邻接点的寻找具有“先进先出”的特点；
2、 8T，直接选择排序就是简单选择排序；
3、 n个叶结点的哈弗曼树的总结点2n-1；

• 推导 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 。
  4、 2.5T，大顶堆（降序堆）是根结点大于其他所有结点的完全二叉树；
  5、 2.7T，二叉链结构存储一颗n个结点的二叉树上，有n+1个空链；
  6、 2.10T，递归的代码一定可以用非递归的形式来实现；
  7、 2.13T，二叉树中，具有两个子结点的结点，中序后继结点最多只可能有一个子结点；
  8、 2.14T，若一颗二叉树的左右子树都是平衡二叉树，则该二叉树为平衡二叉树×；

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

2、2012

1、 6T，；

• 链式结构线性表的存储空间比顺序结构多，而且链表结点的存储空间利用率比顺序表稍低（存储密度不够大）。

• 元素的物理顺序与逻辑顺序不一致，顺序存储结构的物理顺序和逻辑顺序一致。
  2、 7T，邻接表，计算所有顶点入度，时间复杂度为O(n+e)；
  3、 13T，子链兄弟链法存储一颗树（孩子兄弟存储：即二叉链表），根结点右指针为空；
  4、 14T，下三角压缩存储方式，是**自然序列的求和**；

• 三角行列式的求和是：

• 注意矩阵从0开始，并且第一次存储地址为0。
  5、 16T,；

• B：图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。
  6、 18T，排序算法：比较次数与初始序列无关的是简单选择排序；

• 排序躺数与初始序列有关的是 起泡排序和快速排序。
  7、 25T，$\lceillog_2(n+1)\rceil$；
  8、 27T，m阶B-树是；

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

• A选项说 m叉排序树 ×，why,A就是原因。
  9、 29T，最短路径求法，如何快速求呢；
  10、 39T，二叉树存的一个中缀表达式前序遍历；
  11、 43T，$n_0=1+n_2+2n_3+3n_4…$；
  12、 44T；

3、2013

1、 2T特例；
2、 6T，顺序表的物理顺序和逻辑顺序有关；

• 链表的物理顺序和逻辑顺序无关。
  3、 12T，关键路径；
  4、 18T，空间复杂度最大的两个，归并是O(n)，快速排序是logn；
  5、 19T；
  6、 22T，23T；
  7、 27T，m阶B-树的根结点最少有1个关键字；
  8、 32T，二叉树的中序遍历可以得到有序序列；
  9、 33T，归并操作；
  10、 35T，为了区分队空还是队满的情况，有三种方法：；

• 1、牺牲一个单元来区分队空和队满。

• 2、类型中增设表示元素个数的数据成员Q.size。

• 3、类型中增设tag数据成员，以区分是队满还是队空。

• 2和3都是使用了操作标记，所以题目中使用的是牺牲一个单元的方法，所以最多可以连续执行n-1次入队操作。

1、 36T，；

• 有向图的邻接表结构比邻接矩阵结构要节省空间。不一定，图为稀疏图，邻接表好，稠密图时，邻接矩阵好。

• ==AOE（activity on edge）==网 是权值在弧上的带权图。 AOV（activity on vertex）
  2、 38T，图的DFS类似于树的先序遍历，BFS类似于图的层次遍历；
  3、 39T，二叉树的前序遍历序列和中序遍历序列相同的是：；

• 所有结点只有右子的二叉树。 √

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

• 只有根结点的二叉树。×，why。
  4、 40T、42T；
  5、 43T，若一颗二叉树上任一结点到根的路径上的结点关键字均为有序排列，则二叉树为；

• 堆，√

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

4、2014

1、 8T，有点别扭；
2、 10T，最小生成树是图的极小连通图，包含图中所有顶点；

• 最小生成树有n-1条边。
  3、 20T，完全二叉树的层次遍历序列与结点间的父子关系存在对应关系；
  4、 23T，大于100000的待排序序列为有序序列，效率最快的是直接插入；
  5、 26T，存储矩阵的三元组表示法；

• 按照行列有序排列。

• 矩阵计算速度更快。不需要进行查找。

• 同行非零元素排列在一起。
  6、 29T，最小生成树的应用：城市之间道路问题；
  7、 33T，哈夫曼树；

• 哈夫曼树上权值最小的结点层数最大。这样才能保证哈夫曼树带权路径长度最小。

• 根据哈夫曼树构造的哈夫曼编码属于变长编码。

  • 若允许对不同字符用不等长的二进制位表示，则称为可变长编码，哈夫曼编码属于变长编码。
    8、 36T；

• A 快速排序的性能优于 归并排序。
  9、 38T，最短路径dijkstra描述；

• Dijkstra 算法是求 有向带权图 中单源点到其余各顶点的最短路径，目标解是一个最短路径集合。

• 以0 为起点的最短弧 属于目标解集。

• 最先求得的是目标解集中最短的最短路径。
  10、 40T，先根序列；
  11、 45T，散列表；

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

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

• 适合于 动态查找

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

5、2015（12.2日二天）

1、 2T，顺序结构线性表是指元素顺序存放在预先分配的缓冲区中；
2、 4T，删除单链表上指定结点的后序结点的最坏时间复杂度为O(1)；
3、 7T，联系二叉树的确定；
4、 9T，n个结点的二叉树链表的空链有n+1个；
5、 21T，Dijkstra算法，最先确定的最短路径是：以起点为弧尾的权值最小的弧；
6、 22T，图的邻接表存储结构上，顶点为n，弧边为e，**e>n，计算所有顶点入度最快的快速算法，时间复杂度**为：；

• O(e)
  7、 25T，；
  8、 28T，二叉平衡树的平衡因子，经典题有推理逻辑，图和公式写在课本上了；
  9、 29T，二叉平衡树的调整，本质上就是，左孩子<父结点<右孩子；
  10、 35T，题有问题，哪一种排序方法的排序躺数与初始序列有关？；

• BD是直接交换排序（起泡）和快速排序，而答案只选了B ：直接交换排序。

1、 38T，深度越小的二叉排序树平均查找性能最好；
2、 45T，消除递归形式不一定要通过栈，比如斐波那契数列；

6、2016

1、 1T，栈的操作性质（注意，是操作性质）；

• 出栈序列与操作顺序有关。√

1、 3T，二叉树性质细节题，王道有有序树和无序树的概念，P119页；

• 二叉树的度为2。×，有五种形态。

• 二叉树是**无向树。×，是有向树**

  • 有向树满足如下条件：
  • 1、有且仅有一个结点入度为0.
  • 2、除树根外的结点入度为1.
  • 3、从树根到任一结点有一条有向通路。

• 二叉树有且只有一个根结点。×。
  2、 4T，一般单链表中，数据元素将放在动态分配的结点中；
  3、 8T，图的论述；

• 无向图的边数等于顶点度数之和。×，还要再除2。

• 有向图中的顶点入度之和等于顶点出度之和。√

• 有向图是特殊的无向图。×，

  • 无向图可以看作每条边都有两个方向的有向图。所以，无向图是特殊的有向图。

• 有向图中的弧在无向图中称为边。×，弧和边不可混淆。

• 无向图邻接矩阵：

  • 1、邻接矩阵是对称的
  • 2、矩阵 1 的个数 为图中总边数 的两倍。
  • 3、矩阵中 1行 或者 第 1列的元素之和即为 顶点 i 的度

• 有向图邻接矩阵：

  • 1、矩阵1 的个数 为 图中的边数。
  • 2、矩阵中 第 i 行的元素之和 即为顶点的出度，第 i 列的元素之和为顶点的入度。
    4、 15T，n个结点的哈弗曼树，可以表示多少个字符的哈弗曼树编码?；

• 就是求叶子结点。

• n 1 = 0 n_1 = 0 n1=0 。

• n = 2 n 0 − 1 n = 2n_0 - 1 n=2n0−1 。
  5、 20T，相比较而言，不适合应用顺序结构线性表来处理的是：数据规模不确定；

• B：支持随机存取。

• C：只在表尾增删数据。

• D：支持折半查找。
  6、 22T，邻接表默认是出度表；

• 因为边表的结点个数就是出度个数。

• 入度个数的统计可以联想到 拓扑排序中 第一步 就是统计入度个数，进行遍历。
  7、 25T，折半查找最坏的时间是logn；
  8、 26T，挖字眼，折半查找算法查找指定元素，至少需要进行1次比较；
  9、 29T，直接交换排序，就是冒泡排序；

• 稳定排序法的排序性更为稳定。×，排序性和稳定性 没有 关系，性能和稳定性也没有关系。

1、 34T，堆排序；

• 升序排序 需要 建立降序堆，也就是大顶堆。
• 降序排序 需要 建立升序堆，也就是小顶堆。
• 建堆过程就是建立一个完全二叉树。

1、 41T，平衡二叉树；

• 平衡二叉树是完全二叉树。×

• 完全二叉树是平衡二叉树。×

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

• 平衡二叉树的左右子树肯定是平衡二叉树。
  2、 43T，折半查找一个存在的数画判定树；
  3、 44T；
  4、 45T，图的邻接矩阵的下三角都是0，则图是；

• 有向无环图。

7、2017（12.3日三天）

1、 6T，单链表的插入删除操作的平均时间复杂性为O(n)错，为1；

• 注意 上句话 中的 删除操作 确实为 O(1)。

• 扩展：静态链表可以通过下标访问。
  2、 10T，三元组描述；

• D：三元组表示法适合按行进行访问。
  3、 11T，D选型：缺少最多；
  4、 16T；
  5、 18T，图的陈述；

• 图根据 关系特征 可以分为有向图和无向图两大类。错，有无方向

• **图的深度优先遍历和广度优先遍历可以确定该图。**错

• 数据既可以部署在图的顶点上也可以部署在弧上。对
  6、 19T，如果有向图的关系集合满足偏序关系，则称为：A；

• A有向无环图，拓扑排序，想想特性

• B生成树

• C无向图

• D完全图。

• 何为偏序关系 。

  • ssss
    7、 27T，求关键路径中ve值可看原题，深度思考一下；

• i和j的位置可能互换了。
  8、 28T，Dijkstra算法陈述正确的为；

• 一条最短路径必是由另一条最短路径构成。错

• 以V0为起点的最短的弧必为一条最短路径。对

• 以V0为起点的最长的弧必不是一条最短路径，错
  9、 29T，不打字了，到时候回看吧；
  10、 32T，判定树记得加1，这里当时忘加1了；
  11、 33T；

8、2018

1、 3T，A的复杂度是O(n)，B的复杂度是O(n2n^2n2)选D；

• 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 的函数。
    2、 4T，回王道看的顺序存储结构的定义，还有串的存储结构和逻辑结构定义；

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

• A
  3、 5T，A**静态链表支持数组下标访问**；

• D：链式存储结构不需要预先分配存储缓冲空间。√
  4、 6T，回看题吧；
  5、 8T循环队列的初始状态，head=tail回看天勤资料；
  6、 10T三元组陈述；

• 三元组表由非零元素值、行数、列数 组成。×，按定义来。

• 三元组表中的非零元素要求按先行后列的顺序有序存储。√

• 三元组表可以节省存储空间，但需要更多的矩阵计算时间。×。从时间复杂复杂度上来看，然而并没有需要更多时间
  7、 11T，坑题BD，括号内外不一样；
  8、 14T，**一颗含有18个叶结点的二叉树，其深度（空树为0）最少为**6；

• 试试，有趣

• 第一步： 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。
  9、 16T，B二叉树是一种链式结构，×，应该是逻辑结构；
  10、 18T，A，哈夫曼树结果不唯一；
  11、 19T，有问题；
  12、 22T，找强连通分量最后看看吧；
  13、 26T，；
  14、 27T，递归实现的快速排序法，递归深度取决于，，，；

• A，

• B，
  15、 28T，先进排序法：是平均时间复杂度为nlogn的排序算法：快排、堆排序、归并排序；

• 简单排序算法虽然排序速度较慢，但实现较为容易。×。（我觉得挺对的）
  16、 31T，C咋错了，性能和稳定性无关系；

9、2019

1、 1T，；

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

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

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

  • 数据元素是数据的基本单位。
    2、 3T，；

• B， 逻辑结构决定了算法的设计，物理结构决定算法的实现。√

• D，同一种物理结构可以用多种逻辑结构来实现。×，

  • 说反了。
    3、 5T，；

• A，线性表中有且只有唯一的表头元素和唯一的表尾元素。× 空表

  • 这是性质，没有错，但是不能这样说，空表就没有。

• B，线性表中，每个元素有且只有唯一的前驱和惟一的后继。×。空表。
  4、 13T，串的暴力破解法，源串为m，模式串为n，则最坏时间复杂度为O(m*n)；
  5、 15T；

• D，带行向量的三元组表上元素访问的最坏时间复杂度 是 O(m*n），×

  • 知道咧，三元组表数据结构为一元数组。存储的是稀疏数组，非零个数小于m*m。
    6、 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。
  7、 22T，23T，画图题.；

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

• A，图的邻接表结构计算 所有顶点 的入度 只需要遍历一遍整个邻接表。√。

  • 拓扑排序第一步：统计入度个数。

• B，图的邻接表结构计算 指定顶点 的出度 只需要遍历一遍整个邻接表。×。只遍历边表即可

  • 指定顶点的边表的结点个数 就是 指定顶点的入度。
    9、 26T；

• B，有向图上的一条路径必属于某一个深度优先遍历序列。√

• C，无向图的一次深度优先遍历可以遍历完所有顶点。×

  • 图包含连通图和连通分量。
    10、 27T，；

• A，如果一次深度优先遍历能遍历完所有的顶点，则该无向图为连通图。√

• 和26T C 有点意思。

• B，如果一次深度优先遍历完遍历完所有顶点，则该有向图为强连通图。×

1、 31T，；

• A，Dijkstra和Floyd都利用了最短路径的局部最优特性。√。

• B，Dijkstra通过穷举起点和终点的所有路径来确定最短路径。×

  • 不是的。

• C，Floyd改善了Dijkstra算法在最坏情况下的时间复杂特性。×

  • 改善额是Dijkstra不能求权值为负值的单源起点最短路径问题。

• D，Dijkstra只适合于单源起点最短路径问题的求解。×

  • 任意两点间路径也可以。
    2、 34T，D选型；
    3、 36T，；

• B，先进排序法中，快速排序法平均时间性能最好，堆排序法空间复杂度最低。√

  • 为什么快速排序的平均性能最好？

• C，先进排序法的平均时间复杂度优于简单排序法，是更快的排序算法。×
  4、 40T，考到了很少考的归并排序；

10、2020（12.4日四天）

1、 1T，抠字眼，紧扣定义；

• A，数据元素是数据项中的数据内容，×，说反了，数据项是数据元素的数据内容。也就是B选项了

• C，数据元素是不可再拆分的数据，×，数据元素由若干个数据项组成。

• 数据项是不可再拆分的数据，×

  • 数据肯定可以拆分。课本定义：数据项是构成数据元素的不可分割的最小单位。
    2、 2T，关键字是特殊的数据项；

• D，关键字是数据项的类型。×。
  3、 4T，定义细节题；

• A，物理结构是逻辑结构的代码表示，×，

  • 分清逻辑结构和物理结构的定义

• B，逻辑结构与物理结构相互对应，×

• C，逻辑结构决定了物理结构，× 物理结构和逻辑结构无关系。

• D，物理结构与算法的实现相关。√。
  4、 5T，复杂度；

• A，时间复杂度不代表算法的速度。√

• B，时间复杂度越高，算法执行时间越长。×

• C，O(logn) 的阶高于 O(n)，×

• D，算法的时间复杂度只与问题规模有关，×
  5、 北化资料13页5T某算法的时间复杂度为O($n^2)，表明该算法：执行时间与)，表明该算法：执行时间与)，表明该算法：执行时间与n^2$成正比；
  6、 6T，细节题，正确的是A；

• A，线性表的关系集合满足非对称性。√

• B，线性表的关系集合是全序关系。×

• C，线性表中的每个元素都有唯一前驱。×，表头没有

• D，线性表中的每个元素有唯一后继。×
  7、 7T，；
  8、 8T，单链表的空间开销高于顺序表×，目前我觉得是不一定；
  9、 11T，；

• 满二叉树的结点数只与树的深度有关。√

• 完全二叉树的前序遍历序号 与 结点间关系 存在唯一映射。×。
  10、 12T，；

• 二叉树的后序遍历对应树的后根遍历。×，应该是二叉树的中序遍历才对。
  11、 13T，；

• A，根据图的关系集合可以分为有向图和无向图。×。

  • 王道199定义：若E是有向边（也称弧）的有限集合时，则图G为有向图。若E是无向边（简称边）的有限集合时，则图G称为无向图。

• 关系集合满足非对称性的图称为有向图。×

• C，有生成树的无向图必为连通图。
  12、 15T，有向无环图的关系集合满足偏序关系√；
  13、 18T，二叉排序树上查找所需最大比较次数取决于结点个数×，取决于深度，最好的状态就是平衡二叉树；
  14、 20T，；

• 堆排序是先进排序法中空间复杂度最低的排序法。√

  • 先进排序法包括：快排、堆、归并。

• 冒泡排序法，需要经过n-1趟冒泡交换来完成排序。×，

  • 不一定，冒泡排序躺数与初始序列有关系。

11、2021

12、22

150分。

我的答案

1-5：AC3BC

6-10：CBC910

11-15：

19：最好m 最坏 m*n

26：公式： ⌊ l o g 2 ( n + 1 ) ⌋ \lfloor log_2(n+1) \rfloor ⌊log2(n+1)⌋

27：公式： n = 2 n 0 − 1 n = 2n_0 - 1 n=2n0−1

28:公式： ⌈ i / 2 ⌉ − 1 \lceil i/2 \rceil - 1 ⌈i/2⌉−1

29：完全二叉树有1000个结点，从0开始编号则非叶子结点最大编号为() 公式： ⌊ i / 2 ⌋ − 1 \lfloor i/2 \rfloor -1 ⌊i/2⌋−1。

32：

二、历年算法真题题 总结

1、 文本

1、 08年：Fibonacci，回文数组，第K层结点个数，；
2、 12年：回文数组，二叉树深度，数组合并，折半查找，数组相同元素最多个数，图的算法题；
3、 13年：数组就地逆转，二叉树结点个数，快速排序，Fibonacci，二叉排序树查找，最短路径Floyd；
4、 14年：单链表逆转，Fibonacci，判断平衡二叉树，序列最值差值，数组合并，三元组快速转置；
5、 15年：队列基本操作，二叉树结点个数，二叉树根结点平衡因子，逆序数，删除序列零元素，堆排序；
6、 16年：栈基本操作，二叉树交换子树，快速排序，删除序列重复元素；
7、 17年：中缀表达式括号下标，Fibonacci，三元组快速转置，判断二叉树是否相同（内容结构），二叉排序树插入，单链表合并、去重，堆排序，逆序数；
8、 18年：单链表交换指定结点，数组移动所有偶数，中缀表达式括号下标，顺序表插入，二叉树叶子结点个数，快速排序，图的深度优先遍历，折半查找算法；
9、 19年：三元组矩阵压缩，折半查找，串的暴力破解，汉诺塔，中缀表达式括号是否匹配，数组合并，二叉树结点个数；
10、 20年：顺序插入，单链表删除结点，二叉树叶子结点个数，判断有向图是否为有向无环图（拓扑排序）,折半查找算法，堆排序；
11. 21年：删除0元素，还原带空节点#的前序遍历序列， 二维数组压缩成三元组，归并排序，判断有向图是否为有向无环图(拓扑排序)
12、 预测22年：；

• 排序or查找：归并排序、快速排序、堆排序、希尔排序、二叉排序树查找、折半查找

• 二叉树：前+中 、 中+后 、 去年真题 、 二叉树非递归遍历 、

• 串or矩阵：稀疏矩阵压缩至三元组、三元组矩阵压缩、字符串暴力破解、kpm、改进kpm(极小概率)

• 图：DFS、BFS、prim、kruskal（可能性小）、Dijkstra、Floyd、拓扑排序、

• 线性表：汉诺塔、约瑟夫环

• 注意： 21年的：还原带空节点#的前序遍历序列 第二题，扩展一下：那么带#的中序和后序是否可以还原呢，还有还原的相应代码。（14年12T，41T选型D，15年6T，17年14T）答：

2、表格

三、历年算法真题

1、Fibonacci 08/13/14/17√

n0 = 0 , n 1 = 1 , n 2 = 1 , n 3 = 2 , n 4 = 3 , n 5 = 5.... n_0=0,n_1=1,n_2=1,n_3=2,n_4=3,n_5=5.... n0=0,n1=1,n2=1,n3=2,n4=3,n5=5....

Nn = N n − 1 + N n − 2 ( n > = 2 ) N_n = N_{n-1}+N_{n-2}(n>=2) Nn=Nn−1+Nn−2(n>=2)

注意题中是否从0开始。

i 递归

int Fibonacci(int n)
{
    if(n <= 2) 
        return 1;//n=1,2   返还1;
    return Fibonacci(n-1) + Fibonacci(n-2);//n>2   返还前两个数之和
}

ii 非递归

int Fibonacci(int n)
{
    int a, b, c;
    a = b = c = 1;
    if(n<=2) 
        return 1; //n=1,2   返还1;
   	while(n > 2)
    {
        c = b + a;  // a 相当于 n_1, b相当于 n_2 。
        a = b;
        b = c;
        n--;
    }
    return c;
}

2、折半查找 12/18/19/20√

i 非递归

int BinarySearch(int L[], int n, int key)
{
	int low = 0, high = n-1;
	while(low <= hign)
	{
		int mid = (low + hign)/2;
	    if(key == arr[mid]) return mid;
		if(key < arr[mid]){
			high = mid-1;
		}else if(key > arr[mid]){
			low = mid +1;
		}
	}
	return -1;
}

ii 递归

//调用
int Search(int L[], int n, int key)
{
	int res = BinarySearch(L, 0, n-1, key);
	return res;
}
// 递归
int BinarySearch(int arr[], int low, int high, int key)
{
	if(low > high) return -1;   //返回-1 即未找到
	int mid = (low + hign)/2;
	if(key == arr[mid]) return mid;
	if(key < arr[mid]){
		return BinarySearch(arr, low, mid - 1, key);
	}else if(key > arr[mid]){
		return BinarySearch(arr, mid + 1, high, key);
	}
}

3、数组合并 12/14/19

排序算法中，二路归并算法用到了此合并算法（最后一步）。

int Merge(int C[], int A[], int An, int B[], int Bn)
{
	int i, j, k;   // 声明三个数组的下标。 i 为A数组下标，j为B数组下标，k为C数组下标
	i = j = k =0;
	while(i < An && j < Bn)
	{
		if(A[i] <= B[j])
			C[k++] = A[i++];
		else
			C[k++] = B[j++];
	}
    while(i < An) C[K++] = A[i++];
    while(j < Bn) C[K++] = B[j++];
    return k;
}

4、***扩展(真题)：单链表合并 第24T。

/**
 * Definition for LinkNode.
 * typedef struct LinkNode {
 *     int data;
 *     LinkNode *next;
 * }LinkNode, *LinkList;
 */
int Merge(LinkList A, LinkList B)
{
    
    LinkNode *pA = A, *pB = B;
    while(pA->next != NULL && pB->next != NULL)
    {
		if(pA->next->data < pB->next->data)   // pA 较小时，pA 后移一位 继续比较
        {
            pA = pA->next;
        }
        else if(pA->next->data > pB->next->data) // pB 较小时，pB插入到pA上，都后移一位比较
        {
            InsertAfter(pA, pB->next->data);
            pA = pA->next;
            pB = pB->next;
        } 
        else 									// 最后相等就都后移一位，再继续比较
        {
            pA = pA->next;
            pB = pB->next;
        }
    }
    // 当A遍历完了，B还有的情况下。注意，因为这里是往A上插入，所以不存在A还没遍历完的情况
    while(pB->next != Null) 
    {
        InsertAfter(pA, pB->next->data);
        pA = pA->next;
        pB = pB->next;
    }
    return 1; // 1代表成功。
}
void InsertAfter(LinkNode &p, int data)
{
    LinkNode newNode = new LinkNode();
    newNode->data = data;
    // 插入操作：先移动后面的，再赋值到 原来p 上
    newNode->next = p->next;
    p->next = newNode;
} 

5、二叉树结点个数 13/15/19

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
int GetNodeCount(BiTree T)
{
	if(T == NULL) 
        return 0;
    int lnum = GetNodeCount(T->lchild);
    int rnum = GetNodeCount(T->rchild);
	return lum + rnum + 1;
}
// 简介版本
int GetNodeCount(BiTree T)
{
	if(T == NULL) return 0;
	return GetNodeCount(T->lchild) + GetNodeCount(T->rchild) + 1;
}

6、快速排序 13/16/18年

// 一次划分
int Partition(int L[], int s, int t)
{
    int low = s, high = t;
    if(s > t) return -1; // s > t 则失败
    
    int temp = L[low];   // 拿第一个数为待排序的数，先暂存起来。类似于二叉查找的 key值。
    while(low < high)
    {
        if(low < high && L[high] > temp) high--;
        if(low < high)
            L[low++] = L[high];
        
        if(low < high && L[low] < temp) low++;
        if(low < high)
            L[high--] = L[low];
    }
    L[low] = temp;
    //Partition(L, s, low-1); //放开这两行就是完整的快速排序
    //Partition(L, low+1, t);
    
    return low;
}

7、堆排序之堆调整 15/17/20

// 堆排序总函数
void heapSort(int R[], int n)
{
    int temp;
    for(int i = n/2; i<n; i--) // 第一步：建堆过程
        HeapAdjust(R, n, i); 
    for(int i = n; i>=2; i--) // 第二步：排序 共 n-1 次
    {
        temp = R[1];
        R[1] = R[i];
        R[i]=temp;
        HeapAdjust(R, i-1, 1); // 
    }
}
// 一次堆调整
// startindex 是调整的位置下标，n是数组长度
int HeapAdjust(int datas[], int n, int startindex) 
{
    if(startindex > n) return 0;
    // lchild 表示左孩子，注意：题目中没有指明数组下标从0还是从1开始存储的，那就默认从0开始。
    int parent = startindex, lchild = 2 * parent + 1;
    int temp = datas[parent];   // 暂存父结点，类似于 快排中的temp
    while(lchild < n)
    {
        if(lchild < n && data[lchild] < datas[lchild + 1]) // 右孩子大，则自加指向右孩子
            lchild++;     // 指向右孩子
        if(lchild < n && datas[parent] < datas[lchild]){ // 孩子大，则 赋值到 父结点。
            datas[parent] = datas[lchild];
            parent = lchild;								 // 下面两行是 继续调整
            lchild = 2 * parent + 1;
        }
    }
    datas[parent] = temp;
    return 1;
}

8、中缀表达式括号下标17/18

记住这个骚操作：统计传过来指针数组的个数。

// 记忆这个，这个不需要 定义常量，下面的需要定义 maxSize 常量
int brackets(char *exp)
{
    int i;
    for(i = 0; exp[i]; i++); // 统计字符串个数   
    int stack[i];
    int top = -1;
    
    for(int j = 0; j< i; j++)
    {
        if('(' == exp[j])
            stack[++top] = j;
        else if(')' == exp[j])
            cout<<stack[top--]<<"--"<<j<<',';
    }
}

// 需要定义 maxSize 常量
int brackets(char *exp)
{
    int stack[maxSize];
    int top = -1;
    
    for(int j = 0; j != '\0'; j++)
    {
        if('(' == exp[j])
            stack[++top] = j;
        else if(')' == exp[j])
            cout<<stack[top--]<<"--"<<exp[j]<<',';
    }
}

18年

请设计算法并写出算法代码，分析指定字符串中括号的匹配顺序，并按匹配顺序输出每一对括号的下标，若匹配出现错误，则停止计算。例如若指定字符串为“（（））”，则输出1 2 0 3。

int Brackets(char *str)
{
    int i;
    for(i = 0; str[i]; i++); // 统计个数赋值到 i
    int stack[i], top = -1;  // 初始化栈
    for(int j = 0; j < i; j++)
    {
        if('(' == str[j])		// 左括号入栈
            stack[++top] = j; 
        else if(')' == str[j]) // 右括号 匹配
        {
            if(top == -1) return -1;  // 出现错误返回-1**********************
            cout<<stack[top--]<<"--"<<exp[j]<<',';
        }
    }
    return 0;   //输出完所有的之后返回0代表，成功输出完毕。
}

9、中缀表达式括号是否匹配 19

请编写算法代码，判断指定表达式串（如“12+（a*(b-8)/3）”）中的括号（只含圆括号）匹配是否正确，匹配正确返回1，匹配有错误返回0。

详解版本 有三种方法，包括指针位移量偏移。

// 记忆下面的
// 这个 麻烦了
int Brackets(char *str)
{
    int i;
    for(i = 0; str[i]; i++); // 统计个数赋值到 i
    int stack[i], top = -1;  // 初始化栈
    for(int j = 0; j < i; j++)
    {
        if('(' == str[j])		// 左括号入栈
            stack[++top] = j; 
        else if(')' == str[j]) // 右括号 匹配
            top--;
    }
    return top == -1 ? 1 : 0;
}

// 这个简单
int Brackets(char *str)
{
    int count = 0;
    for(int i = 0; str[i] != '\0'; i++)
    {
        if(str[i] == '(')
            count++;
        else if(str[i] == ')')
            count--;
    }
    return count == 0 ? 1 : 0;
}

10、***判断有向无环图(拓扑排序) 20/21

/**
 * typedef struct ArcNode {
 * 	   int adj;
 * 	   ArcNode *nextarc;
 * }ArcNode;
 * 
 * typedef struct VexNode {
 * 	   ArcNode *firstarc;
 * }VexNode;
 * 
 * typedef struct Graph {
 * 	   VexNode *vexes;
 *     int vexnumber;
 * }Graph;
 */
// 拓扑排序
// 答案上给的是系统自带的stack 和 vector，这里我自定义的栈和数组

// 第一步：计算顶点入度：需要定义数组。
// 第二步：遍历数组，将入度为0的结点入度。
// 第三步：生成拓扑排序：主要是遍历边表。
bool HasCircuit(const Graph& G)
{
    //第一步 								统计各结点入度
    int n = G.vexnumbe;
    int inDegree[n];
    for(int i = 0; i < n; i++) 
        inDegree[i] = 0;
    // for 循环 遍历边表。
    for(int i = 0; i < n; i++)
        for(ArcNode *p = G.vexes[i].firstarc; p != NULL ; p = p->nextarc)
            inDegree[p->adj]++;
    
    // 第二步 入度为0的顶点入栈或队，用栈来贯穿这个算法
    int stack[n], top = -1;
    for(int i = 0; i < n; i++)
        if(inDegree[i] == 0)
            stack[++top] = i;
    
    // 第三步 生成拓扑序列
    int count = 0; // 用于判断是否成功
    while(top != -1)
    {
        int j = stack[top--];   
        count++;				// cout<<j<<" ";  // j 的输出就是 拓扑排序
        // 遍历边表，删除入度为0的点。
        for(ArcNode *p = G.vexes[j].firstarc; p! = null; p = p->nextarc)
        {
            inDegree[p->adj]--;
            if(inDegree[p->adj] == 0) 
                stack[++top] = p->adj; 
        }
    }
    return count == n;  // 返回1，则成功；返回0，则失败。
}

11、回文数组 08 12

// best method
// 简洁版
bool IsPalindrome(const char *s)
{
	int i=0,j;
	for(j=0; s[j]; j++); // 计算数组大小
	j--; 
    
	while(i < j)
		if(s[i++] != [j--])
			return false;
	return true;
}
// 正常版
bool IsPalindrome(const char *s)
{
	int i=0,j;
	for(j=0; s[j]; j++); // 计算数组大小
	j--; 
	while(i < j)
	{
		if(s[i]==s[j])
        {
            i++;
            j--;
			continue; // 不加也可以
		}
        else
			return false;
	}
	return true;
}

12、数组就地逆转、***单链表逆转13 14

数组逆转：解决方法：头和尾互换。画图思想

void Inverse(int arr[], int n)
{
	int temp;
	for(int i = 0; i < n/2; i++){ // 从中间分开，对称即可。
		temp = arr[i];
		arr[i] = arr[n-i-1];      // 注意右边的位置  n-i-1
		arr[n-i-1] = temp;
	}
}

单链表逆转 。解决方法：头插法即可解决。 画图思想。

将指定含头结点的单链表就地逆转（排列顺序反转）

/**
 * Definition for BiNode.
 * typedef struct LinkNode {
 *     ElementType data;
 *     Struct LinkNode *next;
 * };LinkNode, *LinkList
 */
void Inverse(LinkedList L)
{
	LinkedNode *p = L->next, *r;// r 保存后面结点。p 用来进行头插法，p指向第一个（非头）结点
	L->next = NULL;				// L 置为空
	while(p != NULL)
	{
		// 这两步：是将 p 结点 单独提取出来，并指向 L 后面的结点。
		r = p->next;			// r 指向 p 的后面结点，用来临时保存后面的地址。
		p->next = L->next;		// L 的后面挂在 p 后面，实现头插法
        // 头插入
		L-> next  = P;			// 然后将 p 指向 L头结点后面，完成头插法
		p = r;					// p 遍历指针后移。
	}
}

13、二叉排序树查找，插入13 17

i 非递归查找

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
BiNode* BinarySortTreeSearch(BiTree T, int key)
{
	while(T != NULL)
	{
		if(key == T->key) return T;
		else if(key > T->key) T = T->rchild;
		else if(key < T->key) T = T->lchild;
	}
	return NULL;
}

ii 递归查找

BiNode* BinarySortTreeSearch(BiTree T, int key)
{
	if(T == NULL) return NULL;
	if(key == T->key) return T;
	else if(key > T->key) 
        return BinarySortTreeSearch(T->rchild, key);
	else if(key < T->key) 
        return BinarySortTreeSearch(T->lchild, key);
}

iii 插入新节点

int Insert(Bitree t, int data)
{
    if(t = NULL){
        // t = (BinNode*)malloc(sizeof(BinNode)); //天勤定义
        t = new BinNode(); // 答案定义
        t->data = data;
        t->lchild = t->rchild = NULL;
        return 0;
    }
    if(data = t->data) return 1;
    else if(data > t->data)
        return Insert(t->rchild, data);
    else if(data < t->data)
        return Insert(t->lchild, data);
}

14、***三元组快速转置 14 17 (第25特殊)

/**
 * Definition for TriNode.
 * typedef struct TriNode {
 *     int row, col, value;
 * }TriNode;
 * typedef struct TriTable {
 *     TriNode *datas;
 *     int mu, nu, tu; // mu 为行数， nu 为列数， tu 为非零元个数。
 * }TriTable;
 */
TriTable Inverse(TriTable &M)
{
    // 准备目标三元组  mu 为行数， nu 为列数， tu 为非零元个数
    TriTable *aTriTable = new TriTable();
    aTriTable->mu = M.nu;
    aTriTable->nu = M.mu;
    aTriTable->datas = new TriNode[M.tu];
    
    // 计算  转置后各行的   非零元个数: 看 M 的列 nu
    int rsum[M.nu]; 
    for(int i = 0; i < M.nu; i++) // 初始化 全为 0， M.nu：M的列数
        rsum[i] = 0; 
    for(int i = 0; i < M.tu; i++) // M.tu : M 的非零元个数
        rsum[M.datas[i].col]++;
    
    // 计算  转置后各行的   排列起始下标
    int rpos[M.nu];
    rpos[0] = 0;
    for(int i = 1; i < M.nu; i++)
        rpos[i] = rpos[i-1] + rsum[i-1];
    
    // 快速转置
    for(int i = 0; i < M.tu; i++)
    {
        int j = rpos[M.datas[i].col]++;
        aTriTable->datas[j].row=M.datas[i].col;
        aTriTable->datas[j].col=M.datas[i].row;
        aTriTable->datas[j].data=M.datas[i].data;
    }
    // 返回 结果三元组
    return aTriTable;
}

15、逆序数 15 17

两层for循环。

int InversionNumber(int L[], int n)
{
    int count = 0;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(L[j] < L[i])
                count++;
    return count;
}

16、删除零元素，删除重复元素15 16 21

重大问题，下面中的简洁方法，似乎在取到最后一个元素的时候是有问题的。仔细改进下。

删除零元素 15年

// 方法一：这个方法很好，方法二：但是还有一个更好的方法。思路很简单，在下面,两个方法都掌握吧
int RemoveZero(int L[], int n)
{
	int i; 
	// i: 找到第一个零元下标，同时也统计了第一个零元之前的非零元个数
	for(i = 0; i< n && L[i] !=0; i++);
    
	for(int j = i + 1; j < n; j++);
	{
		if(L[i] == 0) continue;
		L[i] = L[j];
		i++;
	}
	return i;
}
// 这里可以扩展 涉及到 java 面试中 的list集合删除元素，list直接删除,会出现问题
int  RemoveZero(int L[], int n)   
{
	int i = 0 ;
    for(int j = 0; j < n; j++)
        if(L[j] != 0)
            L[i++] = L[j];
    }
	return i;  // 新数组长度
}

删除重复元素16

// 和上面的删除0元素一样，也有一个暴力简单的方法
int Zip(int L[], int n)
{
    if(n == 0) return 0;
	int i;
	for(i = 0; i < n-1 && L[i+1] > L[i]; i++); //找到第一个重复的下标。
	
	for(int j = i+1; j < n; j++)
	{
		if(L[j] > L[i])
            L[++i] = L[j];
	}
	return i+1; // 因为i 是下标，返回长度要+1。
}

// 删除重复元素。
int Zip(int L[], int n)    // 这里有问题，最后一个不会进行移动，所以for后面进行一步处理。
{
    int i = 0;
    // 当 j 取 n-1 时，n-1 最右端数据了，但是下边的 j+1 就数组越界了，所以改为 j < n-1。
    for(int j = 0; j < n-1; j++)
    {
        if(L[i] < L[j+1])
            L[i++] = L[j];
    }
    if(L[n-1] > L[i]) L[i++] = L[n-1];
	return i;  // 新数组长度
}

17、顺序表插入 18 20

/**
 * Definition for SList.
 * typedef struct SList {
 *     int buffer[BUFFERLEN];
 *	   int tablelen;
 * }SList;
 */
int Insert(SList &L, int pos, int data)
{
    if(pos < 0 || pos > L.tablelen) return 1;
    if(L.tablelen >= BUFFERLEN) return 1;      // 以上两行判断
    
    int n = L.tablelen - 1;
    for(int i = n; i >= pos; i--)
        L.buffer[i+1] = L.buffer[i];

    L.buffer[i] = data;
    L.bufferlen++; 							  // 忘记了,别忘记
    return i;								  // 题目没说，我这里返回的是插入的位置
}

18、二叉树叶子结点个数 18 20

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * }BinNode, *BiTree;
 */
int LeafNumber(BiTree T)
{
    if(T == NULL) return 0;
    if(T->lchild == NULL && T->rchild == NULL) 
        return 1;
    return LeafNumber(T->lchild) + LeafNumber(T->rchild);   // 注意哦
}

19、***还原带空节点#的前序遍历序列 21

还应该有后序确定二叉树

i 官方答案（有 bug）

Bitree GreatBitree(const char *s)
{
    InitStack(S);
    BiTree T = new BiTree;
    Bitree p = T;
    BiTree Lchild,Rchild;
    p.data = s[0];
    for(int i = 1; s[i] != '\0'; i++)
    {
        if(s[i] != '#')
        {
            Lchild = new BiTree();
            Lchild.data = s[i];
            Push(S, p);
            p->lchild = Lchild;
            p = p->lchild;
        }
        p->lchild = NULL;
        i++;
        if(s[i] == '#')
        {
            while(s[i] == '#')
            {
                p->rchild = NULL;
                POP(S, p);
            }
        }else
        {
            Rchild = new BiTree;
            Rchild.data = s[i];
            Push(S, p);
            p->rchild = Rchild;
            p = p->rchild;
        }
    }
    return T;
}

ii 网上正确答案（背这个）

#include<stdio.h>
#include<stdlib.h>

typedef char DataType;
typedef struct BinaryTree
{
    DataType data;
    struct BinaryTree* lchild;
    struct BinaryTree* rchild;
}BT;

// 背下面那个简介版本
BT* CreatTree(char* s, int i)
{
    if (s[i] != '\0')
    {
        if (s[i] != '#')
        {
            BT *p = (BT*)malloc(sizeof(BT));
            p->data = s[i];
            i = i + 1;
            // 创建左子树
            p->lchild = CreatTree(s, i);
            i = i + 1;
            // 创建右子树
            p->rchild = CreatTree(s, i);
            return p;
        }
        else
            return NULL;
    }
    return NULL;
}

BT* CreatTree(char* s, int i)
{
    if (s[i] == '\0' || s[i] != '#')
        return NULL;
    
    BT* p = new BT();
    p->data = s[i];
    i++;
    // 创建左子树
    p->lchild = CreatTree(s, i);
    i++;
    // 创建右子树
    p->rchild = CreatTree(s, i);
    return p;
}

int main()
{
    char s[100];
    BT *ps;
    int i = 0;
    ps=CreatTree(s, i);
    return 0;
}

20、二维数组压缩成三元组 21

/**
 * Definition for TriNode.
 * typedef struct TriNode {
 *     int i, j, e;
 * }TriNode;
 * typedef struct TriTable {
 *     TriNode *datas;
 *     int mu, nu, tu; // mu 为行数， nu 为列数， tu 为非零元个数。
 * }TriTable;
 */
// mu: 行。  nu：列
int CreateTrible(TriTable &T, int **A[][], int mu, int nu)
{
    int t = 0;   // 注意从 1 开始。
    for(int i = 0; i < mu; i++)
        for(int j = 0; j < nu; j++)
            if(A[i][j] != 0)
            {
                T.data[t].i = i;
                T.data[t].j = j;
                T.data[t].e = A[i][j];
                t++;
            }
    T.mu = mu;   // 矩阵的 行数
    T.nu = nu;   // 矩阵的 列数
    T.tu = t-1;  // 矩阵非零元个数
}

21、归并排序算法 21

// 试卷给的函数头只有 L 和 n。天勤给的 在下面，包含三个参数，所以这里要对天勤算法进行改编。
void MergeSortGuiBing(int L[], int n)
{
    MergeSort(L, 0, n-1);
}
// 天勤给的算法
void MergeSort(int L[], int low, int high)
{
    if(low < high)
    {
        int mid = (low + high)/2;
        MergeSort(L, low, mid);     // 左边 归并
        MergeSort(L, mid + 1, high); // 右边 归并
        merge(L, low, mid, high); // 其实就是两个数组合并的那个方法
    }
}

// 两个数组 合并的代码 等价于 3T
void merge(int arr[], int low, int mid, int high)
{
    int i, j, k;
    int n1 = mid - low, n2 = high - mid;
    int L[n1], R[n2];
    for(i = 0; i < n1; i++)
        L[i] = arr[low + i];
    for(j = 0; j < n2; j++)
        R[j] = arr[mid + j];
    
    i = j = 0;
    k = low;
    while(i < n1 && j < n2)
    {
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];
}

22、单链表删除结点 20

删除p 结点后面的结点。

/**
 * Definition for LinkNode.
 * typedef struct LinkNode {
 *     int data;
 *     LinkNode *next;
 * }LinkNode, *LinkList;
 */
int removeAfter(LinkNode* p){
    if(p == NULL || p->next == NULL) return 0;
    LinkNode *q;
    q = p->next;
    p->next = q->next;
    free(q);                             // 注意 delete q 和 free(q)
    return 1;
}

23、单链表交换指定结点 18

将一条单链表上指定结点后面的两个结点交换顺序。画图，清晰明了。

/**
 * Definition for LinkNode.
 * typedef struct LinkNode {
 *     int data;
 *     LinkNode *next;
 * }LinkNode, *LinkList;
 */
int Swap(LinkedNode *p)
{
    if(p == NULL || p->next == NULL || p->next->next == NULL) return 0;
    LinkedNode *q = p->next;
    p->next = q->next;
    q->next = p->next->next;   // 后面的 也可以是  q->next->next。
    p->next->next = q;
    return 1; // 1代表成功，0代表失败。一般 0-false，1-true。所以最好按正规的来。
}

24、***单链表合并并去重 17

单链表合并并去重

/**
 * Definition for LinkNode.
 * typedef struct LinkNode {
 *     int data;
 *     LinkNode *next;
 * }LinkNode, *LinkList;
 */
int Merge(LinkList A, LinkList B)
{
    LinkNode *pA = A, *pB = B;
    while(pA->next != NULL && pB->next != NULL)
    {
		if(pA->next->data < pB->next->data)      // pA 较小时，pA 后移一位 继续比较
            pA = pA->next;
        else if(pA->next->data > pB->next->data) // pB 较小时，pB插入到pA上，都后移一位比较
        {
            InsertAfter(pA, pB->next->data);     // 考试的时候写注释就可以了
            pA = pB->next;						 // PA 和 PB 都后移一位
            pB = pB->next;
        } 
        else 							// 最后相等就都后移一位（相当于去重了），再继续比较，
        {
            pA = pA->next;
            pB = pB->next;
        }
    }
    // 当A遍历完了，B还有的情况下。注意，因为这里是往A上插入，所以不存在A还没遍历完的情况
    while(pB->next!=Null) 
    {
        InsertAfter(pA, pB->next->data);
        pA = pA->next;
        pB = pB->next;
    }
    return 0;
}
void InsertAfter(LinkNode &p, int data)
{
    LinkNode newNode = new LinkNode();
    newNode->data = data;
    // 插入操作：先移动后面的，再赋值到 原来p 上
    newNode->next = p->next;
    p->next = newNode;
} 

25、***一维数组中的非压缩矩阵压缩到三元组 19

**问题描述：请编写算法代码，将指定的m行n列按行优先顺序非压缩存储在长度为m*n的的一维数组matrix中的系数矩阵压缩存储到目标三元组表T**中。数据结构见注释。

/**
 * Definition for TriNode.
 * typedef struct TriNode {
 *     int data, row, col;
 * }TriNode;
 * typedef struct TriTable {
 *     TriNode *datas;
 *     int mu, nu, tu; // mu 为行数， nu 为列数， tu 为非零元个数。
 * }TriTable;
 */
int CreateTriTable(TriTable &T, int matrix[], int m, int n)
{
    // 第一步：初始化 T
    T.mu = m;
    T.nu = n;
    
    // 第二步：统计非零元个数，也就是压缩三元组的总行数
    int count = 0;
    for(int i = 0; i < m * n; i++)
        if(matrix[i] != 0)        
            count++;
    T.tu = count;
    T.datas = new TriNode[count];
    
    // 第三步： 核心赋值操作，很经典。
    int k = 0, t = 0;            // k 为一位数组下标，  t 为目标三元组下标
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            if(matrix[k] != 0)    // 只要数据不为 0 ， 存就完事了！！！！！
            {
                T.datas[t].row = i;
                T.datas[t].col = j;
                T.datas[t].data = matrix[k];
                t++;
            }
            k++;
    return 1; // 1代表成功。
}

26、串的暴力破解 19

背官方答案

/**
 * Definition for Str.
 * typedef struct  {
 *     char *ch;
 *     int length;
 * }Str;
 */
// 串从数组下标 1 位置开始存储，因此初值为 1；
// 题中有可能不给 length，可以自己求出来。
int strstr(Str str, Str substr)
{
    int i, j, k ;  // 两个串的下标。i 为 主串的 下标，j 为子串的 下标。
    i = j = k = 1; 
    while(i <= str.length && j <= substr.length)
    {
        if(str.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
        {
            j = 1;   // 子串 直接 归 1 ，数组 从1开始存数据的。
            i = ++k; // 匹配失败，i 从主串的下一个位置开始， k 中记录了上一次的起始位置
        }
    }
    if(j > substr.length)
        return k;  
    else 
        return 0;  // 返回0代表失败 返回 k 代表匹配成功的主串开始位置。
}

官方答案：

char *strstr(char *src, char *pattern)
{
    char *p0 = arc;
    char *p1 = pattern;
    int k = 0; // 记录主串上次的位置
    while(p0 != '\0' && p1 != '\0')
    {
        if(*p0 == *p1)
        {
            p0++;
            p1++;
        }
        else
        {
            p0 = ++k; 	   // 主串回到 上一个初始值+1。
            p1 = pattern;  // 子串回到初始位置
        }
    }
    if(*p1 == '\0') // 匹配成功，返回主串对应的位置
        return k;
    else
        return NULL;  // 返回 NULL 代表失败 返回 k 代表匹配成功的主串开始位置。
}

27、汉诺塔 19

int Hanoi(int n, int a, int b, int c)
{
    if(n <= 0) return 0;
    Hanoi(n-1, a,c,b);
    Move(n,a,c); // 输出 cout<<a<<" -> "<<c<<endl;
    Hanoi(n-1, b, a, c);
    return 1;
}

28、图的DFS 18

/**
 * typedef struct ArcNode {
 * 	   int adj;
 * 	   ArcNode *nextarc;
 * }ArcNode;
 * 
 * typedef struct VexNode {
 * 	   ArcNode *firstarc;
 * }VexNode;
 * 
 * typedef struct Graph {
 * 	   VexNode *vexes;
 *     int vexnum;
 * }Graph;
 */
void DFS(Graph &G, int v0; int visited[])
{
    visited[v0] = 1;
    Visit(G, v0); //答案为  // cout << v0->data;  // 输出代码  
      
    ArcNode *p = G.vexes[v0].firstarc;
    while(p != NULL)
    {
        if(visit[p->adj] == 0)
            DFS(G, p->adj, visited);
        p = p->next;
    }
}

// 这个也可以，代替while 循环。
for(ArcNode *p = G.vexes[v0].firstarc; p != null ; p = p->next)
{
    if(visit[p->adj] == 0)
        DFS(G, p->adj, visited);
}

29、图的算法题:求最远距离 12

问题描述： 已知一个强连通图，用邻接表结构存储，请编写算法，计算指定顶点，V0到距V0最远的顶点的距离。V0到Vi的距离定义为V0到Vi的**最短路径的长度**，路径的长度定义为路径中弧的个数。数据结构看注释

求最远距离

/**
 * Definition for Graph.
 *  struct ArcNode
 * {
 * 	   int adj;
 * 	   int length;
 * 	   ArcNode *nextarc;
 * };
 * struct VexNode
 * {
 * 	   ArcNode * firstarc;
 * };
 * struct Graph
 * {
 * 	   VexNode vexes[MAXVEXNUMBER];
 * 	   int vexnumber;
 * };
 *
 */

// 就是 BFS 扩展了一下，多了一个 dist 数组
int visited[MAXVEXNUMBER]; // 访问标记数组
int GetMaxDistance(Graph &G, int v0)
{
    int n = G.vexnumber;
    
    int dist[n]; // 存储v0 到 vi的最短距离
    int que[n];int front = 0,rear = 0; 
    
    for(int i = 0; i < n; i++)
    {
        dist[i] = 0;
        visited[i] = 0;
    }
    
    visited[V0] = 1;
    rear = (rear + 1) % n; //Enqueue(Q, v0);
    que[rear] = v0;
    
    // 以上为初始化，接下来为 BFS 算法主过程
    while(front != rear)//!isEmpty(Q)		// 
    {
        front = (front + 1) % n; //DeQueue(Q, v0);// 对头元素v0出队
        int j = que[front];
        
        for(int w = FirstNeighbor(G, j); w >= 0; w = NxtNeightbor(G, v0, w))
            if(visited[w] == 0) // w 为 v0 尚未访问的邻接顶点
            { 
                visited[w] = 1; // 设1、已访问标记
                dist[w] = d[v0] + 1;  //2、路径长度加1
                rear = (rear + 1) % n;//3、顶点 w 入队
                que[rear] = w;
            }
        }
    }
    // 求 d  数组 中的最大值。
    int max = dist[0];
    for(int i = 1; i < n; i++)
        if(dist[i] > max)
            max = dist[i];
    return max;
}

// 下面这个应该是不可以的
        //for(int w = FirstNeighbor(G, j); w >= 0; w = NxtNeightbor(G, v0, w))
        for(ArcNode *p = G.vexes[j].firstarc; p != null; p = p->next){
            if(visited[p->adj] == 0) // w 为 v0 尚未访问的邻接顶点
            { 
                visited[p->adj] = 1; // 设1、已访问标记
                dist[p->adj] = d[v0] + 1;  //2、路径长度加1
                rear = (rear + 1) % n;//3、顶点 w 入队
                que[rear] = p->adj;
            }
        }

30、最短路径Floyd 13

/**
 *  struct ArcNode
 * {
 * 	   int adj;
 * 	   int length;  // 权值数据
 * 	   ArcNode *nextarc;
 * };
 * struct VexNode
 * {
 * 	   ArcNode * firstarc;
 * };
 * struct Graph
 * {
 * 	   VexNode vexes[MAXVEXNUMBER];
 * 	   int vexnumber;
 * };
 * 预定义常量名MAXINT 表示int 的最大值，可以用来表示无穷大。
 */
void GetMinPath(Graph &G, int** result)
{
	int n = G.vexnumber;
	// 第一步：将邻接表 转化为 邻接矩阵（官方给出的）
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			// 先对整个二维数组赋值，因为下面的转化，仅赋值了一部分
			result[i][j] = MAXINT; 
    // for循环遍历边表，对 result 进行 实际 赋值
	for(int i = 0; i < n; i++)
		for(ArcNode *p = G.verex[i].firstarc; p != NULL; p = p->nextarc)
			result[i][p->adj] = p->length;

	// 第二步：核心 Floyd 算法
	for(int k = 0; k< n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(result[i][j] > result[i][k] + result[k][j])
					result[i][j] = result[i][k]+result[k][j];
}

31、数组移动所有偶数 18

类似题：16年4T （删除序列重复元素）, 15年5T（删除序列中零元素） 都在第16题。

int GetEven(int L[], int n)
{
    int evenLen = 0; // 当做指针下标
    for(int i = 0; i < n; i++)  
        if((L[i]%2) == 0)
            L[evenLen++] == L[i];
    return evenLen;  // 返回处理后的总长度
}

32、序列最值差值 14

int Range(int arr[], int n)
{
	int max = 0; // 存最大值下标 
    int min = 0; // 存最小值下标
	for(int k = 1; k < n; k++)
	{
		if(arr[max] < arr[k]) 
            max = k; // 存最大
        else if(arr[min] > arr[k]) 
            min = k; // 存最小
	}
	return arr[max] - arr[min];
}

33、数组相同元素最多个数 12

int GetMaxPlatformWidth(int Height[], int n)
{
	// 进行选择相同个数最多的数和下标
	int tempNums = 1; 	   // 当前遍历相同元素的个数， 从 1 开始。
	int maxNums = 0;       // 前边遍历相同元素最多的个数
	for(int i = 0; i < n - 1; i++)  // 共比较 n-1 次，因为是相邻的两个元素比较，最多 n-1次。
	{
		if(Height[i] == Height[i+1])
			tempNums++;
		else 
        {     				// 如果不相等，则判断上一个连续的平台是否最宽
			if(maxNums < tempNums){
				maxNums = tempNums;  // 当前的大于前边的的， 那就取当前为最多的
                tempNums = 1;   // 相邻高度不同，重新计数
			}
		}
    }
	return maxNums;
}

34、（背）判断二叉树是否相同（内容结构） 17

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
// 主要就是第三个if的数据判断。
int Compare(BiTree t1, BiTree t2)
{
    if(t1 == NULL && t2 == NULL)   // 第一：空树
        return 1;
    if(t1 != NULL && t2 != NULL)   // 第二：都不为空
    {
        if(t1->data != t2->data)   // 第三：判断数据
            return 0;			   // 第四：递归
        return Compare(t1->lchild, t2->lchild) && Compare(t1->rchild, t2->rchild);
    }
    return 0;  // 返回 1 则相同，返回 0 则不相同
}

35、二叉树交换子树 16

将指定的二叉链结构二叉树中**所有结点的左右子树交换**（左子树变成右子树，右子树变成左子树）。只交换左右子树 即可。

前序交换（类似于前序遍历），从头交换到脚。

// 数据结构同上一题
// 前序交换（类似于前序遍历）：从根结点开始，进行 交换。 下面的递归，依次进行交换。
int SwapLeftRight(BiTree T)
{
	if(T == NULL) 
        return 0;
    
	BiNode* temp = T->lchild;   // 交换，类似于冒泡 交换。
	T->lchild = T ->rchild;
	T->rchild = temp;
    // 递归操作 recursion 
	SwapLeftRight(T->lchild);
	SwapLeftRight(T->rchild);
	return 1;  
}

36、（背）二叉树深度 12

下面 37和 39 都用到了此函数。

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
int deepth(BiTree T)
{
	if(T == NULL) return 0;
    
    int Ld = deepth(T->lchild);
    int Rd = deepth(T->rchild);
    return (Ld > Rd ? Ld : Rd) + 1;   // 三元组表示法
}

37、二叉树根结点平衡因子 15

和14年3T（判断指定的二叉树是否为平衡二叉树） 异曲同工之妙，也就是下面的39T。

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
int GetBalanceFactor(BiTree T)
{
	if(T == NULL) return 0; // 空树，平衡因子为 0。
	int lDepth = deepth(T->lchild);
	int rDepth = deepth(T->rchild);
	return lDepth - rDepth;
}
// 获取最大高度的函数
int deepth(BiTree T)
{
	if(T == NULL) return 0;
    
    int Ld = deepth(T->lchild);
    int Rd = deepth(T->rchild);
    return (Ld > Rd ? Ld : Rd) + 1;   // 三元组表示法
}

38、二叉树第K层结点个数 08

天勤上有个层次遍历应用的题，求树的宽度，不用看了，比较难。

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
int PointsInLevel(BiTree T, int k)
{
	if(T == NULL || K < 0) return 0;
	if(K == 0) return 1; // 题目设定根结点在0层  // 如果是根结点在1层, 则 if 判断为 k == 1
	return PointsInLevel(T->lchild, k-1) + PointsInLevel(T->rchild, k-1);
}

39、判断是否为平衡二叉树 14

如果根结点的 平衡因子 大于1 或 小于 -1 则不平衡。借用了37T的思想

/**
 * Definition for BiNode.
 * struct BiNode {
 *     ElementType data;
 *     Struct BiNode *lchild, *rchild;
 * };BinNode, *BiTree
 */
int IsBalance(BiTree T)
{
	if(T == NULL) return 1; // 空树也是平衡树, 1 代表平衡二叉树
	int hl = deepth(T->lchild);
	int hr = deepth(T->rchild);
    if((hl - hr) > 1 || (hl - hr) < -1)  // if(abs(hl - hr) > 1) 
		return 0;  // 0 代表 不是平衡二叉树。 1 代表是平衡二叉树
	else 
		return IsBalance(T->lchild) && IsBalance(T->rchild);
}
// 获取高度的函数 就是 二、36T。
int deepth(BiTree T)
{
	if(T == NULL) return 0;
    
    int Ld = deepth(T->lchild);
    int Rd = deepth(T->rchild);
    return (Ld > Rd ? Ld : Rd) + 1;   // 三元组表示法
}

40 、栈基本操作 16

注意 初始值 top 位置。栈满时的条件

/**
 * Definition for Stack.
 * struct Stack {
 *     double buffer[MAXBUFFERLEN];
 *     int top; // 题目设定初始时，top = 0
 * }Stack;
 */
// 入栈
int Push(Stack &S, double data)
{
	if(S.top == MAXBUFFERLEN) return 0; // 栈满  注意这里的初始，top 为0，教材一般为-1
	S.buffer[S.top] = data;
	S.top++;
	return 1; // 0 失败，1成功
}
//出栈
int Pop(Stack &S)
{
	if(S.top == 0) return 1; // 栈空
	double data = S.buffer[--S.top];
	return data;
}
//栈空
int Empty()
{
	if(S.top == 0) 
        return 1;
    else 
		return 0; // 1 代表栈空， 0代表 不空
}

41、队列基本操作 15

/**
 * Definition for Queue.
 * typedef struct Queue {
 *     double buffer[MAXBUFFERLEN];
 *     int head, tail; // 初始时 head=tail=0;
 * }Queue;
 */
//入队操作
int EnQueue(Queue &Q, double data)
{
	int front = Q.head, rear = Q.tail;
	rear = (rear + 1) % MAXBUFFERLEN;
	if(rear = MAXBUFFERLEN) 
        return 0; // 判断队满
	else 
	{
		Q.buffer[rear] = data;
	}
	return 1;  // 0表示队满，1表入队成功
}
//出队操作
int DeQueue(Queue &Q)
{
	int front = Q.head, rear = Q.tail;
	double res;
	if(rear = front) 
        return 0; // 判断队空
	else 
	{
		front = (front + 1) % MAXBUFFERLEN;
		res = Q.buffer[front];
	}
	return res;  // 返回出队的数据，0 代表失败
}

四、扩展必背

1、二叉树的确定

i 前序+中序

// 如果考到，不一定给 L1 R1 L2 R2
// pre[]: 前序序列数组 数组下标范围 从 L1 到 R1。 L1 从0或者1开始，注意题干是否给出，不给出 默认 0
// in[]:  中序序列数组 数组下标范围 从 L2 到 R2。
BTNode *CreateBT(char pre[], char in[], int L1, int R1, int L2, int R2)
{
    if(L1 > R1) return NULL;
    
    // 第一步：从前序数组 拿首元素 做为根节点
    BTNode *s = (BTNode *)malloc(sizeof(BTNode));
    s->lchild = s->rchild = NULL;
    s->data = pre[L1];
    
    // 第二步：在中序序列中 找到根结点位置，将中序序列分成两部分。
    int i;
    for(i = L2; i <= R2; ++i)  
        if(in[i] == pre[L1])   
            break;
    
    // 第三步：递归操作
    // pre 数组 和 in 数组的 左分支
    s->lchild = CreateBT(pre, in, L1 + 1, L1 + i - L2, L2, i - 1);
    // pre 数组 和 in 数组的 右分支
    s->rchild = CreateBT(pre, in, L1 + i - L2 +1, R1, i + 1, R2);
    return s;
}

ii 中序+后序

BTNode *CreateBT(char post[], char in[], int L1, int R1, int L2, int R2)
{
    if(L1 > R1)
    	return NULL;
    // 第一步： 从后序数组 拿未元素 做为根节点
    BTNode *s = (BTNode *)malloc(sizeof(BTNode));
    s->lchild = s->rchild = NULL;
    s->data = post[R1];
    
    // 第二步：在中序序列中 找到根结点位置，将中序序列分成两部分。
    int i;
    for(i = L2; i <= R2; ++i)
        if(in[i] == post[R1])
            break;
    // 第三步：递归操作
    // post 数组 和 in 数组的 左分支
    s->lchild = CreateBT(post, in, L1, L1 + i - L2 - 1, L2, i - 1);
    // post 数组 和 in 数组的 右分支
    s->rchild = CreateBT(post, in, L1 + i - L2, R1 - 1, i + 1, R2);
    return s;
}

2、最小生成树（针对无向图，邻接矩阵）

i prim(普利姆算法) 针对顶点

void Prim(MGraph g, int v0, int &sum)
{
    // 第一步：初始化 lowcost 和 vset
    int lowcost[maxSize], vset[maxSize];
    for(int i = 0; i < g.n; ++i)
    {
        lowcost[i] = g.edges[v0][i];
        vset[i] = 0;
    }
    vset[v0] = 1;
    sum = 0;

    // 第二步：核心代码，注意 共循环 n-1次，因为上面 v0 开始结点。
    int k, min, v = v0;  // k：临时存储最小权值的 结点下标。min ：最小值。v：初始顶点。
    for(int i = 0; i < g.n-1; ++i)
    {
        min = INF;	// INF: 是一个已经定义的比图中所有边权值都大的常量。
        for(int j = 0; j < g.n; ++j)
            // 选出当前生成树到其余顶点最短边中的最短的一条（注意这里两个最短的含义）
        	if(vset[j] == 0 && lowcost[j] < min) 
            {							
                min = lowcost[j];
                k = j;
            }
        vset[i] = 1; // 注意 是 i，看第一个for循环对应的哪个结点。
        v = k;
        sum += min;
        // 下面这个循环以刚并入的顶点 v 为媒介更新侯选边。
        for(int j = 0; j < g.n; ++j)
            if(vset[j] == 0 && lowcost[j] > g.edges[v][j])
                lowcost[j] = g.edges[v][j];
    }
}

ii 克鲁斯科尔（可能性不大，因为有排序）

typedef struct
{
    int a, b;  // a 和 b 为一条边所连的两个顶点
    int w;     // 边的权值
}Road;

Road road[maxsize];

int v[maxsize];  // 并查集数组

// 克鲁斯卡尔
void Kruskal(Mgraph g, int &sum, Road road[])
{
    // 第一步：初始化sum 和 并查集数组。
    sum = 0;
    for(int i = 0; i < g.n; ++i)
        v[i] = 1;				
    
    // 第二步：按权值排序
    sort(road, g.e); // 对 road 数组中的 E 条边按权值从小到大排序（任意排序算法即可）

    // 第三步：核心代码
    for(int i = 0; i < g.e; ++i)
    {
        int a = getRoot(road[i].a);
        int b = getRoot(road[i].b);
        if(a != b)// 相等：有相同根，属于同一个集合。不相等：无相同根，不属于同一个集合。
        {
            v[a] = b;  			// 更新并查集，将 b 并入
            sum += road[i].w;
        }
    }
}

// 根据结点 a 找到根结点。
int getRoot(int a)
{
    while(a != v[a]) 
        a = v[a];    
    return a;
}

3、最短路径（针对有向图，邻接矩阵）

i 迪杰斯特拉

// dist[] 数组中存放了v点到其余顶点的最短路径长度，
// path[] 中存放 v 点到其余各顶点的最短路径。
// set[] 并入最短路径的结点设置为1，类似于 prim算法中的cset。
// INF: 是一个已经定义的比图中所有边权值都大的常量。

void Dijkstra(Mgraph g, int v, int dist[], int path[])
{
    // 第一步：初始化 dist,set,path。
    int set[maxSize];
    for(int i = 0; i < g.n; ++i)
    {
        dist[i] = g.edges[v][i];
        set[i] = 0;
        if(g.edges[v][i] < INF)  // INF 为最小常量，也就是v-i有路径，则赋值为v。
            path[i] = v;
        else
            path[i] = -1;
    }
    set[v] = 1; 
    path[v] = -1;
        
    // 第二步：关键操作开始， 共为 n-1 轮，因为 v0 已经并入了
    int min, u;  // min:存最小值，u:存最小值时的下标。
    for(int i = 0; i< g.n -1; ++i)
    {
        min = NIF; 
       // 这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的
        for(int j = 0; j < g.n; ++j)
            if(set[j] == 0 && dist[j] < min)
            {
                min = dist[j];
                u = j;
            }
        set[u] = 1; // 将选出的顶点并入最短路径中
        // 这个循环以刚并入的顶点作为中间点，对所有通过剩余顶点的路径进行检测。
        for(int j = 0; j < g.n; ++j)
			// 这个if语句判断顶点u的加入是否会出现通往顶点j的更短的路径，如果出现，则改变原来路径及长度，否则什么都不做
            if(set[j] == 0 && dist[j] > dist[u] + g.edges[u][j])
            {
                // 如果小于，则改变dist和path，类似于Floyd
                dist[j] = dist[u] + g.edges[u][j]; 
                path[j] = u;
            }
    }
}

/**path 数组中其实保存了一棵树，这是一颗用双亲存储结构存储的树，通过这棵树可以打印出从源点到任何一个顶点最短路径上所经过的所有顶点。树的双亲表示法只能直接输出由叶子结点到根结点路径上的结点，而不能逆向输出，因此需要借助一个栈来实现逆向输出，打印算法如下。**/
void printPath(int path[], int a)
{
    int stack[maxSize], top = -1;
    // 这个循环以由叶子结点到根结点的顺序将其入栈。
    while(path[a] != -1)
    {
        stack[++top] = a;
        a = path[a];
    }
    stack[++top] = a;
    while(top != -1)
        count << stack[top--]<<" "; // 出栈并打印出栈元素，实现了顶点的逆序打印。
    cout<<endl;
}

ii Floyd 真题 13年，二、30

void GetMinPath(Graph &G, int** result)
{
	int n = G.vexnumber;
	// 第一步：将邻接表 转化为 邻接矩阵（官方给出的）
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			// 先对整个二维数组赋值，因为下面的转化，仅赋值了一部分
			result[i][j] = MAXINT; 
    // for循环遍历边表，对 result 进行 实际 赋值
	for(int i = 0; i < n; i++)
        // 遍历 边表。
		for(ArcNode *p = G.verex[i].firstarc; p != NULL; p = p->nextarc)
			result[i][p->adj] = p->length;

	// 第二步：核心 Floyd 算法
	for(int k = 0; k< n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				if(result[i][j] > result[i][k] + result[k][j])
					result[i][j] = result[i][k]+result[k][j];
}

4、串的算法

i 暴力破解法 二、26

ii kmp算法

// 获取 nextval 数组 substr：模式串
void getnext(Str substr, int next[])
{
    int i = 1, j = 0;// 串从数组下标 1 位置开始存储，因此 i 初值为 1. next数组由i决定，从1开始
    next[1] = 0;
    while(i < substr.length)
    {
        if(j == 0 || substr.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}

// kmp 算法
int kmp(Str str, Str substr, int next[])
{
    int i = 1, j = 1; // i 为主串下标，j 为子串下标。 都从 1 开始
    while(i <= str.length && j <= substr.length)
    {
        if(j == 0 || str.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
        }
        else
            j = next[j];
    }
    if(j > substr.legnth)
        return i-substr.length;
    else 
        return 0;
}

iii 改进kmp算法

仅有nextval替换 next 数组而已

void getnextval(Str substr, int nextval[])
{
    int i = 1; j = 0; // 串从数组下标1 位置开始存储，因此 i 初值 为1
    nextval[1] = 0;
    while(i < substr.length)
    {
        if(j == 0 || substr.ch[i] == substr.ch[j])
        {
            ++i;
            ++j;
            if(substr.ch[i] != substr.ch[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

5、汉诺塔(27T)、约瑟夫环（最后看吧）

约瑟夫环

int Joseph(int n, int m)
{
    int num = n; // 环内剩余人数
    int count = 0; // 计数，当 count == m 时，淘汰这个人。
    int index = 0;
    int circle[n]; // 0 表示在这个人在约瑟夫环内，1 表示这个人出圈
    
    // 初始化约瑟夫环
    for(int i = 0; i < n; i++)
        circle[i] = 0; 
    
    
    while(num > 1)	   // 只要环内剩余人数大于1，则一直进行循环
    {
        if(circle[index] == 0) // 轮到报数 是 0  的计数，是 1 则判断下一个孩子
            count++;
        if(count == m)         // 当 count==m 时，就要淘汰当前这个人
        {
            circle[index] = 1;
            num--;
            count = 0;
        } 
        // 与总人数 n 取余，则可以使 index 在 0~n-1之间 一直循环，达到循环数组的目的的
        index = (index + 1) % n;
    }
}

6、图的 DFS(28T)、BFS广度优先遍历（层次遍历）

邻接表的 深度、广度 时间复杂度 都是 O(n+e)

邻接矩阵 的 深度、广度 时间复杂度 都是 O(n2)

// 声明队列 + 4 + 2 + 4。4：访问和入队，2：出队
void BFS(AGraph *G, int v, int visit[maxSize])// visit 被默认初始化为0
{
    int que[maxSize], front = 0, rear = 0;
    int j;
   
    // 访问和入队                     一般都连着 ，这四行 一块记忆，下面核心遍历中也是这四行。
    Visit(v);
    visit[v] = 1;
    rear = (rear + 1) % maxsize;
    que[rear] = v;
    
    // 核心遍历 
    while(front != rear)
    {
        front = (front + 1) % maxsize;		// 顶点出队。
        j = que[front];
        
        for(ArcNode *p = G->adjlist[j].firstarc; p != null; p = p->nextarc)
        {
            if(visit[p->adjvex] == 0)       // 当前邻接顶点 未被访问，则进队
            {
                Visit(p-adjvex);
                visit[p-adjvex] = 1;
                rear = (rear + 1) % maxsize; // 该顶点入队
                que[rear] = p->adjvex;
            }
        }
    }
}

// 用上面的 for 循环 代替了下面的，上面的 for循环会更方便记忆代码和逻辑，
// 这两段代码 同一个作用：遍历 边表。
// 好多地方用到的基本上都是 for循环版本 来遍历 边表，如 拓扑排序、Floyd算法中邻接表转化为邻接矩阵
p = G->adjlist[j].firstarc;			// p 指向出队顶点j 的第一条边。
// 核心操作
while(p != NULL)					// 将p的所有邻接点 中未被访问的入队
{
    if(visit[p->adjvex] == 0)       // 当前邻接顶点 未被访问，则进队
    {
        Visit(p-adjvex);
        visit[p-adjvex] = 1;
        rear = (rear + 1) % maxsize; // 该顶点入队
        que[rear] = p->adjvex;
    }
    p = p->nextarc;  // p 指向j 的下一条边
}

7、二叉树的层次和深度遍历 递归和非递归（03年之前都考过）

i 二叉树的深度优先 非递归遍历

记完前序和中序，后序就根据前序背出来啦。

1、 前序；

void preorderNonrecursion(BTNode *bt)
{
    if(bt == null) 
        return;
    BTNode *stack[maxSize]; int top = -1; // 声明栈

    BTNode *p;  	// 遍历指针
    stack[++top] = bt; // 入栈
    
    // 核心遍历
    while(top != -1)
    {
        p = stack[top--];// 出栈 访问
        Visit(p);
        
        if(p->rchild != null)	// 先入 右孩子、 再入 左孩子。
            stack[++top] = p->rchild;
        if(p->lchild != null)
            stack[++top] = p->lchild;
    }
}

1、 中序；

void inorderNonrecursion(BTBode *bt)
{
    if(bt == null) 
        return;
    BTNode *stack[maxSize]; int top = -1;

    BTNode *p = bt;
    while(top != -1 || p != null)
    {
        while(p != null)		// 左孩子依次入栈
        {	
            stack[++top] = p;
            p = p->lchild;
        }
        if(top != -1)
        {
            p = stack[top--];
            Visit(p);
            p = p->rchild;
        }
    }
}

1、 后序和前序一样，有三个不一样点记住特殊吧；

void postorderNonrecursion(BTNode *bt)
{
    if(bt != null)
    {
        // 定义两个栈
        BTNode *stack1[maxSize]; int top1 = -1;
        BTNode *stack2[maxSize]; int top2 = -1;  	// 第一个不同点
        BTNode *p;
        stack[++top1] = bt;
        while(top1 != -1)
        {
            p = stack1[top1--];
            stack2[++top2] = p; // 第二个不同点：注意这里和先序遍历的区别，输出改为入stack2
            if(p->lchild != null)// 第三个不同点：这里是先左再右
                stack1[++top1] = p->lchild;
            if(p->rchild != null)
                stack1[++top1] = p->rchild;
        }
    }
    while(top2 != -1)
    {
        // 出栈顺序即为后序遍历序列
        p = stack2[top2--];
        Visit(p); // Visit() 是访问p的函数，在这里执行打印结点值的操作。
    }
}

ii 前中后序 递归遍历

// 记住一个，其他三个全部都记住啦
//1. 前序
void preOrder(BTNode *p)
{
    if(p!=null)
    {
        Visit(p);

        preOrder(p->lchild);
        preOrder(p->rchild);
    }
}
//2. 中序
void inOrder(BTNode *p)
{
    if(p!=null)
    {
        inOrder(p->lchild);
        
        Visit(p);
        
        inOrder(p->rchild);
    }
}
//3. 后序
void postOrder(BTNode *p)
{
    if(p!=null)
    {
        postOrder(p->lchild);
        postOrder(p->rchild);
        
        Visit(p);
    }
}

iii 二叉树的广度优先遍历：层次遍历

void level(BTNode *p)
{
    if(p == null) return;
    
    BTNode *que[maxSize]; int front = 0, rear = 0;		// 1. 声明队列和遍历指针
    BTNode *q;
    
    rear = (rear + 1) % maxSize; // 2. 入队
    que[rear] = p;
    while(front != rear)
    {
        front = (front + 1) % maxSize;	// 3. 出队 访问
        q = que[front];
        Visit(q);
        
        if(q->lchild != NULL)			// 4. 左右入队。
        {
            rear = (rear + 1) % maxSize;
            que[rear] = q->lchild;
        }
        if(q->rchild != NULL)
        {
            rear = (rear + 1) % maxSize;
            que[rear] = q->child;
        }
    }
}

8、08年之前的代码，需要看一下

类似题：24T：单链表去重合并，12T：单链表逆转，

i 两个单链表交叉合并 2003

**问题描述：**请编写一个算法，将指定的一个单链表（带头结点）**交叉合并**到另一个单链表（带头结点）中。

例如，对单链表A（a1,a2,a3,…）和B（b1,b2,b3…）使用该算法，应该得到结果单链表A为（a1,b1,a2,b2,a3,b3…），B为空表。

/**
 * Definition for LinkNode.
 * typedef struct LinkNode {
 *     ElementType data;
 *     struct LinkNode *next;
 * }
 * typedef LinkNode *LinkList;
 */
void MergeLinkList(LinkList &A, LinkList B)
{
    LinkNode *pa = A->next; *pb = B->next; // p和q 分别指向链表AB的第一个结点
    LinkNode *r = A; // 设 r 为指向链表A的尾指针，程序使用尾插法，遍历指针
    A->next = NULL;  // 摘下头结点 
    while(pa != NULL && pb != NULL)
    {
        r->next = pa;
        r = pa;
        pa = pa->next;
        r->next = pb;
        r = pb;
        pb = pb->next;
    }
    if(pa)
        r->next = pa; // 把剩余结点连接
    else 
        r->next = pb;
    free(B); // 释放链表B
}

五、大纲要求

1. 排序and 查找：归并+希尔是重点

i 直接插入排序

void insert(int arr[], int n)
{
    int temp,j;
    for(int i = 1; i < n; i++)  // 注意从1开始，共 n-1 趟。
    {
        temp = arr[i];
        j = i - 1;
        while(j >= 0 && temp < arr[j]) // 核心 通过while循环找到待插入的位置，
        {
            arr[j + 1] = arr[i];
            j--;
        }
        arr[j+1]=temp;
    }
}

ii 冒泡排序

void bubble(int arr[], int n)
{
    int temp, flag;
    for(int i = n-1; i > 0; i--) // 共 n-1 次，倒着来。
    {
        flag = 0;
        for(int j = 1; j <= i; j++)
        {
            if(arr[j-1] > arr[j]) // 核心操作，找到冒泡操作
            {
                temp = arr[j-1];
                arr[j-1]=arr[j];
                arr[j] = temp;
            }
        }
        if(flag == 0)
            return;
    }
}

iii 简单选择排序

void simplySelectSort(int arr[], int n)
{
    int temp, k;
    
    for(int i = 0; i < n; i++)
    {
        k = i;
        for(int j = i + 1; j < n; j++) // 核心操作算法，找到一个序列中 最小值，并保存 下标。
        {
            if(arr[j-1] < arr[j])
                k = j-1;
        }
        temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
}

iv 希尔排序 **

void shellSort(int arr[], int n)
{
    int temp;
    for(int gap = n/2; gap > 0; gap /=2)
    {
        for(int i = gap; i < n; i++)
        {
            temp = arr[i];
            int j;
            for(j = i; j > gap && arr[j-gap] > temp; j-=gap) //第三个for循环 比较交换
                arr[j] = arr[j-gap];
            arr[j] = temp;
        }
    }
}

2. 图 前面都有了

3 二叉树：真题+下面的北化资料了

4 线性表：真题为主

5 串+矩阵：二维压缩成三元组，三元组转置，kpm，暴力。

六、北化资料必背

1、判断是否是完全二叉树（理解+背）

画图来分析。：利用层次遍历 来判断是否为完全二叉树。

第一步：二叉树层次遍历（不同点：这里不用判断是否为空）

第二步：遇到null，进else ，依次出队，有一个不为null 则为非完全二叉树。

int isComplete(BiTree T)
{
    if(T == NULL) return 1;	// 空树为满二叉树。
    
    BiTree que[maxSize];
    int front = 0, rear = 0;
    
    rear = (rear + 1) % maxSize;
    que[rear] = T;
    
    while(front != rear)
    {
        // 先层次遍历，
        front = (front + 1) % maxSize;
        Bitree p = que[front];
        
        if(p)  				// 结点非空，将其左右子树入队列
        {
            rear = (rear + 1) % maxSize; 
            que[rear] = p->lchild;
            rear = (rear + 1) % maxSize;
            que[rear] = p->rchild;
        }
        else				// 进来就是第一次结点为null，检查其后是否有非空结点。
        {
            while(front != rear)
            {
                front = (front + 1) % maxSize;
        		Bitree p = que[front];
                if(p) return 0;    // 结点非空，则二叉树为非完全二叉树
            }
        }
    }
}

2、判断是否是二叉排序树（理解+背）

利用性质：左孩子<父结点<右孩子，来判断是否为二叉排序树。

int predt = -32767; // 为全局变量，保存当前结点中序前缀的值，初始 为 -无穷。
int JudgeBST(BiTree bt)
{
    if(bt == NULL) 
        return 1;
    
    int b1, b2;
    b1 = JudgeBST(bt->lchild);   // 递归到最左边结点
    if(b1 == 0 || predt >= bt->data)
        return 0;
    
    predt = bt->data;
    b2 = JudgeBST(bt->rchild);
    return b2;
}

3、求指定结点在给定二叉排序树中的层次(easy)

简单，加上一个count值，累加即可。

int level(BiTree bt, BSTNode *p)
{
    if(bt == NULL) 
        return 0;
    
    int l = 1;
    BiTree t = bt;

    while(t->data != p->data)
    {
        if(t->data < p->data)	// 右子树查找
            t = t->lchild;
        else
            t = t->rchild;		// 左子树查找
        l++;
    }
    return l;
}

4、递归求二叉树高度 二、36

int GetDepth(BiTree T)
{
	if(T == NULL) return 0; // 高度为0
	int lDepth = GetDepth(T->lchild);
	int rDepth = GetDepth(T->rchild);
    return (lDepth > rDepth ? lDepth : rDepth) + 1; 
}

版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: