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

假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

27. 请画出与下列二叉树对应的森林。

28. 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示

?01001??10010????00011????01101???10110??

（1）画出该图的图形；

（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。

29. 已知一个散列表如下图所示：

12

其散列函数为h(key)=key%13, 处理冲突的方法为双重散列法，探查序列为：

hi=(h(key)+ *h1(key))%m i =0,1,?，

m－1

其中

h1(key)=key%11+1

回答下列问题：

（1）对表中关键字35，20，33和48进行查找时，所需进行的比较次数各为多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

30. 设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构

并给出该二叉树的前序、中序和后序遍历序列。

31. 设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼

树并计算哈夫曼树的带权路径长度WPL。

32. 设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟

快速排序结果以及第2趟简单选择排序后的结果。

33. 设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数

H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。

34. 设无向图G（如右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该

图的最小生成树。

四、算法设计

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

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

int CountX(LNode* HL,ElemType x)

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

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

4． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链

式存储结构表示。

5． 设计在单链表中删除值相同的多余结点的算法。

6． 设计一个求结点x在二叉树中的双亲结点算法。

7． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表

中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。

8． 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

9． 在链式存储结构上建立一棵二叉排序树。

10． 设计判断两个二叉树是否相同的算法。

11． 设计两个有序单链表的合并排序算法。

12． 设计在顺序有序表中实现二分查找的算法。

13． 设计判断二叉树是否为二叉排序树的算法。

14． 在链式存储结构上设计直接插入排序算法

15． 设计在链式结构上实现简单选择排序算法。

16． 设计在顺序存储结构上实现求子串算法。

17． 设计求结点在二叉排序树中层次的算法。

18． 设计一个在链式存储结构上统计二叉树中结点个数的算法。

19． 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

20．设计计算二叉树中所有结点值之和的算法。

21．设计将所有奇数移到所有偶数之前的算法。

22．设计判断单链表中元素是否是递增的算法。

23．设计在链式存储结构上合并排序的算法。

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