?? 第1章 緒論.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></TR></TBODY></TABLE>
<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: 黑體; mso-hansi-font-family: 宋體; mso-bidi-font-size: 10.5pt"><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="FONT-FAMILY: 黑體; mso-hansi-font-family: 宋體; mso-bidi-font-size: 10.5pt">三．填空題<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．數據元素<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．數據的組織形式，即數據元素之間邏輯關系的總體。而邏輯關系是指數據元素之間的關聯方式或稱“鄰接關系”。<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．表示（又稱映像）。<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">6</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．算法的時間復雜度和空間復雜度。<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">8</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．（<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">9</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．（<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">10</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">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: -18pt; mso-list: l1 level1 lfo10; tab-stops: list 40.8pt"><![if !supportLists]><SPAN
lang=EN-US
style="FONT-FAMILY: 宋體; mso-bidi-font-family: 宋體; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-list: Ignore">16.<SPAN style="FONT: 7pt 'Times New Roman'">
</SPAN></SPAN></SPAN><![endif]><SPAN lang=EN-US
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">①<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="FONT-FAMILY: 黑體; mso-hansi-font-family: 宋體; mso-bidi-font-size: 10.5pt">四．應用題<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="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-bidi-font-size: 10.5pt">．數據結構是一門研究在非數值計算的程序設計問題中，計算機的操作對象及對象間的關系和施加于對象的操作等的學科。<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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．數據類型是程序設計語言中的一個概念，它是一個值的集合和操作的集合。如</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">C</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">語言中的整型、實型、字符型等。整型值的范圍（對具體機器都應有整數范圍），其操作有加、減、乘、除、求余等。實際上數據類型是廠家提供給用戶的已實現了的數據結構?！俺橄髷祿愋停?lt;/SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">ADT</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-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: 0.05pt; TEXT-INDENT: -0.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="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋體; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）邏輯結構相同但存儲不同，可以是不同的數據結構。例如，線性表的邏輯結構屬于線性結構，采用順序存儲結構為順序表，而采用鏈式存儲結構稱為線性鏈表。</SPAN><SPAN
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -