question_4.htm

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

<p class=MsoNormal style='mso-layout-grid-align:none;text-autospace:none'><span
lang=EN-US 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'>EdgeType</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'>typedef ElemType EdgeType</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'>typedef struct{//</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'>VertexType vexs[MAX_VERTEX_NUM]</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
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'>EdgeType edge[MAX_EDGE_NUM]</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
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 vexnum</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'>arcnum</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
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;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>}</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>ELGraph</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 MiniSpanTree_Kruskal(ELGraph
G</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'>SqList&amp;
MSTree){<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'>//G.edge </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'>//</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'>MSTree</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'>MFSetF</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'>InitSet(F</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'>G.vexnum)</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'>F</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
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'>InitList(MSTree</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'>G.vexnum)</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
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'>i=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=1</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'>while(k&lt;<u><span
style="mso-spacerun: yes">&nbsp; </span>(1)<span style="mso-spacerun:
yes">&nbsp; </span></u>){<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'>e=G.edge[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'>//</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
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'>/*</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'>fix_mfset</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'>rl=fix_mfset(F</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'>LocateVex(e.vex1))</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'>r2=<u><span style="mso-spacerun:
yes">&nbsp; </span>(2)<span style="mso-spacerun: yes">&nbsp; </span></u>//</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'>if(r1<u><span style="mso-spacerun:
yes">&nbsp; </span>(3)<span style="mso-spacerun: yes">&nbsp; </span></u>r2){//</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
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'>if(ListInsert(MSTree</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'>e){<u><span style="mso-spacerun:
yes">&nbsp; </span>(4)<span style="mso-spacerun: yes">&nbsp; </span></u></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
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'>mix_mfset(E</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'>rl</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'>r2)</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
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;font-family:宋体;mso-hansi-font-family:
"Times New Roman"'>}<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'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span><u><span style="mso-spacerun:
yes">&nbsp;&nbsp;</span>(5)<span style="mso-spacerun: yes">&nbsp; </span></u></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
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'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span></span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体;mso-hansi-font-family:"Times New Roman"'>}<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'>DestroySet(F)</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 align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体;mso-hansi-font-family:"Times New Roman"'>}</span><span
style='font-size:8.5pt;font-family:"MS Sans Serif";mso-font-kerning:0pt;
mso-ansi-language:ZH-CN'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

</div>

</body>

</html>