计算机水平考试-中级软件设计师下午试题分类模拟13

《计算机水平考试-中级软件设计师下午试题分类模拟13》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中级软件设计师下午试题分类模拟13试题一阅读以下说明和C程序，填入横线处的字句。丄、［说明］现有n(nV1000)节火车车厢，顺序编号为丄，2,3,n,按编号连续依次从A方向的铁轨驶入，从B方向铁轨驶出，一旦车厢进入车站(Station)就不能再回到A方向的铁轨上；一旦车厢驶入B方向铁轨就不能再回到车站，如下图所示，其屮Station为栈结构，初始为空月•最多能停放1000节车厢。132/123九54JStation车站示意图下面的C程序判断能否从B方向驶出预先指定的车厢序列，程序屮使用了栈类型STACK,关于栈基本操作的函数原型说明如下。voidInitSt

2、ack(STACK*s):初始化栈。voidPush(STACK*szinte):将一个整数压入栈，栈屮元素数目增丄。voidPop(STACK*s):栈顶元素岀栈，栈中元素数目减intTop(STACKs)：返冋非空栈的栈顶元索值，栈屮元素数口不变。intIsEmpty(STACKs):若是空栈则返回1;否则返回0。［C程序］#include八此处为栈类型及其基本操作的定义，省略★/intmain(){STACKstation；intstate［1000］；intn；/*车厢数*/intbegin,izj,maxNo；/*maxNo为A端正

3、待入栈的车厢编号*/printf(”请输入车厢数：”)；Scanf(n%dnz&n)；printf(”请输入需耍判断的车厢编号序列(以卒格分隔)：”)；if(n

4、rintf("%d",Top(station))；Pop(&station)；i++；}elseif(){printf(nerrorlf)；return1；else{begin=；for(j=begin+l；j<=state[i]；j++){Push(&station,j)；else("当栈为空吋*/begin=maxNo；for(j=begin；j<=state[i]；j++){Push(&station,j)；}maxNo=；printf("OK");return0；}试题二阅读下列说明，回答下面问题。［说明］现需在某城市中选择一个社区建一个大型超市，

5、使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其屮顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置，即在给定图屮选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。算法首先需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点Z间的最短路径；然后对每个顶点，计算其他齐顶点到该顶点的最短路径Z和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。2、本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V={1,不存在屮间顶点因此

6、1J当k>0时，该最短路径上所有的屮间顶点均属于集合{1,2,，k)若屮间顶点包括顶点k,,、d(k)一,29…,n},W={w..}nxn^J权重矩阵。设,J为从顶点i到顶点j的一条最短路径的权重。当k=0时,则箱F汀+4J于是得到如下递归式：若屮间顶点不包括顶点k,Wjj%~d畀)十硝T)k=0k>0因为对于任意路径，所有的中间顶点都在集合{1,2,n)内，因此矩阵D⑴={d,)hn表示顶J给出了任意两个顶点Z间的最短路径，即对所冇i,jev,点i到顶点j的最短路径。下面是求解该问题的伪代码，请填充其中的空缺处。伪代码中的主要变量说明如下。•w：权重矩阵。

7、•n：图的顶点个数。•SP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n。•minSP：最小的最短路径权重Z和。•minv：具有最小的最短路径权重之和的顶点。•i：循环控制变量。•匕循环控制变量。•k：循坏控制变量。LOCATE-SHOPPINGMALL(Wzn)1D(0)=w2for3fori=lton4forj=1ton5ifd笄WdW舁67else89fori=lton10SP[i]=011forj=1ton1213minSP=SP[1]14_15fori=2ton16ifmin_SP>SP[i]17min_SP=

8、SP[i]18min_v=i19ret