2022.02.15

哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近.

True

一棵哈夫曼树的带权路径长度等于其中所有叶结点的带权路径长度之和

True

(后序线索树)的遍历仍需要栈的支持（不懂）

A : 前序遍历（中左右）、中序遍历（左中右）的最后访问的节点都是左或右叶节点， 叶节点是没有子树的，所以两个指针域空出来了，可以存放线索指针用于回溯。但是后续遍历（左右中），最后访问的是子树的根节点，子树根节点的两个指针域都指向子树了，所以不能空出来存放线索信息，只能借助栈存储。

一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到(108)个不同的码字

A：哈夫曼树并不是满二叉树，是正则二叉树（也叫正规二叉树），即其中只有度为0和度为2的结点 因为n0 = n2 + 1，n = n0 + n2; 所以 n = 2n0 - 1，即n0 = (n + 1) / 2;叶子结点n0对应的即是不同的编码。 至于满二叉树当然也是正则二叉树的特例。

在ASC算法team日常开发中，常常面临一些数据结构的抉择，令人纠结。目前大家在策划一个FBI项目（Fast Binary Indexing），其中用到的词汇有6200条，词汇长度在10-15之间，词汇字符是英文字母，区分大小写。请在下面几个数据结构中选择一个使检索速度最快的：

TRIE树，寻找子节点开销：1次运算/每字符

A：注解:又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

在存储对称矩阵时，为了节省空间，通常可以用一个数组以行优先方式只存储上三角阵来实现。请问如果一个100*100的矩阵用上述方法来实现存储，在原矩阵中位置为选项中哪一项的元素可以通过访问数组下标为2017的位置来获得?( )数组和矩阵下标均从0开始。

(70，22)，该题为选择题，因此可以先获得公式，再带入试。

具体计算公式为：前n行的总和再加上当前行的个数，之后的和等于2017.

因为是个标准的等差数列，因此可以使用简单的高斯前n项求和，

(100+100-(i-1))*i/2 + (j-i) = 2017

将答案中的选项带入试验。

注意该矩阵为对称矩阵，因此需要把(70,22)看成(22,70)

对于一棵节点数为n、度为4的树来说那么树的高度至多是n-3

度为4,高度为h的树，至少有h+3个节点。

Hadoop的三种运行模式

Hadoop是一个由Apache基金会所开发的分布式系统基础架构。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力进行高速运算和存储。

1.独立（本地）运行模式：无需任何守护进程，所有的程序都运行在同一个JVM上执行。在独立模式下调试MR程序非常高效方便。所以一般该模式主要是在学习或者开发阶段调试使用 。

2.伪分布式模式： Hadoop守护进程运行在本地机器上，模拟一个小规模的集群，换句话说，可以配置一台机器的Hadoop集群,伪分布式是完全分布式的一个特例。

3.完全分布式模式：Hadoop守护进程运行在一个集群上。

注意：所谓分布式要启动守护进程 ，即：使用分布式hadoop时，要先启动一些准备程序进程，然后才能使用比如start-dfs.sh start-yarn.sh。而本地模式不需要启动这些守护进程。

采用败者树进行K路平衡归并时,总的(包括访外)归并效率与K

(有关)

hashmap为啥扩容因子是0.75

https://www.cnblogs.com/aspirant/p/11470928.html

提高空间利用率和 减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小，

AOE网

在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

与AOV网相反（见拓扑排序）

从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。

关键活动组成了关键路径，关键路径是图中的最长路径，关键路径长度代表整个工期的最短完成时间，关键活动延期完成，必将导致关键路径长度增加，即整个工期的最短完成时间增加，

关键路径并不唯一，当有多条关键路径存在时，其中一条关键路径上的关键活动时间缩短，只能导致本条关键路径变成非关键路径，而无法缩短整个工期，因为其他关键路径没有变化，

凸多边形三角划分

在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是 键盘上输入凸多边形的边数n，求不同划分的方案数f（n）？

卡特兰数是组合数学中一个常出现在各种计数问题中的数列。

Dn+1=（4n-6)/n*Dn
则
D8=(4*7-6)/7 *D7
D7=(4*6-6)/6 *D6
D6=(4*5-6)/5 *D5
因为
D5=5
故
D8=132

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为

(n+1)/2

普通计算方法：https://blog.csdn.net/qq_27445903/article/details/108861737