数据结构题目收录（十四）

谁践踏了优雅 2024-04-03 11:27 86阅读 0赞

#### 1、对下图进行拓扑排序，可得不同拓扑序列的个数是（）。 ####

![在这里插入图片描述][8917400d421247e8a05f8c5c29c62fb8.png]

*  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，后续得到的其余各最短路径的目标顶点依次是（）。 ####

![在这里插入图片描述][aa0db82a285d4c96ac565c3ee181048d.png]

*  A：d,e,f
 *  B：e,d,f
 *  C：f,d,e
 *  D：f,e,d

###### 解析 ######

从a到各顶点的最短路径的求解过程如下：  
![在这里插入图片描述][7e9f78f96e2e4474bcfeec69972d213b.png]  
后续目标顶点依次为f,d,e。

###### 答案：C ######

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

![在这里插入图片描述][1fe14d8474544b5c8368e1627285bbef.png]

*  A：c和e
 *  B：d和c
 *  C：f和d
 *  D：f和h

###### 解析 ######

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

###### 答案：C ######

#### 5、对下图所示的有向图进行拓扑排序，得到的拓扑序列可能是（）。 ####

![在这里插入图片描述][97c74ba1889c4a0d8cea9bc10a29c5cd.png]

*  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( n 2 n^2 n2)
 *  D：O(ne)

###### 解析 ######

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

###### 答案：B ######

#### 7、使用Dijkstra算法求下图中从顶点1到其余各顶点的最短路径，将当前找到的从顶点1到顶点2，3，4，5的最短路径长度保存在数组dist中，求出第二条最短路径后，dist中的内容更新为（）。 ####

![在这里插入图片描述][31f8871179f44fb2a8b388000c186357.png]

*  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。

![在这里插入图片描述][e1c4fb08c6d84a6db2026db7a27fb70e.png]

###### 答案：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。

###### 答案：C ######

### 学海无涯苦作舟 ###

![这里写图片描述][70]

[8917400d421247e8a05f8c5c29c62fb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c193fbf315484c1dabe7a64b1d3235b9.png
[aa0db82a285d4c96ac565c3ee181048d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bd72c63d97be4a4ea38264fa31a9c39b.png
[7e9f78f96e2e4474bcfeec69972d213b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bdc3f0dcb0e04c1dbd955f2f17adae6a.png
[1fe14d8474544b5c8368e1627285bbef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/fb21a366447e4bb8b217f46989875b26.png
[97c74ba1889c4a0d8cea9bc10a29c5cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/2b0f56dd652c43e3b506c1824316424d.png
[31f8871179f44fb2a8b388000c186357.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/4f44d664578c4d019730391b2ef3eafa.png
[e1c4fb08c6d84a6db2026db7a27fb70e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3579fd8b9c37487ca3bee5306bac5c87.png
[70]: https://img-blog.csdn.net/20180408232122585?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1bnRlckFybGV5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70