华东师大软工考研独家平台

撰稿 | 康康哥

修改 | 丽丽姐

这篇文章由华东师大软工博士学长自创

转发自微信大众号：“丽娃软工考研”

15年软专真题说明（2）

次序表刺进值与哈夫曼树

我们好，我是康康哥：

在这儿，我会给我们逐个说明华师软工专业课的真题，期望能给小火伴们带来一些协助。

自从15年后华师图书馆中止出售考研真题后，软工真题试卷就断档了。

咱们先从15年的真题初步分析，后续还会有更多，更新的真题分析共享给我们哦~

本期咱们要讲的是次序表刺进一个数据元素与

哈弗曼树的疑问。试题如下：

简答题

在有序的次序表中刺进一个数据元素x的算法

这道题承受上一道简答题，书写对言语没有硬性的需求。假定运用python言语，实践已封装了对次序表的操作办法，如下：

刺进?

这道题则需要从头构建一个次序表

初始化办法，包括次序表最大长度length、每个元素数据值data以及数据个数num；

写入append办法在建表时添加元素，insert办法为次序表刺进元素

其间，在刺进元素时，需要思考刺进地址index的值小于0的情况，假定小于0不思考，假定索引大于已稀有据个数，则直接在已稀有据后添加调append办法。

输入元素后，在第一个方位处添加“康康哥”，第二个方位处添加“丽丽姐”：

成果如下 ?

简答题

四、某电文中呈现七个字母，为a，b，c，d，e，f和g，呈现的概率为0.05、0.06、0.07、0.10、0.14、0.28、0.39.请规划哈弗曼树，需求左子树的权不大于右子树的权

这道题查询的是哈弗曼树的规划。

哈弗曼树是二叉树其间的一种，也是最优二叉树。

首要咱们对这组数字按升序排序：

0.05、0.06、0.07、0.10、0.14、0.28、0.39

取排序后最小的两个数作为子节点，并将两数进行相加，相加得到头节点。

规划如下 ?

0.07、0.10、0.11、0.14、0.28、0.39

然后将和0.11放入余下数字中取最小的两个构成节点，假定两个数的和正好是下一步的两个最小数的其间的一个，那么这个树直接往上生长就可以了。

假定这两个数的和比照大不是下一步的两个最小数的其间一个，那么就并排生长，如下图所示 ?

此时变成了：0.11、0.14、0.17、0.28、0.39

持续按上述进程改变 ?

此时变成了：0.17、0.25、0.28、0.39

0.28、0.39、0.42

最终变成如下图 ?

不过需要指出，这道题出题人是不是在提示求和中存在疑问，将一切节点的数值规划完后，算出来的额总和跨越了1，细心的研友们你们觉得呢？

好啦！

今日的华师真题说明就先到这儿，后边还有会更多精彩有用的内容哦。

詹姆斯上星期末翻开了一年一度的我国行活动，首选也是仅有地址定在了上海，我也有幸参加了詹姆斯在上海戏曲学院的主题讲演。将来也期望我们都能来上海，获得更多触摸大咖的机缘。

活动现场，猜猜我在哪儿

这篇文章转发自微信大众号：“丽娃软工考研”回来搜狐，查看更多

责任修改：