若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列一定不存在。

第1题：

第2题：

若具有n个顶点且不带权的连通图采用邻接矩阵存储，则该邻接矩阵中至少有（）个非零元素。

正确答案:2(n-1)

第3题：

若一个有向图的邻接矩阵中，对角线以下元素均为0，则该图的拓扑有序序列必定存在。

正确答案:正确

第4题：

证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。

正确答案:任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。
假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。

第5题：

对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。

正确答案:错误

第6题：

任一个有向图的拓扑序列（）。

• A、不存在
• B、有一个
• C、一定有多个
• D、有一个或多个

正确答案:D

第7题：

用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

• A、逆拓扑有序
• B、拓扑有序
• C、无序
• D、深度优先遍历序列

正确答案:A

第8题：

第9题：

第10题：

第11题：

第12题：

第13题：

在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。

正确答案:错误

第14题：

若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）

正确答案:n²-2e

第15题：

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。

正确答案:正确

第16题：

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

正确答案:回路

第17题：

若一个n阶矩阵A中的元素满足：A_ij=A_ji（0<=I，j<=n-1）则称A为（）矩阵；若主对角线上方（或下方）的所有元素均为零时，称该矩阵为（）。

正确答案:上；三角矩阵

第18题：

若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。

正确答案:正确

第19题：

第20题：

第21题：

第22题：

第23题：

第24题：