首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
admin
2009-02-15
66
问题
阅读下列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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在软件开发过程中,详细设计的内容不包括()设计。
甲公司接受乙公司委托开发了一项应用软件,双方没有订立任何书面合同。在此情形下,()享有该软件的著作权。
某开发小组欲开发一个软件系统,实现城市中不同图书馆的资源共享,包括实体资源和电子资源,共享规则可能在开发过程中有变化。客户希望开发小组能尽快提交可运行的软件,且可以接受多次交付。这种情况下最适宜采用(31)开发过程模型。主要是因为这种模型(32)。(
不同加密机制或算法的用途、强度是不相同的,一个软件或系统中的加密机制使用得是否合理,强度是否满足当前要求,是需要通过测试来完成的,通常_______是测试的一个重要手段。
对于一般的树结构,可以采用孩子.兄弟表示法,即每个结点设置两个指针域,一个指针(左指针)指示当前结点的第一个孩子结点,另一个指针(右指针)指示当前结点的下一个兄弟结点。某树的孩子一兄弟表示如下图所示。以下关于结点D与E的关系的叙述中,正确的是_____。
在程序控制流图中,有8条边,6个节点,则控制流程图的环路复杂性V(G)等于(55)。
(16)是一种面向数据流的开发方法,其基本思想是软件功能的分解和抽象。
在程序执行过程中,Cache与主存的地址映像由()。
关于软件质量,______的叙述是正确的。①软件满足规定或潜在用户需求特性的总和②软件特性的总和,软件满足规定用户需求的能力③是关于软件特性具备“能力”的体现④软件质量包括“代码质量”、“外部质量”和“使用质量”3部分A.
在结构化分析方法中,利用分层数据流图对系统功能建模。以下关于分层数据流图的叙述中,不正确的是___________(32)。采用数据字典为数据流图中的每个数据流、文件、加工以及组成数据流或文件的数据项进行说明,其条目不包括____________(33)。
随机试题
第一个分组交换计算机网络是()年建立起来的。
体温调节的重要中枢位于
9个月婴儿,近一个月夜惊,睡眠差,多汗.烦躁,运动发育迟,刚会坐,不能爬。体检:前囟大,方颅。有哈氏沟及串珠。本病确切的诊断
过氧化物酶呈强阳性反应多见于
以下不属于膜剂优点的是
浮顶储罐是罐顶盖浮在敞口的圆筒形罐壁内的液面上并随液面升降的立式圆筒形储罐,其优点是()。
某公司适用的所得税税率为25%,2014年有关交易或事项如下:(1)2014年1月初,该公司股东权益总额是20500万元,其中股本为10000万元(股数10000万股,每股1元),资本公积为3000万元,盈余公积为6000万元,未分配利
围绕小组的总目标要建立的相应的目标是沟通目标、过程目标、实质目标和()。
黏膜支持式义齿(mucosa-supporteddentures)
就知识产权中的财产权而言,其基本特征之一是具有法定保护期的限制,但是并非知识产权中每一项财产权都具有时间限制。根据知识产权法的有关规定,以下说法正确的是:______。
最新回复
(
0
)