📄 st07.htm
字号:
style='mso-spacerun:yes'> </span>B</span>．<span
lang=EN-US>1347652<span style='mso-spacerun:yes'>
</span>C</span>．<span lang=EN-US>1534276<span
style='mso-spacerun:yes'> </span>D</span>．<span lang=EN-US>1247653<span
style='mso-spacerun:yes'> </span>E</span>．以上答案均不正确<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.0pt'><!--[if supportFields]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-element:field-begin'></span><span
style='mso-spacerun:yes'> </span>= 2 \* GB3 <span style='mso-element:field-separator'></span></span><![endif]--><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-no-proof:yes'>②</span><!--[if supportFields]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-element:field-end'></span></span><![endif]--><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>．<span lang=EN-US>A</span>．<span lang=EN-US>1534267<span
style='mso-spacerun:yes'> </span>B</span>．<span
lang=EN-US>1726453<span style='mso-spacerun:yes'>
</span>C</span>．<span lang=EN-US>l354276<span
style='mso-spacerun:yes'> </span>D</span>．<span
lang=EN-US>1247653<span style='mso-spacerun:yes'>
</span>E</span>．以上答案均不正确<span lang=EN-US><span
style='mso-spacerun:yes'> </span><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:180.0pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>19</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>．下面哪一方法可以判断出一个有向图是否有环（回路）：【东北大学<span lang=EN-US> 2000 4</span>、<span
lang=EN-US>2</span>（<span lang=EN-US>4</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:26.0pt;mso-char-indent-count:2.48;
tab-stops:180.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>A</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．深度优先遍历 <span lang=EN-US><span
style='mso-spacerun:yes'> </span>B. </span>拓扑排序<span lang=EN-US><span
style='mso-spacerun:yes'> </span>C. </span>求最短路径<span lang=EN-US><span
style='mso-spacerun:yes'> </span>D. </span>求关键路径<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:list 72.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>20. </span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>在图采用邻接表存储时，求最小生成树的<span
lang=EN-US> Prim </span>算法的时间复杂度为<span lang=EN-US>(<span
style='mso-spacerun:yes'> </span>)</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A. O(n)<span
style='mso-spacerun:yes'> </span><span style='mso-tab-count:
1'> </span><span style='mso-spacerun:yes'> </span>B.
O(n+e)<span style='mso-spacerun:yes'>
</span>C. O(n<sup>2</sup>)<span
style='mso-spacerun:yes'> </span>D. O(n<sup>3</sup>)<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【合肥工业大学<span lang=EN-US> 2001 </span>一、<span
lang=EN-US>2 </span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>21. </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>下面是求连通网的最小生成树的<span lang=EN-US>prim</span>算法：集合<span
lang=EN-US>VT</span>，<span lang=EN-US>ET</span>分别放顶点和边，初始为（<span lang=EN-US> 1 </span>），下面步骤重复<span
lang=EN-US>n-1</span>次<span lang=EN-US>: a</span>：（<span lang=EN-US> 2 </span>）；<span
lang=EN-US>b</span>：（<span lang=EN-US> 3 </span>）；最后：（<span lang=EN-US> 4 </span>）。【南京理工大学<span
lang=EN-US> 1997 </span>一、<span lang=EN-US>11_14 </span>（<span lang=EN-US>8</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0;
mso-outline-level:1;tab-stops:44.25pt'><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>（<span lang=EN-US>1</span>）．<span lang=EN-US>A</span>．<span
lang=EN-US>VT</span>，<span lang=EN-US>ET</span>为空<span lang=EN-US><span
style='mso-spacerun:yes'>
</span>B</span>．<span lang=EN-US>VT</span>为所有顶点，<span lang=EN-US>ET</span>为空<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>
</span>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span
lang=EN-US>VT</span>为网中任意一点，<span lang=EN-US>ET</span>为空<span lang=EN-US><span
style='mso-spacerun:yes'>
</span>D</span>．<span lang=EN-US>VT</span>为空，<span lang=EN-US>ET</span>为网中所有边<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0;
mso-outline-level:1;tab-stops:44.25pt'><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>（<span lang=EN-US>2</span>）．<span lang=EN-US>A. </span>选<span
lang=EN-US>i</span>属于<span lang=EN-US>VT</span>，<span lang=EN-US>j</span>不属于<span
lang=EN-US>VT</span>，且（<span lang=EN-US>i</span>，<span lang=EN-US>j</span>）上的权最小<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>
</span>B</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．选<span
lang=EN-US>i</span>属于<span lang=EN-US>VT</span>，<span lang=EN-US>j</span>不属于<span
lang=EN-US>VT</span>，且（<span lang=EN-US>i</span>，<span lang=EN-US>j</span>）上的权最大<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>
</span>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．选<span
lang=EN-US>i</span>不属于<span lang=EN-US>VT</span>，<span lang=EN-US>j</span>不属于<span
lang=EN-US>VT</span>，且（<span lang=EN-US>i</span>，<span lang=EN-US>j</span>）上的权最小<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>
</span>D</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．选<span
lang=EN-US>i</span>不属于<span lang=EN-US>VT</span>，<span lang=EN-US>j</span>不属于<span
lang=EN-US>VT</span>，且（<span lang=EN-US>i</span>，<span lang=EN-US>j</span>）上的权最大<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0;
mso-outline-level:1;tab-stops:44.25pt'><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>（<span lang=EN-US>3</span>）．<span lang=EN-US>A</span>．顶点<span
lang=EN-US>i</span>加入<span lang=EN-US>VT</span>，（<span lang=EN-US>i,j</span>）加入<span
lang=EN-US>ET<span
style='mso-spacerun:yes'>
</span>B. </span>顶点<span lang=EN-US>j</span>加入<span lang=EN-US>VT</span>，（<span
lang=EN-US>i,j</span>）加入<span lang=EN-US>ET<o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span
style='mso-spacerun:yes'>
</span>C. </span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>顶点<span
lang=EN-US>j</span>加入<span lang=EN-US>VT</span>，（<span lang=EN-US>i,j</span>）从<span
lang=EN-US>ET</span>中删去<span lang=EN-US><span
style='mso-spacerun:yes'> </span>D</span>．顶点<span
lang=EN-US>i,j</span>加入<span lang=EN-US>VT</span>，（<span lang=EN-US>i,j</span>）加入<span
lang=EN-US>ET<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0;
mso-outline-level:1;tab-stops:44.25pt'><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>（<span lang=EN-US>4</span>）．<span lang=EN-US>A</span>．<span
lang=EN-US>ET </span>中为最小生成树<span lang=EN-US><span
style='mso-spacerun:yes'>
</span>B</span>．不在<span lang=EN-US>ET</span>中的边构成最小生成树<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>
</span>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span
lang=EN-US>ET</span>中有<span lang=EN-US>n-1</span>条边时为生成树，否则无解<span lang=EN-US><span
style='mso-spacerun:yes'> </span>D</span>．<span lang=EN-US>ET</span>中无回路时，为生成树，否则无解<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>22. (1). </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体'>求从指定源点到其余各顶点的迪杰斯特拉（<span lang=EN-US>Dijkstra</span>）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>(2). </span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>利用<span lang=EN-US>Dijkstra</span>求每一对不同顶点之间的最短路径的算法时间是<span
lang=EN-US>O(n<sup>3</sup> ) </span>；（图用邻接矩阵表示）<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>(3). Floyd</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>上面不正确的是（<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>）。【南京理工大学<span
lang=EN-US> 2000 </span>一、<span lang=EN-US>21 </span>（<span lang=EN-US>1.5</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:bold'>．</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>(1),(2),(3)<span
style='mso-spacerun:yes'>
</span>B</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-bidi-font-weight:bold'>．</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>(1)<span
style='mso-spacerun:yes'>
</span>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-bidi-font-weight:bold'>．</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>(1),(3)<span
style='mso-spacerun:yes'>
</span>D</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-bidi-font-weight:bold'>．</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>(2),(3)<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>23</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．当各边上的权值<span lang=EN-US>(<span style='mso-spacerun:yes'> </span>)</span>时，<span
lang=EN-US>BFS</span>算法可用来解决单源最短路径问题。【<span style='color:black'>中科院计算所<span
lang=EN-US>2000</span>一、<span lang=EN-US>3 (2</span>分）</span>】<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．均相等<span lang=EN-US><span
style='mso-spacerun:yes'> </span>B</span>．均互不相等<span
lang=EN-US><span style='mso-spacerun:yes'> </span>C</span>．不一定相等<b><span
lang=EN-US><o:p></o:p></span></b></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>24. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>求解最短路径的<span lang=EN-US>Floyd</span>算法的时间复杂度为<span lang=EN-US>(<span
style='mso-spacerun:yes'> </span>)</span>。【合肥工业大学<span
lang=EN-US> 1999 </span>一、<span lang=EN-US>2 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:20.95pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>O</span>（<span
lang=EN-US>n</span>）<span lang=EN-US><span
style='mso-spacerun:yes'> </span>B. O</span>（<span
lang=EN-US>n+c</span>）<span lang=EN-US><span
style='mso-spacerun:yes'> </span>C. O</span>（<span
lang=EN-US>n*n</span>）<span lang=EN-US><span
style='mso-spacerun:yes'> </span>D. O</span>（<span
lang=EN-US>n*n*n</span>）<⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -