算法选择题

偏执的太偏执、 2022-05-16 06:52 167阅读 0赞

1.【问题】：基于比较的排序算法是（ ）  
A.基数排序  
B.冒泡排序  
C.桶排序  
D.希尔排序  
【答案】：BD  
【分析】：基于比较的排序算法有：（1）直接插入排序；（2）冒泡排序；（3）简单选择排序；（4）希尔排序；（5）快速排序；（6）堆排序；（7）归并排序。

2.【问题】：下面哪些使用的是贪心算法  
A.单源最短路径中的Dijkstra算法  
B.最小生成树的Prim算法  
C.最小生成树的Kruskal算法  
D.计算每对顶点最短路径的Floyd-Warshall算法  
E.字符串匹配中的KMP算法  
【答案】：ABC  
【分析】：**贪心算法（又称贪婪算法）**是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。  
**A.单源最短路径中的Dijkstra算法**：Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既**先求出长度最短的一条最短路径**，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

**B.最小生成树的Prim算法**:Prim算法基于贪心算法设计，其从一个顶点出发，**选择这个顶点发出的边中权重最小的一条加入最小生成树中，**然后又从当前的树中的所有顶点发出的边中选出权重最小的一条加入树中，以此类推，直到所有顶点都在树中，算法结束。  
**C.最小生成树的Kruskal算法**按照权值**从小到大的顺序**选择n-1条边，并保证这n-1条边不构成回路。  
**D.计算每对顶点最短路径的Floyd-Warshall算法**:单独一条边的路径也不一定是最佳路径。 从任意一条单边路径开始。所有两点之间的距离是边的权的和，(如果两点之间没有边相连, 则为无穷大）。 从第一个顶点开始，依次将每个顶点作为媒介 k，然后对于每一对顶点 u 和 v ，查看其是否存在一条经过 k 的，距离比已知路径更短的路径，如果存在则更新它。  
**E.字符串匹配中的KMP算法**  
在传统算法的基础上，当匹配失败后，并不简单地从目标串下一个字符开始新一轮的检测，而是依据在检测之前得到的有用信息，或者说模式串本身的特征信息，取得next函数跳转的位置，直接跳过不必要每次从头检测，从而达到一个较高的检测效率。

【问题】：  
【答案】：  
【分析】：