数据结构-树习题复习课程.ppt

《数据结构-树习题复习课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-树习题一棵节点数为2000的完整二叉树的叶子数是（）。A.999B.1000C.1001D.1002在有N个叶子节点的霍夫曼树中，其节点总数为（）。A不确定B2NC2N+1D2N-1一棵完全二叉树有200个结点，则度数为1的结点个数为（），度数为0的结点个数为（）度数为2的结点个数为（）a100b98c1d99e50f120g0对于一棵满二叉树，m个叶子结点，n个结点，深度为h，则（）an=h+mbh+m=2ncm=h-1dn=2h-1在一棵二叉树上第5层的结点数最多为（）（假设根结点的层数为0）a8b

2、16c15d32设T是哈夫曼树，具有5个叶子结点，树T的高度最高可以是（）a3b4c5d6在树和二叉树的转换中，每棵树都对应一棵二叉树。下列结论正确的是（）1树的先序遍历与其对应的二叉树的先序遍历相同2树的后序遍历与其对应的二叉树的后序遍历相同3树的先序遍历与其对应的二叉树的中序遍历相同4以上都不正确具有3个结点的树和具有3个结点的二叉树的所有不同形态分别是（）A2b6c5d8关于二叉树的下列说法正确的是（）。A．二叉树的度为2B．二叉树的度可以小于2C．每一个结点的度都为2D．至少有一个结点的度为2具有68个结

3、点的完全二叉树的深度为（）A6b7c868若一棵完全二又树中某结点无左孩子，则该结点一定是（）。A．度为1的结点B．度为2的结点C．分支结点D．叶子结点遍历一棵具有n个结点的二叉树，在前序序列、中序序列和后序序列中所有叶子结点的相对次序()A．都不相同B．完全相同C．前序和中序相同D．中序与后序相同一棵有124个叶结点的完全二叉树，最多有()个结点。(A)247(B)248(C)249(D)250(E)25l一棵完全二叉树的层次序列为：ABCDEFGHIJKL，请写出后序序列。具有2000个节点的二叉树，其高度至

4、少为（）。A9B10C11D12某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）二叉树。A空或只有一个节点B高度等于其节点数C任一节点无左孩子D任一节点无右孩子如果节点A有3个兄弟，而且B为A的父节点，则B的度为（）。A3B4C5D1中序遍历一棵二叉排序树所得到的节点访问序列是节点值的（）序列。A递增或递减B递减C递增D无序在一棵树中，（）没有前驱结点。A.分支结点B.叶结点C.树根结点D.空结点由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53在

5、一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2B.1C.0D.–1以二叉链表作为二叉树存储结构，在有N个节点的二叉链表中，值为非空的链域的个数为（）。AN-1B2N-1CN+1D2N+1已知某二叉树是由森林转换过来的，如图所示，请将这棵二叉树还原成森林，并给出森林的前根序列和后根序列。有一段正文由字符集A，D，C，D，E，F中的字母组成，这6个字母在正文中出现的次数分别为12，18，26，6．4．34。(1)为这6个字母设计哈夫曼编码。(2)设每个字节由8位二进制位组成，请计算按哈夫曼编码压缩存

6、储这段正文共需多少个字节?将一棵树T转换为一棵二叉树T2，则T的后序遍历是T2的()．a．先序b．中序c．后序d．无法确定树最适合于用来表示（）．a线性结构的数据b顺序结构的数据c元素之间无前驱和后继关系的数据d元素之间有包含和层次关系的数据设一棵二叉树度2的结点数是7，度为1的结点数是6，则叶子结点数是A．6B．7C．8D．9设a、b为一棵二叉树的两个结点，在后序遍历中，a在b前的条件是A．a在b上方B．a在b下方C．a在b左方D．a在b右方线索二叉树树是一种()．a逻辑结构b．线性结构c．逻缉和线性结构d．物

7、理结构N个结点的线索二叉树中，线索的数目是〔)。A．N—1B．N+1C．2ND．2N—1假设一棵二叉树的按层次遍历序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。已知一棵二叉树的前序序列和中序序列分别为：ABDGCEFH和DGBAECHF，则该二叉树的后序序列是什么？答：既可先画树而得后序序列，也可直接推出后序序列，结果为：GDBEHFCA将下列树转为相应的二叉树。哈夫曼树是带权路径长度之和最小的树，但现在要求带权路径长度之和最大的树，你认为应该怎样求？请写出设计思路。假设字符a,b,

8、c,d,e,f的使用频度分别是0.07,0.09,0.16,0.18,0.23,0.27，请画出对应的WPL最大的树并计算WPL的值。解：（1）根据给定的n个权值构成n颗二叉树的集合F（2）在F中选取两颗根结点的权值最大的数作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值较小者（3）在F中删除这两棵树，同时将新得到的二叉树加入F中（