1、中级软件设计师下午试题-128 及答案解析(总分：100.01，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)1.说明 现有 n(n1000)节火车车厢，顺序编号为 1，2，3，n，按编号连续依次从 A 方向的铁轨驶入，从 B方向铁轨驶出，一旦车厢进入车站(Station)就不能再回到 A 方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如下图所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。 （分数：20.00）_二、试题二(总题数：1，分数：20.00)说明 现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总
2、和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。 现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。（分数：20.00）(1).本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。已知图 G 的顶点集合为V=1，2，n，W=w ij nn 为权重矩阵。设 为从顶点
3、i 到顶点 j 的一条最短路径的权重。当 k=0 时，不存在中间顶点，因此 。 当 k0 时，该最短路径上所有的中间顶点均属于集合1，2，k)。若中间顶点包括顶点 k，则 ；若中间顶点不包括顶点 k，则 。 于是得到如下递归式： 因为对于任意路径，所有的中间顶点都在集合1，2，n)内，因此矩阵 给出了任意两个顶点之间的最短路径，即对所有 i，jV， 表示顶点 i 到顶点 j 的最短路径。 下面是求解该问题的伪代码，请填充其中的空缺处。伪代码中的主要变量说明如下。 W：权重矩阵。 n：图的顶点个数。 SP：最短路径权重之和数组，SPi表示顶点 i 到其他各顶点的最短路径权重之和，i 从 1 到
4、n。 min SP：最小的最短路径权重之和。 min v：具有最小的最短路径权重之和的顶点。 i：循环控制变量。 i：循环控制变量。 k：循环控制变量。 LOCATE -SHOPPINGMALL(W, n) 1 D(0)=w 2 for _ 3 for i=1 to n 4 for j=1 to n 5 （分数：10.00）_(2).上一题中伪代码的时间复杂度为_(用 O 符号表示)。（分数：10.00）_三、试题三(总题数：1，分数：20.00)2.说明 对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅访问一次的过程。函数 InOrder()借助栈
5、实现二叉树的非递归中序遍历运算。 设二叉树采用二叉链表存储，节点类型定义如下： typedef struct BtNode ElemType data; /*节点的数据域，ElemType 的具体定义省略*/ struct BtNode *lchild, *rchild; /*节点的左、右孩子指针域*/ BtNode, *BTree; 在函数 InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类型定义如下： typedef struct StNode /*链栈的节点类型*/ BTree elem; /*栈中的元素是指向二叉链表节点的指针*
6、/ struct StNode *link; StNode; 假设从栈顶到栈底的元素为 e n ，e n -1 ，e 1 ，则不含头节点的链栈示意图如下图所示。 （分数：20.00）_四、试题四(总题数：1，分数：20.00)说明 某餐厅供应各种标准的营养套餐。假设菜单上共有 n 项食物 m 1 ，m 2 ，m n 每项食物 m i 的营养价值为 v i ，价格为 p i ，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。（分数：20.01）(1).下面是用动态规划策略求解该问题的伪代码，请填充其中的横线处。伪代码中的主要变量说
7、明如下。 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 套餐的最大营养价值。问题最终要求套餐的最大营养价值为 nvnM。伪代码如下： MaxNutrientValue (n, v,
8、 p, M, x) 1 for i = 0 t0 n 2 nvi 0 = 0 3 for j = 1 t0 M 4 nv0 j = 0 5 for i = 1 to n 6 for j = 1 to M 7 if jpi /若食物 mi 不能加入到套餐中 8 nvi j = nvi-1 j 9 else if _ 10 nvi j = nvi-1 j 11 else 12 nvi j = nvi-1 j-pi + vi 13 j=M 14 for i=n downt0 1 15 if _ 16 xi=0 17 else 18 xi=1 19 _ 20 return x and nvn M（分数
9、：6.67）_(2).现有 5 项食物，每项食物的营养价值和价格如下表所示。 食物营养价值及价格 编码 营养价值 价格 m 1 200 50 m 2 180 30 m 3 225 45 m 4 200 25 m 5 50 5 若要求总价格不超过 100 元的营养价值最大的套餐，则套餐应包含的食物有_(用食物项的编码表示)，对应的最大营养价值为_。（分数：6.67）_(3).第一小题中伪代码的时间复杂度为_(用 O 符号表示)。（分数：6.67）_五、试题五(总题数：1，分数：20.00)3.说明 已知集合 A 和 B 的元素分别用不含头节点的单链表存储，函数 Difference()用于求解集
10、合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=5，15，35，25，如下图(a)所示，运算完成后的结果如下图(b)所示。 （分数：20.00）_中级软件设计师下午试题-128 答案解析(总分：100.01，做题时间：90 分钟)一、试题一(总题数：1，分数：20.00)1.说明 现有 n(n1000)节火车车厢，顺序编号为 1，2，3，n，按编号连续依次从 A 方向的铁轨驶入，从 B方向铁轨驶出，一旦车厢进入车站(Station)就不能再回到 A 方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如下图所示，其
11、中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。 （分数：20.00）_正确答案：()解析：InitStack( /*节点的数据域，ElemType 的具体定义省略*/ struct BtNode *lchild, *rchild; /*节点的左、右孩子指针域*/ BtNode, *BTree; 在函数 InOrder()中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表(简称链栈)，其节点类型定义如下： typedef struct StNode /*链栈的节点类型*/ BTree elem; /*栈中的元素是指向二叉链表节点的指针*/ struct
12、StNode *link; StNode; 假设从栈顶到栈底的元素为 e n ，e n -1 ，e 1 ，则不含头节点的链栈示意图如下图所示。 （分数：20.00）_正确答案：()解析：ptr!=NULL qlink=stacktop ptr=ptrlchild stacktop=stacktoplink qrchild四、试题四(总题数：1，分数：20.00)说明 某餐厅供应各种标准的营养套餐。假设菜单上共有 n 项食物 m 1 ，m 2 ，m n 每项食物 m i 的营养价值为 v i ，价格为 p i ，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超
13、过 M 的营养价值最大的套餐。（分数：20.01）(1).下面是用动态规划策略求解该问题的伪代码，请填充其中的横线处。伪代码中的主要变量说明如下。 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 项食物组合且价
14、格不超过 j 套餐的最大营养价值。问题最终要求套餐的最大营养价值为 nvnM。伪代码如下： MaxNutrientValue (n, v, p, M, x) 1 for i = 0 t0 n 2 nvi 0 = 0 3 for j = 1 t0 M 4 nv0 j = 0 5 for i = 1 to n 6 for j = 1 to M 7 if jpi /若食物 mi 不能加入到套餐中 8 nvi j = nvi-1 j 9 else if _ 10 nvi j = nvi-1 j 11 else 12 nvi j = nvi-1 j-pi + vi 13 j=M 14 for i=n d
15、ownt0 1 15 if _ 16 xi=0 17 else 18 xi=1 19 _ 20 return x and nvn M（分数：6.67）_正确答案：()解析：nvi-1j=nvi-1j-pi+vi nvij=nvi-1j j=j-pi(2).现有 5 项食物，每项食物的营养价值和价格如下表所示。 食物营养价值及价格 编码 营养价值 价格 m 1 200 50 m 2 180 30 m 3 225 45 m 4 200 25 m 5 50 5 若要求总价格不超过 100 元的营养价值最大的套餐，则套餐应包含的食物有_(用食物项的编码表示)，对应的最大营养价值为_。（分数：6.67）
16、_正确答案：()解析：m 2 ，m 3 ，m 4 605(3).第一小题中伪代码的时间复杂度为_(用 O 符号表示)。（分数：6.67）_正确答案：()解析：O(nM)五、试题五(总题数：1，分数：20.00)3.说明 已知集合 A 和 B 的元素分别用不含头节点的单链表存储，函数 Difference()用于求解集合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=5，15，35，25，如下图(a)所示，运算完成后的结果如下图(b)所示。 （分数：20.00）_正确答案：()解析：pa=*LA pb&pbelem!=paelem pb panext 或(*pa).next 或*pa.next prenext 或(*pre).next 或*pre.next pre=pa
