请构造一个字符为叶子结点的Huffman树，并写出各字符的Huffman编码，（构造时按左小右大、左0右1的规则进行）。
29、已知一组初始记录关键字序列为（55,63,44,38,75,80,31）,则写出 （1）利用快速排序得到第一趟的变化序列。 （2）用堆排序建立起来的第一个大根堆。
30、已知如下无向网的邻接矩阵，其权值为整形数据。
∞ 6 1 5 ∞ ∞ 6 ∞ 5 ∞ 3 ∞ 1 5 ∞ 5 6 4 5 ∞ 5 ∞ ∞ 2 ∞ 3 6 ∞ ∞ 6 ∞ ∞ 4 2 6 ∞ （1） 写出从顶点4出发的DFS、BFS序列。
（2） 写出使用Prim 算法构造最小生成树的过程。 31. 有下列图的数据结构：
V = {0，1，2，3，4，5，6，7，8，9}；
E = {（0，1），（0，3），（1，2），（1，7），（2，8），（3，4），（3 ，5），（5，6），
（5，8），（5，9），（6，7），（7，8），（8，9）}
（1）写出它的邻接表； （2）根据邻接表存储分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
五、程序题
1、试编写在带头结点的单链表上实现线性表操作LENGTH（L）的算法，并将长度写入头结点的数据域中。
typedef struct node{ int data; struct node* next; }linklist; int length(linklist* head) 1分 { linklist*p; int n=0;
p=head->next; 1分 while(p!=NULL) 2分 { p=p->next; n++; } 4分 head->data=n; 1分 return n; 1分 }
2、已知DBF（int j）是连通图的遍历算法。非连通图的遍历算法如下，请在此基础上修改算法，使该算法具有求出非连通图中有多少个连通分量的功能. TRAVER ( )
- 12 -
{ int j;
for(j=0;j
{ DFS(j);
printf(“comp end\\n”); } }
int TRAVER ( ) { int j;
int k=0; 2分 for(j=0;j
{ DFS(j);
printf(“comp end\\n”); k++; 4分 }
return k; 2分 } 1分 }
3.如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {
int low=0; int high=n-1; while (low<=high) {
int mid=_____________