《数据结构与算法》(清华)典型例题

学习必备 欢迎下载

else

Q一>[++rear]＝s—>rchild； //s结点的右孩子的地址人队 } }

return 1； }

若二叉树采用顺序存储结构，则只需判断从第一个结点位置到最后一个结点位置之间 没有空结点即可。假设二叉树存储在数组bt[n+1]中，具体算法如下： int fu11bitree2 (char bt[]，int n) {

int i；

for(i＝1；i<＝n；i++) 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 }

学习必备 欢迎下载

11.3 典型例题

一、单项选择题

(例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。

(例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” 解析：由图的广度优先搜索遍历可知，序列“a c □、“a e □，和“a b e

f c d”□，中加框顶点为出错的遍历顶点，其他序列都是正确序列。本题答案为：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) 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 解析：错误。根据图的邻接矩阵存储方式可知，无向图的邻接矩阵一定是对称矩阵，而有向图的邻接矩阵一般是非对称矩阵，但若有向图中的弧都是成对的(即有，则必有)，则其邻接矩阵也是对称矩阵。

[例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为出发点的深度优先搜索遍历序列为 ；广度优先搜索遍历序列为 。