首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,求得从
阅读下列程序说明和C代码,将应填入(n)处的字句写在对应栏内。 【说明】 设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,求得从
admin
2009-05-15
36
问题
阅读下列程序说明和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。
【函数5-9】
#include <stdio.h>
#define M 20
#define N 50
int a[N+1]; /*用于存放一条线路上的各站编号*/
iht 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条公交车线路前进方向的各站编号(O<=编号<=%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 pdnff("从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
解析
本题考查图的应用——求最少换车次数。
函数buildG的功能是输入车站数、公交线路数,以及各公交线路的车站等信息,然后构建有向图的邻接矩阵。对每一条线路,按从始发站至终点站的顺序输入线路上的车站编号。空 (1)所在while循环正是用来顺序读入某一条线路上的车站编号。为了实现输入-1表示结束,先将输入值保存在临时变量dd中,若dd不为-1,则将dd的值保存到数组a中,sc是当前线路站计数器,注意到while循环体中并没有类似sc++的语句,故空(1)应填a[sc++]=dd。
某条新路输入完毕后,用for循环来构建有向图G中关于该条线路的邻接矩阵。根据邻接矩阵的定义易得,空(2)应填“[a[j]][a[k]]”。
函数minLen的功能是根据图G的邻接矩阵求从站0到站n-1的最少换车次数。函数中采用求两点间最短路径的算法。先将邻接矩阵的第0行内容复制到数组dist[],并置dist[0]为1。这样,就在dist[]中预置了能从站0出发直接到达的车站。接着是一个循环,每次循环做以下事情:利用数组dist[],找出下一个最少上车次数的站号。如果没有这样的站号(站0不可达站n-1),或下一个最少上车次数的站就是n-1(找到解),则结束循环。若找到下一个最少上车次数的车站但还不是n-1号站,则设置该站已求得站0到达该站所需最少上车次数dist[k];将dist[k]的值变为负值。值为负就表示已为站k求得解,到达站k的最少上车次数为-dist[k]。由于已求得站k最少上车次数,那些还未求得的最少上车次数、经过k站可以达到的车站的上车次数应做相应调整。顺序考查各站j(站0除外),若站j还未求得解(dist[j]>0),并且经站 k能直接到达站j(g[k][j]=1),并且或从站0不能到达站j,或到达站j的上车次数比经过站k到达的次数要多(dits[j]==0|| -dist[k]+1<dist[j]),则到达站j的最少上车次数改为-dist[k]+1。故空(3)应为“dist[j]>=0&& g[k][j]==1”,空(4)应填“-dist[k]+1”。
求解循环结束有两种情况,一是没有找到下一个最少上车次数的站(k<0),二是下一个最少上车次数的站就是n-1号站。若是前者,函数因未找到解而返回-1(任意负值均可);若是后一种情况,从站0到站n-1上车次数为dist[n-1],即换车次数是dist[n-1]-1。故空
(5)应填“k<0 ?-1:j-1”。
转载请注明原文地址:https://kaotiyun.com/show/E5xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
ISDN是由(51)定义的一种网络设备标准。在ISDN的各种设备之间定义可(52)个参考点,其中把网络终端设备和用户终端设备分开的参考点为(53)。若一个大的企业要连入ISDN,要用到一个叫NT2的设备,NT2实际上就是(54)。ISDN网络的构成不包括(
ISDN是由(51)定义的一种网络设备标准。在ISDN的各种设备之间定义可(52)个参考点,其中把网络终端设备和用户终端设备分开的参考点为(53)。若一个大的企业要连入ISDN,要用到一个叫NT2的设备,NT2实际上就是(54)。ISDN网络的构成不包括(
在OSI网络管理标准中定义了网络管理的5大功能。对历史数据进行分析、统计和整理,为未来的网络规划提供参考的功能属于(41);提供一系列实时数据采集、分析和可视化工具对流程、负载、丢包、温度、内存、延迟等网络设备和线路进行实时检测的功能属于(42);接收报警
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
DQDB同时支持(26)两种服务。DQDB子网的双总线结构由(27)总线以及接在这两条总线上的大量的节点组成。DQDB网络为双总线提供了(28)访问控制方式,其中能够提供非等时服务是(29),它用于(30)业务。
Linux中一种常用的引导工具是(51);在Linux操作系统下安装网卡,如果操作系统没有内置的驱动程序,那么用户必须(52),才能完成驱动程序的安装;为一块设备名为eth0的网卡分配IP地址和子网掩码的命令是:(53);如果不打算使用DNS或者NIS进行
随机试题
激光打印机属于()。
猪向牛抱怨它不受人们的欢迎:“人们经常提及你的善良和你那仁慈的目光。确实,你给予了人们牛奶和奶油,但我给予人类的更多,我奉献人类熏肉和火腿,但是,人们还是不喜欢我,为什么?”牛想了想说:“也许是因为我是在生前奉献的。”牛的回答很巧妙,生前奉献是针对猪的评论
人民法院的下列哪些做法违反了两审终审制度?()
注册造价工程师继续教育规定,在公开发行的国家级杂志上发表工程造价管理方面的专业论文,每篇论文计( )个学时。
导游进行沿途风光讲解时,应注意()。
心理咨询过程应该(),才能帮助人们纠正不合理的欲望和错误的观念。
中国特色社会主义进入新时代,我国社会主要矛盾已经转化为人民日益增长的()需要和()的发展之间的矛盾。
王某邀请张某到家里吃饭,张某打车准时到王某家门口时,王某打电话给张某说,自己要加班.不能请张某吃饭了,张某只好又打车回家,以下说法正确的是()。
1903年,清政府下令废除科举,兴办学堂。()
暑期集训营有四个班,编号分别是1、2、3、4,每个班中恰好有一台电脑和一支手写笔。这8件物品每一件都是在2013年、2014年和2015年这三年中的某一年购进的,且满足以下条件:(1)1班的电脑和3班的手写笔是在2014年购进的;(2)2班的电脑和1班
最新回复
(
0
)