1、软件设计师-常用算法设计(一)及答案解析(总分：135.02，做题时间：90 分钟)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说明快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下：(1)分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。(2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。(3)合并：快速排序在原地排序，故不需要合并操作。问题 1下面是快速
2、排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下：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，r)；PARTITION(A，p，r)X=Ar；i=p-1；for(j=p；jr-1；j+)if(Ajx)i=i+1；交换 Aj和 Aj交换 (1) 和 (2) /注：空(1)和空(
3、2)答案可以互换，但两个空全部答对方可得分return (3) 问题 2(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)问题 3(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处
4、。其中，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:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说
5、明希赛公司供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m 2，m n，每项食物 mi的营养价值为vi，价格为 pi，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。问题 1下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)。伪代码中的主要变量说明如下：n：总的食物项数；v：营养价值数组，下标从 1 到 n，对应第 1 项到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 项到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x：解向量(数组)，下标从 1
6、 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 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 jpi /若食物 mi不能加入到套餐中8 nvij=nvi-1j9
7、 else if (1) 10 nvij=nvi-1j11 else12 nvij=nvi-1j-pi+vi13 j=M14 for i=n downto 115 if (2) 16 xi=017 else18 xi=119 (3) 20 return x and nvnM问题 2现有 5 项食物，每项食物的营养价值和价格如表 21-2 所示。表 21-2 食物的营养价值和价格表编码 营养价值 价格ml 200 50m2 180 30m3 225 45m4 200 25m5 50 5若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最
8、大营养价值为 (5) 。问题 3问题 1 中伪代码的时间复杂度为 (6) (用 O 符号表示)。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 c 函数，将应填入 (n) 处的字句写在对应栏内。说明已知集合 A 和 B 的元素分别用不含头结点的单链表存储，函数 Difference()用于求解集合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=5，15，35，25，如图 21-10(a)所示，运算完成后的结果如图 21-10(b)所示。（分数：15.0
9、0）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明现需要在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。首先，算法需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后，对每个顶点计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径
10、之和最小的顶点作为建大型超市的最佳位置。问题 1本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。已知图 G 的顶点集合为V=1，2，n)，W=W ijn*n为权重矩阵。设 为从顶点 i 到顶点 j 的一条最短路径的权重。当 k=0 时，不存在中间顶点，因此 ；当 k0 时，该最短路径上所有的中间顶点均属于集合 1，2，k。若中间顶点包括顶点 k，则 ；若中间顶点不包括顶点 k，则 。于是得到如下递归式：因为对于任意路径，所有的中间顶点都在集合 1，2，n 内，因此矩阵 给出了任意两个顶点之间的最短路径，即对所有 i，jV， 表示顶点 i 到顶点 j 的最短路径。下面
11、是求解该问题的伪代码，请填充其中的空缺(1)(6)。伪代码中的主要变量说明如下：W：权重矩阵；n：图的顶点个数；SP：最短路径权重之和数组，SPi表示顶点 i 到其他各顶点的最短路径权重之和，i 取值为 1n；min_SP：最小的最短路径权重之和；min_v：具有最小的最短路径权重之和的顶点；i：循环控制变量；j：循环控制变量；k：循环控制变量。LOCATE -SHC)PPINGNALL(W，n)1 D(0)=W2 for (1) 3 for i=1 to n4 for j=1 to n5 if （分数：14.98）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项
12、1:_填空项 1:_阅读下列说明和 C 函数代码，将应填入 (n) 处的字句写在对应栏内。说明对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二又树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BtNodeElemType data； /*结点的数据域，ElemType 的具体定义省略*/struct BtNode *lchiid，*rchiid； /*结点的左、右孩子指针域*/BtNode，*BTree；在函数 InOrderO 中，用栈暂存二叉树中
13、各个结点的指针，并将栈表示为不含头结点的单向链表(简称链栈)，其结点类型定义如下：typedef struct StNode /*链栈的结点类型*/BTree elem； /*栈中的元素是指向二叉链表结点的指针*/Struct StNode *link；StNode；假设从栈顶到栈底的元素为 en，e n-1，e 1，则不含头结点的链栈示意图如图 21-11 所示。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明0-1 背包问题可以描述为：有 n 个物品，i=1，2，n，第 i 个物品价值
14、为 vi，重量为 wi(vi和 wi为非负数)，背包容量为 W(W 为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即 ，其中，x i0，1，x i=0 表示第 i 个物品不放入背包，x i=1表示第 i 个物品放入背包。问题 1用回溯法求解此 0-1 背包问题，请填充伪代码中的空缺(1)(4)。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使
15、扩展了也不能得到最优解的结点。现在假设已经设计了 BOUND(v，w，k，w)函数，其中 v、w、k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无须再扩展。下面给出 0-1 背包问题的回溯算法伪代码。函数参数说明如下：W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的
16、背包重量；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 cpcp+vk8 Yk19 kk+110 if kn then11 if fpcp then12 fpcp13 fwcw14 kn15 XY16 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 c
17、wcwwk23 cpcpvk24 (4) 问题 2考虑表 21-3 所示的实例，假设有 3 个物品，背包容量为 22。图 21-12 是根据上述算法构造的搜索树，其中结点的编号表示搜索树生成的顺序，边上的数字 I/O 分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。表 21-3 0-1 背包问题实例物品 1物品 2物品 3重量 15 10 10价值 30 18 17单位价值 2 1.8 1.7（分数：15.0
18、4）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在对应栏内。说明对有向图进行拓扑排序的方法如下。(1)初始时拓扑序列为空。(2)任意选择一个入度为 0 的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧。(3)重复(2)，直到不存在入度为 0 的顶点为止(若所有顶点都进入拓扑序列，则完成拓扑排序；否则，由于有向图中存在回路无法完成拓扑排序)。函数 int* TopSort(LinkedDigraph G)的功能是对有向图 G 中的顶点进行拓扑排序，返
19、回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图 G 中的项点从 1 开始依次编号，顶点序列为v1，v2，vn，图 G 采用邻接表表示，其数据类型定义如下：#define MAXVNUM 50 /*最大顶点数*/typedef struct ArcNode /*表结点类型*/int adjvex； /*邻接顶点编号*/Struct ArcNode *nextarc； /*指示下一个邻接顶点*/ArcNode；typedef struct AdjList /*头结点类型*/char vdata； /*顶点的数据信息*/ArcNode *firstarc； /*指向邻接表的第
20、一个表结点*/AdjList；typedef struct LinkedDigraph /*图的类型*/int n； /*图中顶点个数*/AdjList VheadMAXVNUM； /*所有顶点的头结点数组*/LinkedDigraph；例如，某有向图 G 如图 21-13 所示，其邻接表如图 21-14 所示。（分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。（分数：5.00）_(2).对于图 21-13 所示的有向图 G，写出函数 TopSort 执行后得到的拓扑序列。若将函数 TopSort 中的队列改为栈，写出函数 TopSort 执行后得到的拓扑
21、序列。（分数：5.00）_(3).设某有向无环图的顶点个数为 n、弧数为 e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数 TopSort 的时间复杂度为 (6) 。若有向图采用邻接矩阵表示(例如，图 21-13 所示的有向图的邻接矩阵如图 21-15 所示)，且将函数TopSort 中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有 n 个顶点、e 条弧的有向无环图，实现上述拓扑排序算法的时间复杂度为 (7) 。*（分数：5.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在对应栏内。说明堆数据结构定义如下：对于 n 个元素的关键字序列 a1，a 2，a n)，
22、当且仅当满足下列关系时称其为堆。在一个堆中，若堆顶元素为最大元素，则称为大顶堆；若堆顶元素为最小元素，则称为小顶堆。堆常用完全二叉树表示，图 21-16 是一个大顶堆的例子。（分数：15.00）(1).根据以上说明和 C 代码，填充 C 代码中的空(1)(5)。（分数：5.00）_(2).根据以上 C 代码，函数 heapMaximum、heapExtractMax 和 maxHeaplnsert 的时间复杂度的紧致上界分别为 (6) 、 (7) 和 (8) (用 0 符号表示)。（分数：5.00）_(3).若将元素 10 插入到堆 A=15，13，9，5，12，8，7，4，0，6，2，1中，
23、调用 maxHeapInsert 函数进行操作，则新插入的元素在堆 A 中第 (9) 个位置(从 1 开始)。（分数：5.00）_阅读下列说明和 c 代码，回答问题 1 至问题 3，将解答写在对应栏内。说明某应用中需要对 100000 个整数元素进行排序，每个元素的取值在 05 之间。排序算法的基本思想是：对每一个元素 x，确定小于等于 x 的元素个数(记为 m)，将 x 放在输出元素序列的第 m 个位置。对于元素值重复的情况，依次放入第 m-1，m-2，个位置。例如，如果元素值小于等于 4 的元素个数有 10 个，其中元素值等于 4 的元素个数有 3 个，则 4 应该在输出元素序列的第 10
24、 个位置、第 9 个位置和第 8 个位置上。算法的具体步骤如下。步骤 1：统计每个元素值的个数。步骤 2：统计小于等于每个元素值的个数。步骤 3：将输入元素序列中的每个元素放入有序的输出元素序列。C 代码下面是该排序算法的 c 语言实现。(1)常量和变量说明R：常量，定义元素取值范围中的取值个数，如上述应用中 R 值应取 6；i：循环变量；n：待排序元素个数；a：输入数组，长度为 n；b：输出数组，长度为 n；c：辅助数组，长度为 R，其中每个元素表示小于等于下标所对应的元素值的个数。(2)函数 sort1 void sort(int n，int a，int b)2 int cR，i；3 fo
25、r(i=0；i (1) ；i+)4 ci=0；5 6 for(i=0；in；i+)7 cai= (2) ；8 9 for(i=1；iR；i+)10 ci= (3) 11 12 for(i=0；in；i+)13 bcai-1= (4) ；14 cai=cai-1；15 16 （分数：15.00）(1).根据说明和 C 代码，填充 C 代码中的空缺(1)(4)。（分数：5.00）_(2).根据 C 代码，函数的时间复杂度和空间复杂度分别为 (5) 和 (6) (用 O 符号表示)。（分数：5.00）_(3).根据以上 C 代码，分析该排序算法是否稳定。若稳定，请简要说明(不超过 100 字)；若不
26、稳定，请修改其中代码使其稳定(给出要修改的行号和修改后的代码)。（分数：5.00）_软件设计师-常用算法设计(一)答案解析(总分：135.02，做题时间：90 分钟)阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说明快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下：(1)分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。(2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+
27、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)；QUICKSORT(A，q+1，r)；PARTITION(A，p，r)X=Ar；i=p-1；for(j=p；jr-1；j+)if(A
28、jx)i=i+1；交换 Aj和 Aj交换 (1) 和 (2) /注：空(1)和空(2)答案可以互换，但两个空全部答对方可得分return (3) 问题 2(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均、最坏)问题 3(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素
29、，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，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:_ （正确答案：i+1）解析：填空项 1:_ （正确答案：Ai+1）解析：填空项 1:_ （正确答案：Ar）
30、解析：(1)和空(2)答案可以互换。填空项 1:_ （正确答案：O(nlgn)或 O(nlog2n)）解析：填空项 1:_ （正确答案：O(nlgn)或 O(nlog2n)）解析：填空项 1:_ （正确答案：O(n 2)）解析：填空项 1:_ （正确答案：最坏）解析：填空项 1:_ （正确答案：Ai）解析：填空项 1:_ （正确答案：Ar）解析：(8)和空(9)答案可以互换。填空项 1:_ （正确答案：否）解析：阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说明希赛公司供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m 2，m n，每项食物 mi的营养价值为vi，价格为
31、 pi，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。问题 1下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)。伪代码中的主要变量说明如下：n：总的食物项数；v：营养价值数组，下标从 1 到 n，对应第 1 项到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 项到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x：解向量(数组)，下标从 1 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 1 表示对应的食物出现在套餐中
32、；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 jpi /若食物 mi不能加入到套餐中8 nvij=nvi-1j9 else if (1) 10 nvij=nvi-1j11 else12 nvij=nvi-1j-pi+vi13 j=M1
33、4 for i=n downto 115 if (2) 16 xi=017 else18 xi=119 (3) 20 return x and nvnM问题 2现有 5 项食物，每项食物的营养价值和价格如表 21-2 所示。表 21-2 食物的营养价值和价格表编码 营养价值 价格ml 200 50m2 180 30m3 225 45m4 200 25m5 50 5若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最大营养价值为 (5) 。问题 3问题 1 中伪代码的时间复杂度为 (6) (用 O 符号表示)。（分数：15.00）填空项
34、 1:_ （正确答案：nvi-jnvi-1j-pi+vi）解析：填空项 1:_ （正确答案：nvij=nvi-1j）解析：填空项 1:_ （正确答案：j=j-pi）解析：填空项 1:_ （正确答案：m 2、m 3、m 4(注：答案中食物编码无前后顺序关系。)）解析：填空项 1:_ （正确答案：605）解析：填空项 1:_ （正确答案：O(nM)，或 O(nM)，或 O(n*M)）解析：阅读下列说明和 c 函数，将应填入 (n) 处的字句写在对应栏内。说明已知集合 A 和 B 的元素分别用不含头结点的单链表存储，函数 Difference()用于求解集合 A 与 B 的差集，并将结果保存在集合
35、A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=5，15，35，25，如图 21-10(a)所示，运算完成后的结果如图 21-10(b)所示。（分数：15.00）填空项 1:_ （正确答案：pa=*LA）解析：填空项 1:_ （正确答案：pbpb-elem!=pa-elem，或其等价表示）解析：填空项 1:_ （正确答案：pb）解析：填空项 1:_ （正确答案：pa-next，或(*pa).next，或其等价表示）解析：填空项 1:_ （正确答案：pre-next，或(*pre).next，或其等价表示）解析：填空项 1:_ （正确答案：pre=pa）解析：阅读下
36、列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明现需要在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。首先，算法需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后，对每个顶点计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。问题 1本题采用 Floyd-Warshall 算法求
37、解任意两个顶点之间的最短路径。已知图 G 的顶点集合为V=1，2，n)，W=W ijn*n为权重矩阵。设 为从顶点 i 到顶点 j 的一条最短路径的权重。当 k=0 时，不存在中间顶点，因此 ；当 k0 时，该最短路径上所有的中间顶点均属于集合 1，2，k。若中间顶点包括顶点 k，则 ；若中间顶点不包括顶点 k，则 。于是得到如下递归式：因为对于任意路径，所有的中间顶点都在集合 1，2，n 内，因此矩阵 给出了任意两个顶点之间的最短路径，即对所有 i，jV， 表示顶点 i 到顶点 j 的最短路径。下面是求解该问题的伪代码，请填充其中的空缺(1)(6)。伪代码中的主要变量说明如下：W：权重矩阵；
38、n：图的顶点个数；SP：最短路径权重之和数组，SPi表示顶点 i 到其他各顶点的最短路径权重之和，i 取值为 1n；min_SP：最小的最短路径权重之和；min_v：具有最小的最短路径权重之和的顶点；i：循环控制变量；j：循环控制变量；k：循环控制变量。LOCATE -SHC)PPINGNALL(W，n)1 D(0)=W2 for (1) 3 for i=1 to n4 for j=1 to n5 if （分数：14.98）填空项 1:_ （正确答案：k=1 to n）解析：填空项 1:_ （正确答案： ）解析：填空项 1:_ （正确答案： ）解析：填空项 1:_ （正确答案： ）解析：填空项
39、 1:_ （正确答案：min_v=1）解析：填空项 1:_ （正确答案：min_v）解析：填空项 1:_ （正确答案：O(n 3)）解析：阅读下列说明和 C 函数代码，将应填入 (n) 处的字句写在对应栏内。说明对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二又树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BtNodeElemType data； /*结点的数据域，ElemType 的具体定义省略*/struct BtNode *lchiid，*r
40、chiid； /*结点的左、右孩子指针域*/BtNode，*BTree；在函数 InOrderO 中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表(简称链栈)，其结点类型定义如下：typedef struct StNode /*链栈的结点类型*/BTree elem； /*栈中的元素是指向二叉链表结点的指针*/Struct StNode *link；StNode；假设从栈顶到栈底的元素为 en，e n-1，e 1，则不含头结点的链栈示意图如图 21-11 所示。（分数：15.00）填空项 1:_ （正确答案：q-elem-rchild）解析：填空项 1:_ （正确答案：pt
41、r!=NULL，或 ptr!=0，或 ptr）解析：填空项 1:_ （正确答案：q-link=stacktop）解析：填空项 1:_ （正确答案：ptr-lchild）解析：填空项 1:_ （正确答案：stacktop=stacktop-link，或 stacktop=q-link）解析：阅读下列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明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)。回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算
