查找树中，由根结点到所有其他结点的路径长度的总和达到最小的树一定是（）A、B-树B、平衡树C、非平衡树D、穿线树

第1题：

第2题：

第3题：

第4题：

树的带权路径长度最小的二叉树中必定没有度为1的结点。

正确答案:正确

第5题：

二叉树的前序、中序和后序遍历法最适合采用__（1）__来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为__（2）__，而使上述路径长度总和达到最小的树称为__（3）__。它一定是__（4）__。在关于树的几个叙述中，只有__（5）__是正确的。空白（2）处应选择（）

• A、路径和
• B、内部路径长度
• C、总深度
• D、深度和

正确答案:B

第6题：

查找树中，由根结点到所有其他结点的路径长度的总和达到最小的树叫（）

• A、B-树
• B、B+树
• C、丰满树
• D、穿线树

正确答案:C

第7题：

请解释结点的度、树的度、结点的层、树的深度、分支、路径、路径长度、树的路径长度、叶子结点、分支结点、内部结点、孩子、双亲、兄弟、堂兄弟、祖先、子孙、有序树、无序树和森林等基本术语的含义。

正确答案:结点的度和树的度：一个结点的后继的数目称为该结点的度，树中各结点度的最大值称为树的度。
结点的层和树的深度：树的根结点所在的层为第1层，其余结点的层等于其前驱结点的层加1，树中各结点的层的最大值称为树的深度。
分支、路径、路径长度和树的路径长度：从一个结点到其后继结点之间的连线称为一个分支，从一个结点X到另一个结点Y所经历的所有分支构成结点X到结点Y的路径，一条路径上的分支数目称为路径长度，从树的根结点到其他各个结点的路径长度之和称为树的路径长度。
叶子结点、分支结点和内部结点：树中度为0的结点称为叶子结点（或终端结点），度不为0的结点称为分支结点（或非终端结点），除根结点以外的分支结点也称为内部结点。
孩子和双亲：在树中，一个结点的后继结点称为该结点的孩子，相应地，一个结点的前驱结点称为该结点的双亲，即一个结点是其孩子结点的双亲、其双亲结点的孩子。
兄弟和堂兄弟：同一双亲的孩子结点之间互称为兄弟，不同双亲但在同一层的结点之间互称为堂兄弟。
祖先和子孙：从树的根结点到某一个结点X的路径上经历的所有结点（包括根结点但不包括结点X）称为结点X的祖先，以某一结点X为根的子树上的所有非根结点（即除结点X外）称为结点X的子孙。
有序树和无序树：对于树中的任一结点，如果其各棵子树的相对次序被用来表示数据之间的关系，即交换子树位置会改变树所表示的内容，则称该树为有序树；否则称为无序树。
森林：m（m≥0）棵互不相交的树的集合就构成了森林。

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是（）。

• A、二叉排序树
• B、赫夫曼树
• C、堆
• D、平衡二叉树

正确答案:C

第16题：

二叉树的前序、中序和后序遍历法最适合采用__（1）__来实现。查找树中，由根结点到所有其他结点的路径长度的总和称为__（2）__，而使上述路径长度总和达到最小的树称为__（3）__。它一定是__（4）__。在关于树的几个叙述中，只有__（5）__是正确的。空白（3）处应选择（）

• A、B-树
• B、B+树
• C、丰满树
• D、穿线树

正确答案:B

第17题：

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h（n），则回溯法所需的计算空间通常为（）

正确答案:O(h(n))

第18题：

树的带权路径长度为树中所有叶子结点的（）。

正确答案:带权路径长度之和

第19题：

哈夫曼树是带权路径长度（）的树，通常权值较大的结点离根结点（）。

正确答案:最小；近

第20题：

第21题：

第22题：

第23题：