數(shù)據(jù)結(jié)構(gòu)考試重點必背

1、word可編輯第一章：緒論：數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)是：爭辯數(shù)據(jù)的各種規(guī)律結(jié)構(gòu)、在計算機中的存儲結(jié)構(gòu)以及各種操作的算法設(shè)計。：數(shù)據(jù)：是客觀描述事物的數(shù)字、字符以及全部的能輸入到計算機中并能被計算機接收的各種集合的統(tǒng)稱。數(shù)據(jù)元素：表示一個事物的一組數(shù)據(jù)稱作是一個數(shù)據(jù)元素，是數(shù)據(jù)的根本單位。數(shù)據(jù)項：是數(shù)據(jù)元素中有獨立含義的、不行分割的最小標識單位。數(shù)據(jù)結(jié)構(gòu)概念包含三個方面：數(shù)據(jù)的規(guī)律結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)的數(shù)據(jù)的操作。數(shù)據(jù)的規(guī)律結(jié)構(gòu)指數(shù)據(jù)元素之間的規(guī)律關(guān)系，用一個數(shù)據(jù)元素的集合定義在此集合上的假設(shè)干關(guān)系來表示，數(shù)據(jù)結(jié)構(gòu)可以分為三種：線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖。：數(shù)據(jù)元素及其關(guān)系在計算機中的存儲表示稱為數(shù)據(jù)的存儲

2、結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)根本形式有兩種：挨次存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。 ：算法：一個算法是一個有窮規(guī)章的集合，其規(guī)章確定一個解決某一特定類型問題的操作序列。算法規(guī)章需滿足以下五個特性：輸入算法有零個或多個輸入數(shù)據(jù)。 輸出算法有一個或多個輸出數(shù)據(jù)，與輸入數(shù)據(jù)有某種特定關(guān)系。 有窮性算法必需在執(zhí)行又窮步之后結(jié)束。 確定性算法的每個步驟必需含義明確，無二義性。 可行性算法的每步操作必需是根本的，它們的原那么上都能夠精確地進行，用筆和紙做有窮次就可以完成。 有窮性和可行性是算法最重要的兩個特征。：算法與數(shù)據(jù)結(jié)構(gòu)：算法建立數(shù)據(jù)結(jié)構(gòu)之上，對數(shù)據(jù)結(jié)構(gòu)的操作需用算法來描述。 算法設(shè)計依靠數(shù)據(jù)的規(guī)律

3、結(jié)構(gòu)，算法實現(xiàn)依靠數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)。：算法的設(shè)計應(yīng)滿足五個目標：正確性：算法應(yīng)精確的滿足應(yīng)用問題的需求，這是算法設(shè)計的根本目標。 健壯性：即使輸入數(shù)據(jù)不適宜，算法也能做出適當?shù)奶幚?，不會?dǎo)致不行控結(jié) 高時間效率：算法的執(zhí)行時間越短，時間效率越高。 果。 高空間效率：算法執(zhí)行時占用的存儲空間越少，空間效率越高。 可讀性：算法的可讀性有利于人們對算法的理解。 ：度量算法的時間效率，時間簡單度，課本39頁。：遞歸定義：即用一個概念本身直接或間接地定義它自己。遞歸定義有兩個條件：至少有一條初始定義是非遞歸的，如1！=1. 由函數(shù)值逐步遞推計算出未知函數(shù)值，如用n-1！定義n！。 第二章：線性表線性表

4、：線性表是由n(n>=0)個類型相同的數(shù)據(jù)元素a0,a1,a2,an-1,組成的有限序列,記作： LinearList = (a0,a1,a2,an-1)其中，元素ai可以是整數(shù)、浮點數(shù)、字符、也可以是對象。n是線性表的元素個數(shù)，成為線性表長度。假設(shè)n=0，那么LinearList為空表。假設(shè)n>0，那么a0沒有前驅(qū)元素，an-1沒有后繼元素，ai0<i<n-1有且僅有一個直接前驅(qū)元素ai-1和一個直接后繼元素ai+1。線性表的挨次存儲是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲次序與它們在線性表中的規(guī)律次序相同。線性表的數(shù)據(jù)元素數(shù)據(jù)同一種數(shù)據(jù)類

5、型，設(shè)每個元素占用c字節(jié)，a0的存儲地址為Loca0，那么ai的存儲地址Locai為：Locai = Loca0+ i*c 數(shù)組是挨次存儲的隨機存儲結(jié)構(gòu)，它占用一組連續(xù)的存儲單元，通過下標識別元素，元素地址是下標的線性函數(shù)。：挨次表的插入和刪除操作要移動數(shù)據(jù)元素。平均移動次數(shù)是 屬數(shù)據(jù)表長度的一半。課本第50頁：線性表的鏈式存儲是用假設(shè)干地址分散的存儲單元存儲數(shù)據(jù)元素，規(guī)律上相鄰的數(shù)據(jù)元素在物理位置上不肯定相鄰，必需接受附加信息表示數(shù)據(jù)元素之間的挨次關(guān)系。它有兩個域組成：數(shù)據(jù)域和地址域。通常成為節(jié)點。課本第55頁及56頁單鏈表課本56頁單鏈表的遍歷：Node<E> p = head

6、; while(p!=null) 訪問p節(jié)點；p = ;單鏈表的插入和刪除操作格外簡便，只要轉(zhuǎn)變節(jié)點間的鏈接關(guān)系，不需移動數(shù)據(jù)元素。單鏈表的插入操作：1：空表插入/頭插入 2)中間插入/尾插入 if(head = null) Node<E> q = new Node<E>(x); head = new Node<E>(x); = ; else = q; Node<E> q=new Node<E>(x); 中間插入或尾插入都不會轉(zhuǎn)變單表 = head; 的頭指針head。 head = q; 單鏈表的刪除操作：頭刪除：head = ;

7、中間/尾刪除：if!=null) = 循環(huán)單鏈表：假設(shè)單鏈表最終一個節(jié)點的next鏈保存單鏈表的頭指針head值，那么該單鏈表成為環(huán)形結(jié)構(gòu)，稱為循環(huán)單鏈表。課本67假設(shè)rear是單鏈表的尾指針，那么執(zhí)行=head;語句，使單鏈表成為一條循環(huán)單鏈表。當=head時，循環(huán)單鏈表為空。：雙鏈表結(jié)構(gòu)：雙鏈表的每個結(jié)點有兩個鏈域，分別指向它的前驅(qū)和后繼結(jié)點， 當=null時，雙鏈表為空。 設(shè)p指向雙鏈表中非兩端的某個結(jié)點，那么成立以下關(guān)系：p=。雙鏈表的插入和刪除：1插入 2)刪除q=new DLinkNodex； = ;=; =p; if=null) = q;=q; .prev = ;循環(huán)雙鏈表：當=

8、head且=head時，循環(huán)雙鏈表為空。第三章：棧和隊列棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進行。允許操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有挨次棧和鏈式棧。棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。棧的進出棧挨次：后進先出，先進后出。及75頁的思考題。：隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進行。向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為隊尾，允許出隊的一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進先出。第四章：串：串是一種特殊的線性表，其特殊性在于線性表中的

9、每個元素是一個字符。一個串記為： s=“s0s1s2sn-1 其中n>=0,s是串名，一對雙引號括起來的字符序列s0s1s2sn-1是串值，sii=0，1，2，n-1為特定字符集合中的一個字符。一個串中包含的字符個數(shù)稱為串的長度。長度為0的串稱為空串，記作“，而由一個或多個空格字符構(gòu)成的字符串稱為空格串。子串：由串s中任意連續(xù)字符組成的一個子序列sub稱為s的子串，s稱為sub的主串。子串的序號是指該子串的第一個字符在主串中的序號。串比較：兩個串可比較是否相等，也可比較大小。兩個串子串相等的充要條件是兩個串子串的長度相同，并且各對應(yīng)位置上的字符也相同。兩個串的大小由對應(yīng)位置的第一個不同字

10、符的大小打算，字符比較次序是從頭開頭依次向后。當兩個串長度不等而對應(yīng)位置的字符都相同時，較長的串定義為較“大。第五章：數(shù)組和廣義表：數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。一維數(shù)組的規(guī)律結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴展。：一維數(shù)組：一維數(shù)組接受挨次存儲結(jié)構(gòu)。一個一維數(shù)組占用一組連續(xù)的存儲單元。設(shè)數(shù)組第一個元素a0的存儲地址為Loca0，每個元素占用c字節(jié)，那么數(shù)組其他元素ai的存儲地址Locai為： Locai= Loca0+i*c數(shù)組通過下標識別元素，元素地址是下標的線性函數(shù)。一個下標能夠唯一確定一個元素，所劃給的時間是O1。因此數(shù)組是隨機存取結(jié)構(gòu)，這是數(shù)組最大的優(yōu)點。：多維數(shù)組

11、的遍歷：有兩種次序：行主序和列主序。行主序：以行為主序，按行遞增訪問數(shù)組元素，訪問完第i行的全部元素之后再訪問第i+1行的元素，同一行上按列遞增訪問數(shù)組元素。 a00,a01,a0(n-1), a10,a11,a1(n-1),a(m-1)0,a(m-1)1,a(m-1)(n-1) 2)列主序：以列為主序，按列遞增訪問數(shù)組元素，訪問完第j列的全部元素之后再訪問第j+1列的元素，同一列上按列遞增訪問數(shù)組元素。 多維數(shù)組的存儲結(jié)構(gòu)：多維數(shù)組也是由多個一維數(shù)組組合而成，組合方式有一下兩種。靜態(tài)多維數(shù)組的挨次存儲結(jié)構(gòu)：可按行主序和列主序進行挨次存儲。 按行主序存儲時，元素aij的地址為：Locaij=

12、Loca00+i*n+j*c按列主序存儲時，Locaij= Loca00+j*m+i*c動態(tài)多維數(shù)組的存儲結(jié)構(gòu)。 二維數(shù)組元素地址就是兩個下標的線性函數(shù)。無論接受哪種存儲結(jié)構(gòu)，多維數(shù)組都是基于一維數(shù)組的，因此也只能進行賦值、取值兩種存取操作，不能進行插入，刪除操作。第六章：樹是數(shù)據(jù)元素結(jié)點之間具有層次關(guān)系的非線性結(jié)構(gòu)。在樹結(jié)構(gòu)中，除根以外的結(jié)點只有一個直接前驅(qū)結(jié)點，可以有零至多個直接后繼結(jié)點。根沒有前驅(qū)結(jié)點。樹是由nn>=0個結(jié)點組成的有限集合樹中元素通常稱為結(jié)點。N=0的樹稱為空樹；n>0大的樹T；有一個特殊的結(jié)點稱為根結(jié)點，它只有后繼結(jié)點，沒有前驅(qū)結(jié)點。除根結(jié)點之外的其他結(jié)點分

13、為mm>=0個互不相交的集合T0,T1,T3.,Tm-1，其中每個集合Ti0<=i<m本身又是一棵樹，稱為根的子樹。樹是遞歸定義的。結(jié)點是樹大的根本單位，假設(shè)干個結(jié)點組成一棵子樹，假設(shè)干棵互不相交的子樹組成一棵樹。樹的每個結(jié)點都是該樹中某一棵子樹的根。因此，樹是由結(jié)點組成的、結(jié)點之間具有層次關(guān)系大的非線性結(jié)構(gòu)。 結(jié)點的前驅(qū)結(jié)點稱為其父母結(jié)點，反之，結(jié)點大的后繼結(jié)點稱為其孩子結(jié)點。一棵樹中，只有根結(jié)點沒有父母結(jié)點，其他結(jié)點有且僅有一個父母結(jié)點。擁有同一個父母結(jié)點的多個結(jié)點之間稱為兄弟結(jié)點。結(jié)點的祖先是指從根結(jié)點到其父母結(jié)點所經(jīng)過大的全部結(jié)點。結(jié)點的后代是指該結(jié)點的全部孩子結(jié)點，

14、以及孩子的孩子等。結(jié)點的度是結(jié)點所擁有子樹的棵數(shù)。度為0的結(jié)點稱為葉子結(jié)點，又叫終端結(jié)點；樹中除葉子結(jié)點之外的其他結(jié)點稱為分支結(jié)點，又叫非葉子結(jié)點或非終端結(jié)點。樹的度是指樹中各結(jié)點度的最大值。結(jié)點的層次屬性反響結(jié)點處于樹中的層次位置。商定根結(jié)點的層次為1，其他結(jié)點的層次是其父母結(jié)點的層次加1。明顯，兄弟結(jié)點的層次相同。樹的高度或深度是樹中結(jié)點的最大層次樹。設(shè)樹中x結(jié)點是y結(jié)點的父母結(jié)點，有序?qū)，y稱為連接這兩個結(jié)點的分支，也稱為邊。設(shè)X0,X1,.,Xk-1是由樹中結(jié)點組成的一個序列，且Xi，Xi+10<=i<k-1都是樹中的邊，那么該序列稱為從X0到Xk-1的一條路徑。路徑長度

15、為路徑上的邊數(shù)。在樹的定義中，結(jié)點的子樹T0，T1.,Tm-1之間沒有次序，可以交換位置，稱為無序樹，簡稱樹。假設(shè)結(jié)點的子樹T0,T1,Tm-1從左到右是有次序的，不能交換位置，那么 稱該樹為有序樹。森林是mm>=0棵互不相干的樹的集合。給森林加上一個根結(jié)點就變成一棵樹，將樹的根節(jié)點刪除就變成森林。二叉樹的性質(zhì)1：假設(shè)根結(jié)點的層次為1，那么二叉樹第i層最多有2 的i-1次方i>=1個結(jié)點。二叉樹的性質(zhì)2：在高度為k的二叉樹中，最多有2的k次方減一個結(jié)點。二叉樹的性質(zhì)3：設(shè)一棵二叉樹的葉子結(jié)點數(shù)為n0,2度結(jié)點數(shù)為n2，那么n0=n2+1。一棵高度為k的滿二叉樹是具有2的k次方減一個

16、結(jié)點的二叉樹。滿二叉樹中每一層的結(jié)點數(shù)目都到達最大值。對滿二叉樹的結(jié)點進行連續(xù)編號，商定根節(jié)點的序號為0，從根節(jié)點開頭，自上而下，每層自左至右編號。一棵具有n個結(jié)點高度為k的二叉樹，假設(shè)他的每個節(jié)點都與高度為k的滿二叉樹中序號為0n-1的結(jié)點一一對應(yīng)，那么這棵二叉樹為為完全二叉樹。滿二叉樹是完全二叉樹，而完全二叉樹不肯定是滿二叉樹。完全二叉樹的第1k-1層是滿二叉樹第k層不滿，并且該層全部結(jié)點必需集中在該層左邊的假設(shè)干位置上。二叉樹的性質(zhì)4：一棵具有n個結(jié)點的完全二叉樹，其高度k=log2n確實定值+1二叉樹的性質(zhì)5：一棵具有n個結(jié)點的完全二叉樹，對序號為i的結(jié)點，有假設(shè)i=0，那么i為根節(jié)點

17、，無父母結(jié)點；假設(shè)i>0，那么i的父母結(jié)點的序號為i-1/2。假設(shè)2i+1<n，那么i的左孩子結(jié)點序號為2i+1；否那么i無左孩子。假設(shè)2i+2<n，那么i的右孩子結(jié)點的序號為2i+2，否那么i無右孩子。二叉樹的遍歷二叉樹的遍歷是依據(jù)肯定規(guī)章和次序訪問二叉樹中的全部結(jié)點，并且每個結(jié)點僅被訪問一次。二叉樹的三種次序遍歷1：先根次序；訪問根節(jié)點，遍歷左子樹，遍歷右子樹。2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。3：后根次序；遍歷左子樹，遍歷右子樹，訪問根節(jié)點。先根次序遍歷時，最先訪問根節(jié)點；后根次序遍歷時，最終訪問根節(jié)點；中根次序遍歷時，左子樹上的結(jié)點在根節(jié)點之前訪問，右

18、子樹上的結(jié)點在根節(jié)點之后訪問。二叉樹的插入和刪除操作P147二叉樹的層次遍歷P149習題P167 610，619第七章圖是由定點集合及頂點間的關(guān)系集合組成的一種數(shù)據(jù)關(guān)邊系。頂點之間的關(guān)系成為邊。一個圖G記為G=V,E，V是頂點A的有限集合，E是邊的有限集合。即 V=A|A屬于某個數(shù)據(jù)元素集合E=(A,B)|A,B屬于V或E=<A,B>|A,B屬于V且PathA,B其中PathA,B表示從頂點A到B的一條單向通路，即PathA,B是有方向的。無向圖中的邊事沒有方向，每條邊用兩個頂點的無序?qū)Ρ硎?。有向圖中的邊是有方向，每條邊用兩個頂點的有序?qū)Ρ硎?。完全圖指圖的邊數(shù)到達最大值。n個頂點的

19、完全圖記為Kn。無向完全圖Kn的邊數(shù)為n*n-1/2,有向完全圖Kn的邊數(shù)為n*n-1。子圖：設(shè)圖G=(V,E),G=(V,E)，假設(shè)V包含于V且E包含于E,那么稱圖G是G的子圖。假設(shè)G是G的真子圖。連通圖：在無向圖G中，假設(shè)從頂點VI到Vj有路徑，那么稱Vi和Vj是聯(lián)通的。假設(shè)圖G中任意一對頂點Vi和VjVi不等于Vj都是聯(lián)通的，那么稱G為連通圖。非連通圖的極大聯(lián)通子圖稱為該圖的聯(lián)通重量。強連通圖：在有向圖中，假設(shè)在每一對頂點Vi和VjVi不等于Vj之間都存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，也存在一條從Vi到Vj的路徑，那么稱該圖的強連通圖。非強連通圖的極大強連通子圖稱

20、為該圖的強連通圖重量。圖的遍歷遍歷圖是指從圖G中任意一個頂點V動身，沿著圖中的邊前行，到達并訪問圖中的全部頂點，且每個頂點僅被訪問一次。遍歷圖要考慮一下三個問題：指定遍歷的第一個訪問頂點由于一個頂點可能與多個頂點相鄰，因此要在多個鄰接頂點之間商定一種訪問次序。由于圖中可能存在回路，在訪問某個頂點之后，可能沿著某條路徑又回到該頂點。深度優(yōu)先搜尋圖的深度優(yōu)先搜尋策略是，訪問某個頂點v，接著查找v的另一個未被訪問的鄰接頂點w訪問，如此反復(fù)執(zhí)行，走過一條較長路徑到達最遠頂點；假設(shè)頂點v沒有未被訪問的其他鄰接頂點，那么回到前一個被訪問頂點，再查找其他訪問路徑。圖的深度優(yōu)先搜尋遍歷算法P188 聯(lián)通的無回

21、路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。各連通重量均為樹的圖稱為森林，樹是森林。由于樹中無回路，因此樹中必定無自身環(huán)也無重邊否那么他有回路假設(shè)去掉樹中的任意一條邊，那么變成森林，成為非聯(lián)通圖；假設(shè)給樹加上一條邊，形成圖中的一條回路，那么不是樹。P191生成樹和生成森林：一個連通無向圖的生成樹是該圖的一個微小聯(lián)通生成子圖，它包含原圖中全部頂點n個以及足以構(gòu)成一棵樹的n-1條邊。 一個非聯(lián)通的無向圖，其各連通圖重量的生成圖組成該圖的生成森林。圖的生成圖或生成森林不是唯一的，從不同頂點開頭、接受不同遍歷可以得到不同的生成樹或森林。 在生成樹中，任何樹中，任何兩個頂點之間只有唯一的一條路徑。第八章折半查找算法描述 P206,P207二叉排序樹及其查找：二叉排序樹或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹：每個結(jié)點都有一個作為查找依據(jù)的關(guān)鍵字，全部結(jié)點的關(guān)鍵字互不相同。假設(shè)一個結(jié)點的左子樹不空，那么左子樹上全部結(jié)點的關(guān)鍵字均小于這個節(jié)點的關(guān)鍵字；每個結(jié)點的左右子樹也分別為二叉排序樹。在一棵二叉排序樹中，查找值為value的結(jié)點，算法