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

1、小結(jié)第一章（1）數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算方法的學(xué)科。（2）數(shù)據(jù)的邏輯結(jié)構(gòu)包括：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)4種類型。（3）集合中不存在結(jié)構(gòu)之間的關(guān)系；線性結(jié)構(gòu)元素之間存在一對(duì)一的關(guān)系；樹(shù)形結(jié)構(gòu)元素之間存在一對(duì)多的關(guān)系；圖形結(jié)構(gòu)元素之間存在多對(duì)多的關(guān)系。具有一對(duì)多和多對(duì)多關(guān)系的結(jié)構(gòu)又稱為非線性結(jié)構(gòu)。（4）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)4種。（5）順序存儲(chǔ)可以采用一維數(shù)組來(lái)存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ)可以采用鏈表結(jié)構(gòu)來(lái)存儲(chǔ)；索引存儲(chǔ)則在原有存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上，附加建立一個(gè)存儲(chǔ)表來(lái)實(shí)現(xiàn)，主要作用是為了提高數(shù)據(jù)的檢索速度；而散列存儲(chǔ)則是通過(guò)構(gòu)造散列函數(shù)來(lái)確定數(shù)據(jù)

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

3、個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。數(shù)據(jù)的邏輯結(jié)構(gòu)不是依賴于計(jì)算機(jī)的。算法是對(duì)解題方法和步驟的描述。二、填空題整理1、數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)。2、數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)。3、數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。4、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)和稱為非線性結(jié)構(gòu)。5、在樹(shù)形結(jié)構(gòu)中，除了樹(shù)根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)幾點(diǎn)。6、在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)

4、點(diǎn)數(shù)和后驅(qū)結(jié)點(diǎn)數(shù)可以任意多個(gè)。7、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu)。8、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。9、線性結(jié)構(gòu)中的元素之間存在一對(duì)一的關(guān)系。10、樹(shù)形結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系。11、圖形結(jié)構(gòu)的元素之間存在多對(duì)多的關(guān)系。12、數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法3個(gè)方面的內(nèi)容。13、數(shù)據(jù)結(jié)構(gòu)被定義為(D,R，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。14、算法是一個(gè)有窮指令的集合。15、算法效率的度量可以分為事先估算和事后統(tǒng)計(jì)法。16、一個(gè)算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。17、算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間，它是該算法求解

5、問(wèn)題規(guī)模n的函數(shù)。18、若一個(gè)算法中的語(yǔ)句頻度之和為T(n=6n+3n(2logn,則算法的時(shí)間復(fù)雜度為O(n(2logn。19、若一個(gè)算法中的語(yǔ)句頻度之和為T(n=3n+n(2logn+n*n,則算法的時(shí)間復(fù)雜度為O(n*n20、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)像以及它們之間的關(guān)系和運(yùn)算的學(xué)科。三、選擇題整理1、數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)及它們之間的相互聯(lián)系。2、在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。3、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為順序存儲(chǔ)結(jié)構(gòu)。4、非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和多個(gè)

6、直接后續(xù)結(jié)點(diǎn)。5、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間分兩部分，一部分放結(jié)點(diǎn)的值，另一部分放表示結(jié)點(diǎn)間關(guān)系的指針。6、算法的計(jì)算量大小稱為算法的時(shí)間復(fù)雜性。7、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。8、每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)存儲(chǔ)空間里，這種結(jié)構(gòu)稱為順序存儲(chǔ)結(jié)構(gòu)。9、每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是鏈?zhǔn)酱鎯?chǔ)。10、任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有邏輯關(guān)系是集合。11、在數(shù)據(jù)結(jié)構(gòu)中，與所用的計(jì)算機(jī)無(wú)關(guān)的是邏輯結(jié)構(gòu)。12、4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是集合。13、與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置和個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的邏輯結(jié)構(gòu)。14、每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含

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

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

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

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

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

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

13、則第i個(gè)結(jié)點(diǎn)的地址為B+（i-1）m。5）在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為O(n。6）設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是P->rear=1。7）兩指針P和Q，分別指向單向鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是P->next=Q。第三章（1）棧是一種運(yùn)n算受限制的線性表，它只允許在棧頂進(jìn)行插入和刪除等操作。（2）棧的邏輯結(jié)構(gòu)和線性表相同，數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，其主要特點(diǎn)是“后進(jìn)先出”。（3）棧的存儲(chǔ)結(jié)構(gòu)有順序棧和鏈棧之分，要求掌握棧的C語(yǔ)言描述方法。（4）重點(diǎn)掌握在順序棧和鏈棧上實(shí)現(xiàn)的進(jìn)棧、出棧、讀棧頂元素、判棧空和判棧滿等基本操作。（5）熟悉棧在計(jì)算機(jī)的軟件設(shè)計(jì)中的各種應(yīng)用，能靈活應(yīng)用棧的基本原理解決一些綜合性的應(yīng)用問(wèn)題。第四章（1）隊(duì)列是一種操作受限制的線性表，一般隊(duì)列只允許