数据结构错题收录（十四）
1、对下图进行拓扑排序，可得不同拓扑序列的个数是（）。
在这里插入图片描述
- A：4
- B：3
- C：2
- D：1
解析
可以得到3种不同的拓扑序列，即abced，abecd和aebcd。
答案：B
2、下列关于最小生成树的叙述中，正确的是（）。
Ⅰ、最小生成树的代价唯一
Ⅱ、所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ、使用Prim算法从不同顶点开始得到的最小生成树一定相同
Ⅳ、使用Prim算法和Kruskal算法得到的最小生成树总不相同
- A：仅Ⅰ
- B：仅Ⅱ
- C：仅Ⅰ、Ⅲ
- D：仅Ⅱ、Ⅳ
解析
最小生成树的树形可能不唯一（因为可能存在权值相同的边），但代价一定是唯一的，Ⅰ正确。
若权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。
设N各结点构成环，N-1条边权值相等，另一条边权值较小，则从不同的顶点开始Prim算法会得到N-1种不同的最小生成树，Ⅲ错误。
当最小生成树唯一时（各边的权值不同），Prim算法和Kruskal算法得到的最小生成树相同，Ⅳ错误。
答案：A
3、对下图所示的有向带权图，若采用Dijkstra算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。
在这里插入图片描述
- A：d,e,f
- B：e,d,f
- C：f,d,e
- D：f,e,d
解析
从a到各顶点的最短路径的求解过程如下：
在这里插入图片描述
后续目标顶点依次为f,d,e。
答案：C
4、下列AOE网表示一项包含8个活动的工程，通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）。
在这里插入图片描述
- A：c和e
- B：d和c
- C：f和d
- D：f和h
解析
找出AOE网的全部关键路径为bdcg、bdeh和bfh。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期。选项A、B和D并不包括在所有的关键路径中，只有C包含，因此只有加快f和d的进度才能缩短工期。
答案：C
5、对下图所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。
在这里插入图片描述
- 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。
答案：D
6、若对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()。
答案：B
7、使用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。
在这里插入图片描述
答案：C
8、评价算法的标准包括如下几方面：正确性、____、健壮性、高效率及低存储量。
- A： 可靠性
- B：可行性
- C：可读性
- D：可能性
解析
算法设计的要求：
- 正确性
- 可读性
- 健壮性
- 效率与低存储量
答案：C
9、一个有n个结点的图，最少有____个连通分量。
- A：0
- B：1
- C：n-1
- D：n
解析
最少是1个，这种情况下，它本身就是一个连通图；
最多是n个，这种情况下，它由n个分散的点组成的一个图。
答案：B
10、对{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。
