《数据结构练习3.doc》由会员分享，可在线阅读，更多相关《数据结构练习3.doc（5页珍藏版）》请在金锄头文库上搜索。
1、华东理工大学网络学院 数据结构-ch6树和二叉树、ch8查找班级 学号 姓名 成绩 一、名词解释（每个2分，共10分）1. 结点的度 2. 哈夫曼树 3.线索化 4. 二叉树 5.冲突答：1 结点的度：结点的子树的个数。2哈夫曼树：带权路径长度WPL最小的二叉树称为哈夫曼树或者最优二叉树。3线索化：对二叉树以某种次序进行遍历并且加以线索的过程。 4二叉树：满足条件（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒；这样的树形结构称为二叉树。5 冲突：不同的关键字可能得到同一个哈希地址，这种现象称为冲突。二、填空题（每空1分，共20分）1.由树转换为二叉树，其根节点的右子树总
2、是 为空 。2. 深度为6（根层次为1）的二叉树至多有 26 1 个结点。3.含17个结点的二叉树的深度是 5 （设根结点的深度为1）。4.一棵高度为h的满二叉树共有 2h-1 个终端结点。5. 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是 9 。6.对线性表进行二分查找时，要求线性表必须以 .顺序 方式存储，且结点按关键字 有序 排列。7. 哈希表的查找效率主要取决于哈希表造表时选取的 哈希函数 和 处理冲突的方法 8. 在各种查找方法中，平均查找长度与结点个数无关的是 哈希查找法 。9. 在分块查找方法中，首先查找 索引（表） ，然后再查找相应的块。10. 由树转换成的二叉树里，一
3、个结点N的左孩子是N在原树里对应结点的 最左子结点 ，而N的右孩子是它在原树里对应结点的 最邻近的右兄弟 。11. 在哈希存储中，装填因子的值越大，则 发生冲突的可能性就越大 ；的值越小，则 发生冲突的可能性就越小 。 12. N个结点的二叉树采用二叉链表存放，共有空链域个数为 n+1 。13.树是结点的有限集合，它有 0个或1个 根结点，记为T。其余的结点分成为m（m0）个 互不相交 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的 父结点 ，Ti称为T的子结点（1im）。一个结点的子树个数为该 结点的度 。三、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10
4、分）1.( T )具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。2.( F )用一维数组存储二叉树时，总是以前序遍历存储节点。3.( T ) 判断线索二叉树中某结点p有左孩子的条件是p-ltag=0。4. ( T ）深度为K的完全二叉树至少有2K-1个结点。5.( F )折半查找适用于有序表，包括有序的顺序表和有序的链表。6.( F ）哈夫曼树中没有度为1的结点，所以必为满二叉树。7.( F )哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 8.( T ）若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。9.( F ）二叉排序树或是一棵空树，或是具有下列性
5、质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的值。10.( F )索引顺序表的特点是块间可无序，但块内一定要有序。四、单项选择题（每小题2分，共20分）1.对包含n个元素的哈希表进行查找，平均查找长度为： D A O(log2n) B O(n) C O(nlog2n) D不直接依赖于n2.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为： C A 48 B 49 C 50 D 513某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、
6、F、G、E，则其左子树中结点数目为： C A 3 B 2 C 4 D54. 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（Prtag=1，则在对该二叉树按照某种次序进行线索化时，该指针域指向该结点的 D 。 A 左孩子 B 右孩子 C 遍历前驱 D 遍历后继10. 设有100个元素，用折半查找法进行查找时，最大比较次数为 C 次。A 5 B 6 C 7 D 8五、简答题（每小题5分，共10分）1. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？答：主要与哈希函数、装填因子有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子较小，则哈
7、希表较稀疏，发生冲突的可能性较小。2. 试分别找出满足以下条件的所有二叉树：(1) 二叉树的前序序列与中序序列相同；(2) 二叉树的中序序列与后序序列相同；(3) 二叉树的前序序列与后序序列相同。答：(1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。六、综合题（每小题5分，共20分。）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 要求： 画出
8、该二叉树； 写出该二叉树的先序序列。答：先序：A B C D E F G H I J K L M 2有关键字集合：53、17、19、61、98、75、79、63、46、49，哈希函数：H（key）=key mod 13，采用开放定址法中的二次探测再散列方法解决冲突。要求： 将上述关键字填入下表； 求等概率下查找成功时的平均查找长度； 求装填因子。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 答： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1453791719984661756349 ASL = 15/12 = 1.25 = 10/15 = 0.67
9、3. 请画出右图所示的树所对应的二叉树。 答：转换后的二叉树为：4.在一段文字中，7个常用汉字及出现频度如下： 的 地 于 个 和 是 有； 20 19 18 17 15 10 1要求： 画出对应的Huffman树； 求出每个汉字的Huffman编码。 10039 61 19地 20的 26 3511 15和 17个 18于 1有 10是答： 01 的 00 地 111 于 110 个 101 和 001 是 1000 有七、算法设计题（10分）若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数。(2) 以二叉树为参数，交换每个结点的左孩子和右孩子。
10、答：(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 ); (2) 交换每个结点的左子女和右子女void exchange ( BinTreeNode * ptr ) BinTreeNode * temp;if ( ptr-leftChild != NULL | ptr-rightChild != NULL ) temp = ptr-leftChild;ptr-leftChild = ptr-rightChild; 第1 / 5 页
