内容发布更新时间 : 2024/5/29 17:20:20星期一 下面是文章的全部内容请认真阅读。
一、判断题
（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个
非空指针域。
（×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5.二叉树中所有结点个数是2-1，其中k是树的深度。（应2-1） （×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2）
i-1
k-1i
（√）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个
为空指针。
（√）9.具有12个结点的完全二叉树有5个度为2的结点。 (? ) 10、哈夫曼树中没有度为1的结点，所以必为满二叉树。 (? )11、在哈夫曼树中，权值最小的结点离根结点最近。 (? )12、线索二叉树是一种逻辑结构。
（√ ）13、深度为K的完全二叉树至少有2个结点。
K-1
(√ )14、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )15、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )16、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 （√）17、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。 （√）18、二叉树的遍历操作实际上是将非线性结构线性化的过程 （√）19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。
（╳）20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。 二、填空
1． 由３个结点所构成的二叉树有 5 种形态。
2. 线索二叉树的左线索指向其_前驱_____，右线索指向其__后继____。 3． 一棵具有257个结点的完全二叉树，它的深度为 9 。
4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_____。
5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
6. 一棵含有n个结点的k叉树，可能达到的最大深度为 n ，最小深度为 2 。 7. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。
8. 在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null 。 三、选择题
1．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C）
A）3 B）2 C）4 D）5 2．二叉树是非线性数据结构，所以（ C ）。
Ａ、它不能用顺序存储结构存储; Ｂ、它不能用链式存储结构存储;
Ｃ、顺序存储结构和链式存储结构都能存储; Ｄ、顺序存储结构和链式存储结构都不能使用
3.具有n(n>0)个结点的完全二叉树的深度为（ C ）。
(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n)+1? 4．把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。 （Ａ）唯一的 （Ｂ）有多种
（Ｃ）有多种，但根结点都没有左孩子 （Ｄ）有多种，但根结点都没有右孩子 5.线索二叉树是一种（ C ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性
6、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（ A） A、98
B、99
C、50
D、48
7、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D） A）M1 B）M1+M2 C）M3 D）M2+M3
8、将一棵有100个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C） A、48
B、49
C、50
D、51
9、引入二叉线索树的目的是（ A ）
A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除 C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一
10．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）
A．9 B．11 C．15 D．不确定 11． 一棵树深度为K的完全二叉树至少有（ C ）个结点