数据结构期末复习 第六章树和二叉树一、选择题1. 树最适合用来表示C。A. 有序数据元素 B. 无序数据元素C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据2. 树中所有结点的度等于所有结点数加D。A. 1 B. 0 C. 2 D. -13. 对于一个满二叉树m个树叶n个结点深度为h则D。A. n h m B. h m 2n C. m h-1 D. n 2 h -14. 如图所示一棵二叉树中C不是完全二叉树。5. 深度为5的二叉树至多有C个结点。A. 16 B. 32 C. 31 D. 106. 假定一棵二叉树中双分支结点数为15单分支结点数为30则叶子结点数为B。A. 15 B. 16 C. 17 D. 477. 二叉树第k层上最多有B个结点。A2k B2k-1 C2k-1 D2k-18.在一棵度具有5层的满二叉树中结点总数为A。A31 B32 C33 D169.在一棵二叉树上第5层的结点数最多为C。A8 B15 C16 D3210.具有127个结点的完全二叉树其深度为B。A8 B7 C6 D511. 设一棵二叉树中没有度为1的结点已知叶子结点数为n此树的结点数为D。A2n2 B2n1 C2n D2n-112.设二叉树中有n2个度为2的结点n1个度为1的结点n0个叶子结点则此二叉树中空指针域个数为D。An0n1n2 Bn2n12n0 C2n2n1 D2n0n1解析结点总数nn0n1n2。在二叉链表中每个结点有2个指针域左孩子和右孩子。总指针域数2n。非空指针域数边数e。在二叉树中边数en−1。即除了根结点每个结点都有一条边。所以空指针域数2n-n-1n1n0n1n21。根据二叉树的性质叶子结点数比度为2的结点多1所以n2可以表示为n0-1所以空指针域数n0n1(n0-1)12n0n113.n个结点的二叉树中用二叉链表做存储非空指针数目为C。An B2n Cn-1 Dn114. 在一棵二叉树的二叉链表中空指针域数等于非空指针域数加C。A0 B1 C2 D-115. 在一非空二叉树的中序遍历序列中根结点的右边A。A. 只有右子树上的所有结点 B. 只有右子树上的部分结点C. 只有左子树上的所有结点 D. 只有左子树上的部分结点16. 如图所示二叉树的中序遍历序列是B。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh17. 设n、m为一棵二叉树上的两个结点中序遍历时n在m前的条件是C。A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孙18.某二叉树的先序遍历序列和后序遍历序列正好相反则该二叉树一定D。A.空或只有一个结点 B.完全二叉树C.二叉排序树 D.深度等于其结点数19.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK中序遍历HFIEJKG该二叉树根的右子树的根是C。AE BF CG DH20. 如果将给定的一组数据作为叶子数值所构造出的二叉树的带权路径长度最小则该树称为A。A哈夫曼树 B平衡二叉树 C二叉树 D完全二叉树21.利用n个值作为叶结点的权生成的哈夫曼树中共包含有D个结点。A. n B. n1 C. 2*n D. 2*n-122. 利用2、4、5、10这四个值作为叶子结点的权生成一棵哈夫曼树该树中所有叶子的最长带权路径长度为C。A. 18 B. 16 C. 38 D. 3023.哈夫曼树是D。A满二叉树 B二叉排序树C树的路径长度最短的二叉树 D带权路径长度最短的二叉树24.用权值分别为15245的四个结点构造出的哈夫曼树为 D 。25.设哈夫曼树的叶结点数为n则它的结点总数为A。A2n-1 B2n C2n1 D不确定二、判断题1树是一种线性结构。×2树最适合表示元素之间具有层次关系的数据。√3如果结点A有 3个兄弟而且B是A的双亲则B的度是4。√4. 树中全部结点的度均大于0。×5. 森林是mm≥0棵互不相交的树的集合。√6. 深度为k的完全二叉树至少有2k-1个结点。×7. 完全二叉树中没有度为1的结点。×8若树的度为2时该数为二叉树。×9具有三个结点的二叉树有五种。√解析如下所示10深度为5的二叉树最多有3层。×11具有256个结点的完全二叉树的深度为9 。√12具有100个结点的完全二叉树有50 个叶子。√解析100个结点的完全二叉树前6层是满的1、2、4、8、16、32共63个结点所以第7层有100-6337个结点都是叶子结点要在第7层产生37个叶子结点则第6层要有18个双分支结点和1个单分支结点所以第6层还剩32-1913个结点没有孩子即叶结点。所以总叶结点数371350.13. 在二叉树的链接存储中每个结点设置三个域值域、左指针域和右指针域。√14二叉树只能采用二叉链表来存储。×15具有n个结点的二叉树采用二叉链表存储共有n1个空链域。√16. 二叉树的先序遍历序列中任意一个结点均处在其子女结点的前面。√17已知一棵树的先序序列和后序序列一定能构造出该树。×解析先序中序→可唯一确定二叉树后序中序→可唯一确定二叉树先序后序→ ❌不能唯一确定二叉树当存在单支结点时产生歧义反例1 1/ \2 2上面两种二叉树先序都不12后序都为21。18. 二叉树的遍历就是按照一定次序访问树中所有结点并且每个结点的值仅被访问一次的过程。√19. 哈夫曼树一定是完全二叉树或满二叉树。×20. 哈夫曼树只存在着双支结点不存在单支结点。√三、本章综合应用或程序题1. 有一棵树如图所示回答下面问题1这棵树的根结点是C2这棵树的叶子结点是E3这棵树的度是A4这棵树的深度是B5c结点的孩子结点是D6c结点的父母结点是C。A. 3B. 4C. aD. e、fE. b、e、d、g2. 由如图所示的二叉树回答以下问题1其中序遍历序列B2其先序遍历序列C3其后序遍历序列AA. gdbeihfca B. dgbaechif C. abdgcefhi3.以34589作为叶结点的权构造一棵哈夫曼树。该树的带权路径长度为DA. 61 B. 62 C.63 D.654.以234789作为叶结点的权构造一棵哈夫曼树。权重值为4的叶结点的哈夫曼编码为ABCA. 000 B. 001 C.010 D.10解析哈夫曼树编码不唯一ABC都是可能的参考答案为B不准确。图示如下