1、软件设计师-算法设计和分析(一)及答案解析(总分：76.00，做题时间：90 分钟)一、综合知识试题(总题数：15，分数：16.00)1.归并排序采用的算法设计方法属于_。（分数：1.00）A.归纳法B.分治法C.贪心法D.回溯方法2.以下的算法设计方法中，_以获取问题最优解为目标。（分数：1.00）A.回溯方法B.分治法C.动态规划D.递推3.设某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n0)及 T(0)=1，则该算法的时间复杂度为_。（分数：1.00）A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)4.若某算法在问题规模为 n时，其基本操作的重复次数可由下式
2、表示，则该算法的时间复杂度为_。（分数：1.00）A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)5.用动态规划策略求解矩阵连乘问题 M1*M2*M3*M4，其中 M1(20*5)、M 2(5*35)、M 3(35*4)和 M4(4*25)，则最优的计算次序为_。（分数：1.00）A.(M1*M2)*M3)*M4B.(M1*M2)*(M3*M4)C.(M1*(M2*M3)*M4D.M1*(M2*(M3*M4)6.若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为_。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2n)D.O
3、(n2)7.下面 C程序段中 count+语句执行的次数为_。for (int i=1; i=11; i*=2)for(int j=1；j=i；j+)count+;（分数：1.00）A.15B.16C.31D.328.若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，_。（分数：1.00）A.插入和删除操作的时间复杂度都为 O(1)B.插入和删除操作的时间复杂度都为 O(n)C.插入操作的时间复杂度为 O(1)，删除操作的时间复杂度为 O(n)D.插入操作的时间复杂度为 O(n)，删除操作的时间复杂度为 O(1)9.一个算法是对某类给定问题求
4、解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有_特性。（分数：1.00）A.有穷性B.可行性C.确定性D.健壮性10.现有 16枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较_次才能够找出该假币。（分数：1.00）A.3B.4C.5D.611.某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n 为问题的规模，a、b、c 和 d为常数，用 O表示其渐近时间复杂度为_。（分数：1.00）A.O(n2)B.O(n)C.O(nlgn)D.O(1)斐波那契(Fibonacci)数列可以递
5、归地定义为：（分数：2.00）A.5B.6C.7D.8A.动态规划B.分治C.回溯D.分支限界12._不能保证求得 0-1背包问题的最优解。（分数：1.00）A.分支限界法B.贪心算法C.回溯法D.动态规划策略13.某算法的时间复杂度可用递归式 表示，若用 表示该算法的渐进时间复杂度的紧致界，则正确的是_。（分数：1.00）A.B.C.D.14.给定一组长度为 n的无序序列，将其存储在一维数组 a0n-1中。现采用如下方法找出其中的最大元素和最小元素：比较 a0和 an-1，若 a0较大，则将二者的值进行交换；再比较 a1和 an-2，若 a1较大，则交换二者的值；然后依次比较 a2和 an-
6、3、a3和 an-4、.，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前 n/2个元素中查找最小元素，在后 n/2个元素查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是_。（分数：1.00）A.动态规划法B.贪心法C.分治法D.回溯法二、案例分析试题(总题数：4，分数：60.00)15.阅读下列说明，回答问题。说明某餐厅供应各种标准的营养套餐。假设菜单上共有 n项食物 m1，m 2，.，m n，每项食物 mi的营养价值为vi，价格为 Pi，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M营养价值最大的
7、套餐。问题 1 下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。n：总食物项数。v：营养价值组，下标从 1n，对应第 1到第 n页食物的营养价值。p：价格数组，下标从 1n，对应第 1到 n项食物的价格。M：总标准即套餐的价格不超过 M。x：解向量(数组)，下标从 1n，其元素值为 0或 1，其中元素值为 0表示对应的食物不出现在套餐中，元素值为 1表示对应的食物出现在套餐中。nv:n+1行 M+1列的二维数组，其中行和列的下标均从 0开始，nvij表示由前 i项食物组合且价格不超过项 j套餐的最大营养价值。问题最终要求的套餐的最大
8、营养价值为 nvnM。伪代码如下：MaxNutrientValue(n,v,p,M,x)1 for i=0 to n2 nvi0=03 for j=1 to M4 nv0j =05 for i=1 to n6 for j=1 to M7 if j pi/若食物 mi不能加入到套餐中8 nvi jl =nvi-1j9 else if (1) 10 nvij =nvi-1j11 else12 nvi j =nvi-1j-pi+vi13 j=M14 for i=n downto 115 if (2) 16 xi =017 else18 xi =119 (3) 20 return x and nvn
9、M问题 2 现有 5项食物， 每项食物的营养价值和价格如表 9.3所示。表 9.3食物营养价值及价格表编码 营养价值 价格m1 200 50m2 180 30m3 225 45m4 200 25m5 50 5若要求总价格不超过 100的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最大营养价值为 (5) 。问题 3 问题 1中伪代码的时间复杂度为 (6) (用 O符号表示)。（分数：15.00）_16.阅读下列说明，回答问题 1至问题 3。说明快速排序是一种典型的分治算法。采用快速排序对数组 APr排序的 3个步骤如下。(1)分解：选择一个枢轴(pivot)元
10、素划分数组。将数组 Apr划分为两个子数组(可能为空)Apg-1和 Aq+1，使得 Ag大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。(2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。(3)合并：快速排序在原地排序，故不需合并操作。问题 1 下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。A：待排序数组。p，r：数组元素下标，从 p到 r。q：划分的位置。x：枢轴元素。i：整型变量，用于描述数组下标。下标小于或等于 i的元素的值小于或等于枢轴元素的值。j：循环控制变量，表示数组元素下标。QUIC
11、KSORT (A,p， r)if (pr)q = PARTITION(A,p,r)；QUICKSORT(A，p，q-1)；QUICKSORT (A，q+1，r)；PARTITION (A，p，r)x=Ar; i=p-1；for(j=p；jr-1; j+)if(Ajx)i=i+1;交换 Ai和 Aj交换 (1) 和 (2) /注：空(1)和空(2)答案可互换，但两空全部答对方可得分return (3) 问题 2 (1)假设要排序包含 n个元素的数组，清给出在各种不同的划分情况下，快速排序的时间复杂度，用 0记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的
12、 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(
13、A,p,r);(2)随机化快速排序是否能够消除最坏情况的发生? (10) 。(是或否)（分数：15.00）_17.阅读下列说明，回答问题。说明0-1背包问题可以描述为：有 n个物品，对 i=1，2，n，第 i个物品价值为 vi，重量为 wi(vi，和 wi为非负数)，背包容量为 W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即 ，其中，X i0，1，x i=0表示第 i个物品不放入背包，x i=1表示第 i个物品放入背包。问题 1 用回溯法求解此 0-1背包问题，请填充下面伪代码中(1)(4)处空缺。回溯法是一种系统的搜索方法。在确定解空间
14、后，回溯法从根节点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前节点，若扩展该节点己经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的节点。现在假设已经设计了 BOUND(v，w，k，w)函数，其中 v，w，k 和 W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个节点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该节点无需再扩展。下面给
15、出 0-1背包问题的回溯算法伪代码。函数参数说明如下。W:背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X:问题的最优解。变量说明如下。cw：当前的背包重量；cp:当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。BKNAP (W,n,w,v,fw, fp,X)1 cwcp02 (1) 3 fp-14 while true5 while kn and cw+wkW do6 (2) 7 cp cp+vk8 Yk 19 k k+110 if kn then11 if fpcp then12 fp cp13 fw ew14
16、 k n15 X Y16 else Y(k) 017 while BOUND(cp, cw, k, W) fp do18 while k0 and Y(k) 1 do19 (3) 20 if k=0 then return21 Yk022 cwcw-wk23 cp cp-vk24 (4) 问题 2 考虑表 9.2的实例，假设有 3个物品，背包容量为 22。图 9.1中是根据上述算法构造的搜索树，其中节点的编号表示了搜索树生成的顺序，边上的数字 1/0分别表示选择/不选择对应物品。除了根节点之外，每个左孩子节点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子节点旁边的数字表示扩展了
17、该节点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。表 9.2 0-1 背包问题实例物品 1 物品 2 物品 3重量 15 10 10价值 30 18 17单位价值 2 1.8 1.7（分数：15.00）_18.阅读下列说明，回答问题。说明现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各项点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点
18、的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各项点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。问题 1 本题采用 Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图 G的顶点集合为V=1，2，.，n)，W=W ij， n*n为权重矩阵。设 为从顶点 i到顶点，的一条最短路径的权重。当 k=0时，不存在中间顶点，因此 。当 k0 时，该最短路径上所有的中间顶点均属于集合 1，2，k，若中间顶点包括顶点 k，则 ，若中间顶点不包括顶点 k，则 。于是得到如下递归式。因为对于任意路径，所有的中间顶点都在集合 1，
19、2，n 内，因此矩阵 n*n给出了任意两个顶点之间的最短路径，即对所有 表示顶点 i到顶点，的最短路径。下面是求解该问题的伪代码，请填充其中空缺的(1)(6)处。伪代码中的主要变量说明如下。W：权重矩阵；n：图的顶点个数；SP：最短路径权重之和数组，SPi表示顶点 f到其他各顶点的最短路径权重之和，i 从 1到 n；min_SP：最小的最短路径权重之和；min_v：具有最小的最短路径权重之和的顶点；i：循环控制变量；j：循环控制变量；k：循环控制变量；LOCATE-SHOPPINGMALL (W, n)1 D(0)=W2 for (1) 3 for i=1 to n4 for j = 1 to
20、 n5 （分数：15.00）_软件设计师-算法设计和分析(一)答案解析(总分：76.00，做题时间：90 分钟)一、综合知识试题(总题数：15，分数：16.00)1.归并排序采用的算法设计方法属于_。（分数：1.00）A.归纳法B.分治法 C.贪心法D.回溯方法解析：要点解析 归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有，n个记录，则可看成是 n个有序的子序列，每个子序列的长度为 1，然后两两归并，得到n/2个长度为 2或 1的有序子序列；再两两归并，如此重复，直至得到一个长度为 n的有序序列为止，这种排序方法称为2一路归并排序。将待排序元素分成大小大致相同的两个
21、子集，分别对两个子集进行排序，最终将排好序的子集合并成所要求的排好序的集合。符合分治算法设计的思想。2.以下的算法设计方法中，_以获取问题最优解为目标。（分数：1.00）A.回溯方法B.分治法C.动态规划 D.递推解析：要点解析 回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了不满足问题规模要求外，能满足所有其他要求，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解
22、的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。动态规划算法通常用于求解具某种最优性质的问题。如果最优解有多个，动态规划算法能找出其中的一个最优解。递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为 N的解，当 N=1时，解或为已知，或能非常方便地得到。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为 i-1的解后，由问题的递推性质，能从已求得的规模为 1，2，i-1 的一系列解，构造出问题规模为i的解。这样，程序可从 i=0或 i=1出发，重复地，由已知至 i-1规模的解，通过递推，获得规模为 i的解，直至得到规模为 N的解。3.设
23、某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n0)及 T(0)=1，则该算法的时间复杂度为_。（分数：1.00）A.O(lgn)B.O(nlgn)C.O(n)D.O(n2) 解析：分析 本题考查简单的时间复杂度问题。由题 T(n)=T(n-1)+n(n0)及 T(0)=1，只是求 1、1、2、3、n 的和，即 1+n(n+1)/2，显然，时间复杂度为 O(n2)。4.若某算法在问题规模为 n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为_。（分数：1.00）A.O(n)B.O(n2) C.O(log2n)D.O(nlog2n)解析：要点解析 根据题中给出的递归定
24、义式进行推导，可得 T(n)=n+n-1+2+1，因此时间复杂度为O(n2)。5.用动态规划策略求解矩阵连乘问题 M1*M2*M3*M4，其中 M1(20*5)、M 2(5*35)、M 3(35*4)和 M4(4*25)，则最优的计算次序为_。（分数：1.00）A.(M1*M2)*M3)*M4B.(M1*M2)*(M3*M4)C.(M1*(M2*M3)*M4 D.M1*(M2*(M3*M4)解析：要点解析 由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，最优的计算次序是使得矩阵连乘中乘法次数最少的次序。选项 A，乘法的次数为 20*35*5+20*4*35+20*25*4=
25、6700选项 B，乘法的次数为 20*35*5+35*25*4+20*25*35=24500选项 C，乘法的次数为 5*4*35+20*4*5+20*25*4=3100选项 D，乘法的次数为 35*25*4+5*25*35+20*25*5=10375可见，选项 C中的计算次序为最优的计算次序。6.若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为_。（分数：1.00）A.O(log2n)B.O(n)C.O(nlog2n) D.O(n2)解析：分析 快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
26、其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序最好的情况就是第一个元素为中问值，那么最好的时间复杂度为 O(nlog2n)。7.下面 C程序段中 count+语句执行的次数为_。for (int i=1; i=11; i*=2)for(int j=1；j=i；j+)count+;（分数：1.00）A.15 B.16C.31D.32解析：要点解析 第 1轮循环，i=1，count+执行 1次，然后 i=2；第 2轮循环，i=2，count+执行 2次，然后 i=4；第 3轮循环，i
27、=4，count+执行 4次，然后 i=8；第 4轮循环，i=8，count+执行 8次，然后 i=16，i11，不满足循环条件，循环结束。可以计算 count+语句执行的次数为：1+2+4+8=15。8.若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，_。（分数：1.00）A.插入和删除操作的时间复杂度都为 O(1)B.插入和删除操作的时间复杂度都为 O(n)C.插入操作的时间复杂度为 O(1)，删除操作的时间复杂度为 O(n) D.插入操作的时间复杂度为 O(n)，删除操作的时间复杂度为 O(1)解析：要点解析 设尾指针的单项循环链表(
28、不含头结点)如下图所示。*设节点的指针域为 next，新节点的指针为 s，则在尾指针所指节点后插入节点的操作为：s-next=t-next；t-next=s；t=s;也就是插入操作的时间复杂度为 O(1)。要删除尾指针所指结点，必须通过遍历操作找到尾结点的前驱结点，其操作序列如下：if (t-next=t) free(t);else p=t-next；while (p-next!=t)p=p-next；p-next=t-next;free (t)；t=p;也就是说，删除操作的时间复杂度为 O(n)。9.一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执
29、行有限次来实现，这句话说明算法具有_特性。（分数：1.00）A.有穷性B.可行性 C.确定性D.健壮性解析：分析 本题考查算法的属性。算法的可行性指的是一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。10.现有 16枚外形相同的硬币，其中有一枚比真币的重量轻的假币，若采用分治法找出这枚假币，至少比较_次才能够找出该假币。（分数：1.00）A.3B.4 C.5D.6解析：要点解析 16 枚硬币分成两份(各 8枚)，选出质量轻的那 8枚；继续分成两份(各 4枚)，选出质量轻的那 4枚；继续分成两份(各 2枚)，选出质量轻的那两枚；继续分成两份(各 1枚)，选出质
30、量轻的那一枚，即为假币。故采用分治法共需比较 4次。11.某算法的时间复杂度表达式为 T(n)=an2+bnlgn+cn+d，其中，n 为问题的规模，a、b、c 和 d为常数，用 O表示其渐近时间复杂度为_。（分数：1.00）A.O(n2) B.O(n)C.O(nlgn)D.O(1)解析：要点解析 本题考查时间复杂度的计算方法。本题中的时间复杂度不仅与输入规模有关，还与系数 a、b、c 和 d有关，因此对该函数进行进一步的抽象，仅考虑运行时间的增长率或称为增长的量级，如忽略上式中的低阶项和高阶项的系数，因此可以得到本题的渐进时间复杂度是 O(n2)。斐波那契(Fibonacci)数列可以递归地
31、定义为：（分数：2.00）A.5B.6C.7 D.8解析：A.动态规划B.分治 C.回溯D.分支限界解析：分析 第(4)题是很简单的，求解 F(5)简单写一下就知道是执行 7次“+”运算。分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的问题，以便各个击破，分而治之。这样运算很明显是符合分治法思想。12._不能保证求得 0-1背包问题的最优解。（分数：1.00）A.分支限界法B.贪心算法 C.回溯法D.动态规划策略解析：要点解析 贪心法在解决问题的策略上仅根据当前已有的信息做出选择，而且一旦做出选择，不管将来有什么结果，这个选择都不会改变。也就是说，贪心法并不是从整体最优考虑
32、，它所做出的选择只是在某种意义卜的局部最优。这种局部最优选择并不能保证总能获得全局最优解，但通常能得到较好的近似最优解。13.某算法的时间复杂度可用递归式 表示，若用 表示该算法的渐进时间复杂度的紧致界，则正确的是_。（分数：1.00）A.B. C.D.解析：要点解析 采用主定理来求解递归式。a=2，b=2，f(n)=nlgn，log ba=1，*，其中 0.2，属于主定理的情况(3)，因此有*14.给定一组长度为 n的无序序列，将其存储在一维数组 a0n-1中。现采用如下方法找出其中的最大元素和最小元素：比较 a0和 an-1，若 a0较大，则将二者的值进行交换；再比较 a1和 an-2，若
33、 a1较大，则交换二者的值；然后依次比较 a2和 an-3、a3和 an-4、.，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前 n/2个元素中查找最小元素，在后 n/2个元素查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是_。（分数：1.00）A.动态规划法B.贪心法C.分治法 D.回溯法解析：分析 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的问题，以便各个击破，分而治之。由题目可知，查找最火元素和最小元素的方法显然是分治法思想。二、案例分析试题(总题数：4，分数：60.00)15.阅读下列说明，回答问题。说明某餐厅
34、供应各种标准的营养套餐。假设菜单上共有 n项食物 m1，m 2，.，m n，每项食物 mi的营养价值为vi，价格为 Pi，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M营养价值最大的套餐。问题 1 下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下。n：总食物项数。v：营养价值组，下标从 1n，对应第 1到第 n页食物的营养价值。p：价格数组，下标从 1n，对应第 1到 n项食物的价格。M：总标准即套餐的价格不超过 M。x：解向量(数组)，下标从 1n，其元素值为 0或 1，其中元素值为 0表
35、示对应的食物不出现在套餐中，元素值为 1表示对应的食物出现在套餐中。nv:n+1行 M+1列的二维数组，其中行和列的下标均从 0开始，nvij表示由前 i项食物组合且价格不超过项 j套餐的最大营养价值。问题最终要求的套餐的最大营养价值为 nvnM。伪代码如下：MaxNutrientValue(n,v,p,M,x)1 for i=0 to n2 nvi0=03 for j=1 to M4 nv0j =05 for i=1 to n6 for j=1 to M7 if j pi/若食物 mi不能加入到套餐中8 nvi jl =nvi-1j9 else if (1) 10 nvij =nvi-1j1
36、1 else12 nvi j =nvi-1j-pi+vi13 j=M14 for i=n downto 115 if (2) 16 xi =017 else18 xi =119 (3) 20 return x and nvn M问题 2 现有 5项食物， 每项食物的营养价值和价格如表 9.3所示。表 9.3食物营养价值及价格表编码 营养价值 价格m1 200 50m2 180 30m3 225 45m4 200 25m5 50 5若要求总价格不超过 100的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最大营养价值为 (5) 。问题 3 问题 1中伪代码的时间
37、复杂度为 (6) (用 O符号表示)。（分数：15.00）_正确答案：(问题 1 (1)nvi-1j=nvi-1j-pi+vi (2)nvij=nvi-1j (3)j=jpi问题 2 (4) m2，m 3，m 4 (5)605问题 3 (6)O(n*M)解析：分析 本题考查动态规划法。题目要求在 n种食物中，找出 x种食物，食物总价不超过 M，且食物的营养价值要尽可能大，这样的问题显然要用动态规划法来将问题分解，进而简化。动态规划法的基本理念是将问题拆解为很多相同的子问题，在求解子问题时，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，最后再从数组中将最终结果导出，这样有
38、效地缩短了解题的时间。而在本题中伪代码正是以此方法求解，将复杂的问题分解成了很多个子问题，而子问题的求解又是建立在之前子问题的结果基础之前，nv 正是用于记录子问题结果的数组。值得一提的是本题第(3)问的出题形式，形式比较新颖，但实际上非常简单，从程序循环层数即可看出复杂度。接下来对代码进行详细16.阅读下列说明，回答问题 1至问题 3。说明快速排序是一种典型的分治算法。采用快速排序对数组 APr排序的 3个步骤如下。(1)分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apg-1和 Aq+1，使得 Ag大于等于 Apq-1中的每个元素，小于 Aq+1r
39、中的每个元素。q 的值在划分过程中计算。(2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。(3)合并：快速排序在原地排序，故不需合并操作。问题 1 下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下。A：待排序数组。p，r：数组元素下标，从 p到 r。q：划分的位置。x：枢轴元素。i：整型变量，用于描述数组下标。下标小于或等于 i的元素的值小于或等于枢轴元素的值。j：循环控制变量，表示数组元素下标。QUICKSORT (A,p， r)if (pr)q = PARTITION(A,p,r)；QUICKSORT(A，p，q-1)；QUICKSOR
40、T (A，q+1，r)；PARTITION (A，p，r)x=Ar; i=p-1；for(j=p；jr-1; j+)if(Ajx)i=i+1;交换 Ai和 Aj交换 (1) 和 (2) /注：空(1)和空(2)答案可互换，但两空全部答对方可得分return (3) 问题 2 (1)假设要排序包含 n个元素的数组，清给出在各种不同的划分情况下，快速排序的时间复杂度，用 0记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)问题 3 (1)待排序数组是否能被较均匀地
41、划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码。利用原有的快速排序的划分操作，请填充其中的空缺处。其中，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) 。(是或否)（分数：15.00）_正确答案：(问题 1 (1)A
42、i+1 (2)Ar(3)(i+1)或+i (其中(1)和(2)的内容可互换)或者(1)A+i (2)Ar或 Aq (3)i(其中(1)和(2)的内容可互换)问题 2 (4) O(nlog2n) (5) O(nlog2n) (6)O(n2)(7)最坏问题 3 (8)Ai (9)Ar(其中(8)和(9)可互换) (10)否)解析：分析 本题是一个算法分析题，一方而考查考生对分治算法的快速排序的理解，另一方面考查考生对伪代码、快速排序的复杂度的掌握，做题的关键是要读懂题干，理解题干中对算法的描述。问题 1 本问题考查伪代码。题中 QUICKSORT(A，p，r)函数是采用了递归方法来处理的。快速排序
43、的核心就是找到可划分的位置 g，当找到划分位置 q以后，再用递归的方法分别对 QUICKSORT(A,p，q-1)和QUICKSORT(A，q+1，r)继续找可划分位置。函数 PARTITION(A，p，r)的功能是求划分位置。在PARTITION(A，p，r)中，是把最后一个元素作为枢轴元素，x=Ar; for 循环语句用于实现一趟划分，比x小的则在 Ai+1的前头，比 x大的则在 Ai的后头。当循环结束以后，将枢轴元素与 Ai+1元素对换，对换以后 Ai+1这个元素的位置就确定了，将它返回作为前段数组的结束位置，作为后段数组的起始地址。所以第(1)空填 Ai+1，第(2)空填 Ar，第(3
44、)空填(i+1)或+i。问题 2 本问题考查快速排序的时间复杂度。快速排序的时间主要耗费在划分操作上，对长度为 k的区间进行划分，共需要 k-1次关键字的比较。时间复杂度都分三种情况：最坏情况、平均情况和最好情况。最坏情况是每次划分选取的基准都是当前无序区中关键字最小 f或最大)的记录，划分结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做 n-1次划分，第 i次划分开始时区间长度为 n-i+1，所需的比较次数为 n-i(1in-1)，故总的比较次数达到最大值：n(n-1)/2。这样，每次取当
45、前无序区的第1个记录为基准，那么当文件的记录已按递增或递减排列时，每次划分所取的基准就是当前无序区中关键字最小(或最大)的记录，因此快速排序所需的比较次数最多，此时时间复杂度是 O(n2)。最好情况下，每次划分所需的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等，总的关键字比较次数为：O(nlog 2n)。就平均性能而言，它是基于关键字比较的内部排序算法中速度最快的，快速排序因此得名，它的平均时间复杂度为：O(nlog 2n)。若 n个元素都具有相同的值，无论怎么选择，所选取的基准都是当前无序区中关键字最大(或最小)的记录，属于最坏情况。问题 3 本问题
46、考查快速排序随机化排序方法。随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大提高了，尤其是对初始化有序的文件，一般不可能导致最坏情况发生。算法的随机化不仅仅适用于快速排序，也适用于其他需要数据随机分布的算法。但是也不能绝对消除最坏情况的发生，所以第(10)空填：否。17.阅读下列说明，回答问题。说明0-1背包问题可以描述为：有 n个物品，对 i=1，2，n，第 i个物品价值为 vi，重量为 wi(vi，和 wi为非负数)，背包容量为 W(W为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即 ，其中，X i0，1，x i=0表示第 i个物品不放入背包，x i=1表示
