科大讯飞笔试

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)

全部评论

相关推荐

但听说转正率很低,我现在有在实习了,好纠结要不要去
熬夜脱发码农:转正率低归低,但是实习的经历你可以拿着,又不是说秋招不准备了
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务