科大讯飞笔试

1、由序列1，2，4，5，6构成的哈夫曼树是

之前没听过这个哈夫曼树，结束了狠狠补习一下。发现这个做出来还是不难的，

初始的每个节点值构成的序列进行排序，选出值最小的两个节点相加，此时这两个值从序列中退出

新产生的值加入到序列中，组成新的序列。重复以上过程。

得到

18

/ \

7 11

/ \ /\

3 4 5 6

/ \

1 2

2、求给出的哈夫曼树的带权路径长度

哈夫曼树的带权路径长度是树中所有叶子节点的带权路径长度之和。

叶子节点的带权路径长度是从根节点到叶子节点的路径长度（即经过的边数）乘以该叶子节点的权值

以上面第一题为例：1*3+2*3+4*2+5*2+6*2 = 39.

3、将数组构造成堆后，堆对应的先序遍历序列可能是:

堆是一个完全二叉树:完全二叉树有很好的性质，每个节点i 父亲节点是i/2,左子节点 2i ,右子节点 2i+1

以小顶堆为例，小顶堆满足每个父亲节点的值都小于或等于子节点的值，其根节点最小。

每次插入元素都将新元素插入到堆的末尾，然后进行上浮，使新元素移动到正确位置，保持堆的性质。

4、编程

//任何一个数n都能拆成若干项不同的、由2的次幂和3的次幂相乘之和。

//输入 给定一个整数n

//输出 先输出项数m，再输出m个不同的整数，从大到小输出。

思路:用一个二重循环把20次方以内的2的幂次和3的幂次乘积，存到一个数组a里（当乘积大于输入时可break）

用sort将数组a从大到小排序，然后从数组a里从大到小挑数挨个匹配，如果数组a里的数小于等于输入n,就将数组a中的数存入答案数组中，并用n减去数组a中的数，继续匹配，直到n等于0break。(hhh)