1.设一棵二叉树的后序遍历序列是dabec，中序遍历序列是debac，请画出对应的二叉树，并写出其前序遍历序列。 2.请画出下图中的邻接矩阵。 3.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20, (5,6)18,(6,7)25};//（起点，终点）边长 用克鲁斯卡尔算法得到最小生成树，试写出构造过程。 4.设给定一个权值集合W=(1，4，5，7，8，10，20)，要求根据给定的权值集合构造一棵哈夫曼树并计算该哈夫曼树的带权路径长度WPL。 五、算法填空题（每空 5 分，共 20 分） 1. 下列算法为二分查找算法，阅读下面程序代码，填充空白位置，使算法完整。 #define n 10 typedef int KeyType; typedef struct { KeyType key; …… } NodeType; int BinSearch (NodeType r[],KeyType k) { int low=1,high=n,mid; while(low<=high) 学号： { ; if(r[mid].key==k) return mid; if( ) high=mid-1; else low= mid+1;; } ……; } 2.下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。 typedef struct node { int data; struct node *lchild ,*rchild; }bt; void btinsert(bt *t,int k) { if (t==NULL) { t=(bt*)malloc(sizeof(bt)); t->data=k; ; } else if (t->data>k) ; else btinsert(t->rchild,k); }

1. 二叉树的结构如下图所示，前序遍历序列为deabcf。

      d
     / \
    b   e
   / \   \
  a   c   f

2. 邻接矩阵如下：

  0  1  2  3  4  5  6
0 0  3  5  8  0  0  0
1 3  0  6  0  10 0  0
2 5  6  0  15 12 9  0
3 8  0  15 0  0  4  20
4 0  10 12 0  0  18 0
5 0  0  9  4  18 0  25
6 0  0  0  20 0  25 0

3. 克鲁斯卡尔算法构造最小生成树的过程如下：

首先将所有的边按照权值从小到大排序，得到排序后的边集合为：

(4,6)4, (1,2)3, (1,3)5, (3,6)9, (2,3)6, (1,4)8, (3,5)12, (2,5)10, (5,6)18, (4,7)20, (3,4)15

然后从权值最小的边开始遍历，如果加入这条边不会形成环，则将这条边加入最小生成树中，否则跳过这条边。重复这个过程，直到最小生成树中包含了所有的顶点。最终得到的最小生成树的边集合为：

(4,6)4, (1,2)3, (1,3)5, (3,6)9, (2,5)10, (5,6)18

4. 构造哈夫曼树的过程如下：

首先将权值集合按照权值从小到大排序，得到排序后的集合为：

1, 4, 5, 7, 8, 10, 20

然后将权值最小的两个节点合并，权值为它们的和，得到一个新的节点，直到只剩下一个节点。合并的过程中，每个节点都标记为左子树或右子树。最终得到的哈夫曼树如下：

         55
        /  \
       /    \
      20     35
            /  \
           /    \
          15    20
         /  \
        7    8

计算带权路径长度WPL的方法是，将每个节点的权值乘以它到根节点的距离，然后将所有节点的结果相加。例如，节点7的WPL为 7*3=21，节点15的WPL为 15*2=30，节点35的WPL为 35*1=35，节点55的WPL为0，因为它没有到根节点的距离。最终得到的WPL为21+30+35=86。

5. 算法填空题：

1.

int  BinSearch (NodeType r[],KeyType k) {
    int  low=1,high=n,mid;
    while(low<=high) {
        mid = (low + high) / 2; 
        if(r[mid].key==k) 
            return  mid; 
        if(r[mid].key > k) 
            high = mid - 1;  
        else  
            low = mid + 1;
    } 
    return -1;
}

2.

void btinsert(bt *t,int k) {
    if (t==NULL)  { 
        t=(bt*)malloc(sizeof(bt)); 
        t->data=k; 
        t->lchild = t->rchild = NULL; // 在这里填写
    } else if (t->data>k) {
        btinsert(t->lchild,k);
    } else {
        btinsert(t->rchild,k);
    }
}