内容发布更新时间 : 2024/12/22 21:39:54星期一 下面是文章的全部内容请认真阅读。

树与二叉树复习

一、填空

1、由二叉树的（ 中 ）序和（ 前、后 ）序遍历序列可以唯一确定一棵二叉树。 2、任意一棵二叉树，若度为0的结点个数为n0，度为2的结点个数为n2，则n0等于（n0=n2+1 ）。

3、一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点。

4、一棵有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点个数n1=（n-2n0+1 ）。

5、在一棵高度为5的完全二叉树中，最少含有（ 16 ）个结点。

6、 2．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，（ C ）次比较后查找成功。 A． 11

B 5

C 4

D 8

7、在有n个叶结点的哈夫曼树中，总结点数（ 2n-1 ）。

8、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用 （递推 ）算法，因为 （递推算法效率高 ）。

9、设一棵完全二叉树有700个结点，则共有（ 350 ）叶子结点。

10、设一棵完全二叉树具有1000个结点，该树有（500）个叶子结点，有（499 ）个度为2的结点，有（ 1 ）个结点只有非空左子树。 二、判断

1、( × )在哈夫曼树中，权值最小的结点离根结点最近。

2、( √ ) 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。 3、( √ )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 4、( × ) 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上。

5、( √ )若以二叉链表作为树和二叉树的存储结构，则给定任一棵树都可以找到唯一的一棵二叉树与之对应。

6、( √ )若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小

值一定在叶结点上。 三、选择

1、树最适合用来表示( C )

A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 2、在有n（n>0）个结点的二叉链表中，空链域的个数为( B )。 A、n B、n+1 C、n-1 D、不确定 3、 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为( A )。

A、CBEFDA B、FEDCBA C、CBEDFA D、不定 4、对于有n 个结点的完全二叉树, 其高度为( C )

A、nlog2n B、log2n C、?log2n?+1 D、不确定 5、在有n个结点的二叉链表中，值为非空的链域的个数为（ A ） A、n-1 B、2n-1 C、n+1 D、2n+1

6、将一棵有100个结点的完全二叉树从根开始编号，每层上从左到右依次对结点进行编号，跟结点的编号为1，则编号为49的结点的左孩子编号为（ A ） / A、98 B、99 C、50 D、48、

+ + 7、设有一表示算术表达式的二叉树（见下图），

* C * - B D E F G 它所表示的算术表达式是（ C ） A A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G

8、已知一算术表达式的中缀形式为A＋B *C–D/E，后缀形式为ABC *+DE/–，其前缀形式为（ D ）。

A、–A+B*C/DE B、–A+B*CD/E C、 –+*ABC/DE D、–+A*BC/DE 9、堆的形状是一棵（ Ｃ ）

Ａ. 二叉排序树 Ｂ.满二叉树 Ｃ.完全二叉树 Ｄ. 平衡二叉树

10、若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（Ｂ）。

Ａ. 79, 46, 56, 38, 40, 84 Ｂ. 84, 79, 56, 38, 40, 46 Ｃ. 84, 79, 56, 46, 40, 38 Ｄ. 84, 56, 79, 40, 46, 38 11．查找效率最高的二叉排序树是（ C ）。 A．所有结点的左子树都为空的二叉排序树。 B．所有结点的右子树都为空的二叉排序树。 C．平衡二叉树。

D．没有左子树的二叉排序树。

12．判断序列是否为堆（小根堆或大根堆），如果不是，将其调整为堆。 17，18，60，40，7，32，73，65

96，83，72，45，28，54，60，23，38，15 25，48，16，35，79，82，23，40，36，72 12，24，18，65，33，56，33，92，86，70

13、下面编码中哪一个不是前缀码（ B ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 11、在解决递归问题时，若不用递归函数就应借助于数据结构（ B ）。

A、线性表 B、栈 C、队列 D、双向队列 14、一棵完全二叉树的第6层有8个叶结点，该二叉树的结点个数最多是（ 111 ）。 15、在分量1~11的数组中按从小到大顺序存放11个元素，如果进行二分查找，查找次数最少的元素位于什么位置？ A.1

B.5

C.6

D.11

16、如果一个完全二叉树最底下一层为第六层（根为第一层）且该层共有8个叶结点，那么该完全二叉树共有多少个结点？ A.31

B.39

C.63

D.71

17、若有一二叉树的总结点数为98，只有一个儿子的结点数为48，则该树的叶结点数是多少？ A.25

B.50

C.不确定

D.这样的树不存在

18、假定只有四个结点A、B、C、D的二叉树，其前序遍历序列为ABCD，则下面哪个序列是不可能的中序遍历序列？ A.ABCD B.ACDB C.DCBA D.DABC

19、对于二叉树，如果其中序遍历结果与前序遍历结果一样，那么可以断定该二叉