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

5. ;

【点评】本题考查双向链表的插入问题，双向链表插入需同时考虑两个方向指针的变化，算法参见教材P36

6.

【点评】折半查找是有序表查找的一种优化算法，具体算法参见教材P220-P221

7.

【点评】根据边的集合，可以构造出孩子关系和兄弟关系，进而得到二叉链表和对应的二叉树，参见教材P136-P137

8.

【点评】普里姆算法参见教材P173-P175

9. 【点评】考查二叉排序树的构造过程，参见教材P227-P229

10.

【点评】通过在二叉树中增加前驱后继指针保持结点的前驱后继信息。线索二叉树构建方法参见教材P132-134

11.

哈希函数取值如下：

H(36)=36 mo 7=1;H１(22)=(1+1) mo 7=2; ….冲突

H(15)=15 mo 7=1;….冲突H2(22)=(2+1) mo 7=3;

H１(15)=(1+1) mo 7=2;

H(40)=40 mo 7=5;

H(63)=63 mo 7=0;

H(22)=22 mo 7=1; ….冲突

（1）哈希表结构：

0123456

（2）等概率平均查找长度： SL=?1?3?1.6 5

【点评】给定哈希函数，根据哈希函数计算每个关键字的地址，采用线性探查解决地址冲突。参见教材P253-P254

12. 【点评】参见教材第10章P273-P276相关算法

13.

(1)树( )先根序列： DEF; 后根序列 DEF ；

(2)森林的先序序列： DEFGHIJK; 后序序列： DEF IJKHG

(3)森林转换为相应的二叉树；

【点评】树的先根序列和后根序列参见教材P138-P139；森林的先序遍历和后序遍历参见教材P139；森林与二叉树的转换参见教材P137-P138

14.

【点评】参见教材P251、P257-P258

15. 【点评】根据前序遍历和中序遍历可以确定二叉树的根，由此递推每一棵子树的根，由

此得到后序遍历序列。

16.

【点评】最小生成树可有普里姆算法或克鲁斯卡尔算法得到，并由最小生成树计算权值之和。算法参见教材P173-P175

17.

【点评】记录关键字为有序序列，可采用折半查找算法计算平均查找长度，参见教材P220-P221

18. 线性探测法： SL1=7/6，链地址法： SL2=4/3

【点评】参见教材P257-P258关于线性探测法和链地址法的讲解。

19. 如下图所示。

【点评】二叉搜索树（即线索二叉树）的构建方法，参见教材P132-P133.

20. DFS：???????

FS：???????

【点评】用邻接表存储图结构，然后分别采用深度优先搜索（DFS）和广度优先搜索（GFS）遍历，参见教材P163-P164邻接表，以及P167-P170

关于深度优先搜索和广度优先搜索的介

绍。

21. 拓朴排序为： 4 3 6 5 7 2 1

【点评】有向无环图的拓扑排序问题，参见教材P180-P182

23.

0 123456 789 1011 12 查找成功的平均查找长度： SL SU =14/10= 1.4

【点评】哈希表查找，关于直接定址法参见教材P253-P254，关于线性探查法解决冲突问题，参见教材

P257

24. 此二叉树的后序遍历结果是：E IHJGF

【点评】根据前序遍历和中序遍历结果，构造二叉树，然后得到二叉树的后序遍历序列，参见教材P128-P132

25.

搜索（GFS）遍历，参见教材P163-P164邻接表、P161-P162邻接矩阵，以及P167-P170关于深度优先搜索和广度优先搜索的介绍。

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