首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
admin
2009-02-15
69
问题
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。
【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,求得从站0出发乘公交车至站n-1的最少换车次数。
程序利用输入信息构建一张有向图G(用邻接矩阵g表示),有向图的顶点是车站,若有某条公交线路经i站到达j站,就在顶点i到顶点j之间设置一条权为1的有向边<i,j>。如果这样,从站点x至站点y的最少上车次数便对应图G中从点x到点y的最短路径长度。而程序要求的换车次数就是上车次数减1。
#include <stdio.h>
#define M 20
#define N 50
int a[N+1]; /*用于存放一条线路上的各站编号*/
int g[N][N]; /*严存储对应的邻接矩阵*/
int dist[N]; /*严存储站0到各站的最短路径*/
int m, n;
void buildG()
{ int i, j, k, sc, dd
printf(“输入公交线路数,公交站数\n”);
scanf("%d%d",&m,&n);
for (i=0;i<n;i++) /*邻接矩阵清0*/
for(j=0;j<n;j++)
g
[j]=0;
for(i=0;i<m;i++)
{ printf("沿第%d条公交线路的各站编号(0<=编号<=%d,-1结束):\n)",i+1,n-1);
sc=0; /* 当前线路站计数器*/
while(1)
{ scanf("%d",&dd);
if(dd=-1)break;
if(dd>=0 && dd<n) (1);
}
a[sc]=-1;
for(k=1;a[k]>=0;k++) /*处理第i+1条公交线路*/
for(j=0;j<k;j++)
g (2)=1;
}
}
int minLen()
{ int j,k;
for(j=0;j<n;j++)
dist[j]=g[0][j];
dist[0]=1;
do{
for(k=-1,j=0;j<n;j++) /*找下一个最少上车次数的站*/
if(dist[j]>0 &&(k==-1||dist[j]<dist[k]))
k=j;
if(k<0||k==n-1)
break;
dist[k]=-dist[k]; /*设置k站已求得上车次数的标记*/
for (j=1;j<n;j++) /*调整经过k站能到达的其余各站的上车次数*/
if((3)&& (dist[j]=0||-dist[k]+1<dist[j]))
dist[j]=(4);
}while(1);
j=dist[n-1];
return (5);
}
void main()
{ int t;
buildG();
if((t=minLen())<0)
printf("无解!\n");
else
printf(“从0号站到%d站需换车%d次\n”,n-1,t);
}
选项
答案
(1)a[sc++]=dd (2)[a[J][a[k]] (3)dist[j]>=0 && g[k][j]==1 (4)-dist[k]+1 (5)k<0?-1:j-1
解析
(1)a[sc++]=dd
将dd赋值给当前线路的a[sc],并同时将当前线路站计数器加1。
(2)[a[J][a[k]]
将a[j]和a[k]之间置为通路1。
(3)dist[j]>=0 && g[k][j]==1
若dist[j]并且k和j之间有通路,或-dist[k]+1<dist[j],也就是经过k对于j来说上车次数更少,则调整经过k站能到达的其余各站的上车次数。
(4)-dist[k]+1
让dist[j]取经过k的更少上车次数-dist[k]+1。
(5)k<0?-1:j-1
若k小于0,表示无解;否则返回j-1也就是上车次数减1。
转载请注明原文地址:https://kaotiyun.com/show/RrDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
给定关系模式R(A,B,C,D)、S(C,D,E),与π1,3,5等价的SQL语句如下:SELECT(22)FROMR,sWHERE(23);下列查询B=“信息”且E=“北京”的A、B、E的关系代数表达式中,查询效率
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
包过滤防火墙是一种通过软件检查数据包以实现系统安全防护的基本手段,以下叙述中,不正确的是()。
兼容性测试的测试范围包括___________。①硬件兼容性测试②软件兼容性测试③数据兼容性测试④平台兼容性测试
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(35)
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,时间复杂度为(41)。(41)
下面的协议中属于应用层协议的是(26),该协议的报文封装在(27)中传送。(26)
在结构化分析方法中,依据______来进行接口设计。
(16)是一种面向数据流的开发方法,其基本思想是软件功能的分解和抽象。
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
随机试题
溃疡性结肠炎发生急性中毒性结肠扩张的诱因中,下列哪项无关
管涌在非黏性土中流沙表现为(),最终被渗流托起等现象。
下列有关注册会计师对错报进行沟通的说法中,错误的是()。
《旅行社条例》规定,在境外发生危及旅游者人身安全情形的,旅行社及其委派的导游人员、领队人员应当及时报告中华人民共和国驻该国使领馆、()。
××省人民政府关于调整全省最低工资标准的通知×府发[2012]×号各市(州)人民政府,省政府各部门、各直属机构:省人民政府决定对全省现行月最低工资标准和非全日制用工小时最低工资标准进行调整。一、
下列各项中,不属于《人民警察法》所规定的公安机关职责是()。
简述影响课程变革的因素。
Chocolatemanufacturersblendmanytypesofbeanstoyield______andcolordesiredinthefinalproduct.
中国革命走农村包围城市、武装夺取政权的道路,必须处理好土地革命、武装斗争、农村革命根据地建设三者之间的关系。其中,中国民主革命的基本内容是
请在“答题”菜单中选择相应的命令,并按照题目要求完成下面的操作。注意:以下的文件必须保存在考生文件夹下。为演示文稿创建3个节,其中“开始”节中包含第1张幻灯片,“更多信息”节中包含最后1张幻灯片,其余幻灯片均包含在“产品特性”节中。
最新回复
(
0
)