数据结构第二章线性表思维导图(王珊数据库系统概论思维导图)

连通图：整个图只有一个连通分量完整图： n个节点，有n*(n-1 )/2条边。 使用邻接矩阵结构存储具有n个顶点的图，宽度优先扫描的时间复杂度使用o(n^2)邻接表结构存储具有n个顶点的图，深度优先扫描的时间复杂度使用o ) ne )邻接表结构存储具有n个顶点的图拓扑排序算法的时间复杂度为o ) ne )，如果是有向图，则如果是该边的强连通有向图，则该边的数量至少为(n )。 在具有n个顶点的e条边的有向图中，有2e个时具有n个顶点的有向图，图中的边数为n(n-1 )/2； 另一方面，在具有n个顶点的有向图的情况下，图中的弧的数量为n(n-1 )。 根据图的定义，图中顶点的最低数量为__ _1 ___图的宽度优先搜索类似于树的(d )扫描。 a .先根b .中根c .后根d .层次图的深度优先搜索扫描与树的(a )顺序扫描相似。 a .先根b .中根c .后根d .层次无向图g有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点时，图g有最大(d )的顶点。 A.11B.12C.15D.16分析：在具有n个顶点的e条边的无向图中，具有2e个度4*5 3*4 2*n2=2*23 n2=7总顶点=5 4 7=16个节点的无向图最多具有(b )条边。 a、14B、28C、56D、112解析：是具有n个顶点的有向图，图中的边数为n(n-1 )/2。 有8个节点的有向完全图具有(c )的边。 A . 14 B . 28 C . 56 D . 112分析：对于具有n个顶点的有向完整图，图中的弧数为n(n-1 )。 有8个节点的有向连通图至少有(c )条边。 A . 5 B . 6 C . 7 D . 8分析：具有n个顶点的图，在连通无向图的情况下，其边数至少为(n-1 )。 在邻接表中显示图表进行宽度优先扫描时，通常使用(b )来实现算法。 a、堆栈b、队列c、树d、图解释：宽度优先遍历通常通过队列实现算法，深度优先遍历通常通过堆栈实现算法。 当在相邻图中执行深度优先遍历时，通常使用(a )来实现算法。 a、堆栈b、队列c、树d、图解释：宽度优先遍历通常通过队列实现算法，深度优先遍历通常通过堆栈实现算法。 g是非连通无向图，共有28边时，该图至少有(c )个顶点。 答： c解释： 8个顶点的有向图最多有8*7/2=28条边，再加一个点构成非连通有向图，所以至少有9个顶点。