2010公共基礎(chǔ)知識-數(shù)據(jù)結(jié)構(gòu)

計算機等級考試

公共基礎(chǔ)知識

數(shù)計學(xué)院衛(wèi)春芳1計算機二級考試公共基礎(chǔ)知識大綱

數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)這四個方面在試卷中出現(xiàn)的情況是：選擇題10個（20分），填空題5個（10分），總分值占到了試卷卷面分的30％，是一個不小的比例。

2計算機二級考試公共基礎(chǔ)知識試卷分析

章節(jié)考試時間數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)2006年4月10分4分6分10分2006年9月10分2分8分10分2007年4月10分2分10分8分2007年9月12分4分8分6分2008年4月10分2分8分10分2008年9月10分2分8分10分2009年3月10分2分8分10分3算法⒈算法的基本概念

2.算法的基本特征

3.

算法的表示

4.算法的要素

5.算法的評價一、基本數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)⒈數(shù)據(jù)結(jié)構(gòu)的概念⒉線性表⒊棧和隊列⒋樹與二叉樹⒌查找技術(shù)⒍排序技術(shù)

對于等級考試，這個部分的考核重點主要在算法的基本概念和特征、二叉樹(遍歷、結(jié)點），還有排序和查找考試中也經(jīng)常會涉及到。4算法的定義對解題方案準(zhǔn)確而完整的描述稱為算法。算法是程序設(shè)計的核心⒈算法的基本概念

算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說，就是計算機解題的過程(計算的方法)。在這個過程中，無論是形成解題思路(推理實現(xiàn)的算法)還是編寫程序(操作實現(xiàn)的算法)，都是在實施某種算法。例：解方程：f(x)=0在區(qū)間[a,b]上有實根且f(a)與f(b)異號，求該方程在區(qū)間[a,b]上的實根。

有多種解法，常用的是用二分法求方程實根。5

2.

算法的基本特征一個算法應(yīng)該具有以下五個重要的特征：有窮性確定性輸入輸出可行性一個算法必須保證執(zhí)行有限步之后結(jié)束；算法的每一步驟必須有確切的定義；一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件；一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成算法的特征：有窮性、確定性、可行性、擁有足夠的情報。6算法與計算機程序算法____是一組邏輯步驟程序——用計算機語言描述的算法3.算法的表示INPUTrS=3.14*r*rPTINTS開始輸入RS=3.14*

R*R輸出S結(jié)束問題：輸入園的半徑，計算園的面積

一個算法的表示需要使用一些語言形式。傳統(tǒng)的算法-------圖形法，如“流程圖”和N-S圖目前常用的方法-------使用偽碼描述算法。7冒泡排序的方法：1.掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大的元素排到表的最后；2.除最后一個元素，對剩余的元素重復(fù)上述過程，將次大的數(shù)排到表的倒數(shù)第二個位置；3.重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。

算法舉例：n個數(shù)排序84.算法的兩個基本要素：基本運算和操作算術(shù)運算關(guān)系運算邏輯運算數(shù)據(jù)傳輸控制結(jié)構(gòu)

順序選擇循環(huán)一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。算法基本設(shè)計方法：列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法

95.

算法評價評價一個算法優(yōu)劣的主要標(biāo)準(zhǔn)是算法的執(zhí)行效率和存儲需求：時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量一般可以用算法在執(zhí)行過程中所需基本運算的執(zhí)行次數(shù)來度量計算工作量空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間

算法在執(zhí)行過程中臨時占用的存儲空間

時間復(fù)雜度它大致等于計算機執(zhí)行一種簡單操作所需的平均時間與算法中進行簡單操作的次數(shù)的乘積。

一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個部分10一、算法對解題方案準(zhǔn)確而完整的描述稱為算法。算法不等于程序，也不等計算機方法，程序的編制不可能優(yōu)于算法的設(shè)計。算法的兩個要素：一是對數(shù)據(jù)對象的運算和操作；二是算法的控制結(jié)構(gòu)。算法的特征：

有窮性、確定性、可行性、輸入、輸出算法評價：

時間復(fù)雜度：執(zhí)行這個算法所需要的計算工作量空間復(fù)雜度：執(zhí)行這個算法所需要的內(nèi)存空間11(1)算法一般都可以用哪幾種控制結(jié)構(gòu)組合而成____。

A.循環(huán)、分支、遞歸

B.順序、循環(huán)、嵌套

C.循環(huán)、遞歸、選擇

D.順序、選擇、循環(huán)(2)算法中，對需要執(zhí)行的每一步操作，必須給出清楚、嚴(yán)格的規(guī)定，這屬于算法的（07年4月）

A）正當(dāng)性B）可行性C）確定性D）有窮性(3)在計算機中，算法是指______。

A.查詢方法B.加工方法

C.解題方案的準(zhǔn)確而完整的描述D.排序方法(4)下列敘述中正確的是（07年4月）A)算法的效率只與問題的規(guī)模有關(guān)，而與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)B)算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量C)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的D)算法的時間復(fù)雜度與空間復(fù)雜度一定相關(guān)(D)(c)(c)(B)算法習(xí)題:12(5)算法的有窮性是指(08年4月)A）算法程序的運行時間是有限的B）算法程序所處理的數(shù)據(jù)量是有限的C）算法程序的長度是有限的D）算法只能被有限的用戶使用(6)算法的時間復(fù)雜度是指______。A.執(zhí)行算法程序所需要的時間B.算法程序的長度C.算法執(zhí)行過程中所需要的基本運算次數(shù)D.算法程序中的指令條數(shù)(7)下列敘述中正確的是(06年9月)

A）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度也必定大

B）一個算法的空間復(fù)雜度大，則其時間復(fù)雜度必定小

C）一個算法的時間復(fù)雜度大，則其空間復(fù)雜度必定小

D）上述三種說法都不對(A)(C)計算工作量(d)13

計算機在進行數(shù)據(jù)處理時，實際需要處理的數(shù)據(jù)元素一般有很多，而這些大量的數(shù)據(jù)元素都需要存放在計算機中，因此，大量的數(shù)據(jù)元素在計算機中如何組織，以便提高數(shù)據(jù)處理的效率，并且節(jié)省計算機的存儲空間，這是進行數(shù)據(jù)處理的關(guān)鍵問題。二、數(shù)據(jù)結(jié)構(gòu)程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

一般來說，人們不會同時處理特征完全不同且互相之間沒有任何關(guān)系的各類數(shù)據(jù)元素，對于具有不同特征的數(shù)據(jù)元素總是分別進行處理。一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。14二.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，它包括三個方面。

（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。151.邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)包含：（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。例：1.一年四季的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={春，夏，秋，冬}R={(春，夏),(夏，秋),(秋，冬)}2.家庭成員的數(shù)據(jù)結(jié)構(gòu)

B=(D,R)D={父親，兒子，女兒}R={(父親，兒子),(父親，女兒)}春夏秋冬數(shù)據(jù)結(jié)構(gòu)的圖形表示父親兒子女兒16常見的邏輯結(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é)構(gòu)中的每個元素之間存在一個對一個的關(guān)系；②樹形結(jié)構(gòu)結(jié)構(gòu)中的每個元素之間存在一個對多個的關(guān)系；③圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的每個元素之間存在多個對多個的關(guān)系。其中，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線形結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)可以用二元關(guān)系表示，也可以直觀地用圖形來表示。17存儲結(jié)構(gòu)（物理結(jié)構(gòu)）是指數(shù)據(jù)結(jié)構(gòu)在計算機存儲器中的具體實現(xiàn)。數(shù)據(jù)結(jié)構(gòu)（包括數(shù)據(jù)及其數(shù)據(jù)之間的關(guān)系）在計算機存儲器上的存儲表示稱為數(shù)據(jù)的物理結(jié)構(gòu)或存儲結(jié)構(gòu)，由于存儲表示的方法有多種，諸如順序、鏈接、索引等，所以一種數(shù)據(jù)結(jié)構(gòu)可以根據(jù)需要表示成一種或多種存儲結(jié)構(gòu)。

18

2.存儲結(jié)構(gòu)（物理結(jié)構(gòu)）計算機在實際進行數(shù)據(jù)處理時，被處理的各數(shù)據(jù)元素總是被存放在計算機的存儲空間中，并且，各數(shù)據(jù)元素在計算機存儲空間中的位置與它們的邏輯關(guān)系不一定是相同的，而且一般也不可能相同。如：一年四季

家庭成員計算機存儲空間怎樣存放？

存儲結(jié)構(gòu)指數(shù)據(jù)結(jié)構(gòu)在計算機存儲空間中的具體實現(xiàn)。常見的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)索引存儲結(jié)構(gòu)19數(shù)據(jù)處理檢索插入刪除更新排序

數(shù)據(jù)處理（數(shù)據(jù)的運算）是指對數(shù)據(jù)集合中各個元素以各種方式進行運算，包括：插入、刪除、查找、更改、排序等，還包括對數(shù)據(jù)元素進行分析。數(shù)據(jù)的邏輯結(jié)構(gòu)表示數(shù)據(jù)元素之間的關(guān)系，有一對一、一對多、多對多的關(guān)系；數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。20數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)和數(shù)據(jù)之間關(guān)系的一門學(xué)科，研究以下三方面內(nèi)容：

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算21常見的數(shù)據(jù)結(jié)構(gòu)

1.線性表

2.棧和隊列

3.樹22１．線性表（LinearList）線性表由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號，元素之間的相對位置是線性的。在復(fù)雜線性表中，由若干項數(shù)據(jù)元素組成的數(shù)據(jù)元素稱為記錄，而由多個記錄構(gòu)成的線性表又稱為文件。簡單的線性表春夏秋冬復(fù)雜的線性表記錄102011001

張三男…

記錄202011003李四女…記錄3記錄423線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特點：（1）線性表中所有元素的所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。ai的存儲地址為：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)為第一個元素的地址，k代表每個元素占的字節(jié)數(shù)。順序表的運算：插入、刪除。24線性表的順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里，順序存儲結(jié)構(gòu)只存儲結(jié)點的值，不存儲結(jié)點間的關(guān)系，結(jié)點間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)?！璦1a2…ai…an…存儲地址200020042000+4*(i-1)2000+4*(n-1)……占4個字節(jié)Loa（ai）=Loa（a1）+L*（i-1）第i個數(shù)的地址第一個數(shù)的地址L為該類型數(shù)所占的字節(jié)25順序表的插入運算順序表的刪除運算順序表的插入和刪除運算在線性表順序存儲情況下，要插入或刪除一個元素，都會由于數(shù)據(jù)元素的移動而消耗大量的處理時間，所以這種存儲方式對于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動的線性表是合適的。線性表的順序存儲結(jié)構(gòu)稱為順序表。26線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)有兩種：

順序存儲結(jié)構(gòu)

鏈?zhǔn)酱鎯Y(jié)構(gòu)注意：數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系與它們的邏輯關(guān)系不一定是相同的。一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且不同的存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。27線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點的指針域指示。鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個存儲結(jié)點不僅存儲結(jié)點的值，而且存儲結(jié)點之間的關(guān)系：數(shù)據(jù)域指針域28應(yīng)用舉例——線性鏈表的存儲結(jié)構(gòu)設(shè)線性表為（a1，a2，a3，a4，a5）1a2923a1145a4106789a3510a50HEAD3a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)線性鏈表的物理狀態(tài)1a12a23a34a45a567線性表的順序存儲結(jié)構(gòu)注意:123此類編號不代表所在的地址單元的地址編碼29線性鏈表數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單元，這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點。結(jié)點由兩部分組成：（1）用于存儲數(shù)據(jù)元素值，稱為數(shù)據(jù)域；（2）用于存放指針，稱為指針域，用于指向前一個或后一個結(jié)點。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯Ψ绞郊纯捎糜诒硎揪€性結(jié)構(gòu)，也可用于表示非線性結(jié)構(gòu)。線性鏈表，HEAD稱為頭指針，HEAD=NULL（或0）稱為空表，如果是兩指針：左指針（Llink）指向前件結(jié)點，右指針（Rlink）指向后件結(jié)點。30單鏈表的插入運算單鏈表的刪除運算線性鏈表的插入和刪除運算采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲空間開銷較大，但是進行插入和刪除運算不會造成大量元素的移動。312.棧和隊列棧和隊列都是特殊的線性表。

棧（Stack）及其基本運算

隊列（Queue）及其基本運算

循環(huán)隊列及其基本運算32棧（Stack）是一種特殊的線性表。其特點是插入和刪除運算都只能在線性表的一端進行。棧是按照“先進后出”或“后進先出”的原則組織數(shù)據(jù)的線性表。用top表示棧頂位置，用bottom表示棧底。棧的基本運算：（1）插入元素稱為入棧運算；（2）刪除元素稱為退棧運算；（3）讀棧頂元素是將棧頂元素賦給一個指定的變量，此時指針無變化。順序棧的進棧和出棧運算在順序棧中插入和刪除運算不需要移動表中其他數(shù)據(jù)元素。33隊列（Queue）是一種特殊的線性表。隊列是指允許在一端（隊尾）進入插入，而在另一端（隊頭）進行刪除的線性表。

Rear指針指向隊尾，front指針指向隊頭。隊列是按照“先進先出”或“后進后出”的原則組織數(shù)據(jù)的線性表。隊列運算包括（1）入隊運算：從隊尾插入一個元素；（2）退隊運算：從隊頭刪除一個元素。順序隊列的運算

34棧有三種操作：入棧＼出棧＼讀棧頂元素隊列有三種操作：入隊＼出隊＼讀隊首元素例：有入棧元素序列：ABCD，求可能的出棧序列．如是隊列又是什么情況呢？35循環(huán)隊列把隊列的存儲空間在邏輯上看作一個環(huán)，當(dāng)R指向存儲空間的末端后，就把它重新置于始端。循環(huán)隊列的運算隊列中進行插入的一端稱做隊尾(rear),進行刪除的一端稱做隊首(front)。

習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于【】結(jié)構(gòu)。（2005年9月）答案：存儲結(jié)構(gòu)。36常見數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)線性表

線性結(jié)構(gòu)棧

是特殊的線性表

隊列

也是一種操作受限的特殊的線性表樹（樹型結(jié)構(gòu)）是一種重要的非線形數(shù)據(jù)結(jié)構(gòu)37線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性結(jié)構(gòu)條件：（1）有且只有一個根結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。a1a2a5a3a4HEAD319510線性鏈表的邏輯狀態(tài)

A∧G∧∧

E∧∧

F∧

B∧

C∧

Dt38數(shù)據(jù)存儲結(jié)構(gòu)方面的考題

1：數(shù)據(jù)的存儲結(jié)構(gòu)是指

（2005年4月）

A)存儲在外存中的數(shù)據(jù)

B)數(shù)據(jù)所占的存儲空間量

C)數(shù)據(jù)在計算機中的順序存儲方式

D)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示2：下列敘述中正確的是（2009年3月）

A）棧是“先進先出”的線性表

B）隊列是“先進后出”的線性表

C）循環(huán)隊列是非線性結(jié)構(gòu)

D）有序線性表既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)3.數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，帶鏈的隊列屬于[]。答案：D。答案：D。答案：線性結(jié)構(gòu)。394。下列敘述中正確的是（）。（2008年9月）

A）順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的，鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的

B）順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu)

C）順序存儲結(jié)構(gòu)能存儲有序表，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表

D）鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間答案：A。5。下列關(guān)于棧的敘述正確的是（2008年4月）

A）棧按“先進先出”組織數(shù)據(jù)B)棧按“先進后出”組織數(shù)據(jù)

C）只能在棧底插入數(shù)據(jù)D）不能刪除數(shù)據(jù)

答案：B。6。假設(shè)用一個長度為50的數(shù)組（數(shù)組元索的下標(biāo)從0到49）作為棧的存儲空間，棧底指針bottom指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有【】個元素。（2009年3月）

答案：19。40樹型結(jié)構(gòu)是一種重要的非線性結(jié)構(gòu)。

樹的概念

二叉樹的概念

二叉樹的存儲

二叉樹的遍歷3.樹與二叉樹41樹的概念

樹的定義：n個結(jié)點的有限集。（n>=0）樹是一種簡單的非線性結(jié)構(gòu)，所有元素之間具有明顯的層次特性。在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為父結(jié)點，沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點，簡稱樹的根。每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點

根：onlyone

若n=0，則稱為空樹；否則，當(dāng)n>1時，其余結(jié)點被分成m（m>0）個互不相交的子集T1，T2，...，Tm，每個子集又是一棵樹。由此可以看出，樹的定義是遞歸的。ABDFECGHIJKM42樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM

結(jié)點的度一個結(jié)點的子樹的個數(shù)；Q：結(jié)點A、G的度數(shù)？

樹的度樹中所有結(jié)點度的最大值；Q：右圖中樹的度？

終端結(jié)點度為0的結(jié)點；

Q：圖中葉子結(jié)點有幾個？7

非終端結(jié)點

度不為0的結(jié)點；

Q：圖中非終端結(jié)點有幾個？5孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點、結(jié)點的子孫、結(jié)點的祖先43樹型結(jié)構(gòu)的常用術(shù)語ABDFECGHIJKM

結(jié)點的層次樹中根結(jié)點的層次為1，根結(jié)點子樹的根為第2層，以此類推；

Q：圖中結(jié)點F的層次？

樹的深度

樹中所有結(jié)點層次的最大值；

Q：圖中樹的深度？

有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，則稱為有序樹，否則稱為無序樹。①②③④44樹的基本術(shù)語在樹結(jié)構(gòu)中，一個結(jié)點所擁有的后件的個數(shù)稱為該結(jié)點的度，所有結(jié)點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。二叉樹的特點：（1）非空二叉樹只有一個根結(jié)點；（2）每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。ABCDFEHG45二叉樹的基本性質(zhì)：（1）在二叉樹的第k層上，最多有2k-1(k≥1)個結(jié)點；（2）深度為m的二叉樹最多有2m-1個結(jié)點；（3）度為0的結(jié)點（即葉子結(jié)點）總是比度為2的結(jié)點多一個；（4）具有n個結(jié)點的二叉樹，其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分；（5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1；461213891011456123滿二叉樹完全二叉樹84567123滿二叉樹是指除最后一層外，每一層上的所有結(jié)點有兩個子結(jié)點，則k層上有2k-1個結(jié)點，深度為m的滿二叉樹有2m-1個結(jié)點。完全二叉樹是指除最后一層外，每一層上的結(jié)點數(shù)均達到最大值，在最后一層上只缺少右邊的若干結(jié)點714151213891011456123非完全二叉樹47（5）具有n個結(jié)點的完全二叉樹的深度為[log2n]+1121314158910114567123深度為4的滿二叉樹深度為4的完全二叉樹84567123深度為３的完全二叉樹具有４～７深度為４的完全二叉樹具有８～１５深度為５的完全二叉樹具有１６～３１log2(8+1)=ln9/In2=4log2(15+1)=In16/In2=4481：在深度為7的滿二叉樹中,葉子結(jié)點的個數(shù)為（2006年4月）

A)32

B)31

C)64

D)632：在深度為7的滿二叉樹中，度為2的結(jié)點個數(shù)為【】

。(07年4月）3：一棵二叉樹中共有70個葉子結(jié)點與80個度為1的結(jié)點，則該二叉樹中的總結(jié)點數(shù)為（07年9月）

A）219B）221C）229D）2314：某二叉樹中度為2的結(jié)點有18個，則該二叉樹中有【】個葉子結(jié)點。（2005年4月）5：一棵二叉樹第六層（根結(jié)點為第一層）的結(jié)點數(shù)最多為【】個。（2005年9月）

樹型結(jié)構(gòu)方面的考題

1答案：C。3答案：A。5答案：32。2答案：63。4答案：19。49二叉樹的存儲在計算機中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。LlinkinfoRlink二叉樹的存儲結(jié)點的結(jié)構(gòu)ABDCFGE

A∧G∧∧

E∧∧

F∧

B∧

C∧

Dt50二叉樹的遍歷（1）前序遍歷（DLR）首先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹；（2）中序遍歷（LDR）首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；（3）后序遍歷（LRD）首先遍歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點。ABCDFEHG遍歷指不重復(fù)地訪問二叉樹中的所有結(jié)點。二叉樹的遍歷的次序與樹型結(jié)構(gòu)上的大多數(shù)運算有聯(lián)系。51二叉樹的遍歷ABCDFEHG先序遍歷的結(jié)果：

ABECFGHD中序遍歷的結(jié)果：

EBAFHGCD后序遍歷的結(jié)果：

E

BHGFDCA52先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCAABCFHDEG下圖所示的二叉樹經(jīng)過三種遍歷得到的順序分別為？練習(xí)：根據(jù)先序遍歷序列，建立二叉樹531:對下列二叉樹（06年9月）

進行中序遍歷的結(jié)果是______。

A）ACBDFEG

B）ACBDFGE

C）ABDCGEF

D）FCADBEG樹型結(jié)構(gòu)方面的考題

22:對如下二叉樹（2006年4月）D進行后序遍歷的結(jié)果為A)ABCDEF

B)DBEAFCC)ABDECF

D)DEBFCAAD54⒌查找技術(shù)順序查找：（1）線性表為無序表；（2）表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。從線性表的第一個元素開始，依次將線性表中的元素與關(guān)鍵字進行比較，若相等，則查找成功；

二分查找：首先將關(guān)鍵字與線性表中間位置的結(jié)點比較，相等則查找成功；不相等則根據(jù)比較結(jié)果確定下一步查找應(yīng)在哪個子表中進行；重復(fù)上述過程，直至查找成功或子表長度為0。適用于順序存儲的有序表，對于長度為n的有序線性表，最壞情況只需比較log2n次。55折半查找算法舉例對給定數(shù)列（有序）{3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

第1次：{3，5，11，17，21，23，28，30，32，50}

K=30mid1=（1+10）/2=5

k>a(mid1)=a(5)=21

第2次：{23，28，30，32，50}mid2=（6+10）/2=8K=a(mid2)=a(8)=30lowhighmidlowhighmid56練習(xí)

假設(shè)待查有序（升序）順序表中數(shù)據(jù)元素的關(guān)鍵字序列為（8,18,27,42,47,50,56,68,95,120），用折半查找方法查找關(guān)鍵字值為27的數(shù)據(jù)元素.對于長度為n的有序線性表，最壞情況只需比較log2n次。

57⒍排序技術(shù)

排序指將一個無序序列整理成按關(guān)鍵字值遞增或遞減排列的有序序列。排序方法中其排序?qū)ο笠话闶琼樞虼鎯Φ木€性表。根據(jù)排序序列的規(guī)模以及數(shù)據(jù)處理的要求，可以采用不同的排序方法：交換類排序法：（1）冒泡排序法；（2）快速排序法。插入類排序法：（1）簡單插入排序法；（2）希爾排序法。選擇類排序法：（1）簡單選擇排序法；（2）堆排序法。58冒泡排序冒泡排序的方法：掃描整個線性表，逐次對相鄰的兩個元素進行比較，若為逆序，則交換；第一趟掃描的結(jié)果使最大(或最小)的元素排到表的最后(或最前)

；除最后(或最前)一個元素，對剩余的元素重復(fù)上述過程，將次大(或次小)的數(shù)排到表的倒數(shù)(或正數(shù))第二個位置；重復(fù)上述過程；對于長度為n的線性表，冒泡排序需要對表掃描n-1遍。59冒泡排序的方法設(shè)待排數(shù)據(jù)元素的關(guān)鍵字為(26,18,32,54,47,9,15)，第一趟冒泡排序后的序列狀態(tài)如圖所示：

2618325447915182632544791518263254479151826325447915182632475491518263247954151826324791554

最大數(shù)60初始第一趟第二趟第三趟第四趟第五趟序列排序后排序后排序后排序后排序后 26 18 1818 189 18 26 2626 915 32 32 329 15 18 54