首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
admin
2009-02-15
32
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
软件可靠性管理把软件可靠性活动贯穿于软件开发的全过程,成为软件工程管理的一部分。确定软件可靠性度量活动属于()阶段。
某指令流水线由4段组成,各段所需要的时间如下图所示。连续输入8条指令时的吞吐率(单位时间内流水线所完成的任务数或输出的结果数)为()。
算术表达式a+b-c*d的后缀式是___________(-、+、*表示算术的减、加、乘运算,运算符的优先级和结合性遵循惯例)。
在数据库逻辑设计阶段,若实体中存在多值属性,那么将E-R图转换为关系模式时,___________,得到的关系模式属于4NF。
以下关于用例图的叙述中,不正确的是(44)。图书馆管理系统需求中包含“还书”用例和“到书通知”用例,对于“还书”用例,应先查询该书是否有人预定,若有则执行“到书通知”。“还书”用例和“到书通知”用例是(45)关系,以下用例图中,(46)是正确的。管理员处
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,时间复杂度为(41)。(40)
一个程序的控制流图中有6个节点,10条边,在测试用例数最少的情况下,确保程序中每个可执行语句至少执行一次所需要的测试用例数的上限是______。
在程序执行过程中,Cache与主存的地址映像由()。
假定X为整数类型变量,X>=1并且X<=10,如果用边界值分析法,X在测试中应该取(48)值。
在WindowsXP操作系统中,用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷,(23)。通常将“C:\Windows\nyprogram.exe”文件设置成只读和隐藏属性,以便控制用户对该文件的访问,这一级安全管理称之为(24)安全管理。
随机试题
算法的有穷性是指()。
A、①B、②C、③D、④A
支持过程的驱动是()
Creutzfeld-Jakob病中晚期可出现典型的脑电图改变,对其描述正确的是
患者,男,25岁。1周前肛门周围持续性跳痛,皮肤红肿,并有局部压痛及波动感,诊断为肛门周围脓肿。经手术治疗,并应用抗生素,选择抗生素的方法,正确的是
鉴证业务是注册会计师对鉴证对象信息提出结论,以增强预期使用者对鉴证对象信息信任程度的业务。( )鉴证业务要素包括鉴证业务的三方关系、鉴证目标、标准、证据和鉴证报告。( )
某小学六年级(1)班举行“我心中的祖国”作文竞赛活动,根据班级活动的目标和功能划分,这属于()类型的班级活动。
A、 B、 C、 D、 D注意一位男士蹲在车轮旁边工作的画面。
Recently,Ihaveheardtwostoriesregardingtheautomobilesector.ThesalesofaSino-USjointventurehaveincreasedsignific
Whatwillthespeakertalkaboutfirstatthemeeting?Thecompany’s______thisyear.
最新回复
(
0
)