数据结构作业题(2)

6. 已知一个森林如图所示：

(1) 分别写出该森林的先序和中序遍历序列 (2) 将该森林转换为一棵二叉树

AH B C D I E F G J L K

7. 设用于通信的电文由8个字母A—H组成。字母在电文中出现的频率分别为0.06, 0.20,

0.01, 0.07, 0.33, 0.02, 0.22, 0.09。试构造相应的哈夫曼树，为这8个字母设计哈夫曼编码。，求平均的码长WPL值，使用0－7的二进制表示形式是另一种编码方案，试比较两种方案的优缺点。 答案

1. 设度为k的结点数为

则有K×

nk，叶子结点数为

n

0nnn＋0＝kk 解得

n0?n(k?1)?1n?1?n?

kkn=n－1

2. （b）

3. (1)先序：ABDGCEFH 中序：DGBAECHF 后序：GDBEHFCA

(2)先序和中序相反的二叉树为

F H D 后序和中序相反的二叉树为 G

(3)

0 1 0 A 0 0 B 1 0 C 0 1 D 0 1 E 1 0 F 1 1 G 1 1 H 1

(4)

(5)

A A B C D E F NIL G H B C D E F G H (6)

A C F

B E H D G

4. 孩子表示法；双亲表示法；孩子兄弟表示法 5. （1）先序：ABEFCDH 后序：EFBCHDA

(2) (3)双亲表示法 A -1 0 A B 0 1 C 0 0 B 2 D E 1 C 3 F 1 3 D 4 H 5 E 6 F H

孩子兄弟表示法 A ∧ B ∧ E ∧ C D ∧ ∧ F ∧ ∧ H ∧

6. (1)先序：ABCEGDGHIJKL 中序：BEFCGDAIJHLK

(2) A H B C I K D J L E G F 7.

第七章作业

1. 常用的又向图的存储结构有______,_______和_______。

常用的无向图的存储结构有______和_______。 2.

V1 V2 (1)分别画出该图的邻接矩阵，邻接表，逆邻接表和十字链表.

(2)求出ID（V5）OD（V5）TD（V2）OD（V3）ID（V3）的值。 V3(3)判断其是否为一强连通图？

V4 V5

V6 3. V1 （1）分别对该图进行深度优先搜索＆广度优 先搜索，并写出遍历序列。

V2 V3 （2）分别画出其深度优先生成树＆广度优先 生成树。

V4V8 V7

V5 V6 V9

4. 从A,G,J分别画出该图的深度优先生成森林及广度优先生成森林。

A J B

G C

E

G I K D

F 5.已知一图的邻接表分别画出从A出发该图的深度优先生成树和广度优先生成树。

A 3 1 ∧

4 2 0 ∧ B

4 1 ∧ 3

C

0 ∧ 2

D

1 ∧ 2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构作业题(2)在线全文阅读。