问题
单项选择题
在有n个无序无重复元素值的数组中查找第i小的数的算法描述如下：任意取一个元素r，用划分操作确定其在数组中的位置，假设元素r为第k小的数。若i等于k，则返回该元素值；若i小于k，则在划分的前半部分递归进行划分操作找第i小的数；否则在划分的后半部分递归进行划分操作找第k-i小的数。该算法是一种基于（）策略的算法。
A．分治
B．动态规划
C．贪心
D．回溯
答案
参考答案：A
解析：
[分析]：本题考查算法的设计策略。
从题干可以看出，划分操作与快速排序中的划分操作是一样的，确定某个元素如r的最终位置，划分后，在r之前的元素都小于r，在r之后的元素都大于r(假设无重复元素)。因此可以据此确定r是数组中第几小的数。题干所述的算法把找第i小的数转换为确定任意一个元素是第几小的数，然后根据这个结果再在依据该元素划分后得到的结果在前一部分还是后一部分来继续确定某个元素为第几小的数，重复这种处理，直到找到第i小的数。这是分治策略的一个典型应用。