资源描述：
《数据结构期末习题2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、6」选择题1、假定在一棵二叉树中，度为2的分支结点个数为15,度为1的分支结点个数为30个，则叶子结点数为（B）。A、15B、16C、17D、472、设n,m为一棵树上的两个结点，在中根遍历吋，n在m前的条件是（C）。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孙3、由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D）0A、23B、37C、46D、444、如果F是由树T转换而来的二叉树，则T中结点的前根就是F中结点的（B）。A、中根遍历B、先根遍历C、后根遍历D、按层遍历5、某二叉树的先根遍历结点序列和后根遍历结点序列刚好相反，则该二叉树一定是（D
2、）0A、空树或只有一个根结点B、完全二叉树C、二叉排序树D、高度等于其结点数6.2填空题1、在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（后继）结点，其余结点的后继结点可以（任意多个）。2、在具有n个结点的二叉树中，有（n+1）个空指针。3、深度为k的完全二叉树至少有（2kd）个结点，至多有（2^1）个结点，若按自上而下，从左到右次序给结点从1开始编号，则编号最小的叶子结点的编号是（n/2+l）。4、由a,b,c三个结点构成的二叉树，共有（5）种不同形态。5、树所对应的二叉树其根结点的（右）子树一定为空。6.3应用题1、给定的树如图6・24
3、（a）所示，冋答以下问题：（1）哪个是根结点，哪些是叶子结点？答:根结点是A,叶子结点是B,K,L,M,G,D,H,I,J。（2）哪个是结点F的双亲结点，哪些是结点F的祖先结点，哪些是结点F的孩子结点？答：结点F的双亲结点是C,祖先结点是A,C,孩子结点是K,L,Mo（3）哪些是结点C的子孙结点，哪些是结点C的兄弟结点？答：结点C的子孙结点是F,G,K,L,M,结点C的兄弟结点是B,D,E。（4）给定树的层数是多少，结点1所在的层数是多少？答：树的层数为4,结点I在第三屋。（5）写出先根遍历、后根遍历和按层遍历的结点序列。答：先根：ABCFKLMGDEHIJ。后根：BKLMFGCDHI
4、JEA。按层：ABCDEFGHIJKLMo2、给定的二叉树如图6・25所示：（1）写出先根遍历、后根遍历、中根遍历和按层遍历的结点序列。答：先根：ABDIKECFGNo中根:DIKBEAFCNGo后根：KIDEBFNGCAo按层：ABCDEFGTNKo（2）画出先根遍历和中根遍历的线索二叉树。答：中根遍历的线索二叉树NULL3、图6-24中的树、森林与二叉树之间进行转换:（1）将图（a）中给定的树转换成二叉树（2）将图（b）中给定的二叉树转换成树(2)（3）将图（c）屮给定的森林转换成二叉树（4）将图6-24>p给定的二叉树转换成森林(4)4、列出所有满足以下条件的二叉树：（1）先根遍
5、历和中根遍历时，得到的结点序列相同答：空树、只有根结点的二叉树或所有的结点都没有左分支的二叉树。（2）后根遍历和中根遍历时，得到的结点序列相同答：空树、只有根结点的二叉树或所有的结点都没有右分支的二叉树。（3）先根遍历和后根遍历时，得到的结点序列相同答：空树或只有根结点的二叉树。5、已知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK,先根遍历的结点序列为ABCDEGFHJIK,画出对应的二叉树，并写出后根遍历的结点序列。答：解题依据：对先根遍历得到的结点序列来讲，第一个访问的结点肯定是二叉树的根结点，根据根结点可以将中根遍历的结点序列分为左子树、根结点和右子树三部分。根据分到的
6、左、右子树包含的结点将先根遍历结点序列分岀根结点、左子树和右子树。对左、右子树也是按先根遍历，所以可重复使用上述规则，就可以分出所有结点在二叉树中的位置。得到的二叉树如图所示：6、一个度为2的树与一棵二叉树有什么区别？答：一个度为2的树是一棵无序树，它的两个分支不分顺序；二叉树是一棵有序树，它的两个分支是有顺序的，分别称为左右子树。7^已知如下所示长度为12的表(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)，按表中元素的顺序构造一棵二叉排序树，插入吋按字典序大小进行比较。答：8、有7个带权结点，其权值分别为：4,7,8,2,5,1
7、6,30,试以它们为叶子结点构造一棵哈夫曼树(要求按每个结点的左子树根结点的权值小于等于右子树根结点的权值的次序构造)。答：构造的哈夫曼树为：9、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为：0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码。使用另一种编码方式是采用二进数的等长编码，给出每个字母的编码，并比较两种编码方案的优缺点。答：第一种方法：哈夫曼编码。为了简简
