数据结构习题(7)

12.对于一个具有 n 个结点的二叉树，当它储存在二叉树表中时，其指针字段的总数为______ 个，其中________个用于链接孩子点，_____________个空闲，

13．一棵深度为 K 的满二叉树结点总数为___________ ，一棵深度为 K 的完全二叉树的结点总数的最小值为________，最大值为____________。

14.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序是 T2 中结点的 _______序。 15.具有 n 个结点的完全二叉树，若按层次从上到下 、从左到右对其编号（根结点为 1号），则编号最大的分支结点序号为_______ ，编号最小的分支结点序号为_______ ，编号最大的叶子结点序号为________ ，编号最小的叶子结点序号为___________ 。

16.有 m个叶子结点的哈夫曼树，其结点总数为________________ 。 17. 由三个结点构成的二叉树，共有_____________种不同的结构。

三、判断题

1.具有n个结点的完全二叉树的高度为?log2n??1。 2.有n个结点的不同的二叉树有n！棵。

3.在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。 4.完全二叉树的某结点若无左孩子，则它必是叶子结点。

5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。

6.由树转化成二叉树，其根的右子女指针总是空的。

7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。 8.在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。 9．二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。

四、应用题

1.假设一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），回答下列问题：

（1）该树的度（2）树的深度（3）终端结点的个数（4）单分支结点的个数（5）双分支结点的个数（6）三分支结点的个数（7）C结点的双亲（8）C结点的孩子结点

2. 已知一棵树边的集合为｛< I ， M >，< I ， N >,< E ， I >，< B ， E >，< B ， D>，< A ， B>，< G ， J >，< G ， K>，< C ， G>，< C ， F>，< H ， L>，< C ， H>，< A ， C >｝，画出这棵树，并回答下列问题： ? 哪个结点是根结点？ ? 哪些结点是叶子结点？

31

? 哪个结点是结点 G 的双亲结点？ ? 哪些结点是结点 G 的祖先结点？ ? 哪些结点是结点 G 的孩子结点？ ? 哪些结点是结点 E 的子孙结点？

? 哪些结点是结点 E 的兄弟结点？哪些是结点 F 的兄弟结点？ ? 结点 B 和 N 的层次分别是多少？ ? 树的深度是多少？

? 以结点 C 为根的子树的深度是多少？ 3. 某二叉树的结点数据采用顺序存储表示如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B (1)试画出此二叉树的图形表示。(2)写出结点D的双亲结点及左、右子女。 (3)将此二叉树看作森林的二叉树表示，试将它还原为森林。

4.假设一棵二叉树的中序序列DCBGEAHFIJK和后序序列为DCEGBFHKJIA请画出该二叉树，并给出先序序列。 5.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。 ①先序遍历序列： EBADCFHGIKJ 中序遍历系列： ABCDEFGHIJK ②中序遍历序列： ACBGEDF 后序遍历序列： ABCDEFG

6.对上题①所得的二叉树，分别画出它的顺序存储结构和二叉链表。

7．已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。

8．如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。

9．已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数。

10．如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点数目最多的那棵完全二叉树的叶子结点数目。

11．在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 12．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 13．分别求出下图中二叉树的三种遍历序列。

32

14．分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。

15．证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①先序：ABCDEFGHI ②先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF

16．证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①后序：DCFEBIHGA ②后序：DECBGIHFA 中序：DCBFEAGHI 中序：DCEBAFHGI

17．已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。

先序：A CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _

18．证明：任意一棵非空的二叉树的先序序列的最后一个结点一定是叶子结点。 19．用反例证明：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。 20．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。

21．设计算法按中序次序依次输出各结点的值及其对应的序号。例如，下图中的二叉树的输出结果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9) (G,10)。

33

22．设计算法以输出每个结点到根结点之间的路径上的所有结点的值。

23．设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储到数组A[n]中，并将其中没有存放结点值的数组元素设置为NULL。

24．设计算法将一棵以顺序存储方式存储在数组A中的二叉树转换为二叉链表形式。

25．写出如下图树的先根遍历序列和后根遍历序列并将此树转化为二叉树：

26.已知某系统在通讯联络中只可能出现6种字符{a,b,c,d,e,f}，其概率分别为0.10，0.22，0.13，0.14，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。

27.假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。试为这8个字母设计不等长Huffman编码，并输出该电文的总码数。 （1）Huffman树为：（2）Huffman编码为（3）电文总长度：

28．对给定的权值｛ 2 ， 3 ， 4 ， 7 ， 8 ， 9 ｝，构造出相应的赫夫曼树和赫夫曼编码，并求出带权路径的长度 WPL 。

29．将下图中的二叉树转换为对应的森林。

34

30．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next； }ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； void Inorder (BinTree T) {

LinkList s； if(T)

{

Inorder(T－>lchild)；

if ((!T－>lchild)&&(!T－>rchild))

{

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)；

} }

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

35

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(7)在线全文阅读。