第六章
一．判断题
（√）（1）树结构中每个结点最多只有一个直接前驱。 （×）（2）完全二叉树一定是满二查树。
（√）（3）由树转换成二叉树，其根结点的右子树一定为空。
（√）（4）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。
（×）（5）用一维数组来存储二叉树时，总是以前序遍历存储结点。
（×）（6）已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结点是哪一个。
（√）（7）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。 （√）（8）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（9）不使用递归，也可以实现二叉树的前序、中序和后序遍历。 （√）（10）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
二．填空题
1．在树中，一个结点所拥有的子树数称为该结点的 度 。
2．一棵含有n个结点的完全二叉树，它的高度是 | log2n |+1 。 （下取整） 3．度为零的结点为 叶子结点（或叶结点） 。
4．一棵深度为h的完全二叉树上的结点总数最少为 2 h-1 个。 5．树内各结点度的最大值称为 树的度 。
6．一棵深度为h的完全二叉树上的结点总数最多为 2 h-1 个。 7．树中结点的最大层次称为树的 深度（或高度） 。 8．三个结点可以组成 2 种不同形态的树。 9．由树转换成二叉树时，其根结点没有 右子树 。
10．有20个结点的完全二叉树，编号为10的结点的左儿子结点的编号是 20 。 11．在树中，一个结点的直接子结点的个数称为该结点的 度 。 12．由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。 13．给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。
14．给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。
HE B F E HA C G F G B C A 15．将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，该结点右孩子的编号为： 2*i+1 。
三．选择题
1．树最适合用来表示（ D ）。
A．有序数据元素 B．无序数据元素
C．元素之间无联系的数据 D．元素之间有分支层次的关系 2．对于一棵满二叉树，m个树叶，n个结点，深度为h，则（ D ）。
A．n=h+m B．h+m=2n C．m：h-1 D．n=2h-1 3．结点前序为ABC的不同二叉树有（ C ）形态。 A．3 B．4 C．5 4．下列4棵树中，（ B ）不是完全二叉树。
A． B． C． D．
D E FD G D E F D E D B C B C B C B C A A A A
D．6
5．根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。 A．3
B．4
C．5
D．6 A BD E F C G 6．如右图所示的二叉树，先序遍历的序列是（ B ） A． A、B、C、D、E、F、G 、H、I B． A、B、D、H、I、E、C、F、G C． H、D、I、B、E、A、F、C、G D． H、I、D、E、B、F、G、C、A
7．下列存储形式中，哪一个不是树的存储形式（ D ）。 A．数组存储法 B．双亲表示法 C．孩子链表表示法 D．孩子兄弟表示法 8．具有35个结点的完全二叉树的深度为（ B ） A．5
K
H I
B．6
K
C．7
K-1
D．8
K-1
9．对于二叉树来说，第K层至多有（ C ）个结点。 A． 2
B．2-1 C．2
D．2-1
10．线索二叉树是一种（ A ）。
A．物理 B．逻辑 C．逻辑和存储 D．线性 11．一棵n个结点的二叉树，其空指针域的个数为（ B ）。
A．n B．n+1 C．n-1 D．不确定 12．如右图所示的二叉树，中序遍历的序列是（ C ） A BD E F C G A． A、B、C、D、E、F、G 、H、I
B． A、B、D、H、I、E、C、F、G
C． H、D、I、B、E、A、F、C、G
D． H、I、D、E、B、F、G、C、A
13．二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（ B ）。 A．正确 B．错误 A． 2
K
C．不确定 D．都有可能
K-1
14．深度为K的二叉树至多有（ B ）个结点。
B．2-1 C．2
K
D．2-1
K-1
15．A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ C ）。 A．A在B右方 B．A是B祖先 C．A在B左方 D．A是B子孙
第七章
一．判断题
（√）（1）图可以没有边，但不能没有顶点。
（×）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。 （×）（3）邻接表只能用于有向图的存储。
（√）（4）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。 （√）（5）一个图的邻接矩阵表示是唯一的。 （×）（6）有向图不能进行广度优先遍历。
（√）（7）一个图的最小生成树是该图所有生成树中权最小的生成树。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（×）（9）有向图的邻接矩阵一定是对称的。 （×）（10）一个图的深度优先遍历的序列是唯一的
二．填空题
1．图有： _邻接矩阵_ 和邻接表等存储结构。
2．n个顶点e条边的图若采用邻接矩阵存储，深度优先遍历算法的时间复杂度为： O（n） 。 3．图的遍历有：深度优先搜和 _广度优先搜 __等方法。
4．n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为： _ O（n2）__。 5．图有：邻接矩阵和 邻接表 等存储结构。 6．若图G中每条边都 _无 方向，则G为无向图。 7．在具有n个顶点的图的生成树中，含有 n-1 条边。 8．有向图的边也称为 _弧___ 。
9．图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。
10．有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。
2
11．图的深度优先遍历序列 ___不是_____唯一的。
12．设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。
13．从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为 图的遍历（或遍历） 。
14．遍历图的两种基本方法是： 深度优先遍历 和广度优先遍历。 15．有向图的邻接表表示适于求顶点的 出度 。
三．选择题
1． 在一个图中，所有顶点的度数之和等于图的边数的( C )倍。
A．1/2 B. 1 C. 2 D. 4 2．生成树的构造方法只有（ B ）。
A．深度优先 B．深度优先和广度优先 C．无前驱的顶点优先 D．无后继的顶点优先
3． 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 A．1/2 B. 1 C. 2 D. 4 4．下面的各种图中，（ C ）的邻接矩阵一定是对称的。 A．AOE图 A．顶点 A．一维 A．n/2
B．AOV图 B．边
C．无向图 D．有向图 C．序号
D．下标
5．无向图顶点v的度是关联于该顶点（ B ）的数目。 6．有n个顶点的有向图的邻接矩阵是用（ B ）数组存储。
B．n行n列 C．任意行n列 D．n行任意列 B．n
C．2n
D．n*n
7．有n个条边的无向图的邻接矩阵（表）存储法中，链表中结点的个数是（ C ）个。 8．在图的表示法中，表示形式唯一的是（ A ）。
A．邻接矩阵表示法 B．邻接表表示法 C．逆邻接表表示法 D．邻接表和逆邻接表表示法 9．最小生成树的构造可使用（ A ）算法。 A．prim算法
10．在下列图中，度为3的结点是（ B ）。
1 B．卡尔算法 C．哈夫曼算法 D．迪杰斯特拉算法
2 3
4 5 A．V1 B. V2 C. V3 D. V4 11．具有4个顶点的无向完全图有（ A ）条边。
A．6 B．12 C． 16 D．20 12 按广度优先进行遍历，则可能得到的一种顶点序列为（ B ）。
A． a，b，e，c，d，f B． a，b，e，c，f，d C. a，e，b，c，f，d D. a，e，d，f，c，b
13．连通分量是（ C ）的极大连通子图。 A．树 A．树
B．图 B．图
14．强连通分量是（ D ）的极大强连通子图。
C．无向图
D．有向图
15．任何一个连通图的生成树 ( C )。
A．可能不存在 B. 只有一棵 C. 有一棵或多棵 D. 一定有多棵
d f a b e c C．无向图 D．有向图
第八章
一．判断题
（√）（1）二分查找法要求待查表的关键字值必须有序。 （√）（2）哈希法是一种将关键字转换为存储地址的存储方法。 （×）（3）在二叉排序树中，根结点的值都小于孩子结点的值。 （×）（4）对有序表而言采用二分查找总比采用顺序查找法速度快。 （√）（5）二叉排序树是一种特殊的线性表。
（√）（6）散列存储法的基本思想是由关键字的值决定数据的存储地址。
（√）（7）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。 （√）（8）一般说来用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。 （×）（9）选择好的哈希函数就可以避免冲突的发生。
（×）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。
二．填空题
1．顺序查找法，表中元素可以 任意 存放。
2． 散列表 查找法的平均查找长度与元素个数n无关。 3．快速排序是对 冒泡 排序的一种改进。
4．在哈希函数H(key)=key % P中，P一般应取 质数 。
5．二分查找的存储结构仅适用于 顺序存储 结构，而且关键字有序的。