數(shù)據(jù)結(jié)構(gòu)課后小結(jié).doc

小結(jié)第一章（1）數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算方法的學科。（2）數(shù)據(jù)的邏輯結(jié)構(gòu)包括：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)4種類型。（3）集合中不存在結(jié)構(gòu)之間的關(guān)系；線性結(jié)構(gòu)元素之間存在一對一的關(guān)系；樹形結(jié)構(gòu)元素之間存在一對多的關(guān)系；圖形結(jié)構(gòu)元素之間存在多對多的關(guān)系。具有一對多和多對多關(guān)系的結(jié)構(gòu)又稱為非線性結(jié)構(gòu)。（4）數(shù)據(jù)的存儲結(jié)構(gòu)包括：順序存儲、鏈式存儲、索引存儲、散列存儲4種。（5）順序存儲可以采用一維數(shù)組來存儲；鏈式存儲可以采用鏈表結(jié)構(gòu)來存儲；索引存儲則在原有存儲結(jié)構(gòu)的基礎(chǔ)上，附加建立一個存儲表來實現(xiàn)，主要作用是為了提高數(shù)據(jù)的檢索速度；而散列存儲則是通過構(gòu)造散列函數(shù)來確定數(shù)據(jù)存儲地址或查找地址。（6）算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法具有有窮性、確定性、可行性、輸入、輸出等特性。（7）一個好的算法應(yīng)該達到正確性、可讀性、健壯性、高效性和低存儲量等目標。（8）算法的效率常用時間復(fù)雜度與空間復(fù)雜度來評價，應(yīng)該逐步掌握其基本分析方法。（9）通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復(fù)雜度。一般只要大致計算出相應(yīng)的數(shù)量級即可；一個程序的空間復(fù)雜度是指程序運行從開始到結(jié)束所需的存儲量。（10）一個算法的時間和空間復(fù)雜度越好，則算法的效益就越高。單元練習1一、判斷題整理數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個基本運算集構(gòu)成的整體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機內(nèi)實際的存儲形式。數(shù)據(jù)的邏輯結(jié)構(gòu)不是依賴于計算機的。算法是對解題方法和步驟的描述。二、填空題整理1、數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。2、數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。3、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。4、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)和稱為非線性結(jié)構(gòu)。5、在樹形結(jié)構(gòu)中，除了樹根結(jié)點以外，其余每個結(jié)點只有1個前驅(qū)幾點。6、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后驅(qū)結(jié)點數(shù)可以任意多個。7、數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。8、數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈式存儲、索引存儲和散列存儲。9、線性結(jié)構(gòu)中的元素之間存在一對一的關(guān)系。10、樹形結(jié)構(gòu)中的元素之間存在一對多的關(guān)系。11、圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。12、數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法3個方面的內(nèi)容。13、數(shù)據(jù)結(jié)構(gòu)被定義為(D,R)，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。14、算法是一個有窮指令的集合。15、算法效率的度量可以分為事先估算和事后統(tǒng)計法。16、一個算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。17、算法的空間復(fù)雜度是指該算法所耗費的存儲空間，它是該算法求解問題規(guī)模n的函數(shù)。18、若一個算法中的語句頻度之和為T(n)=6n+3n(2logn),則算法的時間復(fù)雜度為O(n(2logn)。19、若一個算法中的語句頻度之和為T(n)=3n+n(2logn)+n*n,則算法的時間復(fù)雜度為O(n*n)20、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對像以及它們之間的關(guān)系和運算的學科。三、選擇題整理1、數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)及它們之間的相互聯(lián)系。2、在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。3、數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址和邏輯地址相同并且是連續(xù)的，稱之為順序存儲結(jié)構(gòu)。4、非線性結(jié)構(gòu)中的每個結(jié)點可能有多個直接前驅(qū)結(jié)點和多個直接后續(xù)結(jié)點。5、鏈式存儲結(jié)構(gòu)所占存儲空間分兩部分，一部分放結(jié)點的值，另一部分放表示結(jié)點間關(guān)系的指針。6、算法的計算量大小稱為算法的時間復(fù)雜性。7、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。8、每個結(jié)點只含有一個數(shù)據(jù)元素，所有存儲結(jié)點相繼存放在一個連續(xù)存儲空間里，這種結(jié)構(gòu)稱為順序存儲結(jié)構(gòu)。9、每一個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是鏈式存儲。10、任何兩個結(jié)點之間都沒有邏輯關(guān)系是集合。11、在數(shù)據(jù)結(jié)構(gòu)中，與所用的計算機無關(guān)的是邏輯結(jié)構(gòu)。12、4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是集合。13、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置和個數(shù)無關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。14、每一個存儲結(jié)點只含有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位置的表，該存儲方式是索引存儲方式。15、算法能正確地實現(xiàn)預(yù)定功能的特性稱為算法的正確性。16、算法在發(fā)生非法操作時可以作出相應(yīng)處理的特性稱為算法的健壯性。17、在O(1),O(n),O(2logn),O(n*n)中，時間復(fù)雜度中最壞的是O(n*n)18、for(i=0;in;i+) For(j=0;jprior-next=p-next。三、選擇題整理1）在具有n個結(jié)點的單向鏈表中，實現(xiàn)遍歷鏈表或求鏈表的第i個結(jié)點的操作，其算法的時間復(fù)雜度是O(n)。3）單向鏈表的存儲密度小于1。（存儲密度=結(jié)點數(shù)據(jù)占得存儲位/整個結(jié)點實際分配的存儲位 可知：順序表的存儲密度等于1，而鏈表的存儲密度小于1。）4）已知一個順序存儲的線性表，設(shè)每個結(jié)點占m個存儲單元，若第一個結(jié)點的地址為B，則第i個結(jié)點的地址為B+（i-1）m。5）在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為O(n)。6）設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是P-rear=1。7）兩指針P和Q，分別指向單向鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是P-next=Q。第三章（1）棧是一種運n算受限制的線性表，它只允許在棧頂進行插入和刪除等操作。（2）棧的邏輯結(jié)構(gòu)和線性表相同，數(shù)據(jù)元素之間存在一對一的關(guān)系，其主要特點是“后進先出”。（3）棧的存儲結(jié)構(gòu)有順序棧和鏈棧之分，要求掌握棧的C語言描述方法。（4）重點掌握在順序棧和鏈棧上實現(xiàn)的進棧、出棧、讀棧頂元素、判棧空和判棧滿等基本操作。（5）熟悉棧在計算機的軟件設(shè)計中的各種應(yīng)用，能靈活應(yīng)用棧的基本原理解決一些綜合性的應(yīng)用問題。第四章（1）隊列是一種操作受限制的線性表，一般隊列只允許在隊尾進行插入操作，在對頭進行刪除操作。（2）隊列的邏輯結(jié)構(gòu)和線性表也相同，數(shù)據(jù)元素之間存在一對一的關(guān)系，其主要特點是“先進先出”。（3）隊列