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

1、华东理工大学网络学院（专科）数据结构ch6树和二叉树、ch8查找班级 学号 姓名 成绩一、名词解释（每个2分，共10分）1 .结点的度：结点的子树的个数。2 .二叉树：满足条件（1）每个结点的度都不大于 2; （2）每个结点的孩子结点次序 不能任意颠倒；这样的树形结构称为二叉树。3 .线索化：对二叉树以某种次序进行遍历并且加以线索的过程。4 .哈夫曼树：带权路径长度 WPL最小的二叉树称为哈夫曼树或者最优二叉树。5 .冲突：不同的关键字可能得到同一个哈希地址，这种现象称为冲突。二、填空题（每空1分，共20分）1 .由树转换为二叉树，其根节点的右子树总是为空 。2 .在分块查找方法中，首先查找索

2、引（表），然后再查找相应的块。3 .含17个结点的二叉树的深度是5（设根结点的深度为 1）。4 .一棵高度为h的满二叉树共有2h-1个终端结点。5 .已知一棵完全二叉树的第 5层有3个结点，其叶子结点数是9。6 .对线性表进行二分查找时，要求线性表必须以.顺序方式存储,且结点按关键字有序 排歹” O7 . N个结点的二叉树采用二叉链表存放，共有空链域个数为n+1。8 .在各种查找方法中，平均查找长度与结点个数无关的是哈希杳找法。9 .深度为6 （根层次为1）的二叉树至多有26 -1个结点。10 .由树转换成的二叉树里，一个结点N的左孩子是 N在原树里对应结点的最左子结点_,而N的右孩子是它在原

3、树里对应结点的最邻近的右兄弟。11 .在哈希存储中，装填因子”的值越大，则发牛冲突的可能性就越大；a的值越小，则 发生冲突的可能性就越小。12 .哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和 处理冲突的方法 。13 .树是结点的有限集合，它有 0个或1个 根结点，记为 To其余的结点分成为 m （m >0）个 互不相交 的集合T1, T2,，Tm,每个集合又都是树，此时结点 T称为Ti 的 父结点 ，Ti称为T的子结点（1wiwm）。一个结点的子树个数为该 结点的度 。三、判断正误（对的用”'表示，错误的用“F”表示。每小题1分，共10分）1 .（ T ）具有n个结点的

4、满二叉树，其叶结点的个数为（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 )二叉排序树或是一棵空树，或是具

5、有下列性质的二叉树：若它的左子树非空， 则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的值。10 .( F )分块查找法中的索引顺序表的特点是块间可无序，但块内一定要有序。四、单项选择题(每小题2分，共20分)1 .对包含n个元素的哈希表进行查找，平均查找长度为：DA O(log2n) B O(n) C O(nlog2n) D 不直接依赖于 n2 .将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号最大的非叶结点的编号为：CA 48 B 49 C 50 D 513 .某二叉树结点的中序序列为A、B、C、D、E、F、

6、G,后序序列为 B、D、C、A、F、G、巳则其左子树中结点数目为：CA 3 B 2 C 4 D54 .设一哈希表表长 M为100 ,用除留余数法构造哈希函数，即H (K) =K MOD P ( P<=M ),为使函数具有较好性能，P应选 CA 100 B 99 C 97D895 .在顺序表(3, 6, 8,10,12,15,16,18, 21,25, 30 )中，用折半法查找关键码值11,所需的关键码比较次数为：CA 2B 3C 4D 56 .将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩子的编号为：AA 98B

7、 99C 50D 487 .平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过_D。A 1 B 1C 0 D 18 .由3个结点所构成的树有B一种形态。A 1B 2 C 3D 49 .二叉树是非线性数据结构，所以C。A它不能用顺序存储结构存储B它不能用链式存储结构存储C顺序存储结构和链式存储结构都能存储D顺序存储结构和链式存储结构都不能使用10 .设有100个元素，用折半查找法进行查找时，最少比较次数为C 次。五、简答题(每小题5分，共10分)1 .试分别找出满足以下条件的所有二叉树：(1)二叉树的前序序列与中序序列相同；(2)二叉树的中序序列与后序序列相同；(3)二叉树的前序序列

8、与后序序列相同。答：(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树;(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。2 .在哈希表中，发生冲突的可能性与哪些因素有关？为什么？答：主要与哈希函数、装填因子“有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子a较小，则哈希表较稀疏，发生冲突的可能性较小。六、综合题(每小题5分，共15分)1 .已知一棵二叉树的中序、后序序列分别如下:中序：D C E F B H G A K J LI M后序：D F E C H G B K L J M I

9、 A要求：画出该二叉树； 写出该二叉树的先序序列。先序：A B C D E F G H I J K L M2.在一段文字中，7个常用汉字及出现频度如下：的 地 于 个 和 是 有;2019181715101要求：画出对应的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 )BinTre