1. 假设用于通信的电文仅由8个字母（a, b, c, d, e, f, g, h ）组成，字母在电文中出现的频率分别是0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21和0.10。为这8个字母设计一套哈夫曼编码，并计算其一个字母的平均编码长度（二进制位数）。

以上述8个字母为叶子结点构造的一棵最优二叉树如下：

由其可得一套哈夫曼编码：

a 0010

b 10

c 00000

d 0001

e 01

f 00001

g 11

h 0011

平均编码长度是 ∑P i ?L i = 0.07×4 + 0.19×2 + 0.02×5 + 0.06×4 + 0.32×2 + 0.03×5 + 0.21×2 + 0.10×4 = 2.61

2. 无向网的5个顶点依序为a, b, c, d, e ，其邻接矩阵如下，画出该图及其最小生成树。

???????

?????????∞∞∞∞

∞∞∞∞

∞∞∞71374114310133811108

3. 画出如下有向图的邻接表。

4. 编写运用栈实现图的深度优先搜索的非递归算法。

void dfs(graph G, int v0) // 一个连通分量上的深度优先搜索

{ int v, w;

visit(G,v0); // 访问出发顶点

G.list[v0].visited=1;

init_stack(S); // 初始化栈

push(S,v0); // 出发顶点地址（下标）入栈

while(!empty_stack(S)) // 当栈非空则执行以下循环

{ v=gettop(S); // 取栈顶

w=first_adj(G,v); // 求其第一个邻接点

while(w && G.list[w].visited) // 寻找一个未被访问的邻接点 w=next_adj(G,v,w);

if(w) // 若存在一个v的未被访问的邻接点w

{ visit(G,w); // 访问w

G.list[w].visited=1;

push(S,w); // w入栈

}

else pop(S); // 否则，v的所有邻接点已访问或无邻接点则v出栈

}

}

void depth_first_search(graph G) // 整个图的遍历

{ for(int i=0; i

if(G.list[i].visited==0) dfs(G,i);

}