邻接矩阵： ??43?4?5??35????55??9???????????????5?55?7654?9?7?3?????63?2????5?2?6?????5??4? ?????6?????最小生成树：

38．试写出对如下有向无环图进行拓扑排序可能得到的所有拓扑序列。

参考答案：

每次输出一个入度为０的顶点。ａｂｃｄｅｆｇ、ａｂｃｄｆｅｇ、ａｂｃｆｄｅｇ。 39．设有向网如下，用弗洛伊德算法求图中各对顶点间的最短路径。

参考答案：

35．设有ＡＯＥ网如下，试求关键路径。

参考答案：

关键路径１：v1→v2→v5→v7 关键路径２：v1→v3→v6→v7

32．下图是带权的有向图G的邻接表表示法，求： （1）以结点V1出发深度遍历图G所得的结点序列； （2）以结点V1出发广度遍历图G所得的结点序列； （3）从结点V1到结点V8的最短路径； （4）从结点V1到结点V8的关键路径。

参考答案：

（1）V1,V2,V3,V8,V5,V7,V4,V6； （2）V1,V2,V4,V6,V3,V5,V7,V8；

（3）V1到V8最短路径56，路径为V1----V2----V5----V7----V8； （4）V1到V8的关键路径是V1----V6----V5----V3----V8，长97。

29．试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各步的状态。

参考答案：

顶点a到顶点b，c，d，e，f，g间的最短路径分别是15，2，11，10，6，13。

34．对图示的AOE网络，计算各活动弧的e(ai)和l(ai)的函数值，各事件（顶点）的ve（Vj）和vl (Vj)的函数值，列出各条关键路径。

7．有向图的邻接表存储如下，要求：（1）画出其邻接矩阵存储；（2）写出图的所有强连通分量；（3）写出顶点a到顶点i的全部简单路径。

参考答案：

（1）略。（注：邻接矩阵下标按字母升序:abcdefghi）

（2）强连通分量：（a），(d)，（h），(b，e，i，f，c，g）

（3）顶点a到顶点i的简单路径：（a->b->e->i），（a->c->g->i），（a->c->b->e->i）。

数组

20．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。

A．13 B．33 C．18 D．40 参考答案：B

23．将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A66,65（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。

A．198 B．195 C．197 D．196 参考答案：B

25．有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。

A．60 B．66 C．18000 D．33 参考答案：B

26．算术表达式a+b*(c+d/e)转为后缀表达式后为（ ）。

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 参考答案：B