第七章 图
一 单选题
1．在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（  ）。
A  s                B  s-1            C  s+1            D  n
    2．    在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（  ）。
        A  n                B  s-1            C  s+1            D  2s
    3． 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（  ）。
        A  s                B  e                C  n+e            D  2e
    4． 在一个具有n个顶点的无向完全图中，所含的边数为（  ）。
        A  n                B  n(n-1)                C  n(n-1)/2            D  n(n+1)/2
    5． 在一个具有n个顶点的有向完全图中，所含的边数为（  ）。
        A  n                B  n(n-1)                C  n(n-1)/2            D  n(n+1)/2
    7． 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（  ）次深度优先搜索遍历的算法。
        A  k                B  1                    C  k-1                D  k+1
    8． 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（  ）。
        A  n                B  n×e                    C  e                    D  2×e
    9． 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（  ）。
        A  n                B  n×e                    C  e                    D  2×e
    10．对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（  ）。
        A      k1                B  k2                    C  k1- k2                    D  k1+ k2
    11．在一个有向图的邻接表中，每个顶点单链表中结点的个数等于顶点的（  ）。
        A      出边数            B  入边数                C  度数                    D  度数减1
    12．若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（  ）。
        A      A，B，C，F，D，E                        B  A，C，F，D，E，B   
        C  A，B，D，C，F，E                        D  A，B，D，F，E，C
    13．若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（  ）。
        A      A，B，C，F，D，E                        B  A，B，D，E，F，    C
        C  A，B，D，C，E，F                        D  A，C，B，F，D，E
    14．若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（  ）。
        A      1，2，5，4，3                            B  1，2，3，4，5
        C  1，2，5，3，4                            D  1，4，3，2，5
    15．若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（  ）。
        A      1，2，3，4，5                            B  1，2，4，3，5
        C  1，2，4，5，3                            D  1，4，2，5，3
    16．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个（  ）。
        A      上三角矩阵                                B  稀疏矩阵
        C  对角矩阵                                D  对称矩阵
    17．一个有n个顶点和n条边的无向图一定是（  ）。
        A  连通的            B  不连通的                C  无环的                    D  有环的
    18．为了实现图的广度优先遍历，其广度优先搜索算法使用的一个辅助数据结构为（  ）。
        A  栈                B  队列                    C  二叉树                    D  树
    19．若要把n个顶点连接为一个连通图，则至少需要（  ）条边。
        A  n                B  n+1                    C  n-1                D  2n
    20．由一个具有n个顶点的连通图生成的最小生成树中，具有（  ）条边。
        A  n                B  n-1                    C  n+1                D  2n
    21．已知一个有向图的边集为{<a，b>，<a，c>，<a，d>，<b，d>，<b，e>，<d，e>}，
则由该图产生的一种可能的拓扑序列为（  ）。
        A      a，b，c，d，e                            B  a，c，d，e，b
        C  a，c，b，e，d                            D  a，c，d，b，e
    22．任何一个无向连通图的最小生成树（  ）。
        A  只有一棵            B  有一棵或多棵            C  定义有多棵        D  可能不存在
    23．对于图7-11中的无向图，若从顶点A出发按深度优先搜索遍历，则可能得到的一种顶点序列为（  ）。
        A      a，c，e，d，b                            B  a，c，d，b，e
        C  a，d，c，e，b                            D  a，b，c，e，d
    24．对于图7-11中的无向图，若从顶点A出发按广度优先搜索遍历，则可能得到的一种顶点序列为（  ）。
        A      a，c，e，d，b                            B  a，c，d，b，e
        C  a，d，c，e，b                            D  a，b，c，d，e
    25．设无向图的顶点个数为n，则该图最多有（  ）条边。
        A  n-1                B  n(n-1)/2                C      n(n+1)/2            D  0
    26．一个有n个结点的图，最少有（  ）个连通分量，最多有（  ）个连通分量。
        A  0                B  1                    C      n-1                D  n
    【北京邮电大学2000二、5（20/8分）】
    27．在一个无向图中，所有顶点的度数之和等于所有边数（  ）倍，在一个有向图中，所
有顶点的入度之和等于所有顶点出度之和的（  ）倍。【哈尔滨工业大学2001二、3（2分）】
        A  1/2                B  2                    C      1                D  4
    28．要连通具有n个顶点的有向图，至少需要（  ）条边。
        A  n-1                B  n                    C      n+1                D  2n
    29．用邻接表存储图所用的空间大小（  ）。【北京交通大学2004一、7（2分）】
        A      与图的顶点数和边数都有关                B  只与图的边数有关
        C  只与图的顶点数有关                        D  与边数的平方有关
    30．下列哪一种图的邻接矩阵是对称矩阵？（  ）【北京交通大学2001一、11（2分）】
        A  有向图            B  无向图                C      AOV网            D  AOE网
    31．无向图G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，
c），（b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（  ）。
    【南京理工大学2001一、14（1.5分）】
        A      a，b，e，c，d，f                            B  a，c，f，e，b，d
        C  a，e，b，c，f，d                            D  a，e，d，f，c，b
    32．设如图7-22所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（  ）
    【南京理工大学2000一、20（1.5分）】
    aebdfc        acfdeb        aedfcb        aefdcb        aefdbc
        A  5个                B  4个                    C      3个                D  2个
    33．在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（  ）。
        A  顶点v的度                                B  顶点v的出度           
C  顶点v的入度                                D  依附于顶点v的边数
    【北京理工大学2004一、7（1分）】
    34．关键路径是AOE网中（  ）。【中南大学2003一、10（1分）】
        A  从始点到终点的最短路径                    B  从始点到终点的最长路径
C  从始点到终点的边数最多的路径                D  从始点到终点的边数最少的路径
    35．下列关于AOE网的叙述中，不正确的是（  ）。【北方交通大学1999一、7（3分）】
        A  关键活动不按期完成就会影响整个工程的完成时间
数据结构与算法考研真题
        B  任何一个关键活动提前完成，那么整个工程将会提前完成
C  所有的关键活动提前完成，那么整个工程将会提前完成
D  某些关键活动若提前完成，那么整个工程将会提前完成
    【北京工业大学1999一、1（2分）】【哈尔滨工业大学2004二、3（1分）】
二 填空题
    1．一个有向图的顶点集为{a，b，c，d，e，f}，边集为{<a，c>，<a，e>，<c，f>，<d，c>，<e，b>，<e，d>}，则出度为0的顶点个数为（  ），入度为1的顶点个数为（  ）。
    2．若一个图的顶点集为{a，b，c，d，e，f}，边集为{（a，b），（a，c），（b，c），（d，e）}，则该图含有（  ）个连通分量。
    3．根据图的存储结构进行某种次序的遍历，从某顶点出发得到的顶点序列是（  ）的。
    4．图有（  ）、（  ）等存储结构，遍历图有（  ）、（  ）等方法。
    5．有向图G用邻接矩阵存储，其第i行的所有元素之和等于第i个顶点的（  ）。
    6．设有一稀疏图G，则G采用（  ）存储比较节省空间。
    7．设有一稠密图G，则G采用（  ）存储比较节省空间。
    8．图的逆邻接表存储结构只适用于（  ）图。
三 判断题
1．有e条边的无向图，在邻接表中有e个结点。（  ）
2．有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（  ）
3．强连通图的各顶点间均可达。（  ）
4．强连通分量是无向图的极大强连通子图。（  ）
5．连通分量指的是有向图中的极大连通子图。（  ）
6．对于任意一个图，从它的某个顶点进行一次先深或先广搜索可以访问到该图的每个顶点。（  ）
7．有n-1条边的图肯定都是生成树。（  ）
8．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（  ）
9．对一个无向图进行先深搜索时，得到的先深序列是唯一的。（  ）
10．有向图的邻接矩阵是对称的。（  ）
11．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是非对称矩阵。（  ）
12．邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（  ）
13．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（  ）
14．一个带权的无向连通图的最小生成树的权值之和是唯一的。（  ）
15．最小代价生成树是唯一的。（  ）
16．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（  ）
17．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环。（  ）
18．无环有向图才能进行拓扑排序。（  ）
19．有环图也能进行拓扑排序。（  ）
20．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。（  ）
21．关键路径是AOE网中从源点到终点的最长路径。（  ）
四 简答题
    1．对于图7-12所示的有向图G1，请给出：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。