有向图G=（V，E),其中V（G)={0，1，2，3，4，5}，用＜a，b，d＞三元组表示弧＜a，b＞及弧上的权d。E（G

则在图的顶点数为40时，计算时间约为__________ms。【南京理工大学2000二、3(1．5分)】

技大学2005二、3(1分)】

4年全国试题42(10分)】

结构的数据类型定义，并画出对应题3表的链式存储结构示意图(示意图中可仅以ID标识结点)。

如下的一维数组中。

要求： (1)写出图G的邻接矩阵A。 (2)画出有向带权图G。 (3)求图G的关键路径，并计算该关键路径的长度。【2011年全国试题41(8分)】

一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点“为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行，请证明之，否则，请举例说明。【2009年全国试题41(10分)】

语句。 void topsort(hdnodes graph[]，int n) {int i，J，k，top；node pointer ptr； top=-1； for(i=0； i<n； i++) if(!graph[i]．count){graph[i]．count：top；top=i；) for (1=0； 1<n； 1++) if①(fpri

计；(2)indegree是有n个分量的一维数组，放顶点的入度； (3)函数crein用于算顶点入度； (4)有三个函数push(data)、pop()、check()其含义为数据data进栈、退栈和测试栈是否空(不空返回1，否则0)。 crein(array，indegree，n) {for(i=0；i<n；i++) indegree[i]=((1) ) for(i=0