question_6.htm

软件设计师模拟试卷,点击里面的Exe文件可以随机出题

style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>≤</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i,j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n)</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示从顶点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>到顶点</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的中间顶点序号不大于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k </span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的最短路径长度。如果</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>到</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的路径没有中间顶点，则对于</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>0</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>≤</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>n,</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>有</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Ck(i,j)=C0(i,j)=a</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］。递推地产生</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>C1</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>C2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>，…，</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>Cn</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>【</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>C++</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>代码】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>#include&lt;iostream</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>h&gt;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＃</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>define NoEdge 10000 //</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>当两个顶点之间没有边相连时，在邻接矩阵中用</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>NoEdge</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>表示<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void Make2DArray(int * *
&amp;x,int rows,int cols);<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>class AdjacencyWDigraph{<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>private<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int n;//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>有向网中的顶点数目<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int**a;//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>存储顶点间弧上的权值<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int**c;//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>存储计算出的最短路径长度<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int**kay;//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>存储求出的最短路径<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>pubic:<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>int Vertices()const {return n;}<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void AllPairs();<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void Input();//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>输入有向网的顶点数、各条弧及权值，建立邻接矩阵</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>a<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void OutShortestPath(int i,int
j);//</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>计算顶点</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>到</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>的最短路径</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>试卷中未列出</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>~AdjacencyWDigraph();//</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>析构函数</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>(</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>试卷中未列出</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>private:<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void outputPath(int i,int j);<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>};<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>void AdjacencyWDigraph::AllPairs()<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>{int i,j,k,t1,t2,t3;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(i=1;i</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=n;k++)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(j=1;j</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=n;++j)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>{c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=<u><span style="mso-spacerun:
yes">&nbsp; </span>(1)<span style="mso-spacerun: yes">&nbsp; </span></u>;kay</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=0;}<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(k=1;k</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=n;k++)<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(i=1;i</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=n;i++){<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if(i==k) continue;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>t1=c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>for(j=1;j</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>=n;j++){<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if(j==k||j==i)continue;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>t2=c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>k</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;t3=c</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>;<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>if(t1!=NoEdge &amp;&amp;
t2!=NoEdge &amp;&amp;(t3==NoEdge||t1+t2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>＜</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>t3))<o:p></o:p></span></p>

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>{c</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>i</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>］［</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>j</span><span style='mso-bidi-font-size: