下载APP
【单选题】
一个有向图D由顶点集V和边集E构成。如果D有n个顶点，那么顶点集为【图片】，如果在D中从【图片】到【图片】有一条有向边，那么【图片】属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的【图片】到【图片】有一条有向边，那么矩阵M的第i行第j列元素的值为1；否则【图片】。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列【图片】将矩阵【图片】的i行j列元素记作【图片】。对于【图片】当且仅当图中存在一条从【图片】到【图片】的路径，并且这条路径除端点外中间只经过【图片】中的顶点。不难看出【图片】就是M，而在【图片】中如果【图片】，则说明D中【图片】和【图片】是连通的。Warshall算法从【图片】开始，顺序计算【图片】,直到【图片】为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是：【图片】
A.
a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
B.
a 可以连通到 b,c,d;b 可以连通到 c;c 可以连通到 d;d 可以连通到 c
C.
a 可以连通到 b,c;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
D.
a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 b,d;d 可以连通到 c
参考答案：
参考解析：
刷刷题刷刷变学霸
举一反三
【多选题】“ p∨ q→r”为假，当且仅当p、q、r的值为( )
A.
p真、q真、r真
B.
p真、q真、r假
C.
p假、q假、r真
D.
p假、q真、r假
E.
p真、q假、r假
【单选题】（22）处填（）。 A．分治法 B．贪心法 C．动态规划方法 D．回溯法
A.
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中，最坏情况下计算时间可以达到O(nlogn)的是 (21) ，该算法采用的设计方法是 (22) 。