北邮数据结构第六章答案详解 图(1)

第 6 章图课后习题讲解1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

1 / 1710.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

第6章树和二叉树习题解答一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分）（√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）2.二叉树中每个结点的两棵子树的高度差等于1。

（√）3.二叉树中每个结点的两棵子树是有序的。

（×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。

（×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。

（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。

（应2i-1）（×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。

（×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。

（应2i-1）（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（正确。

用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。

由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。

）即有后继链接的指针仅n-1个。

（√）10. 〖01年考研题〗具有12个结点的完全二叉树有5个度为2的结点。

最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5二、填空（每空1分，共15分）1．由３个结点所构成的二叉树有5种形态。

2. 【计算机研2000】一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。

注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。

3．一棵具有２５７个结点的完全二叉树，它的深度为9。

（注：用⎣ log2(n) ⎦+1= ⎣ 8.xx ⎦+1=94.【全国专升本统考题】设一棵完全二叉树有700个结点，则共有350个叶子结点。

数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。

下面是一些关于栈的应用场景。

1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。

1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。

通过使用栈，我们可以很方便地进行算术运算。

1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。

将数据依次压入栈中，然后再逐个弹出即可。

2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。

下面是一些关于队列的实现和应用。

2.1 数组实现队列队列可以使用数组来实现。

我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。

2.2 链表实现队列队列还可以使用链表来实现。

我们可以使用一个指针指向队列的头部，并在尾部添加新元素。

通过移动指针来实现出队操作。

2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。

在BFS中，我们需要按照层级来访问节点。

使用队列可以帮助我们按照顺序存储和访问节点。

3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。

下面是一些关于树的遍历和应用的介绍。

3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。

通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。

3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。

通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。

3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。

这种结构可以用于高效地进行数据查找。

4. 图的表示与遍历图是由节点和边组成的一种数据结构。

下面是一些关于图的表示和遍历的说明。

4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。

使用一个二维数组来表示节点之间的连接关系。

图1. 填空题⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

第6章 树和二叉树（参考答案）6.1(1)根结点a6.2三个结点的树的形态： 三个结点的二叉树的形态：（1） （1） （2） （4） （5）6．3 设树的结点数是n ，则n=n0+n1+n2+……+nm+ (1)设树的分支数为B ，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m-1)nm+16.4(1) k i-1 (i 为层数)(2) (n-2)/k+1(3) (n-1)*k+i+1(4) (n-1)%k !=0; 其右兄弟的编号 n+16.5（1）顺序存储结构注：#为空结点6.6(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFCA6.7(1) 空二叉树或任何结点均无左子树的非空二叉树(2) 空二叉树或任何结点均无右子树的非空二叉树(3) 空二叉树或只有根结点的二叉树6.8int height(bitree bt)// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度{ int bl,br; // 局部变量，分别表示二叉树左、右子树的高度if (bt==null) return(0);else { bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }}// 算法结束6.9void preorder(cbt[],int n,int i);// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数// 组下标，初始调用时为1。

本算法以非递归形式前序遍历该二叉树{ int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0if (n<=0) { printf(“输入错误”);exit（0）；}while (i<=n ||top>0){ while(i<=n){visit(cbt[i]); // 访问根结点if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈i=2*i;// 先序访问左子树}if (top>0) i=s[top--]; // 退栈，先序访问右子树} // END OF while (i<=n ||top>0)}// 算法结束//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示void preorder(bt[],int n,int i);// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。

第6章图一、选择题1、设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。

A.5B.6C.7D.82、若非连通无向图G含有21条边，则G的顶点个数至少为（ B ）。

A．7 B．8 C．21 D．223、一个有n个顶点的连通无向图，其边的个数最少为（B ）。

A. nB. n-1C. n+1D. nlog2n4、设有向图的顶点个数为n，则该图最多有（ B ）条弧。

A．n-1 B．n(n-1) C．n(n+1) D． n25、对下面给定的有向图，从顶点1出发，其深度优先搜索序列为（A ）。

A. 1,2,5,3,4B. 1,2,4,3,5C. 1,4,3,2,5D. 1,2,3,4,56、具有10个顶点的连通图的深度优先生成树，其边数为（B ）。

A. 11B. 9C. 10D. 87、下列说法不正确的是（C ）。

A. 图的广度遍历适用于有向图B. 无向图的邻接矩阵是对称矩阵C. 图的深度遍历不适用于有向图D. 图的深度遍历是一个递归过程8、下列说法中正确的是（D ）。

A. 一个具有n个顶点的无向完全图的边数为n(n-1)B. 连通图的生成树是该图的一个极大连通子图C. 图的深度优先搜索是一个非递归过程D. 非连通图遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量9、对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（C ）。

A. 求一个顶点的邻接点B. 深度优先遍历C. 求一个顶点的度D. 广度优先遍历10、下列说法正确的是（ C ）。

A. 图的广度遍历不适用于有向图B. 有向图的邻接矩阵是对称矩阵C. 图的深度遍历适用于有向图D. 图的广度遍历是一个递归过程11、连通网的最小生成树是其所有生成树中（A ）。

A. 边权值之和最小的生成树B. 边集最小的生成树C. 顶点权值之和最小的生成树D. 顶点集最小的生成树12、有n个顶点的连通图G的最小生成树有（B ）条边。

1．分画出具有3个点的和3个点的二叉的所有不同形。

2．1所得各种形的二叉，分写出前序、中序和后序遍的序列。

3．一棵度k的中有n1个度1的点，n2个度2的点，⋯⋯，nk个度k的点，中有多少个叶子点并明之。

假一棵二叉的先序序列EBADCFHGIKJ，中序序列ABCDEFGHIJK，画出二叉。

5．二叉有50个叶子点，二叉的点数至少有多少个？6．出足以下条件的所有二叉：①前序和后序相同②中序和后序相同③前序和后序相同7．n个点的K叉，假设用具有k个child 域的等点存的一个点，空的Child域有多少个？8．画出与以下序列的Ｔ：的先根次序序列GFKDAIEBCHJ；的后根次序序列DIAEKFCJHBG。

9．假用于通的文由8个字母成，字母在文中出的率分：，，，，，，，8个字母哈夫曼。

10．二叉采用二叉表存放,要求返回二叉T的后序序列中的第一个点指,是否可不用且不用来完成?述原因.11.画出和以下的二叉：12．二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。

13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。

在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。

15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。

18．二叉树按照二叉链表方式存储，利用栈的根本操作写出后序遍历非递归的算法。

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正那么二叉树。

正那么二叉树是指：在二叉树中不存在子树个数为 1的结点。

20．计算二叉树最大宽度的算法。

二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。

21．二叉树按照二叉链表方式存储，利用栈的根本操作写出先序遍历非递归形式的算法。

图1. 填空题⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（）。

【解答】其自身⑶ 图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。

⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。

【解答】出度⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。

【解答】前序，栈，层序，队列⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。

【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。

⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

【解答】回路⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。

【解答】vi, vj, vk【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。

1第6章 图一、填空题1、用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网（AOV-网）。

2、有n(n-1)/2条边的无向图称为_无向完全图__；有n(n-1)条边的有向图称为_有向完全图。

3、一个含n 个结点的完全无向图中，其最大边数为__ n(n-1)/2_。

4、顶点表示事件，弧表示活动，权表示活动持续时间的有向图称为AOE-网。

二、判断题1、任何无向图都存在生成树。

（ ）2、连通分量是无向图中的极小连通子图。

（ ）3、强连通分量是有向图中的极大强连通子图。

（ ）4、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

（ ）5、邻接表法只用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。

（ ）6、求最小生成树的Prim 算法在边较少、结点较多时效率较高。

（ ）7、图的最小生成树的形状可能不唯一。

（ ）8、一个AOV 网的拓扑序列一定是唯一的。

网的拓扑序列一定是唯一的。

（ ） 9、若AOV 网中存在环，则不能求它的拓扑排序序列。

（ ）10、若AOV 网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存在环。

（ ） 11、缩短关键路径上活动的工期一定能够缩短整个工程的工期。

（ ） 12、AOE 网中一定只有一条关键路径。

（ ）三、单项选择题1、在一个图中，所有顶点的度数之和等于图的边数的（、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。

）倍。

A ．1/2 B ．1 C ．2D ．4 2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。

）倍。

A ．1/2 B ．1 C ．2 D ．4 解释：有向图所有顶点入度之和等于所有顶点出度之和。

3、具有n 个顶点的有向图最多有（个顶点的有向图最多有（ B ）条边。

）条边。

第六章课后习题6、1、各层的结点数目是：K2、编号为n的结点的双亲结点是：<=(n-2)/k的最大整数3、编号为n的结点的第i个孩子结点编号是：k*(n-1)+1+i4、编号为n的结点有右兄弟的条件是：(n-1)能被k整除右兄弟的编号是：n+1.7、1、先序序列和中序序列相同：空二叉树或没有左子树的二叉树。

2、中序序列和后序序列相同：空二叉树或没有右子树的二叉树。

3、先序序列和后序序列相同：空二叉树或只有根的二叉树。

9、中序序列：BDCEAFHG和后序序列：DECBHGFA的二叉树为：AB FC GD E H先序序列：ABCDEFGH算法设计：3、typedef struct{int data[100];int top;}seqstack;seqstack *s;Perorder(char a[],int n){int i=1,count=1;s->top=-1;if(n==0)return(0);else{if(I<=n){s->top++;s->data[s->top]=a[I];}while(count<n){printf(“%c”,s->data[s->top]);count++;s->top--;if(s->data[s->top]);==a[i]){ printf(“%c”,s->data[s->top]);count++;s->top--;}if((2*i+1)<n){i=2*i;s->top++;s->data[s->top]=a[i+1];s->top++;s->data[s->top]=a[i];}else if(a*i<n){i=2*i;s->top++;s->data[s->top]=a[i];}else if(i/2%2==1)i=i/2/2+1;else i=i/2+1;}}}main(){char A[]=“kognwyuvb”;int n=strlen(A);s=(seqstack *)malloc(sizeof(seqstack)); printf(“\n”);Perorder(A,n);}。

《数据结构》吕云翔编著第6章图习题解答第六章图习题解答一、选择题1.某无向图的邻接矩阵A=，可以看出该图共有（）个顶点A.3B.6C.9D.以上答案均不正确【解答】A2．无向图的邻接矩阵是一个（），有向图的邻接矩阵是一个（）A 上三角矩阵B 下三角矩阵C 对称矩阵D 无规律【解答】C，D3．下列命题正确的是（）。

A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一【解答】B4. 在一个具有n 个顶点的有向完全图中包含有（）条边：A n(n-1)/2B n(n-1)C n(n+1)/2D n2【解答】B5．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（）棵树。

A kB nC n - kD 1【解答】C6．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

A 逆拓扑有序B 拓扑有序C 无序D 深度优先遍历序列【解答】A7. 关键路径是AOE网中（）。

A 从源点到终点的最长路径B从源点到终点的最长路径C 最长的回路D 最短的回路【解答】A二、填空题1.设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。

【解答】0，n(n-1)/2，0，n(n-1)2.任何连通图的连通分量只有一个，即是（）。

【解答】其自身3.图的存储结构主要有两种，分别是（）和（）。

【解答】邻接矩阵，邻接表4.已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。

【解答】Ｏ(n+e)5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。

【解答】求第j列的所有元素之和6.有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。