?? da09.htm
字號:
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>29.√<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>30.×<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>31.×<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>32.√<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.4pt;border-top:none;border-left:none;
border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>33.√<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>34.×<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>35.√<o:p></o:p></span></p>
</td>
<td width=47 valign=top style='width:35.45pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>36.√<o:p></o:p></span></p>
</td>
</tr>
</table>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph;
text-indent:22.35pt;mso-char-indent-count:2.0'><span style='font-size:10.5pt;
font-family:宋體'>部分答案解釋如下。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>4</span><span
style='font-size:10.5pt;font-family:宋體'>．不能說哪種哈希函數(shù)的選取方法最好，各種選取方法有自己的適用范圍。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>8</span><span
style='font-size:10.5pt;font-family:宋體'>．哈希表的結(jié)點中可以包括指針，指向其元素。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>11</span><span
style='font-size:10.5pt;font-family:宋體'>．單鏈表不能使用折半查找方法。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>20</span><span
style='font-size:10.5pt;font-family:宋體'>．按插入后中序遍歷是遞增序列的原則，若某結(jié)點只有右子樹，而插入元素的關(guān)鍵字小于該結(jié)點的關(guān)鍵字，則會插入到該結(jié)點的左側(cè)，成為其左孩子。這種插入就不是插入到葉子下面。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>21</span><span
style='font-size:10.5pt;font-family:宋體'>．從平衡因子定義看，完全二叉樹任一結(jié)點的平衡因子的絕對值確實是小于等于<span
lang=EN-US>1</span>。但是，平衡二叉樹本質(zhì)上是二叉排序樹，完全二叉樹不一定是排序樹。故不能說完全二叉樹是平衡二叉樹。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>23</span><span
style='font-size:10.5pt;font-family:宋體'>．某結(jié)點的左子樹根結(jié)點不一定是它的中序前驅(qū)，其右子樹根結(jié)點也不一定是它的中序后繼。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>24</span><span
style='font-size:10.5pt;font-family:宋體'>．在等概率下，查找成功時的平均查找長度相同，查找失敗時的平均查找長度不相同。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>26</span><span
style='font-size:10.5pt;font-family:宋體'>．只有被刪除結(jié)點是葉子結(jié)點時命題才正確。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
style='font-size:10.5pt;font-family:宋體'>三．填空題<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>1</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>n<span
style='mso-spacerun:yes'> </span>n+1<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>2</span>．<span
lang=EN-US>4<span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>3</span>．<span lang=EN-US>6,9,11,12 <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>4</span>．<span lang=EN-US>5<span
style='mso-spacerun:yes'> </span><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>5</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>26</span>（第<span
lang=EN-US>4</span>層是葉子結(jié)點，每個結(jié)點兩個關(guān)鍵字）<span lang=EN-US><span
style='mso-spacerun:yes'>
</span>6</span>．<span lang=EN-US>1,3,6,8,11,13,16,19<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>7</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>5,96<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>8</span>．<span
lang=EN-US>m-1,</span>「<span lang=EN-US>m/2</span></span><span lang=EN-US
style='font-size:10.5pt;font-family:Symbol;mso-ascii-font-family:宋體;mso-hansi-font-family:
宋體;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>ù</span></span><span lang=EN-US
style='font-size:10.5pt;font-family:宋體'>-1 <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>9</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>2,4,3<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>10</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>(1)</span>哈希函數(shù)<span
lang=EN-US>(2)</span>解決沖突的方法 <span lang=EN-US>(3)</span>選擇好的哈希函數(shù) <span
lang=EN-US>(4)</span>處理沖突的方法 <span lang=EN-US>(5)</span>均勻<span lang=EN-US>(6)</span>簡單<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>11</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>AVL</span>樹<span
style='color:red'>（高度平衡樹，高度平衡的二叉排序樹），</span>或為空二叉樹，或二叉樹中任意結(jié)點左子樹高度與右子樹高度差的絕對值小于等于<span
lang=EN-US>1</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>12</span><span
style='font-size:10.5pt;font-family:宋體'>．小于等于表長的最大素數(shù)或不包含小于<span lang=EN-US>20</span>的質(zhì)因子的合數(shù)<span
lang=EN-US><span style='mso-spacerun:yes'> </span>13</span>．<span
lang=EN-US>16<span style='mso-spacerun:yes'>
</span>14</span>．</span><span lang=EN-US style='font-size:10.5pt;font-family:
Symbol;mso-ascii-font-family:宋體;mso-hansi-font-family:宋體;mso-char-type:symbol;
mso-symbol-font-family:Symbol'><span style='mso-char-type:symbol;mso-symbol-font-family:
Symbol'>ë</span></span><span style='font-size:10.5pt;font-family:宋體'>㏒<sub><span
lang=EN-US>2</span></sub><sup><span lang=EN-US>n</span></sup>」<span lang=EN-US>+1<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>15</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>(1)45 (2)45 (3)46</span>（塊內(nèi)順序查找）<span
lang=EN-US><span style='mso-spacerun:yes'> </span>16</span>．<span
lang=EN-US>k(k+1)/2<span style='mso-spacerun:yes'> </span>17</span>．<span
lang=EN-US>30</span>，<span lang=EN-US>31.5</span>（塊內(nèi)順序查找）<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>18</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>(1)</span>順序存儲或鏈式存儲 <span
lang=EN-US><span style='mso-spacerun:yes'> </span>(2)</span>順序存儲且有序 <span
lang=EN-US>(3)</span>塊內(nèi)順序存儲，塊間有序 <span lang=EN-US>(4) </span><span
style='color:red'>散列</span>存儲<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>19</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>(n+1)/2<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>20</span>．<span lang=EN-US
style='color:red'>(n+1)/n*log<sub>2</sub>(n+1)-1</span><span lang=EN-US><span
style='mso-spacerun:yes'> </span>21</span>．結(jié)點的左子樹的高度減去結(jié)點的右子樹的高度<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>22</span><span
style='font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>(1)</span>順序表<span
lang=EN-US>(2)</span>樹表<span lang=EN-US>(3)</span>哈希表<span lang=EN-US>(4)</span>開放定址方法<span
lang=EN-US>(5)</span>鏈地址方法<span lang=EN-US>(6)</span>再哈希<span lang=EN-US>(7)</span>建立公共溢出區(qū)<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-align:justify;text-justify:inter-ideograph'><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>23</span><span
style='font-size:10.5pt;font-family:宋體'>．直接定址法<span lang=EN-US><span
style='mso-spacerun:yes'> </span>24</span>．<span
lang=EN-US>log</span></span><sub><span lang=EN-US style='font-size:10.5pt;
font-family:Symbol;mso-ascii-font-family:宋體;mso-hansi-font-family:宋體;
mso-char-type:symbol;mso-symbol-font-family:Symbol'><span style='mso-char-type:
symbol;mso-symbol-font-family:Symbol'>é</span></span></sub><sub><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>m/2</span></sub><sub><span
lang=EN-US style='font-size:10.5pt;font-family:Symbol;mso-ascii-font-family:
宋體;mso-hansi-font-family:宋體;mso-char-type:symbol;mso-symbol-font-family:Symbol'><span
style='mso-char-type:symbol;mso-symbol-font-family:Symbol'>ù</span></span></sub><span
lang=EN-US style='font-size:10.5pt;font-family:宋體'>(<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?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -