图与树的基本概念（对应C10）

姓名

树的性质、二叉树的遍历

1. 一棵深度为6的完全二叉树，它最少包含（　）个节点。

2. 已知一棵二叉树的前序遍历序列为ABDGECF，中序遍历序列为GDBEACF，则它的后序遍历序列为（　）。

3. 在一棵二叉树中，若度为2的节点（即有两个子节点的节点）有15个，则度为0的节点（即叶子节点）有（　）个。

4. 现有一个包含5个字符的字符集，其出现频率分别为{4,5,6,7,8}。若使用哈夫曼算法为其构造编码，则这棵哈夫曼树的带权路径长度（WPL）为（　）。

5. 已知一棵二叉树共有100个节点，则这棵二叉树的最少深度（层数）为（　）。

6. 一棵完全二叉树共有1000个节点，则这棵树中度为1的节点个数为（　）。

7. 对于任意一棵包含n个节点的树（非二叉树），其边数必定为（　）。

8. 在哈夫曼编码中，假设字符集只有{A,B,C,D,E}五个字符，其出现的频率分别为{1,2,3,4,5}。则字符A和B的编码长度可能为（　）。

图的基本概念

1. 在一个无向图中，共有10条边，且所有顶点的度数之和为（　）。

2. 一个包含8个顶点的无向完全图，其包含的边数为（　）。

3. 若一个无向图包含n个顶点（n≥2），且是一个连通图，那么它的边数最少为（　）。

4. 对于任意一个有向图，关于顶点的度数，下列说法正确的是（　）。

5. 一个包含5个顶点的无向连通图，若要求每个顶点的度数都至少为3，则该图至少包含（　）条边。