st10.htm

1800道数据结构题和答案

style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>B. </span>冒泡<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>C. </span>快速 <span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>D. </span>插入<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋体'>20</span><span style='font-family:
宋体'>．对序列<span lang=EN-US>{15</span>，<span lang=EN-US>9</span>，<span lang=EN-US>7</span>，<span
lang=EN-US>8</span>，<span lang=EN-US>20</span>，<span lang=EN-US>-1</span>，<span
lang=EN-US>4}</span>进行排序，进行一趟后数据的排列变为<span lang=EN-US>{4</span>，<span
lang=EN-US>9</span>，<span lang=EN-US>-1</span>，<span lang=EN-US>8</span>，<span
lang=EN-US>20</span>，<span lang=EN-US>7</span>，<span lang=EN-US>15}</span>；则采用的是（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）排序。
【南京理工大学<span lang=EN-US> 1998 </span>一、<span lang=EN-US>8</span>（<span
lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=a style='margin-right:0cm;text-indent:34.2pt;mso-char-indent-count:
3.0'><span lang=EN-US style='font-family:宋体'>A. </span><span style='font-family:
宋体'>选择 <span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>B. </span>快速<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>C. </span>希尔<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>D. </span>冒泡<span lang=EN-US><o:p></o:p></span></span></p>

<p class=a style='margin-top:0cm;margin-right:0cm;margin-bottom:0cm;margin-left:
9.7pt;margin-bottom:.0001pt;text-indent:-9.7pt;mso-char-indent-count:-.85'><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 style='mso-bidi-font-weight:
bold'>若上题的数据经一趟排序后的排列为<span lang=EN-US>{9</span>，<span lang=EN-US>15</span>，<span
lang=EN-US>7</span>，<span lang=EN-US>8</span>，<span lang=EN-US>20</span>，<span
lang=EN-US>-1</span>，<span lang=EN-US>4}</span>，则采用的是（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）排序。<span lang=EN-US><o:p></o:p></span></span></span></p>

<p class=a style='margin-right:0cm;text-indent:22.8pt;mso-char-indent-count:
2.0'><span lang=EN-US style='font-family:宋体'>A</span><span style='font-family:
宋体'>．选择<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>B. </span>堆 <span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>C.
</span>直接插入<span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>D. </span>冒泡<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></span>【南京理工大学<span lang=EN-US> 1998 </span>一、<span
lang=EN-US>9</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:9.7pt;text-indent:-9.7pt;mso-char-indent-count:
-.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>22</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．下列排序算法中<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>)</span>不能保证每趟排序至少能将一个元素放到其最终的位置上。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:93.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'>&nbsp; </span>B. shell</span>排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>C. </span>堆排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>D.</span>冒泡排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span></span>【合肥工业大学<span
lang=EN-US> 2001 </span>一、<span lang=EN-US>3</span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:17.35pt;text-indent:-17.35pt;mso-char-indent-count:
-1.52'><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'>&nbsp;&nbsp;&nbsp; </span>)</span>排序在一趟结束后不一定能选出一个元素放在其最终位置上。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;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'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>B. </span>冒泡<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>C. </span>归并<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>D. </span>堆<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:93.0pt'><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>【南京理工大学<span
lang=EN-US> 2001 </span>一、<span lang=EN-US>7</span>（<span lang=EN-US>1.5</span>分）】
【哈尔滨工业大学<span lang=EN-US> 2001 <span style='mso-spacerun:yes'>&nbsp;</span></span></span><!--[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'>&nbsp;</span>= 2 \* CHINESENUM3 <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>4</span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:
-.4'><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><span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span></span>）是执行第一趟快速排序后所得的序列。<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span></span>【福州大学<span
lang=EN-US> 1998 </span>一、<span lang=EN-US>9 <span
style='mso-spacerun:yes'>&nbsp;</span>(2</span>分<span lang=EN-US>)</span>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:
-.4'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>A. [68</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>，<span lang=EN-US>11</span>，<span lang=EN-US>18</span>，<span
lang=EN-US>69]<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>[23</span>，<span
lang=EN-US>93</span>，<span lang=EN-US>73]<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>B. [68</span>，<span lang=EN-US>11</span>，<span
lang=EN-US>69</span>，<span lang=EN-US>23]<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>[18</span>，<span lang=EN-US>93</span>，<span
lang=EN-US>73] <o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:4.55pt;text-indent:-4.55pt;mso-char-indent-count:
-.4'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>C. [93</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>，<span lang=EN-US>73]<span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>[68</span>，<span lang=EN-US>11</span>，<span
lang=EN-US>69</span>，<span lang=EN-US>23</span>，<span lang=EN-US>18]<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>D. [68</span>，<span
lang=EN-US>11</span>，<span lang=EN-US>69</span>，<span lang=EN-US>23</span>，<span
lang=EN-US>18]<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span>[93</span>，<span
lang=EN-US>73]<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>25</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．有一组数据（<span lang=EN-US>15</span>，<span lang=EN-US>9</span>，<span
lang=EN-US>7</span>，<span lang=EN-US>8</span>，<span lang=EN-US>20</span>，<span
lang=EN-US>-1</span>，<span lang=EN-US>7</span>，<span lang=EN-US>4</span>） 用快速排序的划分方法进行一趟划分后数据的排序为
<span lang=EN-US>(<span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>)</span>（按递增序）。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></span>【南京理工大学<span lang=EN-US>
1996<span style='mso-spacerun:yes'>&nbsp; </span></span>一、<span lang=EN-US>4 </span>（<span
lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.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>B</span>，<span
lang=EN-US>C</span>，<span lang=EN-US>D</span>都不对。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>B</span>．<span
lang=EN-US>9</span>，<span lang=EN-US>7</span>，<span lang=EN-US>8</span>，<span
lang=EN-US>4</span>，<span lang=EN-US>-1</span>，<span lang=EN-US>7</span>，<span
lang=EN-US>15</span>，<span lang=EN-US>20<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>20</span>，<span
lang=EN-US>15</span>，<span lang=EN-US>8</span>，<span lang=EN-US>9</span>，<span
lang=EN-US>7</span>，<span lang=EN-US>-1</span>，<span lang=EN-US>4</span>，<span
lang=EN-US>7<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>D. 9</span>，<span
lang=EN-US>4</span>，<span lang=EN-US>7</span>，<span lang=EN-US>8</span>，<span
lang=EN-US>7</span>，<span lang=EN-US>-1</span>，<span lang=EN-US>15</span>，<span
lang=EN-US>20<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>26</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．一组记录的关键码为（<span lang=EN-US>46</span>，<span lang=EN-US>79</span>，<span
lang=EN-US>56</span>，<span lang=EN-US>38</span>，<span lang=EN-US>40</span>，<span
lang=EN-US>84</span>），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）。<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span></span>【燕山大学 <span lang=EN-US>2001 </span>一、<span
lang=EN-US>4</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;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>(38,40,46,56,79,84)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span>B. (40,38,46,79,56,84)<o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>C</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>．<span lang=EN-US>(40,38,46,56,79,84)<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>D. (40,38,46,84,56,79)<o:p></o:p></span></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>27. </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'>&nbsp;&nbsp;&nbsp; </span>) </span>。
【南京理工大学<span lang=EN-US> 1999 </span>一、<span lang=EN-US>17</span>（<span
lang=EN-US>1</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:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>．希尔排序<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>B. </span>堆排序<span
lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>C. </span>选择排序<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>D. </span>归并排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:17.35pt;text-indent:-17.35pt;mso-char-indent-count:
-1.52;tab-stops:36.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>28</span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是<span lang=EN-US>( <span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span>)</span>排序。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:17.35pt;text-indent:-17.35pt;mso-char-indent-count:
-1.52;tab-stops:36.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>A</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>． 冒泡<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span>B. </span>希尔 <span
style='mso-spacerun:yes'>&nbsp;</span><span lang=EN-US>C. </span>快速 <span
style='mso-spacerun:yes'>&nbsp;</span><span lang=EN-US>D. </span>堆<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span></span>【南京理工大学<span
lang=EN-US> 2001 </span>一、<span lang=EN-US>12 </span>（<span lang=EN-US>1.5</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:9.7pt;text-indent:-9.7pt;mso-char-indent-count:
-.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>29.</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;mso-font-kerning:
0pt'>下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;color:black;
mso-font-kerning:0pt'>A. </span><span style='mso-bidi-font-size:10.5pt;
font-family:宋体;color:black;mso-font-kerning:0pt'>直接插入排序<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>B. </span>快速排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;
</span>C.<span style='mso-spacerun:yes'>&nbsp; </span></span>直接选择排序<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>D.<span style='mso-spacerun:yes'>&nbsp; </span></span>堆排序<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:21.1pt;text-indent:-21.1pt;mso-char-indent-count:
-1.85'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>30. </span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>对初始状态为递增序列的表按递增顺序排序，最省时间的是（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）算法，最费时间的是（<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </sp