单项选择题

归并排序采用的算法设计方法属于______。

A．归纳法
B．分治法
C．贪心法
D．回溯方法
<上一题 目录 下一题>
热门 试题

问答题
阅读下列说明，回答问题。 [说明] 0-1背包问题可以描述为：有n个物品，对i=1，2，…，n，第i个物品价值为vi，重量为wi(vi，和wi为非负数)，背包容量为W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即，其中，Xi∈0，1，xi=0表示第i个物品不放入背包，xi=1表示第i个物品放入背包。 [问题1] 用回溯法求解此0-1背包问题，请填充下面伪代码中(1)～(4)处空缺。 回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的节点。现在假设已经设计了BOUND(v，w，k，w)函数，其中v，w，k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个节点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该节点无需再扩展。 下面给出0-1背包问题的回溯算法伪代码。 函数参数说明如下。 W:背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X:问题的最优解。 变量说明如下。 cw：当前的背包重量；cp:当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。 BKNAP (W,n,w,v,fw, fp,X) 1 cw←cp←0 2 (1) 3 fp←-1 4 while true 5 while k≤n and cw+w[k]≤W do 6 (2) 7 cp← cp+v[k] 8 Y[k] ← 1 9 k← k+1 10 if k＞n then 11 if fp＜cp then 12 fp ← cp 13 fw ← ew 14 k ← n 15 X ← Y 16 else Y(k)← 0 17 while BOUND(cp, cw, k, W) ≤fp do 18 while k≠0 and Y(k) ≠1 do 19 (3) 20 if k=0 then return 21 Y[k]←0 22 cw←cw-w[k] 23 cp ← cp-v[k] 24 (4) [问题2] 考虑表9.2的实例，假设有3个物品，背包容量为22。图9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字1 0分别表示选择 不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了该节点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。 表9.2 0-1背包问题实例 物品1 物品2 物品3 重量 15 10 10 价值 30 18 17 单位价值 2 1.8 1.7 对于表9.2的实例，若采用穷举法搜索整个解空间，则搜索树的节点数为 (7) ，而用了上述回溯法，搜索树的节点数为 (8) 。
问答题
阅读下列说明，回答问题1至问题3。 [说明] 快速排序是一种典型的分治算法。采用快速排序对数组A[P..r]排序的3个步骤如下。 (1)分解：选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..g-1]和A[q+1..]，使得A[g]大于等于A[p..q-1]中的每个元素，小于A[q+1..r]中的每个元素。q的值在划分过程中计算。 (2)递归求解：通过递归的调用快速排序，对子数组A[p..q-1]和A[q+1..r]分别排序。 (3)合并：快速排序在原地排序，故不需合并操作。 [问题1] 下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。 A：待排序数组。 p，r：数组元素下标，从p到r。 q：划分的位置。 x：枢轴元素。 i：整型变量，用于描述数组下标。下标小于或等于i的元素的值小于或等于枢轴元素的值。 j：循环控制变量，表示数组元素下标。 QUICKSORT (A,p， r) if (p＜r) q = PARTITION(A,p,r)； QUICKSORT(A，p，q-1)； QUICKSORT (A，q+1，r)； PARTITION (A，p，r) x=A[r]; i=p-1； for(j=p；j≤r-1; j++) if(A[j]≤x) i=i+1; 交换A[i]和A[j] 交换 (1) 和 (2) 注：空(1)和空(2)答案可互换，但两空全部答对方可得分 return (3) [问题2] (1)假设要排序包含n个元素的数组，清给出在各种不同的划分情况下，快速排序的时间复杂度，用0记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。 (2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况 (7) 。(最佳、平均、最坏) [问题3] (1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码。利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i j)表示随机取i到j之间的一个数，包括i和j。 RANDOMIZED-PARTITION(A,p,r) i= RANDOM(p，r); 交换 (8) 和 (9) ； 注：空(8)和空(9)答案可互换 return PARTITION(A,p,r); (2)随机化快速排序是否能够消除最坏情况的发生 (10) 。(是或否)
相关试题