科大讯飞笔试
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)