【课后习题】第6章 树和二叉树
 网络工程2010级（  ）班   学号：              姓名：         
题  号
一
二
三
四
五
总分
得  分
一、填空题（每空1分，共16分)
1. 从逻辑结构看，树是典型的        。
2. 设一棵完全二叉树具有999个结点，则此完全二叉树有      个叶子结点，有        个度为2的结点，有        个度为1的结点。
3. 由n个权值构成的哈夫曼树共有        个结点 。
4. 在线索化二叉树中，T所指结点没有左子树的充要条件是            。
5. 在非空树上，_____没有直接前趋。
6. 深度为k的二叉树最多有        结点，最少有      个结点。
7. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为
          且小于n时，结点i的右兄弟是结点        ，否则结点i没有右兄弟。
8. N个结点的二叉树采用二叉链表存放，共有空链域个数为          。 
9. 一棵深度为7的满二叉树有___ ___个非终端结点。
10. 将一棵树转换为二叉树表示后,该二叉树的根结点没有         。
11. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的        遍历结果是一样的。
12. 一棵Huffman树是带权路径长度最短的二叉树，权值        的外结点离根较远。
二、判断题（如果正确，在对应位置打“ ”，否则打“ ”。每题0.5分，共5分)
1
2
3
4
5
6
7
8
9
10
1. 对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i-1个结点。
2. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该二叉树的根结点是那一个，则可以确定这棵二叉树。
3. 一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。
4. 度≤2的树就是二叉树。
5. 一棵Huffman树是带权路径长度最短的二叉树，权值较大的外结点离根较远。
6. 采用二叉树来表示树时，树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。
7. 不存在有偶数个结点的满二叉树。
8. 满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。
9. 已知二叉树的前序遍历顺序和中序遍历顺序，可以惟一确定一棵二叉树； 
10. 已知二叉树的前序遍历顺序和后序遍历顺序，不能惟一确定一棵二叉树； 
三、单项选择（请将正确答案的代号填写在下表对应题号下面。每题1分，共30分)
题号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
答案
　
　
　
　
　
　
　
　
　
　
题号
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
答案
　
　
　
　
　
　
　
　
　
　
二叉树公式1. 树的后根遍历序列等同于该树对应的二叉树的(  ).
A). 先序序列  B). 中序序列  C). 后序序列  D) 层次序列
2. 设一棵二叉树中，度为1的结点数为9，则该二叉树的叶结点的数目是(  )。
A)10                B)11                  C)12                  D)不确定
3. 哈夫曼算法可以用于（  ）。
A) 动态存储管理          B) 表达式求值 
C) 数据通信的二进制编码  D) 城市间的交通网设计
4. 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（  ）。
A．队列          B．栈          C．线性表        D．有序表
5. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（  ）。
A．不一定相同    B．都相同      C．都不相同    D．互为逆序
6. 由下列三棵树组成的森林换成一棵二叉树为（  ）。
7. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（  ）。
A．层次遍历算法  B．前序遍历算法    C．中序遍历算法    D．后序遍历算法
8. 哈夫曼树是访问叶结点的外部路径长（  ）的二叉树。
A.最短；      B.最长      C.可变      D.不定；
9. 三个结点可以构成（  ）种不同形状的树。
A. 2；      B. 3      C. 4    D. 5；
10. 三个结点可以构成（  ）种不同形状的二叉树。
A. 无穷    B. 3      C. 4    D. 5；
11. 一棵有16个结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（  ）。
A. 2，14    B. 2，15    C. 3，14    D. 3，15；
12. 深度为k的二叉树最多有（  ）结点。
A.2k      B.2k-1；      C.2k-1     D.k2；
13. 具有100个结点的完全二叉树的深度为（  ）。
A. 6      B. 7；      C. 8    D. 9；
14. 叶结点个数比度为2的结点的个数多一个，该性质只适用于（  ）。
A.完全二叉树    B.满二叉树    C.树    D.所有二叉树；
15. 具有n个结点的完全二叉树的深度为（  ）。
A. log2n +1      B. log2n +1；        C. log2n    D. log2n ；
16. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是(    )
A）M1        B）M1+M2        C）M2+M3      D）M3；
17. 二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while（p->lchild!=Nu11）p=p->lchild，则（  ）。
A. p指向二叉树的最右下方的结点      B. p指向二叉树的最左下方的结点；
C. p仍指向根点                      D. p为null；
18. 如果图1所示为一棵二叉树，则其中序遍历序为（    ）。
A、abcdefgh      B、abdfcegh      C、fdbgheca      D、bfdagehc；
19. 对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=(  )
A.n1+1    B. n2+1        C. n1+n2        D.2n1+1

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