数据结构 树 考试习题
发布时间：2024-11-21
数据结构考试内容
第五章 树
11． 不含任何结点的空树( )
A）是一棵树 B）是一棵二叉树 Ｃ）既不是树也不是二叉树 D）是一棵树也是一棵二叉树 12．二叉树是非线性数据结构，所以( )
A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储;
C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 13．把一棵树转换为二叉树后，这棵二叉树的形态是( ) A）唯一的 B）有多种
C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子
9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ） A) 24 B) 72 C) 48 D) 53 10.一棵含18个结点的二叉树的高度至少为( )
A) 3 B) 4 C) 6 D) 5 11.下面的二叉树中，( C )不是完全二叉树。
10. 设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（ ） A）x是y的左兄弟 B）x是y的右兄弟 C）y是x的祖先 D）y是x的孩子
11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（ ） A） 6 B） 5 C） 4 D） 3 7． 下列陈述中正确的是（ ）
A） 二叉树是度为2的有序树 B） 二叉树中结点只有一个孩子时无左右之分 C） 二叉树中必有度为2的结点 D） 二叉树中最多只有两棵子树，并且有左右之分 8. 树最适合用来表示（ ）
A） 有序数据元素 B） 无序数据元素 C） 元素之间具有分支层次关系的数据 D） 元素之间无联系的元素
数据结构考试内容
9. 3个结点有（ ）不同形态的二叉树
A） 2 B） 3 C） 4 D） 5 6．二叉树是非线性数据结构，( )
A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储; C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用 7．二叉树上叶结点数等于( )
A ) 分支结点数加1 B ) 单分支结点数加1 C ) 双分支结点数加1 D ) 双分支结点数减1
8．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1的一维数组中，设某结点下标为k(k>0)，则其双亲结点的下标是( ) A ) (k-1)/2 B ) (k+1)/2 C ) k/2 D ) k-1 8. 树最适合用来表示（ ）。
A．有序数据元素 B．无序数据元素 C. 元素之间具有分支层次关系的数据 D．元素之间无联系的元素 10.有64个结点的完全二叉树的深度为(
) (根的层次为第1层)。
A. 8 B. 7 C. 6 D. 5
11.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有２个，那么，该树有（ ）个叶子结点。
A. 4 B. 5 C. 6 D. 7 9.一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A、2 长度为（ ）
A 24 B 71 C 48 D 53 8. 二叉树上叶结点数等于（
）。
B、3
C、4
D、5
10. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径
A．分支结点数加1 B．单分支结点数加1 C．双分支结点数加1 D．双分支结点数减1
8. 某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。 A.空或只有一个结点 B.高度等于其结点数
数据结构考试内容
C.任一结点无左孩子 D.任一结点无右孩子
9. 在有n个结点的二叉链表中，值为空的链域的个数为( ) A. n-1 B. 2n-1 C. n+1 D. 2n+1 10. 一棵含18个结点的二叉树的高度至少为( )
A. 8 B. 7 C. 6 D. 5 11. 深度优先遍历类似于二叉树的( )
A.先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历
9. 一棵124个叶结点的完全二叉树，最多应有(
A.245
B.246
C.247
D.248
)个结点。
10. 后缀表达式“ 5 6*3 2 + -”的值为（ ）。
A.15 B.25 C.30 D.35
11. 由权值分别为 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（
）
A. 24 B. 71 C. 48 D. 53
7. 对一个满二叉树，m个树叶, n个结点, 深度为为h, 则（ ）。
A. n=2-1 B.h+m=2n C.m=h-1 D. n=h+m
8. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。
h
A.2 B.1 C.0 D.-1
9. 若完全二叉树的结点总个数为100（结点编号从1开始编号，按层序编号），则第58个结点的度为（ ）
A.2 B.1 C.0 D.不确定
）
10. 已知完全二叉树的第9层有240个结点，则该完全二叉树的结点数是（
二、填空题
1. 一棵深度为5的二叉树，至多有_____________个结点。31
A.494 B.495 C.496 D.497
6.图的存储结构有__________________和__________________，遍历图有______________、_____________等方法。邻接矩阵 邻接表 深度优先 广度优先 7.深度为ｋ的完全二叉树最多有 个结点。2 1
8.若按层序对深度为ｋ的完全二叉树中全部结点从１开始编号，则叶子结点可能的最小编号
k
数据结构考试内容
为 。2
k 2
1
6.设有树如图所示，则结点ｃ的度为___________，层次为___________，树的度为
___________，树的高度为___________。为２， 树的度为３，高度为４
结点ｃ的度为２， 层次
7.深度为ｋ的完全二叉树至少有___________个结点，最多有___________个结点。2
k 1
，
2k 1
7.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为
_______个，其中_______个用于链接孩子结点，_______个空闲着。2n，n-1，n+1 2. 后缀表达式“2 10 + 5 * 6 – 9 /”的值为 。6 3.由n个权值构成的哈夫曼树共有 个结点。2n-1 6.在一棵树中， ____ 结点没有后继结点。叶
4．后缀表达式“2 10 + 5 * 6 – 9 /”的计算结果为 。6
4.一棵深度为7的二叉树，最多有个结点。127
5.若一棵树的括号表示为A(B,C(E,F(G)),D),该树的叶子结点个数为________ ，该树的度为_____________ ，该树的深度为_____________。4、3、4 6.在有n个叶子结点的哈夫曼树中，总结点数是_______。2n-1
1. 深度为4的完全二叉树最少有______个结点，最多有_______个结点。8
15
6. 假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数分别为______、______、______和______个。2
2
7
6. 若结点A有其他三个兄弟,B是A的双亲结点,B的度是_______________。4
7. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_____________个。33
8. 一棵深度为7的二叉树，最多有 个结点。127
数据结构考试内容
三、应用题
1、名词解释：
树，子树，结点的度，叶子结点，孩子，双亲，兄弟，深度，有序树，森林，二叉树，遍历二叉树，树的带权路径长度，哈夫曼树。
2、描述二叉树的性质。
3、从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换为二叉树的基本目的是什么？指出树和二叉树的主要区别。 4、已知一棵树边的结点为{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>, <G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H.,,A,C>}，试画出这棵树,并回答下列问题：
（1）哪个是根结点？ （2）哪些是叶子结点？
（3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？
（7）哪些是结点E的兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？
5、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
6、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点， ，nk个度为k 的结点，问该树中有多少个叶子结点？
7、已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。
8、有n个结点的二叉树，已知叶子结点个数为n0，写出求度为1的结点的个数n1的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式。
9、假设n 和m 为二叉树中两结点，用“1”，“0”或“”（分
数据结构考试内容
子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。 10、找出所有满足下列条件的二叉树：
（a）它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的结点访问序列相同； 11、分别画出和下列树对应的各个二叉树：
12、画出和下列二叉树相应的森林：
13、画出和下列已知序列对应的树T：
树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为CBEFDGAJIKLH。
14、假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。
数据结构考试内容
15、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
16、编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。
17、编写递归算法，计算二叉树中叶子结点的数目。
5. 用于通信的电文仅由a、b、c、d、e、f、g、h等8个字母组成，字母在电文中出现的频率分别为：007、0.19、0.02、0.06、0.32、0.03、0.21、0.10。试构造相应的哈夫曼树并为这些字母设计哈夫曼编码。（9分） 得到的编码如下 ：
a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 h:0011 此题答案不唯一。
5. 设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树，并写出此二叉树的后序遍历。（10分）
后序： DHFBFIGCA
6. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算带权路径长度. （9分）
答案：
带权路径长度=（9+11+16）*2+7*3+（2+5）*4=121
1.已知一组关键字为{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素顺序依次插入
数据结构考试内容
到一棵初始为空的二叉排序树中,画出该二叉排序树,并求在等概率的情况下查找成功的平均查找长度。（10分）
1 1 2 2 3 3 3 4 2 5 1 6 ASL 3.5
12
1．设先序遍历某个树的结点次序为ABDEHCFGI，中序遍历该树的结点次序为DBEHAFCIG,要求画出这个二叉树,并写出该树的后序遍历的结点次序。(6分)
1. .后序:DHEBFIGCA
1．已知一棵树二叉如下，请写出按前序、中序、后序和层次遍历时得到的结点序列。（8分）
A
B C
D E F
G H
前序：
数据结构考试内容
中序： 后序： 层次：
各遍历次序如下
前序：Ａ，Ｂ，Ｄ，Ｇ，Ｃ，Ｅ，Ｆ，Ｈ 中序：Ｄ，Ｇ，Ｂ，Ａ，Ｅ，Ｃ，Ｈ，Ｆ 后序：Ｇ，Ｄ，Ｂ，Ｅ，Ｈ，Ｆ，Ｃ，Ａ 层次：Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ
4. 已知一棵完全二叉树共有999个结点，试求：(写出详细的分析过程) （9分） 1、树的高度（深度） 2、叶子结点的数目 3、度为1的结点数目
深度：10
叶子节点数目：500 度为1的节点数目：0
1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A
.请将下图所示的森林森林转换为所对应的二叉树。 B
图5-16
A
C E F
H
G
I J
K L
N
O
数据结构考试内容
4．将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。 答案
数据结构考试内容
1.已知一棵二叉树的中序遍历序列为： dfebagc，先序遍历序列为：abdefcg，请画出这棵二叉树
2.设用于通信的电文由７个字母组成，字母在电文中出现的频率分别为0.16、0.38、0.01、0.06、0.24、0.11、0.04，试为这７个字母设计赫夫曼编码。
赫夫曼树：
赫夫曼编码： ａ（0.15）： ｂ（0.39）：
数据结构考试内容
ｃ（0.01）： ｄ（0.06）： ｅ（0.24）： ｆ（0.11）： ｇ（0.04）：
1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA
2. 给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树，并计算WPL.
答案：
wpl=（9+11+16）*2+7*3+（2+5）*4=121
1.已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序列。 答案：
后序序列:ACDBGIHFE
2．在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。
数据结构考试内容
71 0 1
30 41
0 1 0 1 16 Y(14) 23 F(18) 0 1 0 1
G(9) U(7) A(12) Z(11)
哈夫曼树
A：100 G：000 F：11 U：001 Y：01 Z：101 （或0、1 相反） （8分） 注意：答案不唯一。
3. 已知一棵完全二叉树共有1001个结点，试求：(写出详细的分析过程) （9分） 1、树的高度（深度） 2、叶子结点的数目 3、度为1的结点数目 深度：10
叶子节点数目：501 度为1的节点数目：0
4. 试给下图所示二叉树的前序、中序和后序遍历序列。若一棵二叉树的前序遍历序列为：A B D E G C F，中序遍历序列为：D B E G A C F，试画出此二叉树。（10分）
数据结构考试内容
前序：ABDEGHCF 中序：DBGEHAFC 后序：DGHEBFCA
5. 一组密文原码由字符{A, B, C, D, E, F, G}组成，其出现的频率分别是{9, 11, 5, 7, 8, 2, 3}，设计相应的哈夫曼树并对7个字符编码。（8分） 哈夫曼树略。
编码方案：A：00 B：10 C：010 D：110 E：111 F：0110 G：0111（此题答案不唯一）
四、综合题
2. 在二叉树的链式存储结构中，结点类型定义如下： typedef struct node { ElemType data;
struct node *lchild,*rchild; } BTNode;
以下算法是计算二叉数深度的递归算法，试补充完整。 int BtreeDepth (BTreeNode *BT) //BT是根结点 { if (BT==NULL) return 0； else {
int dep1,dep2； //dep1、dep2分别为根结点左子树、右子树高度 dep1= ； dep2= ； if (dep1>dep2)
return ； else
return ；
}
数据结构考试内容
}
2. BtreeDepth（BT->lchild）
BtreeDepth（BT->rchild） dep1+1 dep2+1 2.编写算法求二叉树的深度（高度）。
2. int BTNodeDepth(BTNode *b) //求二叉树b的深度 {
int lchilddep,rchilddep; if (b==NULL)
return(0); //空树的高度为0 else {
lchilddep=BTNodeDepth(b->lchild); //求左子树的高度为lchilddep rchilddep=BTNodeDepth(b->rchild); //求右子树的高度为rchilddep return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); } }
1.二叉树中结点定义如下，试编写算法，求二叉树中结点的个数。
typedef struct node {
ElemType data; struct node *lchild; struct node *rchild;
//数据元素 //指向左孩子 //指向右孩子
} BTNode;
int Nodes(BTNode *b) //求二叉树b的结点个数
{
int num1,num2;
if (b==NULL)
return 0;
else if (b->lchild==NULL && b->rchild==NULL) return 1; else {
num1=Nodes(b->lchild); num2=Nodes(b->rchild); return (num1+num2+1); }
数据结构考试内容
}
2.下列递归算法实现了交换二叉树中每个结点的左孩子和右孩子，试补充完整。
void exchange(BTNode *b) //初始化时b为根结点 { BTNode *temp; //临时结点变量temp
if(b!=NULL) //if语句实现b的左右孩子交换 { temp=b->lchild;
b->lchild=_________________________; b->rchild=_________________________;
exchange(________________); //递归实现左子树中结点的左右孩子交换 exchange(________________); //递归实现右子树中结点的左右孩子交换 } }
2. b->rchild temp b->lchild b->rchild
1. 二叉树中结点定义如下，编写递归算法实现二叉树的先序、中序、后序遍历。
typedef struct node {
ElemType data; struct node *lchild; struct node *rchild;
//数据元素 //指向左孩子 //指向右孩子
} BTNode;
void PreOrder(BTNode *b) { }
void InOrder(BTNode *b)
//中序遍历的递归算法
if (b!=NULL) { }
printf("%c ",b->data); //访问根结点 PreOrder(b->lchild); PreOrder(b->rchild);
//递归访问左子树 //递归访问右子树 //先序遍历的递归算法
数据结构 树 考试习题.doc
将本文的Word文档下载到电脑
上一篇：进口奶粉及奶源分析ppt
下一篇：专四阅读理解题型分解要点
