?? da01.htm
字號:
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt;
mso-fareast-font-family:黑體'><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><span lang=EN-US style='mso-bidi-font-size:10.5pt;
mso-fareast-font-family:黑體'><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><span lang=EN-US style='mso-bidi-font-size:10.5pt;
mso-fareast-font-family:黑體'><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><span lang=EN-US style='mso-bidi-font-size:10.5pt;
mso-fareast-font-family:黑體'><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><span lang=EN-US style='mso-bidi-font-size:10.5pt;
mso-fareast-font-family:黑體'><o:p> </o:p></span></p>
</td>
</tr>
</table>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:黑體;
mso-hansi-font-family:宋體'><o:p> </o:p></span></p>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span style='mso-bidi-font-size:10.5pt;font-family:黑體;mso-hansi-font-family:
宋體'>三．填空題<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:宋體'>1</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><span
style='mso-spacerun:yes'> </span>2</span>．集合<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>線性結構<span
lang=EN-US><span style='mso-spacerun:yes'> </span></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:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋體'>3</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:22.8pt;mso-char-indent-count:2.0'><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'> </span>5</span>．（<span lang=EN-US>1</span>）邏輯特性<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>（<span
lang=EN-US>2</span>）在計算機內部如何表示和實現<span lang=EN-US><span
style='mso-spacerun:yes'> </span></span>（<span lang=EN-US>3</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:宋體'>6</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體'>．算法的時間復雜度和空間復雜度。<span
lang=EN-US>7</span>．（<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><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:宋體'>8</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體'>．（<span lang=EN-US>1</span>）有窮性<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>（<span
lang=EN-US>2</span>）確定性 （<span lang=EN-US>3</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:宋體'>9</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體'>．（<span lang=EN-US>1</span>）<span
lang=EN-US>n+1<span style='mso-spacerun:yes'> </span></span>（<span
lang=EN-US>2</span>）<span lang=EN-US>n<span style='mso-spacerun:yes'>
</span></span>（<span lang=EN-US>3</span>）<span lang=EN-US>n(n+3)/2<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span></span>（<span lang=EN-US>4</span>）<span
lang=EN-US>n(n+1)/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:宋體'>10</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體'>．<span lang=EN-US>1+</span>（<span
lang=EN-US>1+2++</span>（<span lang=EN-US>1+2+3</span>）<span lang=EN-US>+</span>…<span
lang=EN-US>+</span>（<span lang=EN-US>1+2+…+n</span>）<span lang=EN-US>=n(n+1)(n+2)/6<span
style='mso-spacerun:yes'> </span>O(n<sup>3</sup>)<sub><o:p></o:p></sub></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:宋體'>11. log<sub>2</sub>n<span
style='mso-spacerun:yes'> </span>12. nlog<sub>2</sub>n<span
style='mso-spacerun:yes'> </span>13. log<sub>2</sub>n<sup>2<span
style='mso-spacerun:yes'>
</span></sup>14. (n+3)(n-2)/2<span
style='mso-spacerun:yes'> </span>15. O(n)<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:40.8pt;text-indent:-18.0pt;mso-list:l1 level1 lfo10;
tab-stops:list 40.8pt'><![if !supportLists]><span lang=EN-US style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-bidi-font-family:宋體'><span style='mso-list:Ignore'>16.<span
style='font:7.0pt "Times New Roman"'> </span></span></span><![endif]><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋體'><span
style='mso-spacerun:yes'> </span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體'>①<span lang=EN-US> (1)1<span
style='mso-spacerun:yes'> </span>(2)1<span
style='mso-spacerun:yes'> </span>(3)f(m,n-1)<span
style='mso-spacerun:yes'> </span>(4)n<span
style='mso-spacerun:yes'> </span></span>②<span lang=EN-US> 9<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>17. n(n-1)/2</span></span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='mso-bidi-font-size:10.5pt;font-family:黑體;
mso-hansi-font-family:宋體'>四．應用題<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:22.8pt;mso-para-margin-left:2.0gd'><span
lang=EN-US style='mso-bidi-font-size:10.5pt;font-family:宋體'>1</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:22.8pt;mso-char-indent-count:2.0'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>．四種表示方法</span><span lang=EN-US style='mso-bidi-font-size:
10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）順序存儲方式。數據元素順序存放，每個存儲結點只含一個元素。存儲位置反映數據元素間的邏輯關系。存儲密度大，但有些操作（如插入、刪除）效率較差。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>2</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）鏈式存儲方式。每個存儲結點除包含數據元素信息外還包含一組（至少一個）指針。指針反映數據元素間的邏輯關系。這種方式不要求存儲空間連續，便于動態操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>3</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）索引存儲方式。除數據元素存儲在一地址連續的內存空間外，尚需建立一個索引表，索引表中索引指示存儲結點的存儲位置（下標）或存儲區間端點（下標），兼有靜態和動態特性。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>4</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）散列存儲方式。通過散列函數和解決沖突的方法，將關鍵字散列在連續的有限的地址空間內，并將散列函數的值解釋成關鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關鍵字隨機存取，不能順序存取，也不能折半存取。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></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'>3</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>．數據類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>C</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應有整數范圍），其操作有加、減、乘、除、求余等。實際上數據類型是廠家提供給用戶的已實現了的數據結構。“抽象數據類型（</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'>ADT</span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）”指一個數學模型及定義在該模型上的一組操作。“抽象”的意義在于數據類型的數學抽象特性。抽象數據類型的定義僅取決于它的邏輯特性，而與其在計算機內部如何表示和實現無關。無論其內部結構如何變化，只要它的數學特性不變就不影響它的外部使用。抽象數據類型和數據類型實質上是一個概念。此外，抽象數據類型的范圍更廣，它已不再局限于機器已定義和實現的數據類型，還包括用戶在設計軟件系統時自行定義的數據類型。使用抽象數據類型定義的軟件模塊含定義、表示和實現三部分，封裝在一起，對用戶透明（提供接口），而不必了解實現細節。抽象數據類型的出現使程序設計不再是“藝術”，而是向“科學”邁進了一步。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:45.0pt'><span lang=EN-US style='mso-bidi-font-size:10.5pt'>4</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>．（</span><span lang=EN-US
style='mso-bidi-font-size:10.5pt'>1</span><span style='mso-bidi-font-size:10.5pt;
font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>）數據的邏輯結構反映數據元素之間的邏輯關系（即數據元素之間的關聯方式或“鄰接關系”），數據的存儲結構是數據結構在計算機中的表示，包括數據元素的表示及其關系的表示。數據的運算是對數據定義的一組操作，運算是定義在邏輯結構上的，和存儲結構無關，而運算的實現則是依賴于存儲結構。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><span
style='mso-spacerun:yes'> </span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>2</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）邏輯結構相同但存儲不同，可以是不同的數據結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><span
style='mso-spacerun:yes'> </span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>3</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數據結構。</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:.05pt;text-indent:-.05pt;tab-stops:45.0pt'><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><span
style='mso-spacerun:yes'> </span></span><span style='mso-bidi-font-size:
10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>（</span><span lang=EN-US style='mso-bidi-font-size:10.5pt'>4</span><span
style='mso-bidi-font-size:10.5pt;font-family:宋體;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"'>）數據結構的評價非常復雜，可以考慮兩個方面，一是所選數據結構是否準確、完整的刻劃了問題的基本特征；二是是否容易實現（如對數據分解是否恰當；邏輯結構的選擇是否適合于運算的功能，是否有利于運算的實現；基本運算的選擇是否恰當。）</span><span
lang=EN-US style='mso-bidi-font-size:10.5pt'><o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -