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

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

admin2009-05-15  18
问题 阅读下列程序说明和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

软件设计师上午基础知识考试

软考中级

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