第一講-數(shù)據(jù)結(jié)構(gòu)與算法課件

大家好1第一講數(shù)據(jù)結(jié)構(gòu)與算法2

本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。31.1算法1、算法是指解題方案的準確而完整的描述。換句話說，算法是對某一特定問題而采取的方法和步驟。*：算法不等于程序，也不等于計算方法。42、算法的基本特征（1）可行性。針對實際問題而設(shè)計的算法，執(zhí)行后能夠得到滿意的結(jié)果。（2）確定性。每一條指令的含義明確，無二義性。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，即相同的輸入只能得出相同的輸出。（3）有窮性。算法必須在有限的時間內(nèi)完成。有兩重含義，一是算法中的操作步驟為有限個，二是每個步驟都能在有限時間內(nèi)完成。5（4）擁有足夠的情報。算法中各種運算總是要施加到各個運算對象上，而這些運算對象又可能具有某種初始狀態(tài)，這就是算法執(zhí)行的起點或依據(jù)。因此，一個算法執(zhí)行的結(jié)果總是與輸入的初始數(shù)據(jù)有關(guān)，不同的輸入將會有不同的結(jié)果輸出。當輸入不夠或輸入錯誤時，算法將無法執(zhí)行或執(zhí)行有錯。一般說來，當算法擁有足夠的情報時，此算法才是有效的；而當提供的情報不夠時，算法可能無效。

6*：綜上所述，所謂算法，是一組嚴謹?shù)囟x運算順序的規(guī)則，并且每一個規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。73、算法復雜度主要包括時間復雜度和空間復雜度。（1）算法時間復雜度：依據(jù)算法編寫的程序在計算機中運行所需基本運算的執(zhí)行次數(shù)來度量（2）算法空間復雜度：依據(jù)算法編寫的程序在計算機中占內(nèi)存空間多少的度量8--------------------------

n+1

-------------------

n(n+1)----------------------------------

n2-----------

n2(n+1)

----

n3for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=0;k<n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][k];}

算法的執(zhí)行次數(shù):

f(n)

=n+1+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+19

當n→∞時，有f(n)/g(n)=常數(shù)≠0，則稱函數(shù)f(n)與g(n)同階,或者說，f(n)與g(n)同一個數(shù)量級，記作

f(n)=O(g(n))

稱上式為算法的時間復雜度,或稱該算法的時間復雜度為O(g(n))

。其中,n為問題的規(guī)模(大小)的量度。算法的時間復雜度為O(n3)lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)

=2n→∞n→∞關(guān)于符號O的的數(shù)學定義10算法中，對需要執(zhí)行的每一步操作，必須給出清楚、嚴格的規(guī)定，這屬于算法的（2007.4）A）正當性B）可行性C）確定性D）有窮性(C)11算法的有窮性是指（2008.4）算法程序的運行時間是有限的算法程序所處理的數(shù)據(jù)量是有限的算法程序的長度是有限的算法只能被有限的用戶使用（A）12算法的時間復雜度是指(2010.3)

A）算法的執(zhí)行時間

B）算法所處理的數(shù)據(jù)量

C）算法程序中的語句或指令條數(shù)

D）算法在執(zhí)行過程中所需要的基本運算次數(shù)（D）131.2數(shù)據(jù)結(jié)構(gòu)的基本概念

數(shù)據(jù)

描述客觀事物的數(shù)字、字符以及一切能夠輸入到計算機中，并且能夠被計算機程序處理的符號的集合。

數(shù)據(jù)元素

數(shù)據(jù)這個集合中的一個一個元素。數(shù)據(jù)對象具有相同特性的數(shù)據(jù)元素的集合。結(jié)構(gòu)數(shù)據(jù)元素之間具有的關(guān)系。14

1.數(shù)據(jù)元素之間的聯(lián)系稱之為結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)就是具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。2.數(shù)據(jù)結(jié)構(gòu)是一個二元組

Data-Structure=(D,R)其中，D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系的集合。15(1).

研究數(shù)據(jù)元素之間的客觀聯(lián)系。

(2).

研究具有某種邏輯關(guān)系的數(shù)據(jù)在計算機存儲器內(nèi)的存儲方式。(3).研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)

的基礎(chǔ)上對數(shù)據(jù)實施一系列有效的基本操作。邏輯結(jié)構(gòu)存儲結(jié)構(gòu)3.數(shù)據(jù)結(jié)構(gòu)所研究的主要內(nèi)容算法164、數(shù)據(jù)結(jié)構(gòu)的圖形表示一個數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點，并簡稱為結(jié)點；為了進一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點指向后件結(jié)點。a1a2a3a30∧list…通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件關(guān)系（即直接前驅(qū)與直接后繼關(guān)系）來描述。17數(shù)據(jù)元素之間具有的邏輯關(guān)系(結(jié)構(gòu))。線性關(guān)系(線性結(jié)構(gòu))

如線性表、數(shù)組、堆棧、隊列等具有某種邏輯結(jié)構(gòu)的數(shù)據(jù)在計算機存儲器中的存儲方式(存儲映象)。順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元依次存放數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過元素的地址直接反映。

用一組地址任意的存儲單元依次存放數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過指針間接地反映。非線性關(guān)系(非線性結(jié)構(gòu))

如樹、二叉樹、圖等物理結(jié)構(gòu)邏輯結(jié)構(gòu)存儲結(jié)構(gòu)5.數(shù)據(jù)結(jié)構(gòu)的分類18

邏輯結(jié)構(gòu)a1a2a3a30…d1d2d3d4

…d30a2a1a3a4a30存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)線性結(jié)構(gòu)（線性表）劉曉光馬廣生王民…張玉華男男…女男漢回壯…漢161721…25……………

姓名性別民族年齡其他

例192.鏈式存儲結(jié)構(gòu)…d1d2d3d4

a1a2a3a30∧list…a2a1a4a3d4d1d5d3201.3線性表及其順序存儲結(jié)構(gòu)

1、線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。線性表是由n(n≥0)個數(shù)據(jù)元素組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。線性表中數(shù)據(jù)元素的個數(shù)稱為線性表的長度。線性表可以為空表。*：線性表是一種邏輯結(jié)構(gòu)，它的存儲方式：順序存儲和鏈式存儲。212、線性表的順序存儲結(jié)構(gòu)具有兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。*：由此可以看出，在線性表的順序存儲結(jié)構(gòu)中，其前后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面，可以通過計算機直接確定第i個結(jié)點的存儲地址。22例：一維數(shù)組的存儲結(jié)構(gòu)inta[5];8824123a[0]a[1]a[2]a[3]a[4]10001006數(shù)組元素地址=數(shù)組起始地址+元素下標*sizeof（數(shù)組類型）a[3]的地址為：1000+3*2=1006233、順序表的插入、刪除運算（1）順序表的插入運算：在一般情況下，要在第i（1≤i≤n）個元素之前插入一個新元素時，首先要從最后一個（即第n個）元素開始，直到第i個元素之間共n-i+1個元素依次向后移動一個位置，移動結(jié)束后，第i個位置就被空出，然后將新元素插入到第i項。插入結(jié)束后，線性表的長度就增加了1。

24

該運算是在線性表的第i1個數(shù)據(jù)元素與第i個數(shù)據(jù)元素之間插入一個由符號item表示的數(shù)據(jù)元素，使長度為n的線性表

(a1,a2,

…

,ai-1,ai,

ai+1,

…

,an-1,

an)

轉(zhuǎn)換成長度為n+1的線性表

(a1,a2,

…

,ai-1,item,ai,

…

,an-1,an

)n個數(shù)據(jù)元素n+1個數(shù)據(jù)元素25

時間復雜度分析

若設(shè)pi為插入一個元素于線性表第i個位置的概率(概率相等)，則在長度為n的線性表中插入一個元素需要移動其他的元素的平均次數(shù)為：

Tis=Pi(n-i+1)=(n-i+1)/(n+1)=n/2稱該算法的時間復雜度是O(n)。ni=1ni=126（2）順序表的刪除運算：在一般情況下，要刪除第i（1≤i≤n）個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，線性表的長度就減小了1。27

該運算是把線性表的第i個數(shù)據(jù)元素從線性表中去掉，使得長度為n的線性表

(a1,a2,

…

,ai-1,ai,

ai+1,

…

,an-1,

an

)

轉(zhuǎn)換成長度為n-1的線性表

(a1,a2,

…

,ai-1,ai+1,…

,an-1,an)n個數(shù)據(jù)元素n-1個數(shù)據(jù)元素28

時間復雜度的分析

若pi為刪除線性表中第i個數(shù)據(jù)元素的概率(概率相等)，在長度為n的線性表中刪除第i個數(shù)據(jù)元素需要移動其他的元素的平均次數(shù)為：

Tds=Pi(n-i)=(n-i)/n=(n-1)/2稱該算法的時間復雜度為O(n)。

ni=1ni=129下列敘述中正確的是

（2007.4）A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B)算法的時間復雜度是指執(zhí)行算法所需要的計算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應的D)算法的時間復雜度與空間復雜度一定相關(guān)(B)30算法的空間復雜度是指(2009.9)A）算法在執(zhí)行過程中所需要的計算機存儲空間B）算法所處理的數(shù)據(jù)量C）算法程序中的語句或指令條數(shù)D）算法在執(zhí)行過程中所需要的臨時工作單元數(shù)(A)311.4棧和隊列1、棧及其基本運算

棧是限定在一端進行插入與刪除運算的線性表。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。棧的基本運算：1）插入元素稱為入棧運算；2）刪除元素稱為退棧運算；3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。棧的存儲方式和線性表類似，也有兩種，即順序棧和鏈式棧。32abcdetopxdcbaetope

堆棧

是一種只允許在表的一端進行插入操作和刪除操作的線性表。允許操作的一端稱為棧頂，棧頂元素的位置由一個稱為棧頂指針的變量給出。當表中沒有元素時，稱之為空棧。先進后出33一個棧的初始狀態(tài)為空?，F(xiàn)將元素1、2、3、4、5、A、B、C、D、E依次入棧，然后再依次出棧，則元素出棧的順序是：（2008.9）A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA（B）34下列關(guān)于棧的敘述正確的是：（2008.4）棧按“先進先出”組織數(shù)據(jù)棧按“先進后出”組織數(shù)據(jù)只能在棧底插入數(shù)據(jù)不能刪除數(shù)據(jù)（B）35假設(shè)用一個長度為50的數(shù)組(數(shù)組元素的下標從0到49)作為棧的存儲空間,棧底指針bottom指向棧底元素,棧頂指針top指向棧頂元素,如果bottom=49,top=30(數(shù)租下標),則棧中具有【】個元素（20）36下列敘述中正確的是(2010.9)

A）在棧中，棧中元素隨棧底指針與棧頂指針的變化而動態(tài)變化

B）在棧中，棧頂指針不變，棧中元素隨棧底指針的變化而動態(tài)變化

C）在棧中，棧底指針不變，棧中元素隨棧頂指針的變化而動態(tài)變化

D）上述三種說法都不對（c）37一個棧的初始狀態(tài)為空。首先將元素5,4,3,2,1依次入棧，然后退棧一次，再將元素A,B,C,D依次入棧，之后將所有元素全部退棧，則所有元素退棧（包括中間退棧的元素）的順序為

（2010.9）1DCBA234538

2隊列及其基本運算abcdeefae隊頭元素隊尾元素ab

隊列簡稱隊，是一種只允許在表的一端進行插入操作,而在表的另一端進行刪除操作的線性表。允許插入的一端稱為隊尾，隊尾元素的位置由rear指出；允許刪除的一端稱為隊頭,隊頭元素的位置由front指出。先進先出39

循環(huán)隊列及其運算：所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向排頭元素的前一個位置，因此，從頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間，所有的元素均為隊列中的元素。40…^list…list…list

線性鏈表循環(huán)鏈表帶頭結(jié)點的循環(huán)鏈表頭結(jié)點41下列敘述中正確的是：（2008.9）循環(huán)隊列有隊頭和隊尾兩個指針，因此，循環(huán)隊列是非線性結(jié)構(gòu)在循環(huán)隊列中，只需要隊頭指針就能反映隊列中元素的動態(tài)變化情況在循環(huán)隊列中，只需要隊尾指針就能反映隊列中元素的動態(tài)變化情況循環(huán)隊列中元素的個數(shù)是由隊頭指針和隊尾指針共同決定（D）42線性表的存儲結(jié)構(gòu)主要分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。隊列是一種特殊的線性表，循環(huán)隊列是隊列的______存儲結(jié)構(gòu)。（2007.9）鏈式43下列對隊列的敘述正確的是

（2007.4）A)隊列屬于非線性表B)隊列按“先進后出”原則組織數(shù)據(jù)C)隊列在隊尾刪除數(shù)據(jù)D)隊列按“先進先出”原則組織數(shù)據(jù)(D)44對于循環(huán)隊列，下列敘述中正確的是(2009.9)A）隊頭指針是固定不變的B）隊頭指針一定大于隊尾指針C）隊頭指針一定小于隊尾指針D）隊頭指針可以大于隊尾指針，也可以小于隊尾指針(D)45一個隊列的初始狀態(tài)為空?，F(xiàn)將元素A，B，C，D，E，F(xiàn)，5，4，3，2，1依次入隊，然后再依次退隊，則元素退隊的順序為【1】。（2010.3）A，B，C，D，E，F(xiàn)，5，4，3，2，146設(shè)某循環(huán)隊列的容量為50，如果頭指針front=45（指向隊頭元素的前一位置），尾指針rear=10（指向隊尾元素），則該循環(huán)隊列中共有【2】個元素。（2010.3）15471.5線性鏈表1、線性表順序存儲的缺點：（1）插入或刪除的運算效率很低。在順序存儲的線性表中，插入或刪除數(shù)據(jù)元素時需要移動大量的數(shù)據(jù)元素；（2）線性表的順序存儲結(jié)構(gòu)下，線性表的存儲空間不便于擴充；（3）線性表的順序存儲結(jié)構(gòu)不便于對存儲空間的動態(tài)分配。

482、線性鏈表：線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表，是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接來實現(xiàn)的。因此，在鏈式存儲方式中，每個結(jié)點由兩部分組成：一部分用于存放數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域，用于指向該結(jié)點的前一個或后一個結(jié)點（即前件或后件），如下圖所示：4950

線性鏈表分為單鏈表、雙向鏈表和循環(huán)鏈表三種類型。在單鏈表中，每一個結(jié)點只有一個指針域，由這個指針只能找到其后件結(jié)點，而不能找到其前件結(jié)點。因此，在某些應用中，對于線性鏈表中的每個結(jié)點設(shè)置兩個指針，一個稱為左指針，指向其前件結(jié)點；另一個稱為右指針，指向其后件結(jié)點，這種鏈表稱為雙向鏈表，如下圖所示：51524、循環(huán)鏈表及其基本運算在線性鏈表中，對于空表和對第一個結(jié)點的處理必須單獨考慮，使空表與非空表的運算不統(tǒng)一。為了克服線性鏈表的這個缺點，可以采用另一種鏈接方式，即循環(huán)鏈表。

53

循環(huán)鏈表具有以下兩個特點：1）在鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置，指針域指向線性表的第一個元素的結(jié)點，而循環(huán)鏈表的頭指針指向表頭結(jié)點；2）循環(huán)鏈表中最后一個結(jié)點的指針域不是空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。下圖中，圖a是一個非空的循環(huán)鏈表，圖b是一個空的循環(huán)鏈表：

5455

循環(huán)鏈表的優(yōu)點主要體現(xiàn)在兩個方面：一是在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點，而線性單鏈表做不到這一點；二是由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點，在任何情況下，循環(huán)鏈表中至少有一個結(jié)點存在，從而使空表與非空表的運算統(tǒng)一。56下列敘述中正確的是：（2008.9）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈式存儲結(jié)構(gòu)的存儲空間不一定是連續(xù)的順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈式存儲結(jié)構(gòu)只針對非線性結(jié)構(gòu)順序存儲結(jié)構(gòu)能存儲有序表，鏈式存儲結(jié)構(gòu)不能存儲有序表鏈式存儲結(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間（A）57下列敘述中正確的是(2010.9)

A）線性表的鏈式存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)所需要的存儲空間是相同的

B）線性表的鏈式存儲結(jié)構(gòu)所需要的存儲空間一般要多于順序存儲結(jié)構(gòu)

C）線性表的鏈式存儲結(jié)構(gòu)所需要的存儲空間一般要少于順序存儲結(jié)構(gòu)

D）上述三種說法都不對（B）58(2009.3)下列敘述中正確的是A)棧是先進先出的線性表B)隊列是"先進后出"的線性表C)循環(huán)隊列是非線性結(jié)構(gòu)D)有序線性表即可以采用順序存儲結(jié)構(gòu),也可以采用鏈式存儲結(jié)構(gòu)（D）59在長度為n的線性表中，尋找最大項至少需要比較

次。（2010.9）1601.6樹與二叉樹1、樹的基本概念樹是一種簡單的非線性結(jié)構(gòu)。在樹這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特性。

61校長一系二系三系六系教務處科研處總務處601602教務科603ABCD…………張三李四王五…例1…工廠62(根目錄)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………63例364

在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點。沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。JIHGFEACXB651.

結(jié)點的度：2.

樹的度：3.

葉結(jié)點：4.

分支結(jié)點:5.

層次的定義:JIHGFEACXB該結(jié)點擁有的子樹的數(shù)目。樹中結(jié)點度的最大值。度為0的結(jié)點.度非0的結(jié)點.

根結(jié)點為第一層,若某結(jié)點在第i層,

則其孩子結(jié)點(若存在)為第i+1層.基本名詞術(shù)語第1層第2層第3層667.

樹林(森林):

m0棵不相交的樹組成的樹的集合.8.

樹的有序性:ABCDEABCDEFF6.

樹的深度:樹中結(jié)點所處的最大層次數(shù).

若樹中結(jié)點的子樹的相對位置不能隨意改變,則稱該樹為有序樹，否則稱該樹為無序樹。JIHGFEACXB有序樹？無序樹？深度為3的樹672、二叉樹及其基本性質(zhì)（1）什么是二叉樹二叉樹是一種很有用的非線性結(jié)構(gòu)，它具有以下兩個特點：1）非空二叉樹只有一個根結(jié)點；2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。*：根據(jù)二叉樹的概念可知，二叉樹的度可以為0（葉結(jié)點）、1（只有一棵子樹）或2（有2棵子樹）。

68二叉樹的基本形態(tài)：(空)根根左子樹根右子樹根左子樹右子樹69（2）.兩種特殊形態(tài)的二叉樹

若一棵二叉樹中的結(jié)點,或者為葉結(jié)點，或者具有兩棵非空子樹,并且葉結(jié)點都集中在二叉樹的最下面一層.這樣的二叉樹為滿二叉樹.1.滿二叉樹

若一棵二叉樹中只有最下面兩層的結(jié)點的度可以小于2,并且最下面一層的結(jié)點(葉結(jié)點)都依次排列在該層從左至右的位置上。這樣的二叉樹為完全二叉樹.2.完全二叉樹701.一棵非空二叉樹的第i層最多有2i–1個結(jié)點(i1)。證明(采用歸納法)(1).當i=1時,結(jié)論顯然正確。非空二叉樹的第1層有且僅有一個結(jié)點,即樹的根結(jié)點.(2).假設(shè)對于第j層(1ji–1)結(jié)論也正確,即第j層最多有2j-1個結(jié)點.(3).有定義可知,二叉樹中每個結(jié)點最多只能有兩個孩子結(jié)點。若第i–1層的每個結(jié)點都有兩棵非空子樹,則第i層的結(jié)點數(shù)目達到最大.而第i–1層最多有2i–2個結(jié)點已由假設(shè)證明,于是,應有

22i–2=2i–1證畢.（3）.二叉樹的性質(zhì)712.深度為h的非空二叉樹最多有2h-1個結(jié)點.證明:

由性質(zhì)1可知,若深度為h的二叉樹的每一層的結(jié)點數(shù)目都達到各自所在層的最大值,則二叉樹的結(jié)點總數(shù)一定達到最大。即有

20+21+22+…+2i-1+…+2h-1=2h-1證畢.723.若非空二叉樹有n0個葉結(jié)點,有n2個度為2的結(jié)點,

則n0=n2+1

證明:

設(shè)該二叉樹有n1個度為1的結(jié)點,結(jié)點總數(shù)為n,有

n=n0+n1+n2

--------(1)

設(shè)二叉樹的分支數(shù)目為B,有

B=n-1

--------(2)這些分支來自度于為1的結(jié)點與度度為2結(jié)點,即

B=n1+2n2

--------(3)聯(lián)列關(guān)系(1),(2)與(3),可得到

n0=n2+1證畢.4.具有n個結(jié)點的完全二叉樹的深度h=log2n+1.證明:(略)735.若對具有n個結(jié)點的完全二叉樹按照層次從上到下,每層從左到右的順序進行編號,則編號為i的結(jié)點具有以下性質(zhì):(1)當i=1,則編號為i的結(jié)點為二叉樹的根結(jié)點;

若i>1,則編號為i的結(jié)點的雙親結(jié)點的編號為i/2.(2)若2i>n,則編號為i的結(jié)點無左子樹;

若2in,則編號為i的結(jié)點的左子樹的根的編號為2i.(3)若2i+1>n,則編號為i的結(jié)點無右子樹;

若2i+1n,則編號為i的結(jié)點的右子樹的根的編號為2i+1.12345678910n=1074一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為：（2007.9）A）219B）221C）229D）231（A）75某二叉樹中有n個度為2的結(jié)點，則該二叉樹中的葉子結(jié)點數(shù)為（2007.4）A)n+1B)n-1C)2nD)n/2(A)76在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為_______（2007.4）6377某二叉樹有5個度為2的結(jié)點,則該二叉樹中的葉子結(jié)點數(shù)是(2009.3)A)10B)8C)6D)4C78某二叉樹有5個度為2的結(jié)點以及3個度為1的結(jié)點，則該二叉樹中共有【】個結(jié)點。（2009.9）1479一棵二叉樹有10個度為1的結(jié)點，7個度為2的結(jié)點，則該二叉樹共有

個結(jié)點。（2010.9）25803、什么是二叉樹的遍歷常用的二叉樹的遍歷方法:

1.前序遍歷

2.中序遍歷

3.后序遍歷

4.按層次遍歷右子樹左子樹根

按照一定的順序(原則)對二叉樹中每一個結(jié)點都訪問一次(僅訪問一次),得到一個由該二叉樹的所有結(jié)點組成的序列,這一過程稱為二叉樹的遍歷.81（1）.前序遍歷ABCDEFGIJ前序序列:ABDEJCFI原則:

若被遍歷的二叉樹非空,則

1.訪問根結(jié)點;

2.以前序遍歷原則遍歷根結(jié)點的左子樹;

3.以前序遍歷原則遍歷根結(jié)點的右子樹.G82（2）.中序遍歷中序序列:DBJEAFIC原則:

若被遍歷的二叉樹非空,則

1.以中序遍歷原則遍歷根結(jié)點的左子樹;

2.訪問根結(jié)點;

3.以中序遍歷原則遍歷根結(jié)點的右子樹.GABCDEFGIJ83（3）.后序遍歷后序序列:DJEBIFGC原則:

若被遍歷的二叉樹非空,則

1.以后序遍歷原則遍歷根結(jié)點的左子樹;

2.以后序遍歷原則遍歷根結(jié)點的右子樹.

3.訪問根結(jié)點;AABCDEFGIJ84對下列二叉樹進行中序遍歷的結(jié)果是：（2008.9）DBXEAYFZCABCDEXFYZ85對下列二叉樹進行中序遍歷的結(jié)果是：（2007.9）ACBDFHGPEFCEADBGHP86對下列二叉樹進行前序遍歷的結(jié)果為

（2007.4）(C)ABCDEYFXZA)DYBEAFCZXB)YDEBFZXCAC)ABDEYCFXZD)ABCDEFXYZ87設(shè)二叉樹如下：對該二叉樹進行后序遍歷的結(jié)果為（2010.3）

EDBGHFCA

88支持子程序調(diào)用的數(shù)據(jù)結(jié)構(gòu)是(2009.3)A)棧B)樹C)隊列D)二叉樹(A)89下列數(shù)據(jù)結(jié)構(gòu)中，屬于非線性結(jié)構(gòu)的是(2009.9)A）循環(huán)隊列B)帶鏈隊列C)二叉樹D）帶鏈棧(C)90下列數(shù)據(jù)結(jié)構(gòu)中，能夠按照“先進后出”原則存取數(shù)據(jù)的是(2009.9)A)循環(huán)隊列B)棧C)隊列D)二叉樹(B)911.7查找技術(shù)查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找結(jié)果：（查找成功：找到；查找不成功：沒找到。）平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。921、順序查找基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。KEY[1:10]

38751957100485076211若查找

k=48經(jīng)過六次比較,查找成功查找失敗若查找

k=3593

在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。

若查找概率相等，則有

ASL=pici=i=

1n+1n2ni=1ni=1

順序查找一個具有n個元素的線性表，其平均復雜度為O（n）。94下列兩種情況下只能采用順序查找：1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，都只能用順序查找。2）即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。952、二分法查找思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。查找過程：1）若中間項（中間項mid=(n-1)/2，mid的值四舍五入取整）的值等于x，則說明已查到；2）若x小于中間項的值，則在線性表的前半部分查找；3）若x大于中間項的值，則在線性表的后半部分查找。96n

排序連續(xù)順序文件中記錄的個數(shù)。low

當前查找范圍內(nèi)第一個記錄在文件中的位置。high

當前查找范圍內(nèi)最后那個記錄在文件中的位置。mid

當前查找范圍內(nèi)位置居中的那個記錄在文件中的位置。初值low=1初值high=nmi