单项选择题

给定一组长度为n的无序序列，将其存储在一维数组a[0..n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较a[0]和a[n-1]，若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值；然后依次比较a[2]和a[n-3]、a[3]和a[n-4]、...，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小元素，在后n/2个元素查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是______。

A．动态规划法
B．贪心法
C．分治法
D．回溯法
<上一题 目录 下一题>
热门 试题

单项选择题
某算法的时间复杂度可用递归式表示，若用表示该算法的渐进时间复杂度的紧致界，则正确的是______。
问答题
阅读下列说明，回答问题。 [说明] 现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。 现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各项点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各项点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。 [问题1] 本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1，2，...，n)，W=Wij，n*n为权重矩阵。设为从顶点i到顶点，的一条最短路径的权重。当k=0时，不存在中间顶点，因此。 当k＞0时，该最短路径上所有的中间顶点均属于集合1，2，…，k，若中间顶点包括顶点k，则，若中间顶点不包括顶点k，则。 于是得到如下递归式。 因为对于任意路径，所有的中间顶点都在集合1，2，…，n内，因此矩阵n*n给出了任意两个顶点之间的最短路径，即对所有表示顶点i到顶点，的最短路径。 下面是求解该问题的伪代码，请填充其中空缺的(1)～(6)处。伪代码中的主要变量说明如下。 W：权重矩阵； n：图的顶点个数； SP：最短路径权重之和数组，SP[i]表示顶点f到其他各顶点的最短路径权重之和，i从1到n； min_SP：最小的最短路径权重之和； min_v：具有最小的最短路径权重之和的顶点； i：循环控制变量； j：循环控制变量； k：循环控制变量； LOCATE-SHOPPINGMALL (W, n) 1 D(0)=W 2 for (1) 3 for i=1 to n 4 for j = 1 to n 5 6 (2) 7 else 8 (3) 9 for i=1 to n 10 Sp[i] =0 11 for j=1 to n 12 (4) 13 min_SP=SP [1] 14 (5) 15 for i=2 to n 16 if min_SP＞SP [i] 17 min_SP=SP[i] 18 min_v=i 19 return (6) [问题2] 问题1中伪代码的时间复杂度为______(用O符号表示)。
相关试题