数据结构总复习

请构造一个字符为叶子结点的Huffman树，并写出各字符的Huffman编码，（构造时按左小右大、左0右1的规则进行）。

29、已知一组初始记录关键字序列为（55,63,44,38,75,80,31）,则写出 （1）利用快速排序得到第一趟的变化序列。 （2）用堆排序建立起来的第一个大根堆。

30、已知如下无向网的邻接矩阵，其权值为整形数据。

∞ 6 1 5 ∞ ∞ 6 ∞ 5 ∞ 3 ∞ 1 5 ∞ 5 6 4 5 ∞ 5 ∞ ∞ 2 ∞ 3 6 ∞ ∞ 6 ∞ ∞ 4 2 6 ∞ （1） 写出从顶点4出发的DFS、BFS序列。

（2） 写出使用Prim 算法构造最小生成树的过程。 31. 有下列图的数据结构：

V = {0，1，2，3，4，5，6，7，8，9}；

E = {（0，1），（0，3），（1，2），（1，7），（2，8），（3，4），（3 ，5），（5，6），

（5，8），（5，9），（6，7），（7，8），（8，9）}

（1）写出它的邻接表； （2）根据邻接表存储分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

五、程序题

1、试编写在带头结点的单链表上实现线性表操作LENGTH（L）的算法，并将长度写入头结点的数据域中。

typedef struct node{ int data; struct node* next; }linklist; int length(linklist* head) 1分 { linklist*p; int n=0;

p=head->next; 1分 while(p!=NULL) 2分 { p=p->next; n++; } 4分 head->data=n; 1分 return n; 1分 }

2、已知DBF（int j）是连通图的遍历算法。非连通图的遍历算法如下，请在此基础上修改算法，使该算法具有求出非连通图中有多少个连通分量的功能. TRAVER ( )

- 12 -

{ int j;

for(j=0;j

{ DFS(j);

printf(“comp end\\n”); } }

int TRAVER ( ) { int j;

int k=0; 2分 for(j=0;j

{ DFS(j);

printf(“comp end\\n”); k++; 4分 }

return k; 2分 } 1分 }

3.如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A[ ],int n,KeyType K) {

int low=0; int high=n-1; while (low<=high) {

int mid=______________________；

if (K==A[mid].key) return mid; //查找成功，返回元素的下标

else if (K<[mid].key)

_______________________; //在左子表上继续查找

}

return -1; //查找失败，返回-1 } 4.

LinkList mynote(LinkList L)

else __________________;//在右子表上继续查找

- 13 -

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题：

（1）说明语句S1的功能； （2）说明语句组S2的功能； 5. 二叉搜索树的查找——递归算法:

bool Find(BTreeNode* BST,ElemType& item) {

if (BST==NULL)

return false; //查找失败 else

{

if (item==BST->data)

{

item=BST->data;//查找成功 return _____（1）____;

}

else

if(itemdata)

return Find(_____（2）_______,item); else return Find(_______（3）______,item); }//if }

6.假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的前趋结点。

- 14 -

7.设有一二叉链表T，编写递归算法，计算二叉链表中叶子的数目；

8.求带头结点的单链表head中结点的值等于给定值X的结点数目。

int count(linklist* head,datatype x) 1分 {

linklist*p=head->next; 1分 int n=0; 1分

while(p!=NULL) 2分 { if(p->data==x) n++; 2分 p=p->next; 2分 }

return n; 1分 }

9、以二叉链表为存储结构，试编写算法求二叉树叶子结点的数目。

int leafnum(bitree *t) 1分 { int num1,num2;

if(t==NULL) return 0; 1分

else if(t->lchild==NULL&& t->rchild==NULL) return 1; 2分 else

{ num1=leafnum(t->lchild); 2分 num2=leafnum(t->rchild); 2分 return(num1+num2); 2分 }

} /* leafnum*/

- 15 -