第六章 树和二叉树
一、选择题
1．树最适合用来表示（ ）。
A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2．深度为5的二叉树至多有（ ）个结点。
A． 16 B． 32 C． 31 D． 10
3．有32个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5
4．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结
点。
A．25 B．15 C．16 D．41
5．在有n个结点的二叉链表中值为非空的链域的个数为（ ）。
A． n-1 B 2n-1 C n+1 D 2n+1
6．有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5
7．对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列
均相同。
A． 3 B． 1 C． 2 D． 不存在
8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。 A． 空或只有一个结点 B． 高度等于其结点数 C． 任一结点无左孩子 D． 任一结点无右孩子
9．前序遍历与中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。
A．一般二叉树 B．只有根结点的二叉树
C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树
10．设n, m为一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（ ）。
A． n在m右方 B． n在m左方 C． n是m祖先 D． n是m子孙
11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。
A． 不发生改变 B． 发生改变
28
C． 不能确定 D． 以上都不对 12．线索二叉树是一种（ ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D． 线性
13. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先
序遍历、中序遍历和后序遍历。如把由树转化得到的二叉树叫做这棵树对应的二叉树，则结论（ ）是正确的。
A． 树的先根遍历序列与对应的二叉树的先序遍历序列相同 B． 树的后根遍历序列与对应的二叉树的后序遍历序列相同 C． 树的先根遍历序列与对应的二叉树的中序遍历序列相同 D． 以上都不对
14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数
至少为（ ）。
A． 2h B． 2h-1 C． 2h+1 D． h+1
15. 设bt是某树的二叉树表示的根结点指针，则bt满足（ ）。
A． bt->lchild==bt->rchild B． bt->rchild==NULL C． bt->lchild==NULL D． bt==NULL
16．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。
A．2n+2 B． 2n+1 C． 2n D． 2n-1
17．设哈夫曼树的叶子结点数为n，则它的结点总数为（ ）。
A． 2n-1 B． 2n C． 2n+1 D． 不确定
18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。
A． 50 B． 60 C. 52 D. 65
19．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根
的右子树的根是（ ）。
A． E B． F C. G D. H 20．下列有关二叉树的叙述中正确的是（ ）。
A． 二叉树的度为2
B． 任何一棵二叉树中至少有一个结点的度为2 C. 度为0的树是一棵二叉树 D. 二叉树中任何一个结点的度为2 21．二叉树上叶结点数等于（ ）。
A． 分支结点数加１ B． 单分支结点数加１ C. 双分支结点数加１ D. 双分支结点数减１ 22．判断线索二叉树中p所指结点由左孩子的条件是（ ）。
29
A． p!=UNLL B． p->lchild!=NULL C. p->ltag==0 D. p->ltag==1
二、填空题
1. 具有n个结点的完全二叉树的深度为 。 2. 二叉树第i层上最多有 个结点。 3. 深度为k的二叉树最多有 个结点。
4．具有n个结点的二叉树的最小深度为 ，最大深度为 ；具有具有n个结点的度为2的树的最小深度为 ，最大深度为 。 5．具有m个叶结点的huffman树共有 个结点。
6．完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。
7．在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 8．三个结点a,b,C．组成二叉树，共有 种不同的结构。
9. 一颗树T中，包括1个度为1的结点，2个度为2的结点，3个度为3的结点，则T的叶子结点数为 。
10．已知某完全二叉树采用顺序存储结构，结点的存放顺序为（A,B,C,D,E,F,G,H,I,J），该完全二叉树的后根遍历序列为 。 11．前序遍历序列是abc且后序遍历序列为cba的二叉树共有 棵。
12. F是由T1, T2, T3三棵树组成的森林，T1, T2, T3 的结点数分别为n1,n2,n3,则F对应的二叉树B(F)的根的左子树中结点数为 ，根的右子树中的结点数为 。
三、基础知识题
1．已知一棵树遍的集合为{
(7) 哪些是结点e的兄弟？哪些是结点f的兄弟？ (8) 结点b和n的层次号分别是什么？
30
(9) 树的深度是多少？
(10) 以结点c为根的子树的深度是多少？ (11) 树的度数是多少？
2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k
的结点，问该树中有多少个叶子结点？
4．对题2所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 5．现有按先序遍历二叉树的结点序列为abc，试写出能得到这一遍历结果的各种二
叉树。
6．一棵非空的二叉树其先序序列和后序序列正好相反，说明这棵二叉树的形状。 7．分别画出和下列树对应的二叉树。
A B
8．画出和下列二叉树相应的森林。
A B
9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权
路径长度。
10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出
31
该树并给出其后序序列。
12. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,
试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。 13. 设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设
计huffman编码并画出对应huffman树。
14. 对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带
权路径长度。
15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15, 18,23，
构造一棵huffman树，并给出每个字符的huffman编码。
16. 设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求：
(1) 画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。
17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21,
10, 要求： (1) 为每个字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。
18．证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。
19. 证明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改
变。
四、算法设计题
1．试给出二叉树先序遍历的非递归形式的算法。 2．试写出按层次遍历二叉树的算法。
3．以二叉链表作存储结构，试编写求二叉树深度的算法。
4．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上叶子结点个数。 5．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上度为2的结点个数。 6．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子结点个数。 7．设计一个算法，统计二叉树中 等于给定值x的结点个数。 8．设计一个算法，从一棵二叉树中查找出所有结点的最大值。 9．编写递归算法，将二叉树中所有结点的左、右子树相互交换。
10．编写求任意二叉树中一条最长的路径的算法，要求输出此路径上各结点的值及路径的长度。
11．设一棵树以孩子-兄弟表示法存储，试编写计算树的深度的算法。
32
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题11级用(7)在线全文阅读。
相关推荐：