數(shù)據(jù)結(jié)構(gòu)作業(yè)點(diǎn)評1

1、數(shù)據(jù)結(jié)構(gòu)作業(yè)點(diǎn)評1作業(yè)1部分答案一、單項(xiàng)選擇題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順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)17存儲(chǔ)結(jié)構(gòu)19頭結(jié)點(diǎn)的指針 指向第一個(gè)結(jié)點(diǎn)的指針20鏈?zhǔn)?鏈表點(diǎn)評：作業(yè)1中涉及到的概念和相關(guān)術(shù)語如下： 數(shù)據(jù)數(shù)據(jù)（data）是描述和量化客觀事物和信息等的符號(hào)，在計(jì)算機(jī)領(lǐng)域是指所有能輸入計(jì)算機(jī)并能被計(jì)算機(jī)系統(tǒng)和程序識(shí)別、存儲(chǔ)、加工和處理的符號(hào)的總稱。包括數(shù)字、字符、圖像和

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

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

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

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

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

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

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

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

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

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