數據結構考試重點必背

第一章：緒論

:數據結構課程的任務是：討論數據的各種邏輯結構、在計算機中的存儲結構以及各

種操作的算法設計。

:數據：是客觀描述事物的數字、字符以及所有的能輸入到計算機中并能被計算機接

收的各種集合的統稱。

數據元素：表示一個事物的一組數據稱作是一個數據元素，是數據的基本單位。

數據項：是數據元素中有獨立含義的、不可分割的最小標識單位。

數據結構概念包含三個方面：數據的邏輯結構、數據的存儲結構的數據的操作。

數據的邏輯結構指數據元素之間的邏輯關系，用一個數據元素的集合定義在此集合上

的若干關系來表示，數據結構可以分為三種：線性結構、樹結構和圖。

:數據元素及其關系在計算機中的存儲表示稱為數據的存儲結構，也稱為物理結構。

數據的存儲結構基本形式有兩種：順序存儲結構和鏈式存儲結構。

:算法：一個算法是一個有窮規(guī)則的集合，其規(guī)則確定一個解決某一特定類型問題

的操作序列。算法規(guī)則需滿足以下五個特性：

輸入——算法有零個或者多個輸入數據。

輸出——算法有一個或者多個輸出數據，與輸入數據有某種特定關系。

有窮性——算法必須在執(zhí)行又窮步之后結束。

確定性——算法的每一個步驟必須含義明確，無二義性。

可行性——算法的每步操作必須是基本的，它們的原則上都能夠精確地進行，用筆和

紙做有窮次就可以完成。

有窮性和可行性是算法最重要的兩個特征。

:算法與數據結構：算法建立數據結構之上，對數據結構的操作需用算法來描述。

算法設計依賴數據的邏輯結構，算法實現依賴數據結構的存儲結構。

:算法的設計應滿足五個目標：

正確性：算法應切當的滿足應用問題的需求，這是算法設計的基本目標。

茁壯性：即使輸入數據不合適，算法也能做出適當的處理，不會導致不可控結

高時間效率：算法的執(zhí)行時間越短，時間效率越高。果。

高空間效率：算法執(zhí)行時占用的存儲空間越少，空間效率越高。

可讀性：算法的可讀性有利于人們對算法的理解。

：度量算法的時間效率，時間復雜度，(課本39頁)。

：遞歸定義：即用一個概念本身直接或者間接地定義它自己。遞歸定義有兩個條件：

至少有一條初始定義是非遞歸的，如1!=1.

由已知函數值逐步遞推計算出未知函數值，如用(n-1)!定義n!。

第二章：線性表

線性表：線性表是由n(n>=0)個類型相同的數據元素a0,a1,a2,…anT,組成的有限序

列，記作：LinearList=(aO,a1,a2,??,an-1)

其中，元素ai可以是整數、浮點數、字符、也可以是對象。n是線性表的元素個數，

成為線性表長度。若n=0,則LinearList為空表。若n>0,則aO沒有前驅元素，an-1

沒有后繼元素，ai(0<i<n-1)有且僅有一個直接前驅元素ai-1和一個直接后繼元素

ai+1o

線性表的順序存儲是用一組連續(xù)的內存單元挨次存放線性表的數據元素，元素在內存

的物理存儲次序與它們在線性表中的邏輯次序相同。

線性表的數據元素數據同一種數據類型，設每一個元素占用c字節(jié)，aO的存儲地址

為Loc(aO),則ai的存儲地址Loc(ai)為：Loc(ai)=Loc(aO)+i*c

數組是順序存儲的隨機存儲結構，它占用一組連續(xù)的存儲單元，通過下標識別元

素，元素地址是下標的線性函數。

：順序表的插入和刪除操作要挪移數據元素。平均挪移次數是

屬數據表長度的一半。(課本第50頁)

：線性表的鏈式存儲是用若干地址分散的存儲單元存儲數據元素，邏輯上相鄰的數據

元素在物理位置上不一定相鄰，必須采用附加信息表示數據元素之間的順序關系。

它有兩個域組成：數據域和地址域。通常成為節(jié)點。(課本第55頁及56頁)

單鏈表(課本56頁)

單鏈表的遍歷:Node<E>p=head;while(p!=nulI){訪問p節(jié)點；p=;}

單鏈表的插入和刪除操作非常簡便，只要改變節(jié)點間的鏈接關系，不需挪移數據元

素。

單鏈表的插入操作：1)：空表插入/頭插入2)中間插入/尾插入

if(head==null)Node<E>q=newNode<E>(x);

{head=newNode<E>(x);=;

}eIse{=q；

Node<E>q=newNode<E>(x);中間插入或者尾插入都不會改變單表

=head;的頭指針head。

head=q;

單鏈表的刪除操作:

頭刪除：head=;

中間/尾刪除：if!=nulI){=

循環(huán)單鏈表：如果單鏈表最后一個節(jié)點的next鏈保存單鏈表的頭指針head值，則該

單鏈表成為環(huán)形結構，稱為循環(huán)單鏈表。(課本67)

若rear是單鏈表的尾指針，則執(zhí)行(=head;)語句，使單鏈表成為一條循環(huán)單鏈表。

當=卜62￡|時，循環(huán)單鏈表為空。

:雙鏈表結構：雙鏈表的每一個結點有兩個鏈域，分別指向它的前驅和后繼結點，

當=皿11時，雙鏈表為空。

設P指向雙鏈表中非兩端的某個結點，則成立下列關系：P=o

雙鏈表的插入和刪除：1)插入2)刪除

q=newDLinkNode(x)；=;

=;=p;if=nulI){

=q；=q；.prev=;}

循環(huán)雙鏈表：當=*62~且=卜62￡1時，循環(huán)雙鏈表為空。

第三章：棧和隊列

棧：棧是一種特殊的線性表，其中插入和刪除操作只允許在線性表的一端進行。允許

操作的一端稱為棧頂，不允許操作的一端稱為棧底。棧有順序棧和鏈式棧。

棧中插入元素的操作稱為入棧，刪除元素的操作稱為出棧。沒有元素的中稱為空棧。

棧的進出棧順序：后進先出，先進后出。(及75頁的思量題)。

:隊列：隊列是一種特殊的線性表，其中插入和刪除操作分別在線性表的兩端進行。

向隊列中插入元素的過程稱為入隊，刪除元素的過程稱為出對，允許入隊的一端稱為

隊尾，允許出隊的一端稱為對頭。沒有元素的隊列稱為空隊列。隊列是先進先出。

第四章：串

：串是一種特殊的線性表，其特殊性在于線性表中的每一個元素是一個字符。一個串

記

為：s="s0s1s2…sn-1”其中n>=0,s是串名，一對雙引號括起來的字符序列

s0s1s2-sn-1是串值，si(i=0,1,2,…n-1)為特定字符集合中的一個字符。一個

串中包含的字符個數稱為串的長度。

長度為0的串稱為空串，記作“”，而由一個或者多個空格字符構成的字符串稱為空

格

串。

子串：由串S中任意連續(xù)字符組成的一個子序列sub稱為S的子串，S稱為sub的主

串。子串的序號是指該子串的第一個字符在主串中的序號。

串比較：兩個串可比較是否相等，也可比較大小。兩個串(子串)相等的充要條件是

兩個串(子串)的長度相同，并且各對應位置上的字符也相同。

兩個串的大小由對應位置的第一個不同字符的大小決定，字符比較次序是從頭開始依

次向后。當兩個串長度不等而對應位置的字符都相同時，較長的串定義為較“大”。

第五章：數組和廣義表

:數組是一種數據結構，數據元素具有相同的數據類型。一維數組的邏輯結構是線性

表，多維數組是線性表的擴展。

:一維數組：一維數組采用順序存儲結構。一個一維數組占用一組連續(xù)的存儲單元。

度數組第一個元素aO的存儲地址為Loc(aO),每一個元素占用c字節(jié)，則數組其他

元

素ai的存儲地址Loc(ai)為：Loc(ai)=Loc(aO)+i*c

數組通過下標識別元素，元素地址是下標的線性函數。一個下標能夠惟一確定一個元

素，所劃給的時間是0(1)。因此數組是隨機存取結構，這是數組最大的優(yōu)點。

：多維數組的遍歷：有兩種次序：行主序和列主序。

行主序：以行為主序，按行遞增訪問數組元素，訪問完第i行的所有元素之后再訪問

第i+1行的元素，同一行上按列遞增訪問數組元素。

aOO,aO1,,?,aO(n-1),a10,a11,,■■al(n-1),,■,a(m-1)0,a(nr-1)1,,,,,a(m-1)(n-1)

2)列主序：以列為主序，按列遞增訪問數組元素，訪問完第j列的所有元素之后

再訪問第j+1列的元素，同一列上按列遞增訪問數組元素。

多維數組的存儲結構：多維數組也是由多個一維數組組合而成，組合方式有一下兩

種。

靜態(tài)多維數組的順序存儲結構：可按行主序和列主序進行順序存儲。

按行主序存儲時，元素aij的地址為：Loc(aij)=Loc(aOO)+(i*n+j)*c

按列主序存儲時，Loc(aij)=Loc(aOO)+(j*m+i)*c

動態(tài)多維數組的存儲結構。

二維數組元素地址就是兩個下標的線性函數。無論采用哪種存儲結構，多維數組都

是基于一維數組的，因此也只能進行賦值、取值兩種存取操作，不能進行插入，刪除

操作。

第六章：

樹是數據元素(結點)之間具有層次關系的非線性結構。在樹結構中，除根以外的結

點惟獨一個直接前驅結點，可以有零至多個直接后繼結點。根沒有前驅結點。

樹是由n(n>=0)個結點組成的有限集合(樹中元素通常稱為結點)。N=0的樹稱為空

樹；nX)大的樹T；

@有一個特殊的結點稱為根結點，它惟獨后繼結點，沒有前驅結點。

@除根結點之外的其他結點分為m(m>=0)個互不相交的集合TO,T1,13……..,Tm-1,

其中每一個集合Ti(0Vi<m)本身又是一棵樹，稱為根的子樹。

樹是遞歸定義的。結點是樹大的基本單位，若干個結點組成一棵子樹，若干棵互不相

交的子樹組成一棵樹。樹的每一個結點都是該樹中某一棵子樹的根。因此，樹是由結

點組成的、結點之間具有層次關系大的非線性結構。

結點的前驅結點稱為其父母結點，反之，結點大的后繼結點稱為其孩子結點。一棵樹

中，惟獨根結點沒有父母結點，其他結點有且僅有一個父母結點。

擁有同一個父母結點的多個結點之間稱為兄弟結點。結點的祖先是指從根結點到其父

母結點所經過大的所有結點。結點的后代是指該結點的所有孩子結點，以及孩子的孩

子等。

結點的度是結點所擁有子樹的棵數。度為0的結點稱為葉子結點，又叫終端結點；樹

中除葉子結點之外的其他結點稱為分支結點，又叫非葉子結點或者非終端結點。樹的

度是指樹中各結點度的最大值。

結點的層次屬性反應結點處于樹中的層次位置。約定根結點的層次為1,其他結點的層

次是其父母結點的層次加1o顯然，兄弟結點的層次相同。

樹的高度或者深度是樹中結點的最大層次樹。

設樹中x結點是y結點的父母結點，有序對(x,y)稱為連接這兩個結點的分支，也

稱為邊。

設(X0,X1,….，Xk-1)是由樹中結點組成的一個序列,且(Xi,Xi+1)(0<=i<k-1)

都是樹中的邊，則該序列稱為從X0到Xk-1的一條路徑。路徑長度為路徑上的邊數。

在樹的定義中，結點的子樹TO,T1-之間沒有次序，可以交換位置，稱為無

序樹，簡稱樹。如果結點的子樹TO,T1……,TnH從左到右是有次序的，不能交換位

置，則稱該樹為有序樹。

森林是m(m>=0)棵互不相干的樹的集合。給森林加之一個根結點就變成一棵樹，將樹

的根節(jié)點刪除就變成森林。

二叉樹的性質1：若根結點的層次為1,則二叉樹第i層最多有2的i-1次方

(i>=1)個結點。

二叉樹的性質2：在高度為k的二叉樹中，最多有2的k次方減一個結點。

二叉樹的性質3：設一棵二叉樹的葉子結點數為n0,2度結點數為n2,則n0=n2+1。

一棵高度為k的滿二叉樹是具有2的k次方減一個結點的二叉樹。滿二叉樹中每一層

的結點數目都達到最大值。對滿二叉樹的結點進行連續(xù)編號，約定根節(jié)點的序號為0,

從根節(jié)點開始，自上而下，每層自左至右編號。

一棵具有n個結點高度為k的二叉樹，如果他的每一個節(jié)點都與高度為k的滿二叉樹

中序號為0~n-1

的結點一一對應，則這棵二叉樹為為徹底二叉樹。

滿二叉樹是徹底二叉樹，而徹底二叉樹不一定是滿二叉樹。徹底二叉樹的第廣廣1層

是滿二叉樹第k層不滿，并且該層所有結點必須集中在該層左邊的若干位置上。

二叉樹的性質4：一棵具有n個結點的徹底二叉樹，其高度k=log2n的絕對值+1

二叉樹的性質5：一棵具有n個結點的徹底二叉樹，對序號為i的結點，有

@若i=0,則i為根節(jié)點，無父母結點；若i>0,則i的父母結點的序號為[(iT)

/2]o

@若21+13,貝I]i的左孩子結點序號為2i+1；否則i無左孩子。

蜻2i+2<n,則i的右孩子結點的序號為2i+2,否則i無右孩子。

二叉樹的遍歷

二叉樹的遍歷是按照一定規(guī)則和次序訪問二叉樹中的所有結點，并且每一個結點僅被

訪問一次。

二叉樹的三種次序遍歷

1：先根次序；訪問根節(jié)點，遍歷左子樹，遍歷右子樹。

2：中根次序；遍歷左子樹，訪問右子樹，遍歷右子樹。

3：后根次序；遍歷左子樹，遍歷右子樹，訪問根節(jié)點。

先根次序遍歷時，最先訪問根節(jié)點；后根次序遍歷時，最后訪問根節(jié)點；中根次序遍

歷時，左子樹上的結點在根節(jié)點之前訪問，右子樹上的結點在根節(jié)點之后訪問。

二叉樹的插入和刪除操作P147

二叉樹的層次遍歷P149

習題P1676—10,6—19

第七章

圖是由定點集合及頂點間的關系集合組成的一種數據關邊系。頂點之間的關系成為

邊。一個圖G記為G=(V,E),V是頂點A的有限集合，E是邊的有限集合。即

V={A|A屬于某個數據元素集合}

E={(A,B)|A,B屬于V}或者E={<A,B>|A,B屬于V且Path(A,B)}其中Path(A,B)表

示從頂點A到B的一條單向通路，即Path(A,B)是有方向的。

無向圖中的邊事沒有方向，每條邊用兩個頂點的無序對表示。

有向圖中的邊是有方向，每條邊用兩個頂點的有序對表示。

徹底圖指圖的邊數達到最大值。n個頂點的徹底圖記為Kn。無向徹底圖Kn的邊數為n*

(n-1)/2,有向徹底圖Kn的邊數為n*(n-1)o

子圖：設圖G=(V,E),G'=(V',E'),若V'包含于V且E'包含于E,則稱圖G'是G

的子圖。若G'是G的真子圖。

連通圖：在無向圖G中，若從頂點VI到Vj有路徑，則稱Vi和Vj是聯通的。若圖G

中任意一對頂點Vi和Vj(Vi不等于Vj)都是聯通的，則稱G為連通圖。非連通圖的

極大聯通子圖稱為該圖的聯通分量。

強連通圖：在有向圖中，若在每一對頂點Vi和Vj(Vi不等于Vj)之間都存在一條從

Vi至UVj的路徑，也存在一條從Vi至ljVj的路徑，也存在一條從Vi至ljVj的路徑，則稱

該圖的強連通圖。非強連通圖的極大強連通子圖稱為該圖的強連通圖分量。

圖的遍歷

遍歷圖是指從圖G中任意一個頂點V出發(fā)，沿著圖中的邊前行，到達并訪問圖中的所

有頂點，且每一個頂點僅被訪問一次。遍歷圖要考慮一下三個問題：

@指定遍歷的第一個訪問頂點

@由于一個頂點可能與多個頂點相鄰，因此要在多個鄰接頂點之間約定一種訪問次序。

@由于圖中可能存在回路，在訪問某個頂點之后，可能沿著某條路徑又回到該頂點。

深度優(yōu)先搜索

圖的深度優(yōu)先搜索策略是，訪問某個頂點v,接著尋覓v的另一個未被訪問的鄰接頂點

w訪問，如此反復執(zhí)行，走過一條較長路徑到達最遠頂點；若頂點v沒有未被訪問的其

他鄰接頂點，則回到前一個被訪問頂點，再尋覓其他訪問路徑。

圖的深度優(yōu)先搜索遍歷算法P188

聯通的無回路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。

各連通分量均為樹的圖稱為森林，樹是森林。

由于樹中無回路，因此樹中必然無自身環(huán)也無重邊（否則他有回路）若去掉樹中的任

意一條邊，則變成森林，成為非聯通圖；若給樹加之一條邊，形成圖中的一條回路，

則不是樹。P191

生成樹和生成森林：

一個連通無向圖的生成樹是該圖的一個極小聯通生成子圖，它包含原圖中所有頂點（n

個）以及足以構成一棵樹的n-1條邊。

一個非聯通的無向圖，其各連通圖分量的生成圖組成該圖的生成森林。

圖的生成圖或者生成森林不是惟一的，從不同頂點開始、采用不同遍歷可以得到不同

的生成樹或者森林。

在生成樹中，任何樹中，任何兩個頂點之間惟獨惟一的一條路徑。

第八章

折半查找算法描述P206,P207

二叉排序樹及其查找：

二叉排序樹或者是一棵空樹；或者是具有下列性質的二叉樹：

@每一個結點都有一個作為查找依據的關鍵字，所有結點的關鍵字互不相同。

@若一個結點的左子樹不空，則左子樹上所有結點的關鍵字均小于這個節(jié)點的關鍵字；

@每一個結點的擺布子樹也分別為二叉排序樹。

在一棵二叉排序樹中，查找值為value的結點，算法描述如下：

@從根結點開始，設P指向根結點

Rvalue與p結