答案
1.1 - 1.2 B C
2.1 - 2.9 B D C D A C D A C
3.1 - 3.5 A A C C C
知识点分析
《二维数组与三对角矩阵》
【二维数组】二维数组本质上是以数组作为数组元素的数组，即“数组的数组”，类型说明符 数组名[常量表达式][常量表达式]。二维数组又称为矩阵，行列数相等的矩阵称为方阵。对称矩阵a[i][j] = a[j][i]，对角矩阵：n阶方阵主对角线外都是零元素。
【三对角矩阵】在线性代数中，三对角矩阵是矩阵的一种，它“几乎”是一个对角矩阵。准确来说：一个三对角矩阵的非零系数在如下的三条对角线上：主对角线、低对角线、高对角线。在许多物理问题中，三对角矩阵常常作为原始数据出现，因此它们本身是很重要的，这种矩阵仅有（2n-1）个独立的元素。由三对角矩阵确定特征值由一些较有效的方法，常见的有两种：QR法、特征多项式法。
《树》
image.png
【二叉树结点计算】n个节点的二叉树形态共有 C(2n,n)-C(2n,n-1) 种。若一棵二叉树的高度（即层数）为h，则该二叉树最多有 2^h-1 个结点（节点）
【二叉链表】树的二叉链表实现方式：每个结点都包含两个指针，一个左孩子，一个右孩子。
【二叉树遍历】（先序：根左右）（中序：左根右）（后序：左右根）。
【满二叉树】一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
【二叉排序树】又叫平衡二叉搜索树、二叉查找树、二叉搜索树
（关键码序列）关键码表示结点上的值，关键码序列的起始必须是根结点，按后面的序列表依次画树，满足即正确。
（定位）
（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
（特点）从左到右排列同层次的结点，其关键字呈现有序排列的特点
非空二叉排序树=完全二叉树+二叉排序树
【最优二叉树】哈夫曼树、霍夫曼树、赫夫曼树
（构建哈夫曼树）排序-->取前2个构建树-->向上生长。最终所有的叶子结点为所有值。具体参考：https://blog.csdn.net/dongfei2033/article/details/80657360
（注意1）有权值重复时，可能树的高度都不唯一
（注意2）编码长度为层数-1
（哈夫曼译码）也称霍夫曼编码，在哈夫曼树上，经过左边路径为0，经过右边路径为1。从树根往下读。
【堆】一棵完全二叉树 + 某个节点的值总是不大于或（不小于）其父节点的值
（大根堆）将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
（关键字序列）下图为小根堆。转换关键字序列（注意堆是完全二叉树，方式为每层从左到右）值为：13 38 27 49 76 65 49 97
image.png
《图》参考：https://www.jianshu.com/p/bce71b2bdbc8
【顶点】有时也称结点、交点、节点。
【概念】图就是一些顶点的集合，每个点有若干条边。
【带权图】有权重的图也称带权图，权重表示每条边上的一个值。
【有向图 与 无向图】有箭头方向的称为“有向图”，反之就是无向图。
【连通图】连通图就是图的所有顶点都存在彼此可以到达的路径。
【无向完全图】每对不同的顶点都有唯一的一条边。（n个顶点有n×(n-1)/2 条边）
【有向完全图】每对不同的顶点都有唯一的二条边（因为有不同方向，以所是二条边）。
【强连通图】=【有向图】+ 任意两点间都存在路径
【有向连通图】=【有向图】+【连通图】
【有向无环图】=【有向图】+ 无法从某个顶点出发经过若干条边回到该点
【拓扑序列】也叫“拓扑排序” =【有向无环图】+ 从某个顶点出发可经过所有条边
【邻接矩阵】用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据。
【对称矩阵】=【无向图】的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
【深度优先】遍历与N阶有关，与边无关。复杂度为O(n^2)
【广度优先】使用队列对图进行广度优化遍历
工作注意
【射线法】一个实用的点是否在面内的算法，比如实现当前用户位置是否在配送范围之内。
image.png
网友评论