第6章 树和二叉树自测卷解答    姓名    班级   
题号
一
二
三
四
五
六
总分
题分
10
15
11
20
20
24
100
得分
一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）
（7）1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有辽个非空指针域。（即 有n+1个空指针）
（X ） 2.二叉树中每个结点的两棵子树的高度差等于1。
说明：只有平衡二叉树仅符合子树高度差＜=1
（V ） 3.二叉树中每个结点的两棵子树是有序的。
（X ） 4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（X ） 5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于 其右非空子树（若存在的话）所有结点的关键字值。    （应当是二叉排序树的特点）
（X ） 6.二叉树中所有结点个数是其中k是树的深度。（应2口）
（X ） 7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。    （应完全二叉树）
（X ） &对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有£—1个结点。（应2"） （V ） 9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为 空指针。
（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一 个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。） 即有后继链接的指针仅n-1个。
（V ） 10. K01年计算机系研题]]具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数=[n/2]=6,再求n2=n（）-l=5
问：具有13个结点的完全二叉树有几个度为2的结点？
二、填空（每空1分，共15分）
1.由3个结点所构成的二叉树有_ 种形态。
2.【计算机研2000】一棵深度为6的满二叉树有也+也=0+匹=n曰=31个分支结点和2“ =32个叶 子。
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3.一棵具有257个结点的完全二叉树，它的深度为 9    二叉树定义。
（注：用log2（257+l）=8.011再向上取整，值为9
4.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。
答：最快方法：用叶子数= [n/2]=350
5.设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点,有499 个度为2的结
点，有 1    个结点只有非空左子树,有    个结点只有非空右子树。
答：最快方法：用叶子数=[n/2] = 500 , n2=n0-l=499o另外，最后一结点为2i属于左叶子，右叶子是空
的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数=0.
6.【严题集6.7③】一棵含有n个结点的k叉树，可能达到的最大深度为n ,最小深度为2。 答：当k=l（单叉树）时应该最深，深度=n （层）；当k=n-l （n-1叉树）时应该最浅，深度=2 （层），但不 包括n=0或1时的特例情况。教材答案是“完全k叉树”，未定量。）
7.【96程试题1】 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历 次序有六种。最常用的是三种：前序法（即按NLR次序），后序法（即按 LRN 次序）和中序 法（也称对称序法，即按LNR次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是
BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是    F E G H I） C B   
解：法1：先由已知条件画图，再后序遍历得到结果；
法2：不画图也能快速得出后序序列，只要到根的位置特征。由前 序先确定root,由中序先确定左子树。例如，前序遍历BEFCGDH中， 根结点在最前面，是B；则后序遍历中B—定在最后面。
法3：递归计算。如B在前序序列中第一，中序中在中间（可知左 右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同 样处理，则问题得解。
&【全国专升本统考题】中序遍历的递归算法平均空间复杂度为    O（n）。
答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k+1,包括叶子的空域也递归了一次。
9.【计算机研2001］用5个权值｛3, 2, 4. 5, 1｝构造的哈夫曼（Huffman）树的带权路径长度是 33 解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL= （4+5+3） X2+ （1+2） X3=33
（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）
（注：合并值应排在叶子值之后）
A. 32    B. 33    C. 34    D. 15）
三、单项选择题（每小题1分，共11分）
（C ） 1.不含任何结点的空树    。
（B ）是一棵二叉树；
（D）既不是树也不是二叉树
（B ）它不能用链式存储结构存储；
（D）顺序存储结构和链式存储结构都不能使用
（A ）是一棵树；
（C）是一棵树也是一棵二叉树；
（C ） 2.二叉树是非线性数据结构，所以   
（A）它不能用顺序存储结构存储；
（C）顺序存储结构和链式存储结构都能存储;
（D） 3. K01年计算机研题1］具有n（n>0）个结点的完全二叉树的深度为    。
（A）「log2（n）］    （B） L log2（n）J （C）Llog2（n） J+l （D）「log2（n+1）［
注：「x］表示不小于x的最小整数；Lx」表示不大于x的最大整数，它们与［］含义不同！
（A ） 4.把一棵树转换为二叉树后，这棵二叉树的形态是    o
（A）唯一的    （B）有多种
（C）有多种，但根结点都没有左孩子    （D）有多种，但根结点都没有右孩子
注:唯一且根结点都没有右孩子
5.【94程P11] 从供选择的答案中，选出应填入下面叙述    ？    内的最确切的解答,把相应编号写在 答卷的对应栏内。
树是结点的有限集合，它丄根结点，记为T。其余的结点分成为m (mMO)个B
的集合Tl, T2,…，Tm,每个集合又都是树，此时结点T称为匚的父结点，匚称为T的子结点(lWi Wm)。一个结点的子结点个数为该结点的 _o
6.【95程P13] 从供选择的答案中，选出应填入下面叙述 ？    内的最确切的解答,把相应编号写在
答卷的对应栏内。
二叉树A。在完全的二叉树中，若一个结点没有B ,则它必定是叶结点。每棵树都能惟一地转 换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的C , 而N的右子女是它在原树里对应结点的D 。
供选择的答案
A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构 B:①左子结点 ②右子结点 ③左子结点或者没有右子结点    ④兄弟
C〜D：①最左子结点    ②最右子结点    ③最邻近的右兄弟    ④最邻近的左兄弟
5最左的兄弟 ⑥最右的兄弟
答案：A=    B=    C=    D=   
答案：ABCDE = 2, 1, 1, 3
四、简答题(每小题4分，共20分)
1.【严题集6.2®] 一棵度为2的树与一棵二叉树有何区别？
答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中 若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
C的结点类型定义如下：
C++算法如下：
2. K01年计算机研题F设如下图所示的二
struct node
C++结点定义：
叉树B的存储结构为二叉链表，root为根
{char data;
Struct BinTreeNodef
指针，结点结构为：(lchild,data,rchild )。
struct node *lchild, *rchild;
Char data;
其中lchild, rchild分别为指向左右孩子的
};
BinTreeNode *lchild,*rchild;}
指针，data为字符型，root为根指针，试
Class BinaryTree{
回答下列问题：
c算法如下：
Public:
1.对下列二叉树B,执行下列算法
void traversal(struct node *root)
BinTreeNode: *root;   
traversal(root),试指出其输出结果；
{if (root)
Void traversal() {
2.假定二叉树B共有n个结点，试分析
{pTintf("%c‘‘, root->data);
if (root)
算法traversal(root)的时间复杂度。
traversal(root->lchild);
{printf(“％c", root->data);
(共8分)
printf("%c'', root->data);
traversal(root->lchild);
traversal(root->rchild);
printf("%c", root->data);
BX \
}
traversal(root->rchild);
CFG
E
}
}
}
}
对于二叉树B执行：
B.traversal()的结果是：

二叉树B 解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：ABCCEEBADFFDGG 特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔 左子树的全部结点后再重复出现；如A, B, D等结点。反之马上就会重复出现。如C, E, F, G等结点。 时间复杂度以访问结点的次数为主，精确值为2*n,时间渐近度为O(n).
3.KOI年计算机研题［【严题集6.27③】给定二叉树的两种遍历序列，分别是：
前序遍历序列：D, A, C, E, B, H, F, G, I；中序遍历序列：D, C, B, E, H, A, G, I, F, 试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
解：方法是：由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树 的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root,不断递 归，则所有元素都将被唯一确定，问题得解。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。