2. 计算机
  3. 阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，

阅读下列C程序和程序说明，将应填入(n)处的字句写在对应栏内。 【说明】设某城市有n个车站，并有m条公交线路连接这些车站，设这些公交车都是单向的，这n个车站被顺序编号为0至n-1。本程序，输入该城市的公交线路数、车站个数，以及各公交线路上的各站编号，

admin2009-02-15  48
问题 阅读下列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://www.kaotiyun.com/show/RrDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)