b. d. c a
b e
d
d c. DFS:acbde; BFS:acebd
a a c c e b b e d 5. 设在某通信系统中使用了八个字符，它们出现的频率分别为0.08，0.05，0.1，0.12，
0.26，0.18，0.14，0.07，试构造一棵赫夫曼树，并给出赫夫曼编码。
赫夫曼编码: 赫夫曼树： 0.08:000 0.05:0110
0.10:002 0.12:010
26 0.26:10 0.18:110
18 14 8 10 12 0.14:111 0.07:0111
5 7
五．算法设计题（共17分）
1. 单链表结点的类型定义如下：
typedef struct LNode { int data;
struct LNode *next;
} LNode, *Linklist;
写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。 (注:不破坏A和B的原有结构.)
Merge(Linklist A, Linklist B, Linklist &C )
void Merge(Linklist A, Linklist B, Linklist &C) {
C=(Linklist)malloc(sizeof(LNode)); pa=A->next; pb=B->next; pc=C;
while(pa&&pb)
{ pc->next=(Linklist)malloc(sizeof(LNode));
pc=pc->next;
if(pa->data<=pb->data)
{ pc->data=pa->data; pa=pa->next;} else { pc->data=pb->data; pb=pb->next;} }
if(!pa) pa=pb; while(pa)
{ pc->next=(Linklist)malloc(sizeof(LNode)); pc=pc->next;
pc->data=pa->data; pa=pa->next; }
pc->next=NULL; }
2. 二叉树用二叉链表存储表示。
typedef struct BiTNode { TelemType data;
Struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
编写一个复制一棵二叉树的递归算法。
BiTree CopyTree(BiTree T) {
if (!T ) return NULL;
if (!(newT = (BiTNode*)malloc(sizeof(BiTNode)))) exit(Overflow);
newT-> data = T-> data;
newT-> lchild = CopyTree(T-> lchild); newT-> rchild = CopyTree(T-> rchild); return newT; } // CopyTree
