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

出此二叉树，并画出它的后序线索二叉树。

12. 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定

选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

6

13. 已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

14. 下图所示的森林：

(1) 求树（a）的先根序列和后根序列；

(2) 求森林先序序列和中序序列；

（3）将此森林转换为相应的二叉树；

(a)(b)

15. 设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链表

处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。

16. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为

ABDEC，要求给出该二叉树的的后序遍历序列。

17. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并

计算最小生成树各边上的权值之和。

18. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，

要求计算出成功查找时的平均查找长度。

19. 设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字

序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

20. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个

数据而生成的二叉搜索树。

21. 对于下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照

终点序号从小到大的次序链接的，试写出：

（1）从顶点①出发进行深度优先搜索所得到的深度优先生成树；

（2）从顶点②出发进行广度优先搜索所得到的广度优先生成树；

22. 已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按照教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

23. 已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排

序的每一次划分结果。

24. 一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，

散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

25. 已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是

EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

26. 已知一个图的顶点集V各边集G如下：

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

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

当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。

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