数据结构期末样卷参考答案

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