if(A[i]]＝＝’@’) return 0; return 1 }
(例10-36) 假设二叉树以链式结构存储，编写一算法判断此二叉树是否为二叉排序树。 解析：由于二叉排序树的中序遍历序列为一递增序列，所以利用中序遍历算法即可判 断该二叉树是否为二叉排序树。具体算法如下： int judgebst ( bitree * t，datatype pre)
//pre为当前遍历结点中序前驱，初值为最小值 {
int m1，m2； if(t==NULL)
return 1； //空树，返回1 ml＝judgebst (t一>lehild，pre)； //判断左子树 if(ml==0)
return 0； //左子树不是BST，整棵树就不是BST if(t—> data<＝pre) //非递增，不是BST return 0；
m2＝judgebst(t一>lchild，pre)；
return m2； //右子树不是BST，整棵树就不是BST }
29
图
一、单项选择题
(例11-1) 若无向图的顶点个数为n，则该图最多有( )条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0
解析：任意一个顶点与其他n-1个顶点间最多有n-l条边，又因为无向图任意两个顶点间至多只能有一条边，所以边数最多为n(n-1)/2。本题答案为：B。
[例11-2] 在一个图中，所有顶点的度数之和等于所有边数的( )倍。 A．1/2 B．2 C．1 D．4
解析：因为每条边与两个顶点相关联，即给这两个顶点分别产生1个度，所以所有顶点的度数之和是所有边数的两倍。本题答案为：B。
(例11-3) 在一个有向图中，所有顶点的人度之和等于所有顶点的出度之和的 ( )倍。 A．1/2 B．2 C．1 D．4
解析：在有向图中，任意一条弧对起点来说产生一个出度，对终点来说产生一个入度， 也就是说出度和入度是一一对应的。本题答案为：C。
(例11-4) 一个有n个顶点的图，最少有( )个连通分量，最多有( )个连通分量。 A．0 B．1 C．n-1 D．n
解析：n个顶点的图，如果是连通图，则只有1个连通分量；如果图中不包含边，则每 个顶点自成连通分量，有n个连通分量。本题答案为：B；D。
(例11-5) 具有7个顶点的无向图至少应该有( )条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 解析：n个顶点的连通图中至少有n-1条边。本题答案为：B。
(例11-6) 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的元素个数为( )。 A．n B．(n-1)2 C．n-1 D．n2 解析：由图的邻接矩阵表示可知，本题答案为：D。
(例11-7) 当一个有n个顶点的有向图用邻接矩阵A表示时，顶点vi的度是 ( )。 A．
?A[i][j] B．?A[i][j] C．?A[j][i] D．?A[i][j]??A[j][i]
i?0j?0n?1n?1n?1i?0n?1i?0n?1j?0解析：在有向图的邻接矩阵中，顶点对应的行上非零元素个数之和为该顶点的出度，顶点对应的列上非零元素个数之和为该顶点的入度，而顶点的度为出度与人度之和。本题答案为：D。
[例11-8] 某无向图如图11.11所示，在下面的5个序列中，符合该图深度优先搜索遍历的序列有( )。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个
f d e b”和“a e d f □c b“中加框顶点为出错的遍 解析：由图的深度优先搜索遍历可知，序列“a c □历顶点，其他序列都是正确序列。本题答案为：C。
30
(例11-9) 某无向图如图11.1l所示，在下面的5个序列中，符合该图广度优先搜索遍历的序列有( )。 a e b c d f a c f d e b a e d f b c a e b c f d a b e f c d A．5个 B．4个 C．3个 D．2个
f d e b”d f b c”f c d” 解析：由图的广度优先搜索遍历可知，序列“a c □、“a e □，和“a b e □，中加框顶点为出错的遍历顶点，其他序列都是正确序列。本题答案为：D。
(例11-10) 已知一有向图的邻接链表存储结构如图11．12所示，以顶点0为出发点的深度优先搜索遍历序列为( )。
A．0 1 2 4 3 B．0 1 2 3 4 C．0 2 3 4 1 D．0 3 2 4 1 解析：由深度优先搜索遍历算法可知，本题答案为：C。
(例11—11) 已知一有向图的邻接链表存储结构如图11.12所示，以顶点0为出发点的广度优先搜索遍历序列为( )。
A．0 1 2 3 4 B．0 2 1 3 4 C．0 2 3 4 1 D．0 3 2 4 1 解析：由广度优先搜索遍历算法可知，本题答案为：B。 (例11-12) 任何一个无向连通图的最小生成树( )。 A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在
解析：任何一个无向连通图有一棵或多棵最小生成树。本题答案为：A。 [例11-13] 关键路径是事件顶点网络中( )。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路
解析：在AOE网中，从源点到汇点的最长路径称为关键路径。本题答案为：A。
二、判断题
[例ll-14] 在有n个结点的无向图中，若边数大于n-1，则该图必是连通图。 解析：错误。n个顶点的无向图至多有n(n-1)/2条边，假设一无向图顶点数为7， 图中任意6个顶点间边数至多为15条，显然15>6。若此6个顶点与另一顶点间没有边相 连，即此图不连通。
(例11-15) 有向图中顶点i的度等于其邻接矩阵中第i行中1的个数。
解析：错误。有向图的邻接矩阵中第i行中1的个数为图中顶点i的出度，第i列中1的个数为图中顶点i的入度，两者之和为顶点i的度。
[例11-16] 强连通分量是无向图的极大强连通子图。 解析：错误。强连通分量是有向图的极大强连通子图。
(例11-17) 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
解析：错误。根据图的邻接矩阵存储方式可知，无向图的邻接矩阵一定是对称矩阵，而有向图的邻接矩阵一般是非对称矩阵，但若有向图中的弧都是成对的(即有
31
称矩阵。
[例ll-18] 不同的求最小生成树的方法最后得到的生成树是相同的。 解析：错误。连通图的最小生成树有可能是多棵。
(例11-19) 拓扑排序算法把一个无向图中的顶点排成一个有序序列。
解析：错误。拓扑排序是将AOV网中的所有顶点排成一个线性序列，它的排序对象是有向图。 (例11-20) 若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。 解析：正确。
[例11-21] 在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。 解析：错误。在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间有可能 缩短，只有缩短了包含在所有路径上的那些关键活动时，才一定能缩短整个工程的时间。 三、填空题
[例11-22] 判断一个无向图是一棵树的条件是 。
解析：树是连通的，且树中必无回路。本题答案为：图是连通的且不存在回路。 [例11-23] 一个连通图的 是一个极小连通子图。 解析：由生成树的定义可知，本题答案为：生成树。
[例11-24] 图G是一个非连通无向图，共有28条边，则该图至少有 个顶点。
解析：图G是非连通无向图，至少有两个连通分量，其中一个连通分量最少的顶点数是由28条边组成的无向图，设其顶点数为n，边数为e，则有e≤n(n-1)/2，e＝28，可得n≥8；另一个连通分量只有一个顶点，所以该图至少有9个顶点。本题答案为：9。
(例11—25) 已知一有向图的邻接链表存储结构如图11.13所示，以顶点0为出发点的深度优先搜索遍历序列为 ；广度优先搜索遍历序列为 。
解析：由图的遍历算法可知，本题答案为：03241；03214。
[例11-26] 已知一个有向图用邻接矩阵表示，删除所有从第i个顶点出发的边的方法是 。 解析：邻接矩阵第i行的非零元素表示从第i个顶点出发的边。本题答案为：将邻接矩阵第i行元素全部置0。
[例11—27] 对有n个顶点的连通图来说，它的生成树一定有 条边。 解析：由生成树的定义可知，本题答案为：n—l。 [例11—28] 有向图G可拓扑排序的判别条件是 。 解析：根据拓扑排序算法可知，本题答案为：图中不存在环。 (例11—29) 一个无向网络如图11.14所示，用Prim算法从顶点0开始求其最小生成树，按次序产生的边为 ，共 条边；用Kruskal算法产生的边次序为 ，共 条边。(注：边用( i，j形式表示。)
解析：从顶点。开始求最小生成树，按次序产生的边为：(0，3)，(3，5)，(5，2)，(3，1)，(1，4)共5条边。采用Kruskal算法产生的边次序为：(0，3)，(2，5)，(3，5)，(1，3)，(1，4)共5条边。本题答案为：(0，3)，(3，5)，(5，2)，(3，1 )，(1，4)；5；(0，3)，(2，5)，(3，5)，(1，3)，(1，
32
相关推荐：
loading