数据结构(专)阶段练习3

《数据结构》------ch6树和二叉树、ch8查找

班级         学号          姓名           成绩      

一、名词解释（每个2分，共10分）

1. 结点的度：结点的子树的个数。          

2.  二叉树：满足条件（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒；这样的树形结构称为二叉树。           

3.线索化：对二叉树以某种次序进行遍历并且加以线索的过程。

4.哈夫曼树：带权路径长度WPL最小的二叉树称为哈夫曼树或者最优二叉树。           

5.冲突：不同的关键字可能得到同一个哈希地址，这种现象称为冲突。

二、填空题（每空1分，共20分）

1.由树转换为二叉树，其根节点的右子树总是 为空   。

2.在分块查找方法中，首先查找  索引（表）    ，然后再查找相应的块。

3.含17个结点的二叉树的深度是   5      （设根结点的深度为1）。

4.一棵高度为h的满二叉树共有   2h-1      个终端结点。

5. 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是    9     。

6.对线性表进行二分查找时，要求线性表必须以   .顺序    方式存储，且结点按关键字

    有序     排列。

7. N个结点的二叉树采用二叉链表存放，共有空链域个数为  n+1   。

8. 在各种查找方法中，平均查找长度与结点个数无关的是  哈希查找法   。

9. 深度为6（根层次为1）的二叉树至多有     26 – 1       个结点。

10. 由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的   最左子结点   ，而N的右孩子是它在原树里对应结点的  最邻近的右兄弟   。

11. 在哈希存储中，装填因子α的值越大，则   发生冲突的可能性就越大  ；α的值越小，则   发生冲突的可能性就越小  。 

12. 哈希表的查找效率主要取决于哈希表造表时选取的   哈希函数    和    处理冲突的方法   。

13.树是结点的有限集合，它有   0个或1个  根结点，记为T。其余的结点分成为m（m≥0）个  互不相交   的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的 父结点  ，Ti称为T的子结点（1≤i≤m）。一个结点的子树个数为该  结点的度    。

三、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10分）

1.(  T  ) 具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。

2.(   F ) 用一维数组存储二叉树时，总是以前序遍历存储节点。

3.(   T ) 判断线索二叉树中某结点p有左孩子的条件是p->ltag=0。

4. (   F ) 哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。

5.(   F )  折半查找适用于有序表，包括有序的顺序表和有序的链表。

6.（  F ）哈夫曼树中没有度为1的结点，所以必为满二叉树。

7.（ T  ）深度为K的完全二叉树至少有2K-1个结点。

8.（ T  ）若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。

9.（ F   ）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的值。

10.(   F  ) 分块查找法中的索引顺序表的特点是块间可无序，但块内一定要有序。

四、单项选择题（每小题2分，共20分）

1.对包含n个元素的哈希表进行查找，平均查找长度为：   D   

A O(log2n)     B O(n)     C O(nlog2n)     D 不直接依赖于n

2.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点

进行编号，根结点编号为1，则编号最大的非叶结点的编号为：  C  

   A 48         B 49         C 50         D 51

3．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：  C    

A 3       B 2      C 4       D5

4. 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选   C    

  A 100    B 99      C 97     D

5. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为：  C  

  A  2          B  3          C  4          D  5

6. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：  A   

   A 98            B 99             C 50             D 48

7. 平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过 D   。

   A  –1      B  1        C  0      D  1

8.由3个结点所构成的树有   B  种形态。

Ａ1        Ｂ 2     Ｃ 3        Ｄ 4

9. 二叉树是非线性数据结构，所以   C    。

Ａ 它不能用顺序存储结构存储            Ｂ它不能用链式存储结构存储  

Ｃ 顺序存储结构和链式存储结构都能存储  Ｄ顺序存储结构和链式存储结构都不能使用

10. 设有100个元素，用折半查找法进行查找时，最少比较次数为  C  次。

A  4     B 3       C 1       D 7

五、简答题（每小题5分，共10分）

1.试分别找出满足以下条件的所有二叉树：

(1) 二叉树的前序序列与中序序列相同；

(2) 二叉树的中序序列与后序序列相同；

(3) 二叉树的前序序列与后序序列相同。

答：(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；

(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；

(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。  

2. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？

答：主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。

六、综合题（每小题5分，共15分）

1．已知一棵二叉树的中序、后序序列分别如下：

中序：D C E F B H G A K J L I M 

后序：D F E C H G B K L J M I A 

要求：⑴ 画出该二叉树；

⑵ 写出该二叉树的先序序列。

先序：A B C D E F G H I J K L M  

2．在一段文字中，7个常用汉字及出现频度如下： 的   地   于   个   和   是   有；

     20   19   18   17   15   10   1

要求：⑴ 画出对应的Huffman树；⑵ 求出每个汉字的Huffman编码。

⑵  01  的          00  地  

    111  于         110  个  

    101  和        001  是  

   1000  有    

3. 请画出右图所示的树所对应的二叉树。

七、算法设计题（15分）

若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：

(1) 统计二叉树中叶结点的个数。

(2) 以二叉树为参数，交换每个结点的左孩子和右孩子。

(1) 统计二叉树中叶结点个数

    int leaf ( BinTreeNode  * ptr ) {if ( ptr == NULL ) return 0;

        else if ( ptr->leftChild == NULL && ptr->rightChild == NULL ) return 1;

        else return leaf ( ptr->leftChild ) + leaf ( ptr->rightChild }

void exchange ( BinTreeNode * ptr )

 {

     BinTreeNode * temp;

        if ( ptr->leftChild != NULL || ptr->rightChild != NULL ) 

{temp = ptr->leftChild;

ptr->leftChild = ptr->rightChild;}

    }