二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(44)

26.

【点评】二叉树与森林的转换，参见教材P137-P138

27. 该图的图形为：

深度优先遍历序列为： e

广度优先遍历序列为： e

【 点评】用邻接矩阵存储图结构，然后分别采用深度优先搜索（DFS）和广度优先搜索（GFS）遍历，参见教材P161-P162邻接矩阵，以及P167-P170关于深度优先搜索和广度优先搜索的介绍。

28. （1）对关键字35、20、33和48进行查找的比较次数为3、2、1、1；

3?2?1?1?29ASL??55 （2）平均查找长度

【点评】通过散列函数和双重散列法解决冲突，计算比较次数和平均查找长度。参见教材P258再哈希法以及P259-P261关于平均查找长度的计算方法。

29. 链式存储结构略，前序 DE ，中序 E ，后序DE 。

【点评】完全二叉树的顺序存储结构参见教材P126，链式存储结构参见P126-P127。完全二叉树的遍历参见教材P128-P132

30.

带全路径长度WPL=78

【点评】哈夫曼树的构造方法，参见教材P144-P145，带权路径长度的计算方法，参见教材P144

31. (18，5，16，19，21，23)，(5，16，21，19，18，23)

【点评】快速排序参见教材P273-P277，简单选择排序参见教材P277-P278

32. 线性探测：

01234567

?8?1025322768

链地址法

h0

h1??8

h2

h3??10

h4??25??32

h5??68

h6??27

【点评】线性探测法解决冲突的方法参见教材P257，链地址法参见教材P258

33. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，

6)，(5,6)}

【点评】参见教材P167-P170关于深度优先搜索和广度优先搜索的介绍以及P173-P176关于最小生成树的构造算法。

四、算法设计

1. 设计递归算法，实现二叉搜索树的查找

ool Find( TreeNode* ST,ElemType& item)

{

if ( ST==NULL)

return f lse; //查找失败

else {

if (item== ST-> t ){

item= ST-> t ;//查找成功

return true;}

else if(item< ST-> t )

return Find( ST->left,item);

else return Find( ST->right,item);

}//if

}

2. 统计出单链表HL中结点的值等于给定值X的结点数。

int ountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器

while(p!=NULL)

{ if (P-> t ==x) i++;

p=p->next;

}//while, 出循环时i中的值即为x结点个数

return i;

}// ountX

3. 设有一组初始记录关键字序列（K1，K2，?，Kn），要求设计一个算法能够在O(n)的时

间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。

voi qui kp ss(int r[], int s, int t)

{

int i=s, j=t, x=r[s];

while(i<j){

while (i<j && r[j]>x) j=j-1; if (i<j) {r[i]=r[j];i=i+1;}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-44.html