st09.htm

1800道数据结构题和答案

宋体'>在一棵含有<span lang=EN-US>n</span>个关键字的<span lang=EN-US>m</span>阶<span
lang=EN-US>B-</span>树中进行查找，至多读盘<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>)</span>次。【<span
style='color:black'>中科院计算所 <span lang=EN-US>2000 </span>一、<span lang=EN-US>6 </span>（<span
lang=EN-US>2</span>分）</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;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp; </span>A. log<sub>2</sub><sup>n</sup><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp; </span>B.<span
style='mso-spacerun:yes'>&nbsp; </span>1+log<sub>2</sub><sup>n</sup><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>C.<span
style='mso-spacerun:yes'>&nbsp; </span>1+log<sub><!--[if gte vml 1]><v:shapetype
 id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
 path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
 <v:stroke joinstyle="miter"/>
 <v:formulas>
  <v:f eqn="if lineDrawn pixelLineWidth 0"/>
  <v:f eqn="sum @0 1 0"/>
  <v:f eqn="sum 0 0 @1"/>
  <v:f eqn="prod @2 1 2"/>
  <v:f eqn="prod @3 21600 pixelWidth"/>
  <v:f eqn="prod @3 21600 pixelHeight"/>
  <v:f eqn="sum @0 0 1"/>
  <v:f eqn="prod @6 1 2"/>
  <v:f eqn="prod @7 21600 pixelWidth"/>
  <v:f eqn="sum @8 21600 0"/>
  <v:f eqn="prod @7 21600 pixelHeight"/>
  <v:f eqn="sum @10 21600 0"/>
 </v:formulas>
 <v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
 <o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:24.75pt;
 height:33.75pt' o:ole="">
 <v:imagedata src="st09.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image002.gif" v:shapes="_x0000_i1025"><![endif]><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
  DrawAspect="Content" ObjectID="_1149856912">
 </o:OLEObject>
</xml><![endif]--></sub><sub><!--[if gte vml 1]><v:shape id="_x0000_i1026"
 type="#_x0000_t75" style='width:38.25pt;height:33.75pt' o:ole="">
 <v:imagedata src="st09.files/image003.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=51 height=45
src="st09.files/image004.gif" v:shapes="_x0000_i1026"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1026"
  DrawAspect="Content" ObjectID="_1149856917">
 </o:OLEObject>
</xml><![endif]--><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>D.<span
style='mso-spacerun:yes'>&nbsp; </span>1+log<sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1027" type="#_x0000_t75" style='width:21.75pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image005.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=29 height=45
src="st09.files/image006.gif" v:shapes="_x0000_i1027"><![endif]></sub><sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1028" type="#_x0000_t75" style='width:41.25pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image007.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=55 height=45
src="st09.files/image008.gif" v:shapes="_x0000_i1028"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1028"
  DrawAspect="Content" ObjectID="_1149856923">
 </o:OLEObject>
</xml><![endif]--><b><o:p></o:p></b></span></p>

<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
font-family:宋体'>25. m</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>1</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>(</span>（<span lang=EN-US>3</span>）<span
lang=EN-US>)</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>5</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; </span>A. m</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋体'>路平衡查找树<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span>B. m</span>路平衡索引树<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp; </span>C. m</span>路<span lang=EN-US>Ptrie</span>树<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>D. m</span>路键树<span
lang=EN-US><span style='mso-spacerun:yes'>&nbsp; </span>E. m-1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;</span>F. m<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;</span>G. m+1<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; </span>H. <sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1029" type="#_x0000_t75" style='width:24.75pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image009.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image002.gif" v:shapes="_x0000_i1029"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1029"
  DrawAspect="Content" ObjectID="_1149856924">
 </o:OLEObject>
</xml><![endif]-->-1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;</span><st1:place
w:st="on">I.</st1:place> <sub><!--[if gte vml 1]><v:shape id="_x0000_i1030"
 type="#_x0000_t75" style='width:24.75pt;height:33.75pt' o:ole="">
 <v:imagedata src="st09.files/image009.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image002.gif" v:shapes="_x0000_i1030"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1030"
  DrawAspect="Content" ObjectID="_1149856925">
 </o:OLEObject>
</xml><![endif]--><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>J. <sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1031" type="#_x0000_t75" style='width:24.75pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image009.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image002.gif" v:shapes="_x0000_i1031"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1031"
  DrawAspect="Content" ObjectID="_1149856926">
 </o:OLEObject>
</xml><![endif]-->+1<o:p></o:p></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>m</span>阶的<span lang=EN-US>B+</span>树中<span lang=EN-US>,
</span>每个非叶结点的儿子数<span lang=EN-US>S </span>应满足 <span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>). </span>【武汉交通科技大学<span
lang=EN-US> 1996 </span>一、<span lang=EN-US>3 (4</span>分<span lang=EN-US>) </span>】<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal style='text-indent:21.6pt'><span lang=EN-US
style='mso-bidi-font-size:10.5pt;font-family:宋体'>A.<sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1032" type="#_x0000_t75" style='width:39.75pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image010.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=53 height=45
src="st09.files/image011.gif" v:shapes="_x0000_i1032"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1032"
  DrawAspect="Content" ObjectID="_1149856927">
 </o:OLEObject>
</xml><![endif]--></span><span style='mso-bidi-font-size:10.5pt;font-family:
宋体'>≤<span lang=EN-US>S</span>≤<span lang=EN-US>m<span
style='mso-spacerun:yes'>&nbsp; </span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>B. <sub><!--[if gte vml 1]><v:shape
 id="_x0000_i1033" type="#_x0000_t75" style='width:24.75pt;height:33.75pt'
 o:ole="">
 <v:imagedata src="st09.files/image012.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image013.gif" v:shapes="_x0000_i1033"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1033"
  DrawAspect="Content" ObjectID="_1149856928">
 </o:OLEObject>
</xml><![endif]--></span>≤<span lang=EN-US>S</span>≤<span lang=EN-US>m <span
style='mso-spacerun:yes'>&nbsp;</span><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;</span>C. 1</span>≤<span lang=EN-US>S</span>≤<span
lang=EN-US><sub><!--[if gte vml 1]><v:shape id="_x0000_i1034" type="#_x0000_t75"
 style='width:39.75pt;height:33.75pt' o:ole="">
 <v:imagedata src="st09.files/image010.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=53 height=45
src="st09.files/image011.gif" v:shapes="_x0000_i1034"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1034"
  DrawAspect="Content" ObjectID="_1149856929">
 </o:OLEObject>
</xml><![endif]--><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>D. 1</span>≤<span
lang=EN-US>S</span>≤<span lang=EN-US><sub><!--[if gte vml 1]><v:shape id="_x0000_i1035"
 type="#_x0000_t75" style='width:24.75pt;height:33.75pt' o:ole="">
 <v:imagedata src="st09.files/image012.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=33 height=45
src="st09.files/image013.gif" v:shapes="_x0000_i1035"><![endif]></sub><!--[if gte mso 9]><xml>
 <o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1035"
  DrawAspect="Content" ObjectID="_1149856930">
 </o:OLEObject>
</xml><![endif]--><o:p></o:p></span></span></p>

<p class=MsoNormal style='margin-left:28.6pt;text-indent:-28.6pt;mso-char-indent-count:
-3.0;tab-stops:44.25pt'><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>{19</span>，<span lang=EN-US>14</span>，<span
lang=EN-US>23</span>，<span lang=EN-US>1</span>，<span lang=EN-US>68</span>，<span
lang=EN-US>20</span>，<span lang=EN-US>84</span>，<span lang=EN-US>27</span>，<span
lang=EN-US>55</span>，<span lang=EN-US>11</span>，<span lang=EN-US>10</span>，<span
lang=EN-US>79}</span>，用链地址法构造散列表，散列函数为<span lang=EN-US>H</span>（<span
lang=EN-US>key</span>）<span lang=EN-US>=key MOD 13,</span>散列地址为<span
lang=EN-US>1</span>的链中有（<span lang=EN-US><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span></span>）个记录。【南京理工大学<span
lang=EN-US> 1997 </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:19.05pt;mso-char-indent-count:2.0;
mso-outline-level:1;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>1<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>B. 2<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>C. 3<span style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>D. 4<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:宋体'>28.<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>(Hash</span>，杂凑<span
lang=EN-US>)</span>查找的说法正确的是<span lang=EN-US>(<span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp; </span>)<span
style='mso-spacerun:yes'>&nbsp; </span></span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋体'>【南京理工大学<span lang=EN-US> 1998 </span>一、<span lang=EN-US>10
</span>（<span lang=EN-US>2</span>分）】<span lang=EN-US style='mso-bidi-font-weight:
bold'><span
style='mso-spacerun:yes'>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>A</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;&nbsp;&nbsp; </span><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>B</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; </span><o:p></o:p></span></span></p>

<p class=MsoNormalIndent style='text-indent:19.05pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>C</span><span style='mso-bidi-font-size:10.5pt;font-family:宋体;mso-bidi-font-weight:
bold'>．不存在特别好与坏的哈希函数，要视情况而定<sp