发布时间 : 星期六 文章数据结构习题更新完毕开始阅读
A.1234567 B.1245367 C.4251637 D.452673l
13.具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0） A．8 B．7 C．6 D．5
14.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序周游的结果为（ ） A．DBFEAC B．DFEBCA C．BDFECA D．BDEFAC 15.Huffman树的WPL 是指（ ）。
A．除根以外所有结点的权值之和 B．所有结点权值之和 C．各叶子结点的带权路径长度之和 D．根结点的值
16．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )
A．4 B．5 C．6 D．7 17．将一棵有 100个结点的完全二叉树，从根这一层开始，每一层从左到右依次对结点编号，根据点的 编号为1，则编号为49的结点的双亲的编号为 。 A.24 B .25 C .23 D无法确定
18．深度为６（根据的层次为１）的二叉树至多有 结点。 Ａ .６４ Ｂ.６３ Ｄ.３１ Ｄ.３２ 19．设二叉树有 n个结点，则其深度为____ 。 Ａ .n-1 B. n C .㏒2n D. 无法确定
20. 设森林Ｔ中有三棵树，第一、第二、 三棵数的活结点个数分别为n1 n2 n3 ,那么将森林转换成二叉树后，其根结点的右子树上有_______ 个结点。 Ａ .n1-1 B.n2+n 3 C .n1 +n2+n3 D.n1
21.设森林Ｔ中有三棵树，第一,二,三棵数的结点个数分别为 n1,n2,n3，那么将森林转换成二叉树后，其根结点的左子树上有_____个结点。
Ａ .n1-1 Ｂ.n2+n3 Ｃ.n1+n2+n3 Ｄ.n1
22. 设深度为Ｋ的二叉树上只有度为０或度为２的结点，则这类二叉树上所含结点总数至少_______。 Ａ .Ｋ＋１ Ｂ.２Ｋ Ｃ２Ｋ—１ Ｄ２Ｋ＋１ 23.树转换成二叉树后，以下结论正确的是_______ 。
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 C. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
29
D. 以上都不对
24.某二叉树的前序遍历结点访问顺序为ABDGCDFH,中序遍历结点访问顺序为DGBAECHE，则其后续遍历结点访问顺序为__________ 。
A. BDGCEFHA B. GDBECFHA C. BDGAECHF D. GDBDHFCA 25. 在一棵非空二叉树的中序遍历序列中，根结点的右边_______ 。 A. 只有右子树上的所有结点 B. 只有右子树砂锅内的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点
26. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_______ 。 A. 不发生变化 B. 发上变化 C. 不能确定 D. 以上都不对
二、填空题
1.在一棵树中， 结点没有前驱结点，______结点没有后继结点。
2.一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点f的层数为______。假定根结点的层数为0。结点k的所有祖先的结点数为 个。 3.在二叉树的第i层上至多有 结点。
4．具有n个结点的完全二叉树的深度为 。深度为k的二叉树的总结点数至少为 ，至多为 。
5．有n个结点的二叉链表中的空链域有_____ 个。
6.二叉树的第i层上至多有 个结点；具有n个结点的完全二叉树的深度为 。
7. 一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有________子女。 8．已知一颗完全二叉树中共有768结点，则该树中共有_____个叶子结点。
9. 假定一棵树的嵌套括号表示法为 A （ B （ E ）， C （ F （ H ， I ， J ）， G ）， D ），则该树的度为______，树的深度为_____，终端点的个数为____，但分支结点的个数为_____，双分支结点为_____，三分支结点的个数为______， C 结点的双亲结点为_________，其孩子结点为__________和为_________结点。
10．设 F 是一个森林， B 是由 F 转换得到的二叉树， F 中有 n 个非终端结点，则 B 中右指针字段为空的结点有____________。
11.对于一个具有 n 个结点的二叉树，当它为一棵二叉树时，具有最小高度，即为________ ，但它一棵单支时具有最大高度，即为___________ 。
30
12.对于一个具有 n 个结点的二叉树，当它储存在二叉树表中时，其指针字段的总数为______ 个，其中________个用于链接孩子点，_____________个空闲，
13．一棵深度为 K 的满二叉树结点总数为___________ ，一棵深度为 K 的完全二叉树的结点总数的最小值为________，最大值为____________。
14.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序是 T2 中结点的 _______序。 15.具有 n 个结点的完全二叉树，若按层次从上到下 、从左到右对其编号（根结点为 1号），则编号最大的分支结点序号为_______ ，编号最小的分支结点序号为_______ ，编号最大的叶子结点序号为________ ，编号最小的叶子结点序号为___________ 。
16.有 m个叶子结点的哈夫曼树，其结点总数为________________ 。 17. 由三个结点构成的二叉树，共有_____________种不同的结构。
三、判断题
1.具有n个结点的完全二叉树的高度为?log2n??1。 2.有n个结点的不同的二叉树有n！棵。
3.在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。 4.完全二叉树的某结点若无左孩子，则它必是叶子结点。
5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
6.由树转化成二叉树，其根的右子女指针总是空的。
7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。 8.在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。 9．二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。
四、应用题
1.假设一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），回答下列问题：
（1）该树的度（2）树的深度（3）终端结点的个数（4）单分支结点的个数（5）双分支结点的个数（6）三分支结点的个数（7）C结点的双亲（8）C结点的孩子结点
2. 已知一棵树边的集合为｛< 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 >｝，画出这棵树，并回答下列问题： ? 哪个结点是根结点？ ? 哪些结点是叶子结点？
31
? 哪个结点是结点 G 的双亲结点？ ? 哪些结点是结点 G 的祖先结点？ ? 哪些结点是结点 G 的孩子结点？ ? 哪些结点是结点 E 的子孙结点？
? 哪些结点是结点 E 的兄弟结点？哪些是结点 F 的兄弟结点？ ? 结点 B 和 N 的层次分别是多少？ ? 树的深度是多少？
? 以结点 C 为根的子树的深度是多少？ 3. 某二叉树的结点数据采用顺序存储表示如下：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B (1)试画出此二叉树的图形表示。(2)写出结点D的双亲结点及左、右子女。 (3)将此二叉树看作森林的二叉树表示，试将它还原为森林。
4.假设一棵二叉树的中序序列DCBGEAHFIJK和后序序列为DCEGBFHKJIA请画出该二叉树，并给出先序序列。 5.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。 ①先序遍历序列： EBADCFHGIKJ 中序遍历系列： ABCDEFGHIJK ②中序遍历序列： ACBGEDF 后序遍历序列： ABCDEFG
6.对上题①所得的二叉树，分别画出它的顺序存储结构和二叉链表。
7．已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。
8．如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。
9．已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数。
10．如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点数目最多的那棵完全二叉树的叶子结点数目。
11．在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 12．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 13．分别求出下图中二叉树的三种遍历序列。
32