1、软件设计师-11 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：17，分数：35.00)1.以下关于渐近符号的表示中，不正确的是_。 A.n2=(n 2) B.n2=O(n2) C.n2=O(n) D.n3=O(n3)（分数：2.00）A.B.C.D.2.某算法的时间复杂度可用递归式 （分数：2.00）A.B.C.D.3.某算法的时间复杂度可用递归式 表示，若用 表示，则正确的是_。 A B(n 2 ) C(n) D （分数：2.00）A.B.C.D.4.对 n 个元素的有序表 A1n进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所
2、进行比较的表中元素个数的期望值)为_。 A.n B.(n+1)/2 C.log2n D.n2（分数：2.00）A.B.C.D.5.对 n 个元素值分别为-1、0 或 1 的整型数组 A 进行升序排序的算法描述如下：统计 A 中-1、0 和 1 的个数，设分别为 n 1 、n 2 和 n 3 ，然后将 A 中的前 n 1 个元素赋值为-1，第 n 1 +1 到 n 1 +n 2 个元素赋值为 0，最后 n 3 个元素赋值为 1。该算法的时间复杂度和空间复杂度分别为_。 A.(n)和 (1) B.(n)和 (n) C.(n 2)和 (1) D.(n 2)和 (n)（分数：2.00）A.B.C.D.
3、6.对于关键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59 所在散列表中的地址为_。（分数：2.00）A.6B.7C.8D.97.用插入排序和归并排序算法对数组3，1，4，1，5，9，6，5进行从小到大的排序，则分别需要进行_次数组元素之间的比较。（分数：2.00）A.12，14B.10，14C.12，16D.10，168.某一维数组中依次存放了数据元素 15、23、38、47、55、62、88、95、102、123，采用折半(二分)法查找元素
4、 95 时，依次与_进行了比较。（分数：2.00）A.62、88、95B.62、95C.55、88、95D.55、959.递增序列 A(a 1 ，a 2 ，a n )和 B(b 1 ，b 2 ，b n )的元素互不相同，若需将它们合并为一个长度为 2n 的递增序列，则当最终的排列结果为_时，归并过程中元素的比较次数最多。（分数：2.00）A.a1，a2，an，b1，b2，bnB.b1，b2，bn，a1，a2，anC.a1，b1，a2，b2，ai，bi，an，bnD.a1，a2，ai/2，b1，b2，bi/2，ai/2+1，ai/2+2，an，bi/2+1，bn10.现要对 n 个实数(仅包含正
5、实数和负实数)组成的数组 A 进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为_。 i=0; j=n-1; while ij do while Ai0 do i=i+1; while Aj0 do j =j-1; if ij do 交换 Ai和 Aj;（分数：2.00）A.(n)和 (n)B.(1)和 (n)C.(n)和 (1)D.(1)和 (1)11.迪杰斯特拉(Diikstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于_策略的算法。（分数：2.00）A.分治B.动
6、态规划C.贪心D.回溯12.在有 n 个无序无重复元素值的数组中查找第 i 小的数的算法描述如下：任意取一个元素 r，用划分操作确定其在数组中的位置，假设元素 r 为第 k 小的数。若 i 等于 k，则返回该元素值；若 i 小于 k，则在划分的前半部分递归进行划分操作找第 i 小的数；否则在划分的后半部分递归进行划分操作找第 k-i 小的数。该算法是一种基于_策略的算法。（分数：2.00）A.分治B.动态规划C.贪心D.回溯13.要在 88 的棋盘上摆放 8 个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用_来实现。（分数：2.00）
7、A.分治法B.动态规划法C.贪心法D.回溯法14.分治算法设计技术_。（分数：2.00）A.一般由 3 个步骤组成：问题划分、递归求解、合并解B.一定用递归技术来实现C.将问题划分为 k 个规模相等的子问题D.划分代价很小而合并代价很大15.用动态规划策略求解矩阵连乘问题 M 1 *M 2 *M 3 *M 4 ，其中 M 1 (20*5)、M 2 (5*35)、M 3 (35*4)和 M 4 (4*25)，则最优的计算次序为_。（分数：2.00）A.(M1*M2)*M3)*M4B.(M1*M2)*(M3*M4)C.(M1*(M2*M3)*M4D.M1*(M2*(M3*M4)16._不能保证求得
8、 0-1 背包问题的最优解。（分数：2.00）A.分支限界法B.贪心算法C.回溯法D.动态规划策略某货车运输公司有一个中央仓库和 n 个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点 i 和 j 之间运输货物存在费用 C ij 。为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地 1，然后选择离运输目的地 1 最近的运输目的地 2每次在需访问的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。该算法采用了_算法设计策略，其时间复杂度为_。（分数：3.00）A.分治B.动态规划
9、C.贪心D.回溯(2). A.(n 2) B.(n) C.(nlgn) D.(1)（分数：1.50）A.B.C.D.二、论述题(总题数：6，分数：65.00)阅读下列说明和 C 代码，回答下面问题。 说明 用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 i 个作业的时间分别为 a i 和 b i 。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间(所有作业被处理的
10、时间之和)最少。 算法步骤如下。 (1)确定候选解上界为最短的单台处理机处理所有作业的完成时间 m： （分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空白处。（分数：5.00）_(2).根据以上 C 代码，算法的时间复杂度为_(用 O 符号表示)。（分数：5.00）_(3).考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如表所示。该实例的最优解为_，最优解的值(即最短处理时间)为_。最优解用(x 1 ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 )表示，其中若第 i个作业在 A 上处理，则 x i =1，否则 x i =2。如(1，1，1，1，2，2)表示
11、作业 1、2、3 和 4 在 A 上处理，作业 5 和 6 在 B 上处理。 各个作业在两台处理机上的处理时间 作业 1 作业 2 作业 3 作业 4 作业 5 作业 6 处理机 A 2 5 7 10 5 2 处理机 B 3 8 4 11 3 4 （分数：5.00）_17.阅读下列说明和 C 代码，将应填入空白处的语句补充完整。 说明 设某一机器由 n 个部件组成，每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 W ij 和价格 C ij 。设计一个算法，求解总价格不超过上限 cc 的最小重量的机器组成。 采用回溯法来求解该问题。 首先定义解空间。解空间由长
12、度为 n 的向量组成，其中每个分量取值来自集合1，2，m，将解空间用树形结构表示。 接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第 1 个部件从第 1 个供应商处购买，得到一个新节点。判断当前的机器价格(C 11 )是否超过上限(cc)，重量(W 11 )是否比当前已知的解(最小重量)大，若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第 2 个部件从第 1 个供应商处购买，得到一个新节点。同样判断当前的机器价格(C 11 +C 21 )是
13、否超过上限(cc)，重量(W 11 +W 21 )是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。 下面是该算法的 C 语言实现。 (1)变量说明 n：机器的部件数 m：供应商数 cc：价格上限 w：二维数组，wij表示第 j 个供应商供应的第 i 个部件的重量 c：二维数组，cij表示第 j 个供应商供应的第 i 个部件的价格 bestW：满足价格上限约束条件的最小机器重量 bestC：最小重量机器的价格 bestX：
14、最优解，一维数组，bestXi表示第 i 个部件来自哪个供应商 cw：搜索过程中机器的重量 cp：搜索过程中机器的价格 x：搜索过程中产生的解，xi表示第 i 个部件来自哪个供应商 i：当前考虑的部件，从 0 到 n-1 j：循环变量 (2)函数 backtrack int n=3; int m=3; int cc=4; int w33=1, 2, 3, 3, 2, 1, 2, 2, 2; int c33=1, 2, 3, 3, 2, 1, 2, 2, 2; int bestW=8; int bestC=0; int bestX3=0, 0, 0; int cw=0; int cp=0; in
15、t X3=0, 0, 0; int backtrack(int i) int j=0; int found=0; if(in-1) /*得到问题解*/ bestW=cw; bestC=cp; for(j=0; jn; j+) _; return 1; if(cp=cc) /*有解*/ found=1; for(j=0; _; j+) /*第 i 个部件从第 j 个供应商购买*/ _; cw=cw+wij; cp=cp+ciij; if(cp=cc /*回溯*/ cw=cw-wij; _; return found; （分数：5.00）_阅读下列说明和 C 代码，回答下面问题。 说明 某应用中需
16、要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m-1、m-2个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元素值等于 4 的元素个数有 3 个，则 4 应该在输出元素序列的第 10 个位置、第 9 个位置和第 8 个位置上。算法具体的步骤如下。 步骤 1：统计每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。 下面是该排序算
17、法的 C 语言实现。 (1)常量和变量说明 R：常量，定义元素取值范围中的取值个数，如上述应用中 R 值应取 6 i：循环变量 n：待排序元素个数 a：输入数组，长度为 n b：输出数组，长度为 n c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数 (2)函数 sort void sort(intn, int a, intb) intcR, i; for (i=0; i_; i+) ci=0; for(i=0; in; i+) cai=_; for(i=1; iR; i+) ci=_; for(i=0; in; i+) bcai-1=_; cai=cai-1; （分数
18、：15.00）(1).根据说明和 C 代码，填充 C 代码中的空缺。（分数：5.00）_(2).根据 C 代码，函数的时间复杂度和空间复杂度分别为_和_(用字母 O 符号表示)。（分数：5.00）_(3).根据以上 C 代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过 100 字)；若不稳定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。（分数：5.00）_阅读下列说明和 C 代码，回答下面问题。 说明 堆数据结构定义如下。 对于 n 个元素的关键字序列a 1 ，a 2 ，a n ，当且仅当满足下列关系时称其为堆。 在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素
19、为最小元素，则称为小顶堆。堆常用完全二叉树表示，下图是一个大顶堆的例子。 （分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空白处。（分数：5.00）_(2).根据以上 C 代码，函数 heapMaximum，heapExtractMax 和 maxHeaplnsert 的时间复杂度的紧致上界分别为_、_和_(用 O 符号表示)。（分数：5.00）_(3).若将元素 10 插入到堆 A=(15，13，9，5，12，8，7，4，0，6，2，1)中，调用 maxHeaplnsert 函数进行操作，则新插入的元素在堆 A 中第_个位置(从 1 开始)。（分数：5.00）_阅读下
20、列说明，回答下面问题。 说明 现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其他各项点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各项点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。（分数：10.00）(1).本题采用 Floyd-Warshall 算法求解任意两个顶
21、点之间的最短路径。已知图 G 的顶点集合为V=1，2，n，W=W ij n*n 为权重矩阵。设 d (k) ij =从顶点 i 到顶点 j 的一条最短路径的权重。当k=0 时，不存在中间顶点，因此 d (0) ij =w ij ；当 k0 时，该最短路径上所有的中间顶点均属于集合1，2，k，若中间顶点包括顶点 k，则 d (k) ij =d (k-1) ik +d (k-1) kj ，若中间顶点不包括顶点则 d (k-1) ij =d (k-1) i ，于是得到如下递归式。 因为对于任意路径，所有的中间顶点都在集合1，2，n内，因此矩阵 D (n) =d (n) ij n*n 给出了任意两个顶
22、点之间的最短路径，即对所有 i，jV，d (n) ij 表示顶点 i 到顶点 j 的最短路径。 下面是求解该问题的伪代码，请填充其中空缺处。伪代码中的主要变量说明如下。 W：权重矩阵 n：图的顶点个数 SP：最短路径权重之和数组，SPi表示顶点 i 到其他各顶点的最短路径权重之和，i 从 1 到 n min SP：最小的最短路径权重之和 min v：具有最小的最短路径权重之和的顶点 i：循环控制变量 i：循环控制变量 k：循环控制变量 LOCATE -SHOPPINGNALL(W, n) D (0) =W for _ for i=0 to n for j =1 to n if （分数：5.00
23、）_(2).第 1 题中伪代码的时间复杂度为_(用 O 符号表示)。（分数：5.00）_18.阅读以下说明和 C 程序，将应填入空白处的字句。 说明 现有 n(n1000)节火车车厢，顺序编号为 1、2、3、n，按编号连续依次从 A 方向的铁轨驶入，从 B方向铁轨驶出，一旦车厢进入车站(Station)就不能再回到 A 方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。 （分数：5.00）_软件设计师-11 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：17，分数：35.00
24、)1.以下关于渐近符号的表示中，不正确的是_。 A.n2=(n 2) B.n2=O(n2) C.n2=O(n) D.n3=O(n3)（分数：2.00）A.B.C. D.解析：C 选项中的 n 2 与 O(n)，明显不在一个数量级之上，所以不对等。2.某算法的时间复杂度可用递归式 （分数：2.00）A. B.C.D.解析：在本题中，我们关键要理解算法的渐进紧致界的概念，举个例子来说吧，假设当 NN 0 时，函数f(N)在一个常数因子范围内等于 g(N)，则称 g(n)是 f(n)的一个渐进紧致界。 3.某算法的时间复杂度可用递归式 表示，若用 表示，则正确的是_。 A B(n 2 ) C(n)
25、D （分数：2.00）A. B.C.D.解析：4.对 n 个元素的有序表 A1n进行顺序查找，其成功查找的平均查找长度(即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值)为_。 A.n B.(n+1)/2 C.log2n D.n2（分数：2.00）A.B. C.D.解析：本题主要考查顺序查找。 使用顺序查找时，如果需要找的元素在第 1 个位置，则只需要比较 1 次；而元素在第 2 个位置，需要比较2 次；以此类推，待查找元素在第 n 个位置时，需要查找 n 次。题目给出条件，待查找元素在每个位置出现的概率相等，所以平均查找长度为：(1+2+3+n)/n=(n+1)/2。5.
26、对 n 个元素值分别为-1、0 或 1 的整型数组 A 进行升序排序的算法描述如下：统计 A 中-1、0 和 1 的个数，设分别为 n 1 、n 2 和 n 3 ，然后将 A 中的前 n 1 个元素赋值为-1，第 n 1 +1 到 n 1 +n 2 个元素赋值为 0，最后 n 3 个元素赋值为 1。该算法的时间复杂度和空间复杂度分别为_。 A.(n)和 (1) B.(n)和 (n) C.(n 2)和 (1) D.(n 2)和 (n)（分数：2.00）A. B.C.D.解析：时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的
27、操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模 n 的某个函数 T(n)。由于许多情况下要精确计算 T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下。 如果存在两个常数 c 和 m，对于所有的 n，当 nm 时有 f(n)cg(n)，则有 f(n)=O(g(n)。也就是说，随着 n 的增大，f(n)渐进地不大于 g(n)。例如，一个程序的实际执行时间为 T(n)=3n 3 +2n 2 +n，则 T(n)=O(n 3 )。 在本题中，根据题目的描述，我们可以知道，遍历完整个数组中的元素，和修改数组中各元素的值都需要时
28、间 n，因此是 2n，那么该算法的时间复杂度为 O(n)。 空间复杂度是指程序运行从开始到结束所需的辅助存储量，在本题中，只需要辅助存储量来存储统计的元素个数，因此其空间复杂度为 O(1)。6.对于关键字序列(26，25，72，38，8，18，59)，采用散列函数 H(Key)=Key mod 13 构造散列表(哈希表)。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则关键字 59 所在散列表中的地址为_。（分数：2.00）A.6B.7C.8D.9 解析：根据题目给出的散列函数我们可以分别计算出关键字(26，25，72，38，8，18，59)对应的散列地址为(0，12，7，12
29、，8，5，7)。 开放定址处理冲突的基本思路是，为发生冲突的关键字在散列表中寻找另一个尚未占用的位置，其解决冲突能力的关键取决于探测序列，在本题中，题目告诉我们采用顺序探查法，即增量为 1 的线性探测法，在该线性探测法中，设 H i (1im)为第 i 次在散列表中探测的位置，其中增量序列为1，2，3，4，5，m-1则有： H i =(H(Key)+i)%m 其中 H(Key)为散列函数，m 为散列表长度，i 为增量序列。而本题中 m=13，因此本题的散列表构造过程如下。 (1)关键字 26、25、72 由散列函数 H(key)得到没有冲突的散列地址而直接存入散列表中。 (2)计算关键字 38
30、 的散列地址为 12，发生冲突(与关键字 25 冲突)，其第 1 次线性探测地址为(12+1)%13=0，但仍然发生冲突(与关键字 26 冲突)，因此需要进行第 2 次线性探测，其地址为(12+2)%13=1，这时没有发生冲突，即将 38 存入地址为 1 的空间。 (3)接着将关键字 8、18 计算其散列地址，由于没有冲突，即分别存入散列地址为 8 和 5 的空间中。 (4)计算关键字 59 的散列地址为 7，发生冲突(与关键字 72 冲突)，其第 1 次线性探测地址(7+1)%13=8，但仍然发生冲突(与关键字 8 冲突)，因此需要进行第 2 次线性探测，其地址为(7+2)%13=9，这时没
31、有发生冲突，即将 59 存入地址为 9 的存储空间。 因此本题的答案选 D。7.用插入排序和归并排序算法对数组3，1，4，1，5，9，6，5进行从小到大的排序，则分别需要进行_次数组元素之间的比较。（分数：2.00）A.12，14 B.10，14C.12，16D.10，16解析：插入排序的基本思想是逐个将待排序元素插入到已排序的有序表中。假设 n 个待排序元素存储在数组 Rn+1中(R0预留)，则： (1)初始时数组 R11中只包含元素 R1，则数组 R11必定有序。 (2)从 i=2 到 n，执行步骤(3)。 (3)此时，数组 R 被划分成两个子区间，分别是有序区间 R1i-1和无序区间 R
32、in，将当前无序区间的第 1 个记录 Ri插入到有序区间 R1i中适当的位置上，使 R1i变为新的有序区间。 在实现的过程中，设置监视哨 R0，并从 Ri-1到 R0查找元素 Ri的插入位置。 那么用插入排序对数组3，1，4，1，5，9，6，5进行排序的过程为： 那么整个排序过程需要比较的次数为 12 次。 归并排序的思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其基本步骤如下。 (1)将 n 个元素的待排序序列中每个元素看成有序子序列，对相邻子序列两两合并，则将生成n/2个子有序序列，这些子序列中除了最后一个子序列长度可能小
33、于 2 外，其他的序列长度都等于 2。 (2)对上述n/2个长度为 2 的子序列再进行相邻子序列的两两合并，则产生n/4个子有序序列，同理，只有最后一个子序列的长度可能小于 4。 名 称 监视哨 序 列 说 明 原元素序列：(3)，1，4，1，5，9，6，5 第 1 趟排序：3 (1，3)，4，1，5，9，6，5 1 插入时与 3 比较 1 次 第 2 趟排序：4 (1，3，4)，1，5，9，6，5 4 插入时与 3 比较 1 次 第 3 趟排序：1 (1，1，3，4)，5，9，6，5 1 插入时比较 3 次 第 4 趟排序：5 (1，1，3，4，5)，9，6，5 5 插入时与 4 比较 1
34、次 第 5 趟排序：9 (1，1，3，4，5，9)，6，5 9 插入时与 5 比较 1 次 第 6 趟排序： 6 (1，1，3，4，5，6，9)， 6 插入时与 9 和 5 分别比较 1 次 5 第 7 趟排序：5 (1，1，3，4，5，5，6，9) 5 插入时与 9、6、5 分别比较 1次 (3)第 i 趟归并排序为，对上述n/i个长度为 i 的子序列两两合并，产生n/2i个长度为 2i 的子有序序列。 (4)重复执行此步骤，直到生成长度为 n 的序列为止。 那么用归并排序对数组3，1，4，1，5，9，6，5进行排序的过程为： 名 称 序 列 说 明 原元素序列：3，1，4，1，5，9，6，
35、5 第1 趟排序：1，3，1，4，5，9，5，6 比较4 次 第2 趟排序：1，1，3，4，5，5，6，9 前半部分比较3 次，后半部分比较3 次 第3 趟1，15 分别排序：，3，4，5，5，6，9 与1、1、3、4 比较一次 所以整个排序过程需要比较的次数为 12 次。8.某一维数组中依次存放了数据元素 15、23、38、47、55、62、88、95、102、123，采用折半(二分)法查找元素 95 时，依次与_进行了比较。（分数：2.00）A.62、88、95B.62、95C.55、88、95D.55、95 解析：本题主要考查折半(二分)查找算法。这里首先需要我们能清楚理解该查找算法。
36、在本题中，给出的数据序列为 15、23、38、47、55、62、88、95、102、123，其中有 10 个元素，那么首先进行比较的应该是第 5 个元素，即 55，由于 95 大于 55，那么应该在后半部分进行查找，这时应该与第8 个元素进行比较，刚好是 95，查找成功，然后结束。因此比较的元素有 55 和 95。9.递增序列 A(a 1 ，a 2 ，a n )和 B(b 1 ，b 2 ，b n )的元素互不相同，若需将它们合并为一个长度为 2n 的递增序列，则当最终的排列结果为_时，归并过程中元素的比较次数最多。（分数：2.00）A.a1，a2，an，b1，b2，bnB.b1，b2，bn，a
37、1，a2，anC.a1，b1，a2，b2，ai，bi，an，bn D.a1，a2，ai/2，b1，b2，bi/2，ai/2+1，ai/2+2，an，bi/2+1，bn解析：要将两个有序序列归并为一个有序序列时，当一个序列的最大值小于另一个序列的最小值，这时需要比较的次数最少。当获得新序列后，两个序列的元素交替的情况(如选项 C)下，需比较的次数最多。10.现要对 n 个实数(仅包含正实数和负实数)组成的数组 A 进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为_。 i=0; j=n-1; while ij do while
38、Ai0 do i=i+1; while Aj0 do j =j-1; if ij do 交换 Ai和 Aj;（分数：2.00）A.(n)和 (n)B.(1)和 (n)C.(n)和 (1) D.(1)和 (1)解析：根据程序不难看出，要将负实数位于正实数之前，其实就是对所有元素进行了一次遍历，正实数和负实数互换位置即可，因此其时间复杂度为 O(n)，由于元素 Ai和 Aj互换时，需要一个临时存储空间来存放元素，因此其空间复杂度为 O(1)。11.迪杰斯特拉(Diikstra)算法用于求解图上的单源点最短路径。该算法按路径长度递增次序产生最短路径，本质上说，该算法是一种基于_策略的算法。（分数：2
39、.00）A.分治B.动态规划C.贪心 D.回溯解析：分治法：对于一个规模为 n 的问题，若该问题可以容易地解决(比如说规模 n 较小)则直接解决；否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 动态规划法：这种算法也用到了分治思想，它的做法是将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题。 贪心算法：它是一种不追求最优解，只希望得到较为满意解的方法。贪心算法一般可以快速得到满意的解，因为它省去了为找到最优解而穷尽所有可能所必须耗费的大量时间。贪心算法常以当前情况为基础做最优选
40、择，而不考虑各种可能的整体情况，所以贪心算法不要回溯。 回溯算法(试探法)：它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。其实现一般要用到递归和堆栈。 针对单源最短路径问题，由 Dijkstra 提出了一种按路径长度递增的次序产生各顶点最短路径的算法。若按长度递增的次序生成从源点 s 到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点的最短路径看作是已生成的源点到其自身的长度为 0 的路径)。这是一种典型的贪心策略，就是每递增一次，经过所有可能的源点、目标点的路径都要计算，得出最优。
41、带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。12.在有 n 个无序无重复元素值的数组中查找第 i 小的数的算法描述如下：任意取一个元素 r，用划分操作确定其在数组中的位置，假设元素 r 为第 k 小的数。若 i 等于 k，则返回该元素值；若 i 小于 k，则在划分的前半部分递归进行划分操作找第 i 小的数；否则在划分的后半部分递归进行划分操作找第 k-i 小的数。该算法是一种基于_策略的算法。（分数：2.00）A.分治 B.动态规划C.贪心D.回溯解析：在解答本题前请参看本节考点精讲中的常用算法描述，当了解完选项中的各种算
42、法特点后，可以发现本题采用了分治法的策略思想。13.要在 88 的棋盘上摆放 8 个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用_来实现。（分数：2.00）A.分治法B.动态规划法C.贪心法D.回溯法 解析：回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。回溯法求解的过程其实是搜索整个解空间来找到最优的解。而“皇后”问题是一个典型的用回溯法求解的问题。14.分治算法设计技术_。（分数：2.00）A.一般由 3 个步骤组
43、成：问题划分、递归求解、合并解 B.一定用递归技术来实现C.将问题划分为 k 个规模相等的子问题D.划分代价很小而合并代价很大解析：分治的基本思想就是：对于一个规模为 n 的问题，若该问题可以容易地解决(比如说规模 n 较小)，则直接解决，否则将其分解为 k 个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。 所以分治算法设计技术主要包括 3 个步骤，分别是问题划分、递归求解、合并解。15.用动态规划策略求解矩阵连乘问题 M 1 *M 2 *M 3 *M 4 ，其中 M 1 (20*5)、M 2 (5*35)、M 3 (35*4)和 M 4 (4*25)，则最优的计算次序为_。（分数：2.00）A.(M1*M2)*M3)*M4B.(M1*M2)*(M3*M4)C.(M1*(M2*M3)*M4 D.M1*(M2*(M3*M4)解析：这个题目的关键是要求最优的计算次序，也就是要求计算过程中，乘法的次数最小。如果用选项 A的次序来计算，需要计算的乘法次数为：20*5*35+20*35*4+20*4*25。同样我们可以求出其他 3 种方法所需的乘法次数。其中最小的是选项 C 的 5*35*4+20*
