數(shù)據(jù)結構作業(yè)點評1

1、數(shù)據(jù)結構作業(yè)點評1作業(yè)1部分答案一、單項選擇題11C 12D 13C 14A 15B 16C 17C 18B 19B 20D二、填空題 1n-i+12n-i 10 n-1 O(n)11s-next=p-next; 12head 13q-next=p-next; 14p-next=head; 15單鏈表16順序存儲 鏈式存儲17存儲結構19頭結點的指針 指向第一個結點的指針20鏈式 鏈表點評：作業(yè)1中涉及到的概念和相關術語如下： 數(shù)據(jù)數(shù)據(jù)（data）是描述和量化客觀事物和信息等的符號，在計算機領域是指所有能輸入計算機并能被計算機系統(tǒng)和程序識別、存儲、加工和處理的符號的總稱。包括數(shù)字、字符、圖像和

2、聲音等。 數(shù)據(jù)元素（data element）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常把數(shù)據(jù)元素作為一個整體來存儲和處理。數(shù)據(jù)元素可由一個或若干個數(shù)據(jù)項組成，數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。 數(shù)據(jù)項數(shù)據(jù)項是數(shù)據(jù)不可分割的，具有獨立含義的最小數(shù)據(jù)單位。數(shù)據(jù)元素可以只是單個的數(shù)據(jù)項，例如學生的年齡就是一個數(shù)據(jù)元素。數(shù)據(jù)元素也可以由多個數(shù)據(jù)項復合組成，例如根據(jù)需要可以把學生的相關信息如學號、姓名、年齡、性別、電話號碼等多個數(shù)據(jù)項組成一個數(shù)據(jù)元素統(tǒng)一處理。數(shù)據(jù)元素在許多應用中又被稱為記錄。 數(shù)據(jù)對象 數(shù)據(jù)對象是數(shù)據(jù)的一個子集，是性質相同的數(shù)據(jù)的集合。 數(shù)據(jù)結構數(shù)據(jù)結構是相互之間存在的一種或多種特

3、定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素間的關系稱為結構。數(shù)據(jù)結構一般包括以下三方面內(nèi)容：（1）數(shù)據(jù)元素之間的邏輯關系，也稱數(shù)據(jù)的邏輯結構（Logical Structure）。數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關，是獨立于計算機的。數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。（2）數(shù)據(jù)元素及其關系在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的存儲結構（Storage Structure）。數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn)（亦稱為映象），它依賴于計算機語言。對機器語言而言，存儲結構是具體的。一般，只在高級語言的層次上討論存儲結構。（3） 數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。數(shù)據(jù)的

4、運算定義在數(shù)據(jù)的邏輯結構上，每種邏輯結構都有一個運算的集合。最常用的檢索、插入、刪除、更新、排序等運算實際上只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。所謂抽象的操作，是指我們只知道這些操作是做什么，而無須考慮如何做。只有確定了存儲結構之后，才考慮如何具體實現(xiàn)這些運算。 數(shù)據(jù)結構研究的內(nèi)容數(shù)據(jù)結構研究的內(nèi)容是： （1）研究數(shù)據(jù)元素之間固有的客觀聯(lián)系（邏輯結構） （2）研究數(shù)據(jù)在計算機內(nèi)部的存儲方法（存儲結構） （3）研究如何在數(shù)據(jù)的各種結構（邏輯和物理）上實施有效的操作（算法） 數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間的邏輯關系，是用戶根據(jù)使用需要建立起來的數(shù)據(jù)組織形式，是獨立于計算機的。

5、根據(jù)數(shù)據(jù)元素之間的不同關系，有以下四種基本邏輯結構。（1）集合：結構中的數(shù)據(jù)除了“同屬于一個集合”的關系外，不存在其它關系。（2）線性結構：結構中的數(shù)據(jù)元素的位置之間存在一對一的關系。（3）樹形結構：結構中的元素之間存在一對多的關系。（4）圖狀結構：結構中的數(shù)據(jù)元素存在多對多的關系。圖狀結構又稱網(wǎng)狀結構。如圖教材1-1所示。數(shù)據(jù)的邏輯結構可概括為兩大類：線性結構和非線性結構。 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構又稱物理結構，是數(shù)據(jù)的邏輯結構在計算機存儲器中的存儲形式（或稱映象）。對機器語言來說，這種存儲形式是具體的，高級語言可以借助它的數(shù)據(jù)類型來描述存儲形式的具體細節(jié)。依據(jù)數(shù)據(jù)元素在計算機中的表示，

6、主要有以下四種不同的存儲結構。（1）順序存儲結構：是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系，可用一維數(shù)組描述。（2）鏈式存儲結構：是借助指示元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關系，可用指針類型來描述。（3）索引存儲結構：是在原有存儲數(shù)據(jù)結構的基礎上，附加建立一個索引表，索引表中的每一項都由關鍵字和地址組成。采取索引存儲結構的主要作用是提高數(shù)據(jù)的檢索速度。（4）散列存儲結構：是通過構造散列函數(shù)來確定數(shù)據(jù)存儲地址或查找地址。 算法的概念算法（algorithm）簡言之就是解決特定問題的方法，是對特定問題求解步驟的一種描述。或者說算法是為了解決問題而規(guī)定的一個有限長的操作序

7、列，是對解題過程的準確且完整的描述。 算法的特征算法具有五個基本特征：有窮性：算法的執(zhí)行必須在有限步內(nèi)結束。確定性：算法的每一個步驟必須是確定的無二義性的。輸入： 算法可以有0個或多個輸入。輸出： 算法一定有輸出結果可行性：算法中的運算都必須是可以實現(xiàn)的。 算法與程序的區(qū)別主要表現(xiàn)在以下幾個方面（1）算法代表了對問題的求解過程，而程序則是算法在計算機上的實現(xiàn)。算法用特定的程序設計語言來描述，就成了程序。（2）程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。（3）一個算法必須在有窮步之后結束，一個程序不一定滿足有窮性。 算法的描述算法可以用流程圖、自然語言、計算機程序設計語言（如C語言

8、或類C語言）來描述，但描述必須精確地說明過程。 時間復雜度算法的時間復雜度是評估算法的重要標準之一，它能較好地體現(xiàn)算法本身的時間效率，而與具體實現(xiàn)算法的計算機軟件、硬件無關。一個算法的執(zhí)行時間等于其所有語句執(zhí)行時間的總和，而任一語句的執(zhí)行時間為該語句執(zhí)行次數(shù)與執(zhí)行該語句一次所需時間的乘機。當算法轉換程序之后，每條語句的執(zhí)行時間取決于機器的硬件速度、指令類型及編譯的代碼質量，而這些是很難確定的。因此，將算法中重復執(zhí)行的次數(shù)作為其執(zhí)行時間的量度。一般情況下，算法基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)。而算法的時間復雜度簡單說來是指算法中某種基本操作執(zhí)行次數(shù)的數(shù)量級。通常用T(n)=O

9、(f(n)表示，其中O表示f(n)的數(shù)量級。 空間復雜度一個程序的空間復雜度是指程序運行從開始到結束所需的存儲空間。包括算法本身所占用的存儲空間。類似于算法的時間復雜度，算法所需存儲空間的量度記作： S(n)=O(f(n)其中n為問題的規(guī)模，算法所需存儲空間是問題規(guī)模n的函數(shù)f(n)。三、問答題的參考答案1簡述數(shù)據(jù)的邏輯結構和存儲結構的區(qū)別與聯(lián)系，它們?nèi)绾斡绊懰惴ǖ脑O計與實現(xiàn)？答：若用結點表示某個數(shù)據(jù)元素，則結點與結點之間的邏輯關系就稱為數(shù)據(jù)的邏輯結構。數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構?？梢?，數(shù)據(jù)的邏輯結構是反映數(shù)據(jù)之間的固有關系，而數(shù)據(jù)的存儲結構是數(shù)據(jù)在計算機中的存儲表示。盡管因采

10、用的存儲結構不同，邏輯上相鄰的結點，其物理地址未必相同，但可通過結點的內(nèi)部信息，找到其相鄰的結點，從而保留了邏輯結構的特點。采用的存儲結構不同，對數(shù)據(jù)的操作在靈活性，算法復雜度等方面差別較大。2解釋順序存儲結構和鏈式存儲結構的特點，并比較順序存儲結構和鏈式存儲結構的優(yōu)缺點。答：順序結構存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，要求內(nèi)存中存儲單元的地址必須是連續(xù)的。優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存

11、儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。優(yōu)點：插入和刪除元素時很方便，使用靈活。缺點：存儲密度小，存儲空間利用率低。3什么情況下用順序表比鏈表好？答：順序表適于做查找這樣的靜態(tài)操作，鏈表適于做插入和刪除這樣的動態(tài)操作。如果線性表的變化長度變化不大，且其主要操作是查找，則采用順序表；如果線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。4解釋頭結點、第一個結點（或稱首元結點）、頭指針這三個概念的區(qū)別？答：頭結點是在鏈表的開始結點之前附加的一個結點；第一個結點（或稱首元結點）是鏈表中存儲第一個數(shù)據(jù)元素的結點；頭指針是指向鏈表中第一個結點（或為頭結點或為首元結點）的指針。5解釋帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)別。 答：帶頭結點的單鏈表和不帶頭結點的單鏈表的區(qū)