得 分 评卷人 三、综合题（每小题15分，共30分） 28.对给定的数列b={6,15,3,7,19,8,5,17,4} (1)依次取b中各数据，构造一棵二叉排序树。 (2)给出按中序遍历该二叉排序树的序列。 (3)给出按后序遍历二叉排序树的序列。 (4)画出在二叉树中副除结点3后的树结构。 29.(1)以4,5,6,13,11,12作为叶结点的权，构造-一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵哈夫曼树有个叶结点，该树共有多少个结点？简述理由？ (4)给出对上述哈夫曼树中序遍历的序列。 得 分 评卷人 四、程序填空题（每空2分，共16分）】 30.职工信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从1到n,以a[0]作 为辅助工作单元。现要以职工的工资号um为关键字进行排序，采用折半插入排序的算法， 以下程序是要把a[i门插人到已经有序的序列a[1],…a[i-1]中，(i=2,3,4,…,n)。 typedef struct char sex; int num; }NODE; void binsort (NODE a[]int n) int x,i,j,s,k,m; for(i=2;i<=(1) i++) 847三、综合题{每小题 15 分，共 30 分) 28. 对给定的数列 b={ 15 汀， 19 17 4} (1)依次取 中各数据，构造一棵二叉排序树。 (2) 给出按中序遍历该二叉排序树的序列。 (3) 给出按后序遍历二叉排序树的序列。 (4) 画出在二叉树中删除结点 后的树结构。 29. (1)以 13 11 12 作为叶结点的权，构造一棵哈夫曼树。 (2) 给出相应权重值叶结点的晗夫曼编码。 (3) 一棵哈夫曼树有 个叶结点，该树共有多少个结点?简述理由? (4) 给出对上述哈夫曼树中序遍历的序列。 |得分|评卷人| | 四、程序填空题{每空 分，共 16 分} 30. 职工信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从 ，以 a[O] 为辅助工作单元。现要以职工的工资号 为关键宇进行排序，采用折半插入排序的算法， 以下程序是要把 a[iJ 插入到已经有序的序列 a[ 刀， "'a[i-lJ 中，( i=2 ，…， n) typedef struct char sex; mt nu口1; }NODE j void binsort (NODE a[ ] ,int n) int x , i,j ,s, k , ru; for (i= 2; i< = (1) ;i++) 847