1、软件水平考试（中级）软件设计师下午（应用技术）历年真题试卷汇编 2 及答案解析(总分：44.00，做题时间：90 分钟)一、必答题(总题数：9，分数：44.00)1.必答题（共 4 道大题，每道大题）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】 设有 m 台完全相同的机器运行 n 个独立的任务，运行任务 i 所需要的时间为 t i ，要求确定一个调度方案，使的完成所有任务所需要的时间最短。假设任务已经按照其运行时间从大到小排序，算法基于最长运行时间作业优先的策略；按顺序先把每个任务分配到一台机器上，然后将剩余的任务一次放入最先空闲的机器。 【C
2、代码】 下面是算法的 C 语言实现。 (1)常量和变量说明 m：机器数 n：任务数 t：输入数组，长度为n，其中每个元素表示任务的运行时间，下标从 0 开始 s：二维数组，长度为 m*n，下标从 oF 始，其中元素 sii表示机器 i 运行的任 j 的编号 d：数组，长度为 m 其中元素 di表示机器 i 的运行时间，下标从 0 开始 count：数组，长度为 m，下标从 0 开始，其中元素 counti 一表示机器 i 运行的任务数 i：循环变量 i：循环变量 k：临时变量 max：完成所有任务的时间 min：临时变量 (2)函数schedule void schedule() int i，
3、j，k max=0； for(i=0；idj)( ( min：dj； k=j； 机器k 空闲 (3) ； countk=countk+1； dk=dk+ti； for(i=0；i（分数：6.00）(1).根据说明和 C 代码，填充 C 代码中的空(1)(4)。（分数：2.00）_(2).根据说明和 C 代码，该问题采用了(5)算法设计策略，时间复杂度为(6)(用 O 符号表示)（分数：2.00）_(3).考虑实例 m=3(编号 02)，n=7(编号 06)，各任务的运行时间为16，14，6，5，4，3，2。则在机器 0、1 和 2 上运行的任务分别为(7)、(8)和(9)(给出任务编号)。从任
4、务开始运行到完成所需要的时间为(10)。（分数：2.00）_阅读以下说明和 C 代码，根据要求回答问题 1问题 3。 【说明】 某工程计算中要完成多个矩阵相乘(链乘)的计算任务。两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算 A mn *B np ，需要 m*n*p 次乘法运算。矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵 A 110100 ，A2 1005 ，A3 550 三个矩阵相乘为例，若按(A1*A2)*A3 计算，则需要进行 10*100*5+10*5*50=7500 次乘法运算；若
5、按A1*(A2*A3)计算，则需要进行 100*5*50+10*100*50=75000 次乘法运算。可见不同的计算顺序对计算量有很大的影响。矩阵链乘问题可描述为：给定 n 个矩阵 n，矩阵 Ai的维数为 Pi-1Pi，其中i=1，2，n。确定一种乘法顺序，使得这 n 个矩阵相乘时进行乘法的运算次数最少。由于可能的计算顺序数量非常庞大，对较大的 n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若 AI*A2*An 的一个最优计算顺序从第 k 个矩阵处断开，即分为A1*A2*Ak 和 Ak+1*Ak+2*An 两个子问题，则该最优解应该包含 A1*A2*
6、Ak 的一个最优计算顺序和Ak+1*Ak+2*An 的一个最优计算顺序。据此构造递归式， * 其中，costij表示Ai+1*Ai+2*Aj+1 的最优计算的计算代价。最终需要求解 cost0n1。 【C 代码】 算法实现采用自底向上的计算过程。首先计算两个矩阵相乘的计算量，然后依次计算 3 个矩阵、4 个矩阵n 个矩阵相乘的最小计算量及最优计算顺序。下面是该算法的 C 语言实现。 (1)主要变量说明 n：矩阵数 seq：矩阵维数序列 cost：二维数组，长度为 n*n，其中元素 costij表示 Ai+1*Ai+2*Aj+l 的最优计算的计算代价 trace：二维数组，长度为 n*n，其中元
7、素 traceij表示Ai+1*Ai+2：i：*Aj+1 的最优计算对应的划分位置，即 k (2)函数 cmm #define N 100 int cost NIN； int trace NN； int cmm(int n，int seq) int tempCost； int tempTrace； int i,j,k , P； int temp； for(i=0；itemp) tempCost=temp； (4) costij=tempCost； traceij=tempTrace： return cost0n1； （分数：6.00）(1).根据以上说和 C 代码，填充 C 代码中的空(1)(
8、4)。（分数：2.00）_(2).根据以上说明和 C 代码，该问题采用了（5）算法设计策略，时间复杂度为(6)(用 0 符号表示)。（分数：2.00）_(3).考虑实例 n=6，各个矩阵的维数：A1 为 5*10，A2 为 10*3，A3 为 3*12，A4 为 12*5，A5 为 5*50，A6为 50*6，即维数序列为 5，10，3，12，5，50，6。则根据上述 C 代码得到的一个最优计算顺序为(7)(用加括号方式表示计算顺序)，所需要的乘法运算次数为(8)。（分数：2.00）_阅读下列说明 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】 用两台处理机 A和
9、B 处理 n 个作业。设 A 和 B 处理第 i 个作业的时间分别为 a i 和 b i 。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上处理时间长，而对某些作业在 B 上处理时间长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间(所有作业被处理的时间之和)最少。 算法步骤： (1)确定候选解上界为最短的单台处理机处理所有作业的完成时间 m， （分数：6.00）(1).根据以上说明和 C 代码，填允 C 代码中的空(1)(5)。（分数：2.00）_(2).根据以上 C 代
10、码，算法的时间复杂度为(6)(用 O 符号表示)。（分数：2.00）_(3).考虑 6 个作业的实例，各个作业在两台处理机上的处理时间如表 15 一 1 所示。该实例的最优解为(7)，最优解的值(即最短处理时间)为(8)。最优解用(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)表示作业 1，2，3 和 4 在 A 上处理，作业 5 和 6 在 B 上处理。 （分数：2.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】设有 n
11、个货物要装入若干个容重为 C 的集装箱以便运输，这 n 个货物的体积分别为s1，s2，sn，且有siC(1in)。为节省运输成本，用尽可能少的集装箱来装运这 n 个货物。下面分别采用最先适宜策略和最优适宜策略来求解该问题。最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容重最小的集装箱，使得该箱子装入货物后闲置空间最小。 【C 代码】 下面是这两个算法的 C 语言核心代码。 (1)变量说明 n：货物数 C：集装箱容量
12、 s：数组，长度为 n，其中每个元素表示货物的体积，下标从 0 开始。 b：数组，长度为 n，bi表示第 n+i 个集装箱当前已经装入货物的体积，下标从 0 开始 i，j：循环变量 k：所需的集装箱数 min：当前所用的各集装箱装入了第 i 个货物后的最小剩余容量 m：当前所需的集装箱数 temp：临时变量 (2)函数 firstfit intfirs 七 fit()( inti，j； k=0; for(i=0;i(j+1)?k：(j+1)； returnk； (3)函数 bestfit intbestfit() inti，j，min，m，temp； k=0； for(i=0；iO intc3
13、3=(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；j （分数：2.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】某应用中需要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本
14、思想是：对每一个元素x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m1、m 一 2、个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元素值等于 4 的元素个数有 3 个，则 4 应该在数据元素序列的第 10 个位置、第 9 个位置和第 8 个位置上。 算法具体的步骤为： 步骤 1：统计每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。 【C 代码】 下面是该排序算法的 C 语言实现。 (1)常量和变量说明 R 常量，定义元素取值范
15、围中的取值个数，如上述应用中 R 值应取 6 i：循环变量 n：待排序元素个数 a：输入数组，长度为 n b：输出数组，长度为 n c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数 sort voidsort(intn，inta，intb) intcR，i； for(i=0；i(1).根据说明和 C 代码，填充 C 代码中的空缺(1)(4)。（分数：2.00）_(2).根据 C 代码，函数的时间复杂度和空间复杂度分别为(5)和(6)(用 O 符号表示)。（分数：2.00）_(3).根据以上 C 代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过 1
16、00 字)；若不稳定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。（分数：2.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下：对于 n 个元素的关键字序列a 1 ，a 2 ，a n ，当且仅当满足下列关系时称其为堆。 在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图 152 是一个大顶堆的例子。 （分数：6.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。（分数：2.00）_(2).根据以上 c 代码，函数 heapMaxi
17、mum，heapExtractMax 和 maxHeaplnsert 的时间复杂度的上界分别为(6)、(7)和(8)(用 O 符号表示)。（分数：2.00）_(3).若将元素 10 插入到堆 A=(15，13，9，5，12，8，7，4，0，6，2，1)中，调用 maxHeaplnsert 函数进行操作，则新插入的元素在堆 A 中第(9)个位置(从 1 开始)。（分数：2.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空： (2)任意选择一个入度为 0 的顶点，将其放入拓扑序列中，同时从图中
18、删除该顶点以及从该顶点出发的弧； (3)重复(2)，直到不存在入度为 0 的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图 G 中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图 G 中的顶点从 1 开始依次编号，顶点序列为v1，v2，vn，图 G 采用邻接表示，其数据类型定义如下： #def ine NAXVNUM 50 *最大顶点数* typedef structArcNode( *表节点类型* int adjvex； *邻接顶
19、点编号* struct ArcNode*nextarc； *指示下一个邻接顶点* ArcNode： typedef struct Adj List( *头节点类型* char vdata； *顶点的数据信息* ArcNode*firstarc； *指向邻接表的第一个表节点* Adj List； typedef struct LinkedDigraph( *图的类型* int n； *图中顶点个数* AdjLiSt VheadMAXVNUM； *所有顶点的头节点数组* LinkedDigraph； 例如，某有向图 G 如图 153 所示，其邻接表如图 15-4 所示。 函数 T0pSon 中用到
20、了队列结构(Queue 的定义省略)，实现队列基本操作的函数原型如表 152 所示： 【C 代码】 int *TopSort(LinkedDigraph G) ArcNode*P； *临时指针，指示表节点* Queue Q；*临时队列，保存入度为 0 的顶点编号* int k=0； *临时变量，用作数组元素的下标* int j=0，W=0； *临时变量，用作顶点编号* int*toporder，*inDegree； toporder=(int*)malloc(Gn+1)*Si zeof(int)； *存储拓扑序列中的顶点编号* inDegree=(int*)malloc(Gn+1)*sizeo
21、f(int)； *存储图 G 中各顶点的入度* if(!inDegree I I!toporder)return NULL； (1)； *构造一个空队列* for(j=1；J=Gn；J+)( *初始化* toporderJ=0； inDegreej=0； for(J=1；J=Gn；J+) *求图 G 中各项点的入度* for(P=GVheadjfirstarc；P；P=p 一nextarc) inDegreep 一adjvex+=1； for(j=1；J=Gn；j+) *将图 G 中入度为 0 的顶点保存在队列中* if(0=inDegreej)EnQueue( intc33=(1，2，3)，
22、(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；j （分数：2.00）_正确答案：(正确答案：(1)bestXj=xi (2)j解析：解析：本题中机器需要 3 个部件，共 3 个供应商，每个供应商可提供 3 种部件，供应商 0 提供的 3个部件数量分别为 1、2、3，价格分别
23、为 1、2、3；供应商 1 提供的 3 个部件数量分别为 3、2、1，价格分别为 3、2、1；供应商 2 提供的 3 个部件数量分别为 2、2、2，价格分别为 2、2、2。价格上限为 4；初始时，满足价格上限约束条件的最小机器重量为 8，最小重量机器的价格为 0。在回溯过程中，先购买第0 个部件，首选选择第 0 个供应商的部件 0，计算总重量和总价格，如果总价值不大于上限 cc，则扩展当前节点；然后购买第 1 个部件，同样先选择第 0 个供应商的部件 1，计算总重量和总价格，如果总价值不大于上限 cc，则扩展当前节点如果当前总价格大于上限 cc 或者当前总重量比已知的最小重要大，则当前节点成为
24、死节点，返回前一次购买部件所在的节点，同时更新总价值和总重量。因此可将空(2)(5)补充完整，如下。 for(j=0；jm；j+)( *第 i 个部件从第 j 个供应商购买* xi=j； cw=cw+wij； cp=cp+cij； if(cp=cc&cwbestw(*深度搜索，扩展当前节点* ifback 七 rack(1+1)ttound=1；， *回溯+ CW=CWwij； cp=cpcij； 如果得到问题解，将部件的总质量和总价值保存在变量 bestW 和 bestC 中，并将部件的来源保存在数组 bestX 中。数组 x 中保存搜索过程中产生的解，把 x 中的元素值赋给数组 bestX
25、 即可。因此空(1)处应填入 bestXj=x 啪。阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】某应用中需要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本思想是：对每一个元素x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m1、m 一 2、个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元素值等于 4 的元素个数有 3 个，则 4 应该在数据元素序列的第 10 个位置、第 9 个位置和第 8 个位置上。 算法具体的步骤为：
26、 步骤 1：统计每个元素值的个数。 步骤 2：统计小于等于每个元素值的个数。 步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。 【C 代码】 下面是该排序算法的 C 语言实现。 (1)常量和变量说明 R 常量，定义元素取值范围中的取值个数，如上述应用中 R 值应取 6 i：循环变量 n：待排序元素个数 a：输入数组，长度为 n b：输出数组，长度为 n c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。 (2)函数 sort voidsort(intn，inta，intb) intcR，i； for(i=0；i(1).根据说明和 C 代码，填充 C 代码中
27、的空缺(1)(4)。（分数：2.00）_正确答案：(正确答案：(1)R(2)cai+1(3)ci+ci-1(4)ai)解析：解析：在函数 sort 中，首先对辅助数组 c 进行初始化，将 R 个元素全部初始化为 0，代码为： for(i=0；i(2).根据 C 代码，函数的时间复杂度和空间复杂度分别为(5)和(6)(用 O 符号表示)。（分数：2.00）_正确答案：(正确答案：(5)O(n+R)或者 O(n)或 n 或线性(6)O(R)或者 O(1)解析：解析：算法中只有单层循环，因此算法的时间复杂度为 O(n+R)。算法中需要用到一个长度为 R 的辅助数组 c，因此算法的空间复杂度为 O(R
28、)。(3).根据以上 C 代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过 100 字)；若不稳定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。（分数：2.00）_正确答案：(正确答案：不稳定。修改第 12 行的 for 循环为：for(i=n1；i：0；i-)即可。)解析：解析：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r i =r j ，且 r i 在 r j 之前，而在排序后的序列中，r i 仍在 r j 之前，则称这种排序算法是稳定的；否则称为不稳定的。题目中，从下标 0 开始读取 a(i元素，
29、第一个读取的值为 ai的元素保存在 bcai一 1，第二个读取的 ai的元素保存在 bcai2，也就是说后读取的值为 ai的元素保存在前面，因此该算法是不稳定的，只需讲最后一个 for 循环改为如下代码即可变为稳定的。 for(i=n 一 1；i=0；i 一一)( bcai一 1=ai； cai=cai一 1； 阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】 堆数据结构定义如下：对于 n 个元素的关键字序列a 1 ，a 2 ，a n ，当且仅当满足下列关系时称其为堆。 在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆
30、。堆常用完全二叉树表示，图 152 是一个大顶堆的例子。 （分数：6.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。（分数：2.00）_正确答案：(正确答案：(1)A-int_array0 (2)A-int_array0=A-int_arrayA-array_size 一 1 (3)A-array_size-1 (4)keyA-int_arrayPARENT(i) (5)A-int_arrayi=key)解析：解析：heapMaximum(A)函数返回大顶堆 A 中的最大元素。大顶堆 A 的优先队列采用顺序存储方式，指int_array 指向优先队列的存储空间首地址
31、，其内容为大项堆 A 中的最大元素，因此空(1)处应填入 A一inLarray0。heapExtractMax(A)功能是去掉并返回大顶堆 A 的最大元素，将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆。可知空(2)处所填的语句应该是将最后一个元素的值存储在原最大元素所在的位置，即存储空间的首地址。maxHeaplnsert(A,key)的功能是把元素 key 插入到大顶堆 A的最后位置，再将 A 调整成大顶堆。在将 A 调整成大堆的过程中需要用到上滤策略。maxHeaplnsert(A，key)函数中，首先用 i 指示元素 key 的位置，则 i=array_size_1；然后将
32、int_arrayi-其父节点进行比较，如果大于其父节点的值，也两者的位置进行交换，key 的位置i=PARENT(i)；往上比较，直至 key 的值不大于其父节点的值。(2).根据以上 c 代码，函数 heapMaximum，heapExtractMax 和 maxHeaplnsert 的时间复杂度的上界分别为(6)、(7)和(8)(用 O 符号表示)。（分数：2.00）_正确答案：(正确答案：(6)O(1) (7)O(1gn) (8)O(1gn)解析：解析：heapMaximum 函数不需要进行比较，直接输出存储空间首地址中的内容。时间复杂度的上界O(1)。heapExtractMax 函
33、数将最后一个元素“提前”到堆顶位置，并将剩余元素调整成大顶堆，在最坏的情况下，需要从根节点下滤比较到最底层，时间复杂度的上界 O(lgn)。maxHeaplnsert(A，key)函数把元素 key 插入到大顶堆 A 的最后位置，再将 A 调整成大顶堆。在最坏的情况下，需要从最底层上滤比较到根节点，时间复杂度的上界 O(lgn)。(3).若将元素 10 插入到堆 A=(15，13，9，5，12，8，7，4，0，6，2，1)中，调用 maxHeaplnsert 函数进行操作，则新插入的元素在堆 A 中第(9)个位置(从 1 开始)。（分数：2.00）_正确答案：(正确答案：3)解析：解析：调用
34、maxtteaplnsert 函数进行排序的过程如下。 可见，元素 10 在堆 A 的第 3 个位置。阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空： (2)任意选择一个入度为 0 的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧； (3)重复(2)，直到不存在入度为 0 的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图 G 中的顶点进行拓扑排序，返回拓扑序
35、列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图 G 中的顶点从 1 开始依次编号，顶点序列为v1，v2，vn，图 G 采用邻接表示，其数据类型定义如下： #def ine NAXVNUM 50 *最大顶点数* typedef structArcNode( *表节点类型* int adjvex； *邻接顶点编号* struct ArcNode*nextarc； *指示下一个邻接顶点* ArcNode： typedef struct Adj List( *头节点类型* char vdata； *顶点的数据信息* ArcNode*firstarc； *指向邻接表的第一个表节点* Ad
36、j List； typedef struct LinkedDigraph( *图的类型* int n； *图中顶点个数* AdjLiSt VheadMAXVNUM； *所有顶点的头节点数组* LinkedDigraph； 例如，某有向图 G 如图 153 所示，其邻接表如图 15-4 所示。 函数 T0pSon 中用到了队列结构(Queue 的定义省略)，实现队列基本操作的函数原型如表 152 所示： 【C 代码】 int *TopSort(LinkedDigraph G) ArcNode*P； *临时指针，指示表节点* Queue Q；*临时队列，保存入度为 0 的顶点编号* int k=0
37、； *临时变量，用作数组元素的下标* int j=0，W=0； *临时变量，用作顶点编号* int*toporder，*inDegree； toporder=(int*)malloc(Gn+1)*Si zeof(int)； *存储拓扑序列中的顶点编号* inDegree=(int*)malloc(Gn+1)*sizeof(int)； *存储图 G 中各顶点的入度* if(!inDegree I I!toporder)return NULL； (1)； *构造一个空队列* for(j=1；J=Gn；J+)( *初始化* toporderJ=0； inDegreej=0； for(J=1；J=Gn
38、；J+) *求图 G 中各项点的入度* for(P=GVheadjfirstarc；P；P=p 一nextarc) inDegreep 一adjvex+=1； for(j=1；J=Gn；j+) *将图 G 中入度为 0 的顶点保存在队列中* if(0=inDegreej)EnQueue(&Q，j)； whi le(!IsEmpty(Q)( (2) ； *队头顶点出队列并用 W 保存该顶点的编号* toporderk+=W； *将顶点 W 的所有邻接顶点的入度减 1(模拟删除顶点 w 及从该项点出发的弧的操作)* for(p=GVheadwfirstarc；P；P=P 一nextarc)( (3
39、)一=1；if(0=(4)EnQueue(Q，P 一adjvex)； *for* *while* free(inDegree)； if( (5) ) return NULL； return topOrder； *TopSort* （分数：6.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。（分数：2.00）_正确答案：(正确答案：(1)InitQueue(&Q)(2)DeQueue(&Q，w)(3)inDegreepadjvex 或其等价形式(4)inDegreep 一adjvex或其等价形式(5)k解析：解析：本题考查数据结构和算法中的拓扑排序算法。在拓扑排序过程中
40、，需要将入度为 O 的顶点临时临时存储起来。函数中用一个队列暂存入度为 0 且没有进入拓扑序列的顶点。显然，空(1)处应填入InitQueue(Q)。根据注释，空(2)处应填入 DeQueue(Q，&w)，实现队头元素出队列的处理。题中图采用邻接表存储结构，当指针 p 指向 vi 邻接表中的节点时，p 一adjvex 表示 vi 的一个邻接顶点，删除 Vi至顶点 p 一adjvex 的弧的操作实现为顶点 p 一adjvex 的入度减 1，因此，空(3)处应填入inDegreep 一adIjvex，当顶点 p 一adjvex 的入度为 0 时，需要将其加入队列，因此空(4)处也应填入 inDegreepadjvex。空(5)处判断是否所有顶点都加入拓扑序列，算法中变量 k 用于对加入序列的项点计数，因此，空(5)处应填入“k(2).对于图 153 所示的有向图 G，写出函数 TopSoa 执行后得到的拓扑序列。若将函数 T0pSort 中的队列改为栈，写出函数 TopSon 执行后得到的拓扑序列。（分数：2.00）_
