数据结构 树练习题
目录
判断
选择
判断
1.一棵有124个结点的完全二叉树，其 叶结点个数是确定的。
【答案】正确
【解析】完全二叉树
若设二叉树的深度为h 除第 h 层外 其它各层 1～(h-1) 的结点数都达到最大个数(即1~(h-1)层为一个满二叉树) 第 h 层所有的结点都连续集中在最左边 就是完全二叉树
124 = 1 + 2 + 4 + 8 + 16 + 32 + 61
有61个叶节点
2.二叉树中序线索化后，不存在空指针域。
【答案】错误
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
3.对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。
【答案】正确
【解析】树中任意节点的权值一定大于自己的左右孩子，但不能保证一定不小于其他下一任结点的权值。
4.哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。
【答案】错误
【解析】哈夫曼树的形状不是唯一的，对于两个权值最小的结点，不区分左右；对于相同权值的结点，并入哈夫曼树的时间可能不同
5.对于一个有N个结点、K条边的森林，不能确定它共有几棵树。
【答案】错误
【解析】对于每一棵树来说，除去根结点，每一个结点上面都有一条边，因此边数e=n-1
则TotalEdgeNum=TotalNodeNum-TreeNum = N - K
6.树的后根序遍历序列等同于它所对应二叉树的中序遍历序列。
【答案】正确
【解析】一棵树的后序遍历和这棵树对应的二叉树的中序遍历相同 以及 高效的二叉树~_敲代码的小提琴手的博客-CSDN博客_树的后序遍历与其对应的二叉树的后序遍历序列相同
7.二叉树可以用二叉链表存储，树无法用二叉链表存储。
【答案】错误
【解析】树可以转化为二叉树
8.将一棵树转成二叉树，根结点没有左子树。
【答案】错误
【解析】树转化为二叉树采用二叉链表,"左孩子,右兄弟",根节点没有兄弟,所以转换后的根节点没有右孩子
9.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。
【答案】正确
【解析】邻接矩阵法的存储大小为n^2，只与顶点数有关，与边无关
10.用一维数组G[]存储有4个顶点的无向图如下：
G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
【答案】正确
【解析】
0
1 0
1 1 0
0 0 1 0g[2][0] = 1 有边
选择
1.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：
选B（左下角这个，别看错）
后序要求左右根，B符合
叶节点，还是右子节点，遍历完它肯定该根节点了
哈夫曼树的特点性质：（节点为的度数为0 表示 n0,以此类推）
①哈夫曼树中只存在度为2和度为0的节点，及n1=0。
②哈夫曼树中，度为0和度为2的节点关系：n2=n0-1
由以上两个性质，本题就很好解出答案：
n0+n2=115
n0+n0-1=115
n0=(115+1)/2=58
根据森林转换为二叉树的法则，二叉树的根结点通常是第一棵树的结点，二叉树的左子树是由第一棵树删去根后所得所有子树构成的，二叉树的右子树是由其它树（第二，第三棵树）构成的，故左子树结点个数是M1-1，右子树上的结点个数是M2+M3。
每个二叉树 ： 叶子节点数 = 度为2的节点数 + 1
全加起来： N = M + 二叉树个数
所以二叉树个数 = N - M
一条边对应一个子节点，剩下的点都是根节点，共有10个
V2没有直接到V3的边
这个带权弄得毫无意义
