首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
admin
2009-02-15
34
问题
阅读下列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,E)和S(B,C,F,G),则R与S自然联结运算后的属性列有(17)个,与表达式π1,3,6,7(σ3<6(RS))等价的SQL语句如下:SELECT(18)FROM(19)WHERE(20);
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
甲公司接受乙公司委托开发了一项应用软件,双方没有订立任何书面合同。在此情形下,()享有该软件的著作权。
对于逻辑表达式((a‖(b&c))‖(C&&d)),需要___________个测试用例才能完成条件组合覆盖。
结构化开发方法中,(35)主要包含对数据结构和算法的设计。对算法设计时,其主要依据来自(36)。描述算法时,(37)不是理想的表达方式。(36)
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用得是否合理,强度是否满足当前要求,是需要通过测试来完成的,通常_______是测试的一个重要手段。
以下所示程序控制流程图中有(59)条线性无关的基本路径。
根据ANSI/IEEE829标准,以下(37)属于《测试程序说明》中程序步骤的内容。 ①启动 ②目的 ③日志 ④设置
在WindowsXP操作系统中,用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷,(23)。通常将“C:\Windows\nyprogram.exe”文件设置成只读和隐藏属性,以便控制用户对该文件的访问,这一级安全管理称之为(24)安全管理。
随机试题
《祖国呵,我亲爱的祖国》中“新刷出的雪白的起跑线”的象征意义是()
孕妇血容量增加最高峰在
仲裁中证据保全必须符合下列条件:()。
地下管线探测时,探测隐蔽管线点常用的方法有()。
我国目前主要的大气环境质量标准有( )。
某种安全分析方法是以关键词为引导,找出过程中工艺状态的变化(偏差),然后分析产生偏差的原因、后果及可采取的对策。其基本步骤包括分析的准备、进行分析和编制分析报告。该安全分析方法是()。
下列有关我国证券交易所的说法中,正确的是()。Ⅰ.为证券集中交易提供场所和设施Ⅱ.组织和监督证券交易Ⅲ.实行自律管理Ⅳ.设立和解散由中国证监会决定
下列关于银行职业道德建设的说法正确的是:()。
考虑到计件工资和计时工资的风险因素,雇员会偏好实行()方案。
在美国这样的商业社会里,无论他们抛出了多少关乎人文、情怀、精神的词藻,几乎所有艺术与技术,____________都是一门生意,即便是教主乔布斯和他的苹果也不例外。但这本身无可指摘,也不____________这些公司和这些人缔造一个伟大的时代。 依次
最新回复
(
0
)