第六章

一.选择题

1.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为 。

A. 15 B. 16 C. 17 D. 47 2.假定一棵二叉树的结点数为18个，则它的最小高度 。

A. 4 B. 5 C. 6 D. 18 3.在一棵二叉树中第五层上的结点数最多为 。

A. 8 B. 15 C. 16 D. 32 4.在一棵具有五层的满二叉树中，结点总数为 。

A. 31 B. 32 C. 33 D. 16

5.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 。

A. 1 B. 2 C. 3 D. 4

6.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 。

A. 23 B. 37 C. 44 D. 46

7.在树中除根结点外，其余结点分成m (m≥0)个 的集合T1,T2,T3...Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。 A. 互不相交 B. 可以相交 C. 叶结点可以相交 D. 树枝结点可以相交 8.下面答案 是查找二叉树（又称二叉排序树）。

A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于１ B. 二叉树中的每个结点的两棵子树的高度差等于１ C. 二叉树中的每个结点的两棵子树是有序的

D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，

且小于其右子树（如果存在）所有结点的关键字值。 9.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是 。 A. 3 B. 4 C. 5 D. 1 10.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是 。

A. (n-1) % k= =0 B. (n-1) % k!=0 C. n % k= =0 D. n % k!=0 11.在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点 ，否则没有左兄弟。

A. 2i-1 B. i+1 C. 2i+1 D. i-1

12.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为

1,2,...,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 编号。

A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列

9

13.最小代价生成树 。

A. 是唯一的 B.不是唯一的 C.唯一性不确定 D.唯一性与原因的边的权数有关

二、填空

1.在树型结构中，树根结点没有 结点，其余每个结点有且仅有 ；树叶

结点没有 ，其余每个结点的 结点数不受限制。 2.对于一棵具有n个结点的树，则该树中所有结点的度之和为 。

3.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：

_______ 。 4.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 ， 若

它存在左孩子，则左孩子结点的下标为 ，若它存在右孩子，则右孩子结点的下标为 。

5.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F))，则该树的深度为 ， 度

为0的结点数为 ，度为1的结点数为 ，度为2的结点数为 ；C结点是A 结点的 ______，E结点是C结点的 _____。

6.在一棵二叉排序树中，按 遍历得到的结点序列是一个有序序列。

7.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度 ┏━━┳━━┳━━━┓

8.假定在二叉树的链接存储中，每个结点的结构为 ┃left┃data┃right ┃，其中 ┗━━┻━━┻━━━┛

data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序 遍历算法 中画有横线的地方填写合适的语句。

void inorder(bt); { if bt!=nil {

(1) ； (2) ； (3) ；}

} 三、判断题

1.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（ ）。

2.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树

的前序遍历序列中的最后一个结点（ ）。 3.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（ ）。 4.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（ ）

5.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（ ）。

6.中序遍历二叉排序树的结点就可以得到排好序的结点序列（ ）。

7.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可（ ）。

四、综合题

1.分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。

10

2. 对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。 3. 试证明已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。

第七章

一、 选择题

1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A. 1/2 B. 1 C. 2 D. 4 2.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 。

A. n B. n+1 C. n-1 D. n+e

3.具有n个顶点的无向完全图，边的总数为 条。

A. n-1 B. n C. n+1 D. n*(n-1)/2 4.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e>=n,故可推得深度优先搜索的时间复杂度为 。

A. O(e) B. O(n) C. O(ne) D. O(n+e) 5.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于 。 A. i+j B. i-j C. 1 D. 0

6.图的深度优先或广度优先遍历的空间复杂性均为 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e)

二、 填空

1.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 ，对于有向图来说等于该顶点的 。

2.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 ， 采用邻接表表示的空间复杂性为 。 3.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 ，按广度优先搜索遍历得到的顶点序列为 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E

┗0 1 0 1 1 0┛F

4.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 。 10

① ② 15 5 2 8 ⑤ 12

11

③ 3 ④

三、 判断题

1.有回路的图不能进行拓扑排序（ ）。 2.有回路的图不能进行拓扑排序（ ）。 3.连通分量是无向图中的极小连通子图（ ） 四、综合题

1.证明n个顶点的无向完全图的边数的n(n－1)/2。

2.证明一个有n个顶点，e条边的无向图G，必有∑dj ＝2e其中dj 为顶点j的度。 3.证明若无向图G的顶点度数的最小值大于或等于2，则G有一条回路。 4. 设无向图G如下图：

B E

A D G

C F 试给出

(1)该图的邻接矩阵；

(2)该图的邻接表；

(3)从A出发的“深度优先”遍历序列； (4)从A出发的“广度优先”遍历序列。

12