1、对下图进行拓扑排序，可得不同拓扑序列的个数是（）。• A：4• B：3• C：2• D：1解析

可以得到3种不同的拓扑序列，即abced，abecd和aebcd。

答案：B2、下列关于最小生成树的叙述中，正确的是（）。

Ⅰ、最小生成树的代价唯一 Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ、使用Prim算法从不同顶点开始得到的最小生成树一定相同 Ⅳ、使用Prim算法和Kruskal算法得到的最小生成树总不相同

• A：仅Ⅰ• B：仅Ⅱ• C：仅Ⅰ、Ⅲ• D：仅Ⅱ、Ⅳ解析

最小生成树的树形可能不唯一（因为可能存在权值相同的边），但代价一定是唯一的，Ⅰ正确。

若权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。

设N各结点构成环，N-1条边权值相等，另一条边权值较小，则从不同的顶点开始Prim算法会得到N-1种不同的最小生成树，Ⅲ错误。

当最小生成树唯一时（各边的权值不同），Prim算法和Kruskal算法得到的最小生成树相同，Ⅳ错误。

答案：A3、对下图所示的有向带权图，若采用Dijkstra算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。• A：d,e,f• B：e,d,f• C：f,d,e• D：f,e,d解析

从a到各顶点的最短路径的求解过程如下：

后续目标顶点依次为f,d,e。

答案：C4、下列AOE网表示一项包含8个活动的工程，通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）。

在这里插入图片描述

• A：c和e• B：d和c• C：f和d• D：f和h解析

找出AOE网的全部关键路径为bdcg、bdeh和bfh。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期。选项A、B和D并不包括在所有的关键路径中，只有C包含，因此只有加快f和d的进度才能缩短工期。

答案：C5、对下图所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。• A：3,1,2,4,5,6• B：3,1,2,4,6,5• C：3,1,4,2,5,6• D：3,1,4,2,6,5解析

按照拓扑排序的算法，每次都选择入度为0的结点从图中删除，此图中一开始只有结点3的入度为0；删除结点3后，只有结点1的入度为0；删除结点1后，只有结点4的入度为0；删除结点4后，结点2和结点6的入度都为0，此时选择删除不同的结点，会得出不同的拓扑序列，分别处理完毕后可知可能的拓扑序列为3,1,4,2,6,5和3,1,4,6,2,5，选D。

答案：D6、若对n个顶点、e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是（）。• A：O(n)• B：O(n+e)• C：O()• D：O(ne)解析

采用邻接表作为AOV网的存储结构进行拓扑排序，需要对n个顶点做进栈、出栈、输出各一次，在处理e条边时，需要检测这n个顶点的边链表的e个边结点，共需要的时间代价为O(n+e)。若采用邻接矩阵作为AOV网的存储结构进行拓扑排序，在处理e条边时需对每个顶点检测相应矩阵中的某一行，寻找与它相关联的边，以便对这些边的入度减1，需要的时间代价为O()。

答案：B7、使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2，3，4，5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新为（）。• A：26，3，14，6• B：25，3，14，6• C：21，3，14，6• D：15，3，14，6解析

在执行Dijkstra算法时，首先初始化dist[]，若顶点1到顶点i（i=2，3，4，5）有边，就初始化为边的权值：若无边，就初始化为∞；初始化顶点集S只含顶点1.Dijkstra算法每次选择一个到顶点1距离最近的顶点j加入顶点集S，并判断由顶点1绕行顶点j后到任一顶点k是否距离更短，若距离更短（即dist[j] + arcs[j][k] < dist[k]），则将dist[x]更新为dist[j]+arcs[j][k]；重复该过程，直至所有顶点都加入顶点集S。数组dist的变化过程如下图所示，可知将第二个顶点5加入顶点集S后，数组dist更新为21，3，14，6，故选C。

答案：C8、评价算法的标准包括如下几方面：正确性、____、健壮性、高效率及低存储量。• A： 可靠性• B：可行性• C：可读性• D：可能性解析

算法设计的要求：

• 正确性• 可读性• 健壮性• 效率与低存储量答案：C

9、一个有n个结点的图，最少有____个连通分量。• A：0• B：1• C：n-1• D：n解析

最少是1个，这种情况下，它本身就是一个连通图； 最多是n个，这种情况下，它由n个分散的点组成的一个图。

答案：B10、对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是____。• A：05，46，13，55，94，17，42• B：05，13，17，42，46，55，94• C：42，13，94，05，55，46，17• D：05，13，46，55，17，42，94解析

按照基数排序：

• （1）先按个位数数字，一次放入对应的桶，取出的结果为：42，13，94，05，55，46，17• （2）再按十位数字，依次放入对应的桶，取出的结果为：05，13，17，42，46，55，94 但题目中问的是一趟排序后的结果，所以选C。答案：C学海无涯苦作舟