2024年4月11日发(作者：)

《数据结构》练习题

一、解答题（共50分）

1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所

示。

请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算

WPL。

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

DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其

先序遍历和层序遍历序列。

3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的

顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表

的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并

开始产生最小生成树的边的序列。

字符

a

b

c

d

e

f

g

h

出现频率

0.05

0.03

0.24

0.16

0.08

0.24

0.18

0.02

写出从顶点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,下标上

1

限为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

if (i

t=r[i]; r[i]=r[j]; r[j]=t; i++; //将较小记录交换到前面

}

while ( ⑺ ) i++； //左侧扫描

if (i

t=r[i]; r[i]=r[j]; r[j]=t; j--; //将较大记录交换到后面

}

}

⑻ //i为轴值记录的最终位置

}

3、以下程序是计算以rt所指向的结点为根结点的二叉树的深度算法，请填空，完善程

序。

2

template

int BiTree::High(BiNode *rt)

{ int lh,rh;

}

三、编程题（共30分）

1.（18分）假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾元素所

在的结点，但不设头指针。试设计相应的入队和出队算法。

template

struct Node

{ T data;

Node * next;

};

template

class CirLinkQueue

{ Node * rear;

public:

CirLinkQueue(){ rear=NULL;}//构造函数

void EnQueue(T x);//将元素x入队

T DeQueue();//出队

……

};

template

void CirLinkQueue ::EnQueue(T x)

{……}

template

T CirLinkQueue ::DeQueue()

3

if( ⑼ ) return 0;

else

{ lh=High(rt->lchild);

}

rh=High(rt->rchild);

return ⑽ ;

{……}

2.（12分）线性表存放在数组data[ArrSize]的前element个单元中，且递增有序。编写

算法，将元素x插入到线性表的适当位置上，并保持线性表的有序性。

const int ArrSize=100;

template

class SeqList

{ T data[ArrSize];

int element;

public:

void Insert(T x);

……

};

template

void SeqList::Insert(T

{……}

x)

4