浙大远程数据结构与算法离线答案-最完整版(6)

2）

26

（

27

【14，4，6】 假设一个文本使用的字符集为{a,b,c,d,e,f,g}, 字符的哈夫曼编码依次为{0110，10，110，111，00，0111，010}。

（1）请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符； （2）若这些字符在文本中出现的频率分别为：{3,35,13,15,20,5,9}，求该哈夫曼树的带权路径长度。 答：

28

【15，5，3】用公式5.6计算一下你的身份证号码的散列值是多少。 答：公式5.6如下h(key)=key mod 11;

身份证号码信息如下：362429198307050010，设身份证为数字类型，对11求余后为4

【16，5，4】设有一组关键字{29，01，13，15，56，20，87，27，69，9，10，74}，散列函数为：H(key) = key % 17，采用平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。 答： 散列地址 0 插入29 插入01 插入13 插入15 插入56 插入20 插入87 插入27 插入69

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 说明 29 无冲突 无冲突 无冲突 无冲突 无冲突 无冲突 无冲突 无冲突 d2=-1 01 13 15 56 20 87 27 69 29

插入9 插入10 插入74 74 9 无冲突 d1=1 无冲突 10

【17，5，4】将关键字序列（7，8，30，11，18，9，14）散列存储到散列列表中，散列表的存储空间是一个下标从0开始的一个一维数组。处理冲突采用线性探测法，散列函数为：H（key）=（key×3）mod TableSize，要求装入因子为0.7。 答：tableSize为7/0.7，即10，散列函数为h(key)=(key*3) mod 10;下面为散列表插入过程 散列地址 0 插入7 插入8 插入30 插入11 插入18 插入9 插入14

30

1 7 2 3 11 4 8 5 18 6 7 9 8 9 说明 无冲突 无冲突 无冲突 无冲突 d1=1 无冲突 无冲突 30 14

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库浙大远程数据结构与算法离线答案-最完整版(6)在线全文阅读。