中级软件设计师下午试题-128

1、中级软件设计师下午试题-128(总分：100.01，做题时间：90分钟)一、试题一(总题数：1,分数：20.00)1. 说明现有n(n v 1000)节火车车厢，顺序编号为1 , 2, 3，n,按编号连续依次从 A方向的铁轨驶入，从 B方向铁轨驶岀，一旦车厢进入车站(Station)就不能再回到A方向的铁轨上；一旦车厢驶入B方向铁轨就不能 再回到车站，如下图所示，其中Station为栈结构，初始为空且最多能停放1000节车厢。下面的C程序判断能否从B方向驶岀预先指定的车厢序列，程序中使用了栈类型STACK关于栈基本操作的函数原型说明如下。void lnitStack(STACK *s):初始化

2、栈。void Push(STACK *s, int e):将一个整数压入栈，栈中元素数目增1。void Pop(STACK *s):栈顶元素出栈，栈中元素数目减1。int Top(STACK s):返回非空栈的栈顶元素值，栈中元素数目不变。int lsEmpty(STACK s):若是空栈则返回1 ;否则返回0。C程序#include v stdio. h >/*此处为栈类型及其基本操作的定义，省略*/int main() STACK station;int state 1000;int n; /* 车厢数*/int begin, i, j, maxNo; /*maxNo为A端正待入栈的

3、车厢编号 * /printf(”请输入车厢数:");Scanf("%d", & n);printf("请输入需要判断的车厢编号序列(以空格分隔):");if (n v 1 =return-1;for (i=0; i v n; i+) /*读入需要驶出的车厢编号序列，存入数组state*/scanf("%d", & statei); /*初始化栈*/maxNo=1;for (i=0; i vn; = /*检查输出序列中的每个车厢号statei是否能从栈中获取*/if () /* 当栈不为空时*/if (stat

4、ei=Top (station) /*栈顶车厢号等于被检查车厢号*/printf ("%d", Top(station);Pop (&station); i+;elseif () printf ("error'n");return 1;else begin=;for (j=begin+1; j v =statei; j+) Push (&station, j);else (/* 当栈为空时*/begin=maxNo;for (j=begin; j < =statei; j+) Push (&station, j);m

5、axNo=;printf ("OK");return 0;(分数：20.00 ) 正确答案：()解析：lnitStack(&station) !lsEmpty(station) statei < Top(station) Top(station)j二、试题二(总题数：1 分数：20.00)说明现需在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型 表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最

6、短路径之和最小。算法首先需要求岀每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间 的最短路径；然后对每个顶点，计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小 的顶点作为建大型超市的最佳位置。(分数：20.00 )(1).本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V=1 ,2,，n，W=w ij nxn为权重矩阵。设 为从顶点i到顶点j的一条最短路径的权重。当 k=0时，不存在f i：i- I中间顶点，因此 。当k > 0时，该最短路径上所有的中间顶点均属于集合1，2，k)。若中间顶点包括顶点 k，则若中间顶点

7、不包括顶点 k，则 于是得到如下递归式：i到顶点j的最短路径因为对于任意路径，所有的中间顶点都在集合1，2,，n)内，因此矩阵 &出了任意两个顶点之间的最短路径，即对所有i , j eV,表示顶点i到顶点j的最短路径,下面是求解该问题的伪代码，请填充其中的空缺处。伪代码中的主要变量说明如下。 W:权重矩阵。 n :图的顶点个数。 SP：最短路径权重之和数组，SPi表示顶点i到其他各顶点的最短路径权重之和，i从1到n min SP ：最小的最短路径权重之和。 min v :具有最小的最短路径权重之和的顶点。 i :循环控制变量。 i :循环控制变量。 k :循环控制变量。LOCATE -

8、SHOPPINGMALL(W, n)1 D(0)=w2 for3 for i=1 to n4 forj=1 to n5 6 7 else8 9 for i=1 to n10 SPi=011 for j=1 to n12 13 min_SP=SP114 15 for i=2 to n16 if min_SP > SPi17 min_SP=SPi18 min_v=i19 return （分数：10.00 ）正确答案：（）解析：k=1 to nmin_v=1 ；min_v(2).上一题中伪代码的时间复杂度为 (用0符号表示)。(分数：10.00 )正确答案：()解析：O(n 3 )三、试题三(

9、总题数：1,分数：20.00)2. 说明对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个节点，且每个节点仅 访问一次的过程。函数lnOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，节点类型定义如下：typedef struct BtNode ElemType data; /*节点的数据域，ElemType的具体定义省略*/struct BtNode *lchild, *rchild;/*节点的左、右孩子指针域 */ BtNode, *BTree;在函数lnOrder（）中，用栈暂存二叉树中各个节点的指针，并将栈表示为不含头节点的单向链表（

10、简称链栈），其节点类型定义如下：typedef struct StNode /*链栈的节点类型 */BTree elem; /* 栈中的元素是指向二叉链表节点的指针*/struct StNode *link; StNode;假设从栈顶到栈底的元素为e n，e n -1 ,，e 1，则不含头节点的链栈示意图如下图所示。C程序int InOrder (BTree root) /*实现二叉树的非递归中序遍历*/BTree ptr; /*ptr用于指向二叉树中的节点*/StNode *q; /*q暂存链栈中新创建或待删除的节点指针*/StNode *stacktop=NULL; /*初始化空栈的栈顶指

11、针 stacktop */ptr=root; /*ptr指向二叉树的根节点*/while (| stacktop != NULL)while (ptr !=NULL)q=(StNode *)malloc(sizeof(StNode);if (q=NULL)return -1;qielem=ptr;stacktop=q; /*stacktop 指向新的栈顶 */ptr=; /*进入左子树*/q=stacktop; /*栈顶元素岀栈*/visit（q）; /*visit是访问节点的函数，其具体定义省略*/ptr=; /* 进入右子树*/free（q）; /*释放原栈顶元素的节点空间*/return

12、 0; /*InOrder*/（分数：20.00 ）为Vi,价格为p i ,其中i=1 , 2,，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解 总价格不超过M的营养价值最大的套餐。（分数：20.01）（1）.下面是用动态规划策略求解该问题的伪代码，请填充其中的横线处。伪代码中的主要变量说明如下。 n：总食物项数。v：营养价值组，下标为1n，对应第1项第n项食物的营养价值。P：价格数组，下标为1n，对应第1项第n项食物的价格。M总标准，即套餐的价格不超过x：解向量（数组），下标为1 n，其元素值为0或1，其中元素值为0表示对应的食物不出现在套餐中，元 素值为1表示对应的食物岀现在套餐

13、中。nv： n+1行M+1列的二维数组，其中行和列的下标均从0开始，nvij表示由前i项食物组合且价格不超过j套餐的最大营养价值。问题最终要求套餐的最大营养价值为nvnM。伪代码如下：MaxNutrientValue （n, v, p, M, x）1 for i = 0 t0 n2 nvi 0 = 03 for j = 1 t0 M4 nv0 j = 05 for i = 1 to n6 for j = 1 to M7 if j v pi / 若食物mi不能加入到套餐中8 nvi j = nvi-1 j9 else if10 nvi j = nvi-1 j11 else12 nvi j = n

14、vi-1 j-pi + vi13 j=M14 for i=n downt0 115 if16 xi=017 else18 xi=119 20 return x and nvn M（分数：6.67 ） 正确答案：（）解析：nvi-1j> =nvi-1j-pi+vinvij=nvi-1jj=j-pi（2）.现有5项食物，每项食物的营养价值和价格如下表所示。食物营养价值及价格编码营养价值价格m 120050m 218030m 322545m 420025m 5505若要求总价格不超过100元的营养价值最大的套餐，则套餐应包含的食物有 （用食物项的编码表示），对应的最大营养价值为。（分数：6.6

15、7 ）正确答案：（）解析：O（nXM）五、试题五（总题数：1分数：20.00）3. 说明已知集合A和B的元素分别用不含头节点的单链表存储，函数Difference。 用于求解集合A与B的差集,并将结果保存在集合 A的单链表中。例如，若集合A=5, 10, 20, 15, 25, 30，集合B=5, 15 , 35, 25, 如下图（a）所示，运算完成后的结果如下图（b）所示。链表节点的结构类型定义如下：typedef struct Node ElemType elem;struct Node *next; NodeType;C程序void Difference (NodeType *LA, NodeType *LB) NodeType *pa, *pb, *pre, *q;pre=NUL