《数据结构》练习题
一、解答题（共50分）
1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所
请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算
WPL。

2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为：
DBEHGAFIC和DHGEBIFCA。

试画出这棵二叉树，并写出其
先序遍历和层序遍历序列。

3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的
顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表
的边表结点按顶点的下标由小到大链接）。

请画出其邻接表，并
写出从顶点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c 开始产生最小生成树的边的序列。

4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。

⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。

⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进行排序，第一趟的排序结果是（）。

二、完善程序（共20分，每空2分）
1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。

请填空完善程序。

int BinSearch(int r[ ], int low,int high,int k)
{ int l,h,m;
l= low; h= high;
while ( ⑴)
{
m= ⑵;
if (k < r[m]) ⑶;
else if (k > r[m]) ⑷;
else return m;
}
return 0;
}
2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。

请填空，完善程序。

int Partition(int r[ ], int first, int end)
{ int i,j,t;
i=first; j=end; //初始化
while ( ⑸)
{
while (i<j && ⑹) j--；//右侧扫描
if (i<j) {
t=r[i]; r[i]=r[j]; r[j]=t; i++; //将较小记录交换到前面}
while ( ⑺) i++；//左侧扫描
if (i<j) {
t=r[i]; r[i]=r[j]; r[j]=t; j--; //将较大记录交换到后面}
}
⑻//i为轴值记录的最终位置
}
3、以下程序是计算以rt所指向的结点为根结点的二叉树的深度算法，请填空，完善程。