st09.htm

1800道数据结构题和答案

<p class=MsoNormal style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A.N+1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>B.2log<sub>2</sub>N<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>C.logN<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>D.N/2<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>E.Nlog<sub>2</sub>N<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>F.N<sup>2</sup><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>4. </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;&nbsp; </span>) </span>【南京理工大学<span
lang=EN-US> 1996 </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='text-indent:19.05pt;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; </span>C. </span>表必须有序，而且只能从小到大排列<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>B. </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;&nbsp; </span>D. </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:宋体'>5. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>对线性表进行二分查找时，要求线性表必须（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>）【燕山大学<span lang=EN-US>
2001 </span>一、<span lang=EN-US>5 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;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> B.</span>以顺序方式存储<span
lang=EN-US>,</span>且数据元素有序<span lang=EN-US> C.</span>以链接方式存储 <span lang=EN-US>D.</span>以链接方式存储<span
lang=EN-US>,</span>且数据元素有序<b><span lang=EN-US><o:p></o:p></span></b></span></p>

<p class=MsoNormal style='tab-stops:44.25pt'><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋体'>6</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> 1997 </span>一、<span lang=EN-US>6 </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:宋体'><span style='mso-spacerun:yes'>&nbsp;&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;&nbsp;&nbsp;&nbsp; </span>B</span>．链接方式存储，元素有序<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:10.85pt;mso-para-margin-left:1.14gd;
text-indent:9.55pt;mso-char-indent-count:1.0;tab-stops:44.25pt'><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><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>D</span>．顺序方式存储，元素有序<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='text-indent:0cm'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>7.<span style='mso-bidi-font-weight:
bold'> </span></span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;
mso-bidi-font-weight:bold'>用二分（对半）查找表的元素的速度比用顺序法<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>) </span></span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>【南京理工大学<span lang=EN-US> 1998 </span>一、<span
lang=EN-US>11 </span>（<span lang=EN-US>2</span>分）】<span lang=EN-US
style='mso-bidi-font-weight:bold'><span style='mso-spacerun:yes'>&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='margin-left:49.5pt;text-indent:-18.0pt;
mso-list:l3 level1 lfo5;tab-stops:list 49.5pt'><![if !supportLists]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-family:
宋体;mso-bidi-font-weight:bold'><span style='mso-list:Ignore'>A．<span
style='font:7.0pt "Times New Roman"'>&nbsp;&nbsp; </span></span></span><![endif]><span
style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:bold'>必然快<span
lang=EN-US><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;&nbsp; </span><span
style='mso-spacerun:yes'>&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>D. </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:宋体'>8</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
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;mso-char-indent-count:2.0;
tab-stops:44.25pt'><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;&nbsp;&nbsp; </span>B.</span>不一定<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>C. </span>在大部分情况下要快<span
lang=EN-US><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='text-indent:19.05pt;mso-char-indent-count:2.0;
tab-stops:44.25pt'><span style='mso-bidi-font-size:10.5pt;font-family:宋体'>【南京理工大学<span
lang=EN-US> 1997 </span>一、<span lang=EN-US>7 </span>（<span lang=EN-US>2</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:宋体'>9. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>具有<span lang=EN-US>12</span>个关键字的有序表，折半查找的平均查找长度（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span></span>）【中山大学<span lang=EN-US>
1998 </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>10 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:9.55pt;mso-char-indent-count:1.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span>A. 3.1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>B. 4<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>C. 2.5<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>D. 5<o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>10. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>折半查找的时间复杂性为（<span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;
</span></span>）【中山大学 <span lang=EN-US>1999 </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>= 1 \* 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>15</span>】<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>A. O</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>（<span lang=EN-US>n<sup>2</sup></span>）
<span style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;</span><span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>B. O</span>（<span lang=EN-US>n</span>）
<span lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span>C.
O</span>（<span lang=EN-US>nlog<sup>n</sup></span>）<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>D.<span style='mso-spacerun:yes'>&nbsp;
</span>O</span>（<span lang=EN-US>log<sup>n</sup></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:宋体'>11</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;&nbsp; </span>) </span>【南京理工大学<span
lang=EN-US> 1996 </span>一、<span lang=EN-US>7 </span>（<span lang=EN-US>2</span>分）】<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:19.05pt;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:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:28.6pt;mso-para-margin-left:2.0gd;
text-indent:-9.55pt;mso-char-indent-count:-1.0'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>B</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='margin-left:21.0pt'><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><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:21.0pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>D. </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><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>12. </span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>二叉查找树的查找效率与二叉树的<span lang=EN-US>( </span>（<span lang=EN-US>1</span>）<span
lang=EN-US>)</span>有关<span lang=EN-US>, </span>在<span lang=EN-US> (</span>（<span
lang=EN-US>2</span>）<span lang=EN-US>)</span>时其查找效率最低【武汉交通科技大学<span lang=EN-US>1996
</span>一、<span lang=EN-US>2(4</span>分<span lang=EN-US>)</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; </span>(1): <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;&nbsp;&nbsp;
</span>B. </span>结点的多少<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>C. </span>树型<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;</span>D. </span>结点的位置<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:38.15pt;text-indent:-38.15pt;mso-char-indent-count:
-4.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>(2): <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; </span>B. </span>完全二叉树<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>C. </span>呈单枝树<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>D. </span>结点太复杂。<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:9.55pt;text-indent:-9.55pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>13. </span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>要进行顺序查找，则线性表（<span lang=EN-US>1</span>）；要进行折半查询，则线性表（<span
lang=EN-US>2</span>）；若表中元素个数为<span lang=EN-US>n,</span>则顺序查找的平均比较次数为（<span
lang=EN-US>3</span>）；折半查找的平均比较次数为（<span lang=EN-US>4</span>）。【北方交通大学<span
lang=EN-US> 1999 </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='margin-left:9.55pt;text-indent:-9.55pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'><span
style='mso-spacerun:yes'>&nbsp; </span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>（<span lang=EN-US>1</span>）（<span lang=EN-US>2</span>）：<span
lang=EN-US>A. </span>必须以顺序方式存储； <span lang=EN-US>B. </span>必须以链式方式存储；<span
lang=EN-US>C. </span>既可以以顺序方式存储，也可以链式方式存储；<span lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:60.15pt;mso-char-indent-count:6.31'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>D. </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:60.45pt;mso-char-indent-count:6.34'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体'>E. </span><span