1、中级软件设计师下午试题-119 及答案解析(总分：75.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.一般的树结构常采用孩子-兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图(a)所示的树的孩子一兄弟表示如图(b)所示。（分数：15.00）_二、B试题二/B(总题数：1，分数：15.00)2.函数 int Toplogical(LinkedWDigraph G)的功能是对图 G 中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G 表示一个具有 n 个顶点的 AOE 网，图中顶点从
2、1n 依次编号，图 G 的存储结构采用邻接表表示，其数据类型定义如下：typedef struct Gnode /*邻接表的表结点类型*/int adjvex; /*邻接顶点编号*/int weight; /*弧上的权值*/struct Gnode*nextarc; /*指示下一个弧的结点*/Gnode;typedef struct Adjlist /*邻接表的头结点类型*/char vdata; /*顶点的数据信息*/struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/Adjulist;typedef struct LinkedWDigraph /*图的类型*/in
3、t n,e; /*图中顶点个数和边数*/struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph;例如，某 AOE 网如图 1 所示，其邻接表存储结构如图 2 所示。图 1 AOE 网（分数：15.00）_三、B试题三/B(总题数：1，分数：15.00)快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的三个步骤如下：分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。
4、递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。合并：快速排序在原地排序，故不需合并操作。（分数：15.00）(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); QUICKSORT(A,q+1,
5、r); PARTITION(A,p,r) x=Ar; i=p-1; for (j=p;j=r-1;j+) if (Aj=x) i=i+1; 交换 Ai和 Aj; 交换U U 1 /U /U和U U 2 /U /U /注：空U 1 /U和空U 2 /U答案可互换，但两空全部答对方可得分 returnU U 3 /U /U （分数：5.00）_(2).(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O 记号。最佳情况为U U 2 /U /U，平均情况为U U 3 /U /U，最坏情况为U U 4 /U /U。 (2)假设要排序的 n 个元素都具有相同值
6、时，快速排序的运行时间复杂度属于哪种情况?U U 5 /U /U。(最佳、平均、最坏)（分数：5.00）_(3).(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取 i 到 j 之间的一个数，包括 i 和 j。 RANDOMIZED-PARTITION(A,p,r) i=RANDOM(p,r); 交换U U 3 /U /U和U U 4 /U /U; /空U 3 /U和空U 4
7、 /U答案可互换，但两空全部答对方可得分 return PARTITION(A,p,r); (2)随机化快速排序是否能够消除最坏情况的发生?U U 5 /U /U。(是或否)（分数：5.00）_四、B试题四/B(总题数：1，分数：15.00)3.阅读下列说明和 C 代码，将应填入(n)处的字句写在答题纸的对应栏内。说明设某一机器由 n 个部件组成，每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 Wij和价格 Cij。设计一个算法，求解总价格不超过上限 cc 的最小重量的机器组成。采用回溯法来求解该问题：首先定义解空间。解空间由长度为 n 的向量组成，其中每个
8、分量取值来自集合1，2，m，将解空间用树形结构表示。接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(C 11)是否超过上限(cc)，重量(W 11)是否比当前已知的解(最小重量)大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(C 11+C21)是否超过上限(cc)，重量(W 11+W21)是否比当前已知
9、的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。C 代码下面是该算法的 C 语言实现。U /U变量说明。n：机器的部件数。m：供应商数。cc：价格上限。w：二维数组，wij表示第 j 个供应商供应的第 i 个部件的重量。c：二维数组，cij表示第 j 个供应商供应的第 i 个部件的价格。best1W：满足价格上限约束条件的最小机器重量。bestC：最小重量机器的价格。bestX：最优解，一维数组，bestX|i表示第 i 个部件来自哪
10、个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x：搜索过程中产生的解，xi表示第 i 个部件来自哪个供应商。i：当前考虑的部件，从 0n-1。j：循环变量。U /U函数 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;int x3=0,0,0;int backtrack(int i)int j=0;int found=0;if(in
11、-1)/*得到问题解*/bestW=cw;bestC=cp;for(j=0;jn;j+)U U /U /U;return 1;if(cp=cc)/*有解*/found=1;for(j=0;U U /U /U;j+)/*第 i 个部件从第 j 个供应商购买*/U U /U /U;cw=cw+wij;cp=cp+ciij;if(cp=ccU U /U /U/*深度搜索，扩展当前结点*/if(backtrack(i+1)found=1;/*回溯*/cw=cw-wij;U U /U /U;return found;（分数：15.00）_五、B试题五/B(总题数：1，分数：15.00)阅读下列说明和 C
12、 代码，回答问题。说明设有 n 个货物要装入若干个容量为 C 的集装箱以便运输，这 n 个货物的体积分别为S1，S2，Sn，且有 siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(Firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(Bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。C 代码下面是这两个算法的 C 语言核心代码。U 1 /U变量说
13、明。n：货物数。C：集装箱容量。s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始。b：数组，长度为 n，bi表示第 i+1 个集装箱当前已经装入货物的体积，下标从 0。i，j：循环变量。k：所需的集装箱数。min：当前所用的各集装箱装入了第 i 个货物后的最小剩余容量。m：当前所需要的集装箱数。temp：临时变量。U 2 /U函数 firstfit。int firstfit()inti,j;k=0;for(i=0;in;i+)bi=0;for(i=0;in;i+)U U 1 /U /U;while(C-bjsi)j+;U U 2 /U /U;k=k(j+1)?k:(j+1);
14、returnkU 3 /U函数 bestfit。int bestfit()int i,j,min,m,temp;k=0;for(i=0;in;i+)bi=0;for(i=0;in;i+)min=C;m=k+1;for(j=0;jk+1;j+)temp=C-bj-si;if(temp0tempmin)U U 3 /U /U;m=j;U U 4 /U /U;k=k(m+1)?k:(m+1);return k;（分数：15.00）(1).根据说明和C 代码，填充 C 代码中的空(1)(4)。（分数：5.00）_(2).根据说明和C 代码，该问题在最先适宜和最优适宜策略下分别采用了U U 2 /U /
15、U和U U 3 /U /U算法设计策略，时间复杂度分别为U U 4 /U /U和U U 5 /U /U(用 O 符号表示)。（分数：5.00）_(3).考虑实例 n=10，C=10，各个货物的体积为4，2，7，3，5，4，2，3，6，2。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为U U 3 /U /U和U U 4 /U /U。考虑一般的情况，这两种求解策略能否确保得到最优解?U U 5 /U /U(能或否)。（分数：5.00）_中级软件设计师下午试题-119 答案解析(总分：75.00，做题时间：90 分钟)一、B试题一/B(总题数：1，分数：15.00)1.一般的树结构常采用孩子-
16、兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图(a)所示的树的孩子一兄弟表示如图(b)所示。（分数：15.00）_正确答案：(1)EnQueue(tempQ,root)。 (2)brotherptr=brotherptr-nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(tempQ， /*邻接顶点编号*/int weight; /*弧上的权值*/struct Gnode*nextarc; /*指示下一个弧的结点*/Gnode;typedef struct Adjlist /*邻接
17、表的头结点类型*/char vdata; /*顶点的数据信息*/struct Gnode*Firstadj; /*指向邻接表的第一个表结点*/Adjulist;typedef struct LinkedWDigraph /*图的类型*/int n,e; /*图中顶点个数和边数*/struct Adjlist*head; /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph;例如，某 AOE 网如图 1 所示，其邻接表存储结构如图 2 所示。图 1 AOE 网（分数：15.00）_正确答案：(1)indegreep-adjvex+。 (2)Stacktop-。 (3)indeg
18、reep-adjvex-。 (4)(vew+p-weight)vep-adjvex。 (5)vew。)解析：解析 此 C 语言程序题考点为拓扑排序和关键路径。在解题之前，先了解几个概念。(1)AVO 网络。一个大工程中有许多项目组，有些项目的实行存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称 AOV 网络，图 3所示是一个 AOV 网络。*图 3 AOE 网络图(2)拓扑排序。对 AOV 网络的顶点进行拓扑排序，就是对全
19、部活动排成一个拓扑序列，使得如在 AOV 网络中存在一条弧(i,j)，则活动 i 排在活动 j 之前。对图 3 中的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567，01243657，02143657，01243567。(3)AOE 网络。利用 AOV 网络，对其进行拓扑排序能对工程中的活动的先后顺序做出安排。一个活动的完成总需要一定的时间，为了能估算某个活动的开始时间，找出那些影响工程完成时间最大的活动，需要利用带权的有向图。图中的顶点表示一个活动结束的事件，图中的边表示活动，边上的权表示完成该活动所需的时间，这种用边表示活动的网络称为 AOE 网络。图 4 所示为一个具有
20、8 个活动的某个工程的 AOE 网络。图中，有 6 个顶点，分别表示事件 V1V6，其中 V1 是工程的开始状态，V4 是工程的结束状态。边上的权表示完成该活动所需的时间。*图 4 AOE 网络图(4)关键路径。在 AOE 网络中某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径，关键路径上的活动为关键活动。如图 4 的 AOE 网络的关键路径为 V1-V2-V6-V4，关键路径长度为 80。了解了上面的这些概念以后，解题就非常容易了。从程序中的注释可知下段程序的作用是求网中各顶点的入度。for(j=1;j=G.n;j
21、+)p=G.headj.Firstadj;while(p)U (1) /Up=p-nextarc;从已知的代码结合邻接表来看，首先 p 指向了邻接表弟 1 个结点 V1 的 Firstadj 域，然后用 while 循环遍历了 V1 的 Firstadj 指向的链表。链表中的记录的，是当前结点可到达的结点，只要统计这些结点在邻接表中所有链表中出现的次数，就可知道其入度。又因为程序前面有：indegree=(int*)malloc(G.n+1)*sizeof(int);/*存储网中各顶点的入度*/所以第(1)空应填 indegreep-adjvex+。接下来看第(2)空，第(2)空是给 w 赋值
22、，接下来是打印第 w 号结点的数据，这也就意味着 w 号结点是拓扑排序选出来的结点，所以 w 必是一个入度为 0 的结点。然而在此之前已经有程序把所有的入度为 0 的结点保存在 Stack 数组中了，而且 Stack 数组是模拟的一个栈，其控制指针只有 top，所以我们应该从 Stack中取出栈项元素赋值给 w。所以第(2)空填 Stacktop-。注意这里不能用“Stack-top”，因为前面有入栈语句“Stack+top=j;”。接下来看下面的程序段。while(p)U (3) /U;if(!indegreep-adjvex)Stack+top=p-adjvex;if U(4) /Uvep
23、-adjvex=vew+p-weight;p=p-nextarc;此段程序的作用是：把选出结点所关联的边去掉，即原来 V1 有到 V3 的边 a1=30 和到 V2 的边 a2=10，当V1 结点选出以后，a1，a2 也要随之消失。这时 V3 和 V2 的入度要更新，也就是把 V3 和 V2 的入度分别减1。所以第(3)空应填 indegreep-adjvex-。第(4)空看起来比较棘手，因为前面没有说明 ve 是用于存放什么数据的，所以应该从整个程序的功能来推敲。程序有一项功能是要返回关键路径的长度，但到目前为止，都没有程序段完成此项功能。所以可以断定if U(4) /Uvep-adjvex
24、=vew+p-weight;的功能是计算关键路径长度。ve 的初值最开始都是 0，而且关键路径是要找从开始点到结束点的最长路径。所以只要保证每到一个点 vx，vevx中存的都是最长路径即可。也就是说，首先选出的是 V1，从 V1V2只有一条路径，所以 vev2=a2=10，从 V1V3 只有一条路径，所以 vev3=a1=30。然后选出 V2 结点，V2 选出以后，因为 V2V6 有 a5=50，所以现在到 V6 的最长路径为 vev6=vev2+a5=60。经过若干步后，当程序选中 V3 结点时，会产生到 V6 的另外一条路径 V1-V3-V6，这条路径的长度为 50，这条路径比现存的路径长
25、度 vev6短，所以单纯的更新语句“vep-adjvex=vew+p-weight”不能正确保存最长路径，为了保证 ve 中保存的路径最长，应该有判断(vew+p-weight)vep-adjvex。所以第(4)空应该填“(vew+p-weight)vep-adjvex”。第(5)空很明显是要返回关键路径。不过具体是要返回哪个结点的最长路径长度，才是整个图的关键路径呢?这一点可以从关键路径的定义着手：“称从开始顶点到结束顶点的最长路径为关键路径”，所以最后一个选出结点的 ve 存放的便是关键路径。所以第(5)空应填 vew。三、B试题三/B(总题数：1，分数：15.00)快速排序是一种典型的分
26、治算法。采用快速排序对数组 Apr排序的三个步骤如下：分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。合并：快速排序在原地排序，故不需合并操作。（分数：15.00）(1).下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下： A：待排序数组。 p，r：数组元素下标，从 p 到 r。 q：划分的位置。 x：枢轴元素。 i：整型变量，用于描
27、述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值。 j：循环控制变量，表示数组元素下标。 QUICKSORT(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;j=r-1;j+) if (Aj=x) i=i+1; 交换 Ai和 Aj; 交换U U 1 /U /U和U U 2 /U /U /注：空U 1 /U和空U 2 /U答案可互换，但两空全部答对方可得分 returnU U 3 /U /U （分数：5
28、.00）_正确答案：(1)Ai+1或 Ar。 (2)Ar或 Ai+1。 (3)i+1。)解析：解析 该题主要考查考生对分治算法的快速排序的理解，对伪代码、快速排序的复杂度的掌握，做题的关键是要读懂题干，理解题干中对算法的描述。 考查的是算法的伪代码表示。分治法的设计思想是将一个难以直接解决的问题，分解成一些规模较小的相同问题，各个击破。其快速排序算法的核心处理是进行划分，根据枢轴元素的值，把一个较大的数组分成两个较小的子数组。一个子数据组的所有元素的值小于等于枢轴元素的值，一个子数组的所有元素的值大于枢轴元素的值，而子数组内的元素不排序。以最后一个元素为枢轴元素进行划分，从左到右依次访问数组的
29、每一个元素，与枢轴元素比较大小，并进行元素的交换。在问题 1 给出的伪代码中，当循环结束后，Api中的值小于等于枢轴元素值 x，而Ai+1r-1中的值应大于 x。此时 Ai+1是第一个比 Ar大的元素，于是 Ar与 Ai+1交换，得到划分后的两个子数组。由于划分操作(即 PARTITION 操作)返回枢轴元素的值，因此返回值为 i+1。(2).(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O 记号。最佳情况为U U 2 /U /U，平均情况为U U 3 /U /U，最坏情况为U U 4 /U /U。 (2)假设要排序的 n 个元素都具有相同值时，
30、快速排序的运行时间复杂度属于哪种情况?U U 5 /U /U。(最佳、平均、最坏)（分数：5.00）_正确答案：(4)O(nlgn)或 O(nlog2n)。(5)O(nlgn)或 O(nlog2n)。(6)O(n2)。(7)最坏。)解析：解析 考查的是算法的时间复杂度分析。当每次都能做均匀划分时，是算法的最佳情况，其时间复杂度为 T(N)=2T(n/2)+O(N)，即时间复杂度为 O(nlgn)；算法的最坏情况是每次为极不均匀划分，即长度为 n 的数组划分后一个子数组为 n-1，一个为 0，其时间复杂度为 T(N)=T(n-1)+O(N)，即时间复杂度为O(n2)；算法的平均情况分析起来比较复
31、杂，假设数组每次划分为 9/10:1/10，此时时间复杂度可以通过计算得到为 O(nlgn)；也就是说在平均情况下快速排序仍然有较好的性能。问题 2 中假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度，属于最坏情况，因为每次都划分为长度为 n-1 和 0 的两个子数组。(3).(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i,j)表示随机取 i 到 j 之间的一个数，包括
32、i 和 j。 RANDOMIZED-PARTITION(A,p,r) i=RANDOM(p,r); 交换U U 3 /U /U和U U 4 /U /U; /空U 3 /U和空U 4 /U答案可互换，但两空全部答对方可得分 return PARTITION(A,p,r); (2)随机化快速排序是否能够消除最坏情况的发生?U U 5 /U /U。(是或否)（分数：5.00）_正确答案：(8)Ai。 (9)Ar。 (10)否。)解析：解析 由于随机化的快速排序的划分调用了 PARTITION 操作，而传统划分每次以数组的最后一个元素作为枢轴元素。随机化的快速排序消除了输入数据的不同排列对算法性能的影
33、响，降低了极端不均匀划分的概率，但不能保证不会导致最坏情况的发生。四、B试题四/B(总题数：1，分数：15.00)3.阅读下列说明和 C 代码，将应填入(n)处的字句写在答题纸的对应栏内。说明设某一机器由 n 个部件组成，每一个部件都可以从 m 个不同的供应商处购得。供应商 j 供应的部件 i 具有重量 Wij和价格 Cij。设计一个算法，求解总价格不超过上限 cc 的最小重量的机器组成。采用回溯法来求解该问题：首先定义解空间。解空间由长度为 n 的向量组成，其中每个分量取值来自集合1，2，m，将解空间用树形结构表示。接着从根结点开始，以深度优先的方式搜索整个解空间。从根结点开始，根结点成为活
34、结点，同时也成为当前的扩展结点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新结点。判断当前的机器价格(C 11)是否超过上限(cc)，重量(W 11)是否比当前已知的解(最小重量)大，若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，根结点不再是扩展结点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新结点。同样判断当前的机器价格(C 11+C21)是否超过上限(cc)，重量(W 11+W21)是否比当前已知的解(最小重量)大。若是，应回溯至最近的一个活结点；若否，则该新结点成为活结点，同时也成为当前的扩展结点，原来的结点不再是扩展结
35、点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活结点为止。C 代码下面是该算法的 C 语言实现。U /U变量说明。n：机器的部件数。m：供应商数。cc：价格上限。w：二维数组，wij表示第 j 个供应商供应的第 i 个部件的重量。c：二维数组，cij表示第 j 个供应商供应的第 i 个部件的价格。best1W：满足价格上限约束条件的最小机器重量。bestC：最小重量机器的价格。bestX：最优解，一维数组，bestX|i表示第 i 个部件来自哪个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x：搜索过程中产生的解，xi表示第 i 个部件来自哪个供应商。
36、i：当前考虑的部件，从 0n-1。j：循环变量。U /U函数 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;int 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+)U U /U /U;return 1;i
37、f(cp=cc)/*有解*/found=1;for(j=0;U U /U /U;j+)/*第 i 个部件从第 j 个供应商购买*/U U /U /U;cw=cw+wij;cp=cp+ciij;if(cp=ccU U /U /U/*深度搜索，扩展当前结点*/if(backtrack(i+1)found=1;/*回溯*/cw=cw-wij;U U /U /U;return found;（分数：15.00）_正确答案：(1)bestXj=xj。 (2)jm。 (3)xi=j。 (4)cwbestW。 (5)cp=cp-cij。)解析：解析 问题 1 本题考查回溯法的应用。 在题目的描述中告诉了回溯法
38、的基本思想。其实回溯法主要有两个过程，一个是向前探索，只要在当前满足设定的判定条件时，才向前探索；而另外一个就是回溯，在两种情况下，需要回溯，其分别是当不满足设定条件时和求的一个解的时候。 下面具体分析本试题。根据题目给出的注释，已知第(1)空所处的位置是得到问题的一个解时，根据题目描述，应该是将这个解记录下来，存放到 bestX 数组当中，而求得的解是保存在 x 数组当中的，因此这里需要循环将 x 数组中的元素值赋给 bestX 数组，因此第(1)空答案为 bestXj=xj。 第(2)空是 for 循环中的循环判定条件，根据题目注释知道该循环的作用是确定第 i 个部件从第 j 个供应商购买
39、，那么在确定第 i 个部件到底是从哪个供应商购买时，需要比较从各供应商购买的情况，因此循环的次数为供应商数，因此第(2)空答案是 jm。结合这个循环体当中的语句和对回溯法的理解，可以发现循环下面的语句是要考虑将第 i个部件从供应商 j 当中购买，也就是 j 是当前解的一部分，因此需要将 j 记录到解当中来，所以第(3)空应该是 xi=j。 第(4)空是 if 语句中的一个条件，根据题目注释，可以知道如果该 if 语句表达式的计算结果为真，需要进行深度搜索，扩展当前结点，那么如果要继续向前探索，就需要满足设定的条件，也就是当前总重量要小于 bestW，而当前总价格要小于等于 cc，因此第(4)空
40、的答案应该填 cwbestW。 根据题目注释，第(5)空是在回溯下面的语句，根据回溯的原则可以知道，回溯时，要将当前考虑的结点的重量和价格从总重量和总价格中减去，因此第(5)的答案是 cp=cp-cij。五、B试题五/B(总题数：1，分数：15.00)阅读下列说明和 C 代码，回答问题。说明设有 n 个货物要装入若干个容量为 C 的集装箱以便运输，这 n 个货物的体积分别为S1，S2，Sn，且有 siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(Firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(Bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。C 代码下面是这两个算法的 C 语言核心代码。U 1 /U变量说明。n：货物数。C：集装箱容量。s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始。b：数组，长度为 n，bi表示
