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

1、小結(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ù)

2、存儲地址或查找地址。（6）算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法具有有窮性、確定性、可行性、輸入、輸出等特性。（7）一個好的算法應該達到正確性、可讀性、健壯性、高效性和低存儲量等目標。（8）算法的效率常用時間復雜度與空間復雜度來評價，應該逐步掌握其基本分析方法。（9）通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復雜度。一般只要大致計算出相應的數(shù)量級即可；一個程序的空間復雜度是指程序運行從開始到結(jié)束所需的存儲量。（10）一個算法的時間和空間復雜度越好，則算法的效益就越高。單元練習1一、判斷題整理數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這

3、個邏輯結(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é)

4、點數(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、一個算法的時間復雜性是算法輸入規(guī)模的函數(shù)。17、算法的空間復雜度是指該算法所耗費的存儲空間，它是該算法求解

5、問題規(guī)模n的函數(shù)。18、若一個算法中的語句頻度之和為T(n=6n+3n(2logn,則算法的時間復雜度為O(n(2logn。19、若一個算法中的語句頻度之和為T(n=3n+n(2logn+n*n,則算法的時間復雜度為O(n*n20、數(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é)點和多個

6、直接后續(xù)結(jié)點。5、鏈式存儲結(jié)構(gòu)所占存儲空間分兩部分，一部分放結(jié)點的值，另一部分放表示結(jié)點間關(guān)系的指針。6、算法的計算量大小稱為算法的時間復雜性。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é)點只含

7、有一個數(shù)據(jù)元素，存儲結(jié)點存放在連續(xù)的存儲空間，另外有一組指明結(jié)點存儲位置的表，該存儲方式是索引存儲方式。15、算法能正確地實現(xiàn)預定功能的特性稱為算法的正確性。16、算法在發(fā)生非法操作時可以作出相應處理的特性稱為算法的健壯性。17、在O(1,O(n,O(2logn,O(n*n中，時間復雜度中最壞的是O(n*n18、for(i=0;i For(j=0;j cij=i+j; 時間復雜度為O(n*n19、算法分析的兩個主要方面是空間復雜度和時間復雜度。20、計算機算法必須具備輸入、輸出和解決問題的有限運算步驟。第二章（1）線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素之間存在著一對一的關(guān)系。其存儲方法通常采用

8、順序和鏈式存儲。（2）線性表的順序存儲可以采用結(jié)構(gòu)體的形式它含有兩個域。一個整型的長度域，用以存放表中元素的個數(shù)；另一個數(shù)組域，用來存放元素，其類型可以根據(jù)需要而定。順序存儲的最大優(yōu)點是可以隨機存取，且存儲空間比較節(jié)約，而缺點是表的擴充困難，插入、刪除操作要作大量的元素移動。（3）線性表的鏈式存儲是通過結(jié)點之間的鏈接而得到的。根據(jù)連接方式又可以分為：單向鏈表、雙向鏈表和循環(huán)鏈表等。（4）單向鏈表由一個數(shù)據(jù)域(data和一個指針域(next組成，數(shù)據(jù)域用來存放結(jié)點的信息；指針域指出表中下一個結(jié)點的地址。在單向鏈表中，只能從某個結(jié)點出發(fā)找它的后續(xù)結(jié)點。單向鏈表最大的優(yōu)點是表的擴充容易、插入和刪除操

9、作方便，而缺點是存儲空間比較浪費。（5）雙向鏈表由一個數(shù)據(jù)域(data和兩個指針域(front和rear組成，它的優(yōu)點是即能找到結(jié)點的前驅(qū)，又能找到結(jié)點的后續(xù)。（6）循環(huán)鏈表使最后一個結(jié)點的指針指向頭結(jié)點（或開始結(jié)點）的地址，形成一個首尾連接的環(huán)。利用循環(huán)鏈表將使某些運算比單向鏈表更方便。一、判斷題整理1）順序存儲優(yōu)于線性表的鏈式存儲結(jié)構(gòu)。2）鏈表的每個結(jié)點不都恰好包含一個指針域。3）在線性表的鏈式存儲結(jié)構(gòu)中，邏輯上相鄰兩個元素在物理位置上并不一定緊鄰。4）順序存儲的優(yōu)點是可以隨機存取表中任意一個元素；節(jié)約存儲空間。7）線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。8）線性

10、表采用順序存儲，必須占用一個連續(xù)的存儲單元。二、填空題整理1）順序表中邏輯上相鄰的元素在物理位置上必須相鄰。2）線性表中結(jié)點的集合是有限的，結(jié)點間的關(guān)系是一對一關(guān)系。3）順序表相對于鏈表的優(yōu)點是節(jié)約存儲空間和隨機存儲。4）鏈表相對于順序表的優(yōu)點是插入和刪除操作方便。5）當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應采用鏈表存儲結(jié)構(gòu)。6）順序表中訪問任意一個結(jié)點的時間復雜度均為O(1。7）鏈表相對于順序表的優(yōu)點是插入、刪除方便；缺點是存儲密度小。8）在雙向鏈表中要刪除已知結(jié)點*P，其時間復雜度為O(1。9）在單向鏈表中要在已知結(jié)點*P之前插入一個新

11、結(jié)點，需找到*P的直接前驅(qū)結(jié)點的地址，其查找的時間復雜度為O(n。10）在單向鏈表中需知道頭指針才能遍歷整個鏈表。11）線性表中第一個結(jié)點沒有直接前驅(qū)，稱為開始結(jié)點。12）在一個長度為n的順序表中刪除第i個元素，要移動n-i個元素。13）在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移n-i+1個元素。14）在無頭結(jié)點的單向鏈表中，第一個結(jié)點的地址存放在頭指針中，而其他結(jié)點的存儲地址存放在前驅(qū)結(jié)點的指針域中。15）線性表的元素總數(shù)不確定，且經(jīng)常需要進行插入和刪除操作，應采用順序存儲結(jié)構(gòu)。16）在線性表的鏈式存儲中，元素之間的邏輯關(guān)系是通過指針決定的。17）在雙向鏈表中，每個結(jié)

12、點都有兩個指針域，它們一個指向其前超結(jié)點，另一個指向其后繼結(jié)點。18）對一個需要經(jīng)常進行插入和刪除操作的線性表，采用鏈式存儲結(jié)構(gòu)為宜。19）雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點，則需要執(zhí)行的操作為p->prior->next=p->next。三、選擇題整理1）在具有n個結(jié)點的單向鏈表中，實現(xiàn)遍歷鏈表或求鏈表的第i個結(jié)點的操作，其算法的時間復雜度是O(n。3）單向鏈表的存儲密度小于1。（存儲密度=結(jié)點數(shù)據(jù)占得存儲位/整個結(jié)點實際分配的存儲位 可知：順序表的存儲密度等于1，而鏈表的存儲密度小于1。）4）已知一個順序存儲的線性表，設(shè)每個結(jié)點占m個存儲單元，若第一個結(jié)點的地址為B，

13、則第i個結(jié)點的地址為B+（i-1）m。5）在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復雜度為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è)計中的各種應用，能靈活應用棧的基本原理解決一些綜合性的應用問題。第四章（1）隊列是一種操作受限制的線性表，一般隊列只允許