計算機等級考試

公共基礎知識

計算機二級考試公共基礎知識大綱

數據結構與算法

程序設計基礎軟件工程基礎數據庫設計基礎

這四個方面在試卷中出現的情況是：選擇題10個（20分），填

空題5個（10分），總分值占到了試卷卷面分的30%,是一個不小

的比例。

第2頁

計算機二級考試公共基礎知識試卷分析

章節考試時間

數據結構程序設軟件工數據庫設計基礎程基礎計基礎與

算法

2007年4月2007年9月2008年4月2008年9月2009年3

月2009年9月2010年3月

10分12分10分10分10分10分10分

2分4分2分2分2分2分0分

10分8分8分8分8分8分10分

8分6分10分10分10分10分10分

第3頁

一、基本數據結構與算法

算法

1.算法的基本概念2.算法復雜2.算法復雜度的概念和意

義

數據結構

1.數據結構的概念2,線性表3.棧和隊列4.樹與二叉樹

5.查找技術6.排序技術

對于等級考試，這個部分的考核重點主要在對于等級考試，這

個部分的考核重點主要在算法和數據結構的基本概重點主要遍

歷、），還有排序和查找考試中也經常會涉及到二叉樹遍歷結點）,

還有排序和查找考試中也經常會涉及到。念、二叉樹（遍歷、結點）,

還有排序和查找考試中也經常會涉及到。

第4頁

1.算法的基本概念

算法的定義

算法是程序設計的核心

對解題方案準確而完整的描述稱為算法。對解題方案準確而完

整的描述稱為算法。

算法是在有限步驟內求解某一問題所使用的一組定義明確的規

則。通俗點說，定義明確的規則。通俗點說，就是計算機解題的過計

算的方法）在這個過程中，程（計算的方法）。在這個過程中，無論

是形成解題思路（推理實現的算法）還是編寫程序（思路（推理實現

的算法）還是編寫程序（操作實現的算都是在實施某種算法。法），

都是在實施某種算法。個數從大到小進行排序。例：n個數從大

到小進行排序。個數從大到小進行排序

常用的有冒泡排序、選擇排序等。有多種排序方法，常用的有

冒泡排序、選擇排序等。

第5頁

2.算法的基本特征

一個算法應該具有以下五個重要的特征：一個算法應該具有以

下五個重要的特征：

有窮性確定性輸入輸出可行性

一個算法必須保證執行有限步之后結束；算法的每一步驟必須

有確切的定義；

一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所

謂0個輸入是指算法本身定除了初始條件；一個算法有一個或多個

輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意

義的；

算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算

后即可完成

第6頁

3.算法的表示

一個算法的表示需要使用一些語言形式。一個算法的表示需要

使用一些語言形式。傳統的算法圖形法，如“流程圖”和N-S圖圖

形法，傳統的算法圖形法流程圖”圖目前常用的方法使用偽碼

描述算法。使用偽碼描述算法。目前常用的方法使用偽碼描述算

法

算法與計算機程序算法是一組邏輯步驟算法是一組邏輯步驟

程序——用計算機語言描述的算法程序用計算機語言描述的算法

問題：輸入園的半徑，計算園的面積INPUTrS=3.14*r*r

PTINTS

開始輸入R輸入RS=3.14*R*R

輸出S輸出S

結束第7頁

算法舉例：個數排序算法舉例：n個數排序

冒泡排序的方法：冒泡排序的方法：

1.掃描整個線性表，逐次對掃描整個線性表，掃描整個線性表

相鄰的兩個元素進行比較，相鄰的兩個元素進行比較，若為逆序，

則交換；若為逆序，則交換；第一趟掃描的結果使最大的元素排到

表的最后；2.除最后一個元素，對剩余除最后一個元素，除最后

一個元素的元素重復上述過程，的元素重復上述過程，將次大的

數排到表的倒數第二個位置；位置；3.重復上述過程；重復上述

過程；重復上述過程對于長度為n的線性表，對于長度為的線性

表，冒泡的線性表排序需要對表掃描n-1遍。排序需要對表掃描

遍

第8頁

4.算法的兩個基本要素：算法的兩個基本要素：

一是對數據對象的運算和操作；二是算法的控制結構。

基本運算和操作

算術運算關系運算邏輯運算數據傳輸

控制結構

順序選擇循環

算法基本設計方法：列舉法、歸納法、遞推、遞歸、減斗遞推

技術、回溯法第9頁

5.算法評價

評價一個算法優劣的主要標準是算法的執行效率和存儲需求：

評價一個算法優劣的主要標準是算法的執行效率和存儲需求：時間

復雜度：執行這個算法所需要的計算工作量時間復雜度：執行這個

算法所需要的計算工作量

一般可以用算法在執行過程中所需基本運算的執行次數來度量

計算工作量

空間復雜度：執行這個算法所需要的內存空間空間復雜度：執

行這個算法所需要的內存空間

算法在執行過程中臨時占用的存儲空間時間復雜度它大致等于

計算機執行一種簡單操作所需的平均時間時間復雜度它大致等于計

算機執行一種簡單操作所需的平均時間與算法它大致等于計算機執

行一種簡單操作所需的平均時間與算法中進行簡單操作的次數的乘

積簡單操作的次數的乘積。中進行簡單操作的次數的乘積。一個

算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用

一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所

占用的存儲空間、算法中的輸入輸出數據所占用的存儲空間和的存

儲空間、算法中的輸入輸出數據所占用的存儲空間和算法在運行過程

中臨時占用的存儲空間這三個部分臨時占用的存儲空間這三個部

分

第10頁

一、算法

對解題方案準確而完整的描述稱為算法。對解題方案準確而完

整的描述稱為算法。算法不等于程序，也不等計算機方法，程序的

編制不算法不等于程序，也不等計算機方法，可能優于算法的設計。

可能優于算法的設計。

算法評價：

時間復雜度：時間復雜度：執行這個算法所需要的計算工作量

空間復雜度：空間復雜度：執行這個算法所需要的內存空間

第11頁

算法習題：

（1）在計算機中，算法是指在計算機中，算法是指。。A.查

詢方法B.加工方法（c）C.解題方案的準確而完整的描述D.排

序方法（2）下列敘述中正確的是（07年4月）下列敘述中正確的

是年月A）算法的效率只與問題的規模有關，而與數據的存儲結構

無關算法的效率只與問題的規模有關，算法的效率只與問題的規模

有關B）算法的時間復雜度是指執行算法所需要的計算工作量算法

的時間復雜度是指執行算法所需要的計算工作量0數據的邏輯結構

與存儲結構是一一對應的數據的邏輯結構與存儲結構是一一對應的

（B）D）算法的時間復雜度與空間復雜度一定相關算法的時間復雜度

與空間復雜度一定相關（3）算法的有窮性是指（08年4月）算法的

有窮性是指年月A）算法程序的運行時間是有限的）（A）B）算

法程序所處理的數據量是有限的）C）算法程序的長度是有限的）

D）算法只能被有限的用戶使用）

第12頁

（4）算法的時間復雜度是指（2010年3月）年月A）算法的執

行時間算法的執行時間B）算法所處理的數據量算法所處理的數據

量C）算法程序中的語句或指令條數算法程序中的語句或指令條數

D）算法在執行過程中所需要的基本運算次數算法在執行過程中所需

要的基本運算次數（5）算法的空間復雜度是指（09年9月）年月

A）算法在執行過程中所需要的計算機存儲空間）B）算法所處理的

數據量）O算法程序中的語句或指令條數）D）算法在執行過程

中所需要的臨時工作單元數）（6）下列敘述中正確的是（06年9

月）年月

（D）

計算工作量

（A）

（D）

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

算法的空間復雜度大，B）一個算法的空間復雜度大，則其時間復雜

度必定小）一個算法的空間復雜度大，C）一個算法的時間復雜度

大，則其空間復雜度必定小）一個算法的時間復雜度大，D）上述

三種說法都不對）

第13頁

二、數據結構

程序=算法數據結構程序算法+數據結構算法

計算機在進行數據處理時，計算機在進行數據處理時，實際需

要處理的數據元素一般有很多，而這些大量的數據元素都需要存放

在計算機中，因此，大量很多，而這些大量的數據元素都需要存放

在計算機中，因此，數據元素在計算機中如何組織，以便提高數據

處理的效率，的數據元素在計算機中如何組織，以便提高數據處理

的效率，并且節省計算機的存儲空間，這是進行數據處理的關鍵問

題。節省計算機的存儲空間，這是進行數據處理的關鍵問題。

數據結構是指相互有關聯的數據元素的集合。數據結構是指相

互有關聯的數據元素的集合。

一般來說，人們不會同時處理特征完全不同且互相之間沒有任何

關系的各類數據元素，對于具有不同特征的數據元素總是分別進行

處理。

一般情況下，在具有相同特征的數據元素集合中，一般情況下,

在具有相同特征的數據元素集合中，各個數據元素之間存在有某種

關系（即聯系），）,這種關系反映了該集元素之間存在有某種關系

（即聯系），這種關系反映了該集合中的數據元素所固有的一種結

構。合中的數據元素所固有的一種結構。

第14頁

二.數據結構

數據結構是指相互有關聯的數據元素的集合。數據結構是指相

互有關聯的數據元素的集合。

數據結構是研究數據和數據之間關系的一門

學科，它包括三個方面。學科，它包括三個方面。（1）數據

集合中各數據元素之間所固有的邏）輯關系，即數據的邏輯結構；

輯關系，即數據的邏輯結構；（2）在對數據進行處理時，各數據元

素在計）在對數據進行處理時，算機中的存儲關系，即數據的存儲

結構；算機中的存儲關系，即數據的存儲結構；（3）對各種數據

結構進行的運算。）對各種數據結構進行的運算。

第15頁

1.

邏輯結構

數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。

數據的邏輯結構是指反映數據元素之間邏輯關系的數據結構。數據

的邏輯結構包含：數據的邏輯結構包含：（1）表示數據元素的信

息；）表示數據元素的信息；（2）表示各數據元素之間的前后件

關系。）表示各數據元素之間的前后件關系。

例:

1.一年四季的數據結構B=（D,R）D=｛春，夏，秋，冬｝春

R=｛（春，夏），（夏，秋），（秋，冬）｝春夏秋2.家庭成員的數據結

構B=（D,R）D=｛父親，兒子，女兒父親，父親兒子，女兒｝R=｛（父

親，兒子，（父親，女兒父親，父親，父親兒子）父親女兒）｝春

數據結構的圖形表示

夏父親秋冬

兒子

女兒第16頁

常見的邏輯結構有：線性結構、樹形結構和圖形結構。線性結

構、樹形結構和圖形結構。

圖形結線性結構樹形結構構

線性結構

結構的的的

樹形結構

結構的

圖形結構

結構

的線形結構。線形結構。圖形。的。

結構

第17頁

結構的樹形結構和圖形結構

2.存儲結構（物理結構）存儲結構（

計算機在實際進行數據處理時，計算機在實際進行數據處理時,

被處理的各數據元素總是被存放在計算機的存儲空間中，并且，算

機的存儲空間中，并且，各數據元素在計算機存儲空間中的位置與它

們的邏輯關系不一定是相同的，而且一般也不可能相同。它們的邏

輯關系不一定是相同的，而且一般也不可能相同。如：一年四季家

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

存儲結構指數據結構在計算機存儲空間中的具體實現。存儲結

構指數據結構在計算機存儲空間中的具體實現。

常見的存儲結構有：常見的存儲結構有：順序存儲結構鏈式

存儲結構索引存儲結構存儲結構

只抽象地反映數據元素之間的關系的結構，系的結構，而不管

其存儲方式的數據結構稱為邏輯結構。數據結構稱為邏輯結構。？

一種數據結構可以根據需要表示一種數據結構可以根據需要表示

成一種或多種存儲結構。成一種或多種存儲結構。

第18頁

通常，一個數據結構中的元素結點可能是動態變化的。通常，

一個數據結構中的元素結點可能是動態變化的。根據需要或在處理

過程中，據需要或在處理過程中，可以在一個數據結構中增加一個

新結插入運算），也可以刪除某個結點（刪除運算），），也可以刪

除某個結點），除此之點（插入運算），也可以刪除某個結點（刪除

運算），除此之對數據結構的運算還有查找、分類、合并、分解、夕卜,

對數據結構的運算還有查找、分類、合并、分解、復制和修改。修

改。在對數據結構的處理過程中，在對數據結構的處理過程中，不

僅數據結構中結點的個數在動態變化，而且，在動態變化，而且，

各數據元素之間的關系也有可能在動態地變化。變化。如：無序表

變有序表

3.數據的運算檢索插入刪除更新排序

數據結構是研究數據和數據之間關系的一門學科，關系的一門

學科，研究以下三方面內容：內容：

數據的邏輯結構數據的存儲結構數據的運算

第19頁

常見的數據結構

1.線性表線性表2.棧和隊列棧和隊列3.樹樹

上一頁下一頁停止放映

第20|92頁20|92頁|92

1.線性表(LinearList)線性表(List)

線性表是由n(線性表是由(n》0)個數據元素

al,a2,-??,ai,?，?,an組成的一個有限序列。，,組成的

一個有限序列。

簡單的線性表

春夏秋冬

復雜的線性表

記錄1記錄記錄2記錄記錄3記錄記錄4記錄

第21頁02011001

張三男李四女

02011003

線性表的存儲結構

線性表的存儲結構有兩種：線性表的存儲結構有兩種：順序存

儲結構鏈式存儲結構

存儲地址

20002004

ala2…ai…an???

占4個字節個字節

線性表的順序存儲結構

順序存儲結構把邏輯上相鄰的順序存儲結構把邏輯上相鄰的

邏輯上相鄰數據元素存儲在物理上相鄰物理上相鄰的存數據元素

存儲在物理上相鄰的存儲單元里，順序存儲結構只存儲儲單元里，

順序存儲結構只存儲結點的值，不存儲結點間的關系，結點的值，

不存儲結點間的關系，結點間的關系由存儲單元的鄰接關系來體

現。關系來體現。

2000+4*(1-1)

2000+4*(n-1)

Loa(Loa(ai)=Loa(al)+L*(i~l)=Loa(+L*(

第i個數的地址第一個數的地址L為該類型數所占的字節第

22頁

順序表的插入和刪除運算

線性表的順序存儲結構稱為順序表。線性表的順序存儲結構稱

為順序表。順序表的插入運算順序表的刪除運算在線性表順序存

儲情況下，在線性表順序存儲情況下，要插入或刪除一個元素，都

會由于數據元素的移動而消耗大量的處理時間，都會由于數據元素

的移動而消耗大量的處理時間，所以這種存儲方式對于小線性表或

其中數據元素不經常變動的線性表是合適的。常變動的線性表是合

適的。

第23頁

線性表的鏈式存儲結構

線性表的鏈式存儲結構稱為線性鏈表。線性表的鏈式存儲結構

稱為線性鏈表。鏈式存儲結構不要求邏輯上相鄰的數據元素物理位

置也相鄰，而且各數據元素的存儲順序也是任意的。置也相鄰，而

且各數據元素的存儲順序也是任意的。各數據元素的先后關系是由

各結點的指針域指示。各數據元素的先后關系是由各結點的指針域

指示。鏈式存儲結構的每一個存儲結點不僅存儲結點的值，鏈式存

儲結構的每一個存儲結點不僅存儲結點的值，而且存儲結點之間的

關系：而且存儲結點之間的關系:

數據域

指針域

第24頁

線性鏈表的物理狀態線性鏈表的物理狀態

應用舉例——應用舉例——線性鏈表的存儲結構——線性鏈

表的存儲結構

設線性表為(al,a2,a3,a4,a5)

1al

線性表的順線性表的順序存儲結構序存儲結構

HEAD

123456789103

a2ala4

9110

2a23a34a45a567

31

注意：123此類編號不代表所在的地址單元的地址編碼

a3a5

10

50

9

5

HEAD

al

a2

a3

a4

a5

第25頁

線性鏈表的邏輯狀態

線性鏈表的插入和刪除運算

單鏈表的插入運算單鏈表的刪除運算采用鏈式存儲結構，存儲

空間開銷較大，采用鏈式存儲結構，存儲空間開銷較大，但是進行

插入和刪除運算不會造成大量元素的移動。入和刪除運算不會造成

大量元素的移動。循環鏈表是加一種形式的鏈式存儲結構。循環鏈

表是加一種形式的鏈式存儲結構。它的特點是表中最后一個結點的

指針域指向頭結點。表中最后一個結點的指針域指向頭結點。

3HEAD19510

al

a2

a3

a4

a5

第26頁

雙向鏈表的存儲結構

提問：單向鏈表的缺點是什么？提示：如何尋找結點的直接前

趨。雙向鏈表可以克服單鏈表的單向性的缺點。在雙向鏈表的結點

中有兩個指針域，在雙向鏈表的結點中有兩個指針域，其一指向直

接后繼，另一指向直接前趨。直接后繼，另一指向直接前趨。

3HEAD1510

al

a2

a3

a4

雙向循環鏈表

第27頁

線性表：{al,a2,a3,a4,a5},,,,

注意：注意：數據元素在計算機存儲空間中的位置關系與它

們的邏輯關系不一定是相同的。不一定是相同的。一個邏輯數據

結構可以有多種存儲結構，可以有多種存儲結構，且不同的存儲

結構影響數據處理的效率。

線性表的存儲結構有兩種

順序存儲結構

1al2a23a34a45a567

HEAD3

鏈式存儲結構

12345678910a3a550a410al1a29

第28頁

2.棧和隊列

棧和隊列都是特殊的線性表。棧和隊列都是特殊的線性表。棧

(Stack)及其基本運算Stack)隊列(Queue)及其基本運算隊列

(Queue)循環隊列及其基本運算

第29頁

棧(Stack)是一種特殊的線性表。其特點是插入和刪Stack)

是一種特殊的線性表線性表。除運算都只能在線性表的一端進行。

除運算都只能在線性表的一端進行。棧是按照“先進后出”后進先

出”棧是按照“先進后出”或“后進先出”的原則組織數據的線

性表。據的線性表。棧的物理存儲結構可以用順序結構，棧的物

理存儲結構可以用順序結構，也可以用鏈表結構。下面討論順序存

儲結構中棧元素的插入和刪除運算。下面討論順序存儲結構中棧元

素的插入和刪除運算。順序棧的進棧和出棧運算

棧的基本運算有三種：入棧、棧的基本運算有三種：入棧、退

棧和讀棧頂元素

在順序棧中插入和刪除運算不需要移動表中其他數據元素。移

動表中其他數據元素。

第30頁

隊列(Queue)是一種特殊的線性表。其特點是所有的隊列

(Queue)是一種特殊的線性表。插入都在表的一端進行所有的刪

除運算都在表的另進行，刪除運算都在表的插入都在表的一端進

行，所有的刪除運算都在表的另一端進行進行。一端進行。隊列

是按照“先進先出”后進后出”隊列是按照“先進先出”或“后

進后出”的原則組織數據的線性表。數據的線性表。隊列的物理

存儲結構可以用順序結構，也可以用鏈式隊列的物理存儲結構可以

用順序結構，結構。結構。順序隊列的運算

棧有三種操作：入棧'出棧\棧有三種操作：入棧'出棧\

讀棧頂元素隊列有三種操作：入隊'出隊\隊列有三種操作：入隊

'出隊'讀隊首元素例：有入棧元素序列：ABCD,求可能的出棧序

列.有入棧元素序列：，求可能的出棧序列.如是隊列又是什么

情況呢？如是隊列又是什么情況呢？

第31頁

循環隊列把隊列的存儲空間在邏輯上看作一個環，把隊列的存

儲空間在邏輯上看作一個環，當R指向存指向存儲空間的末端后，

就把它重新置于始端。儲空間的末端后，就把它重新置于始端。循

環隊列的運算

隊列中進行插入的一端稱做隊尾(rear),進行刪除的一端進行

刪除的一端隊列中進行插入的一端稱做隊尾稱做隊首(front)。稱

做隊首。

習題：數據結構分為邏輯結構和存儲結構，習題：數據結構分

為邏輯結構和存儲結構，循環隊列屬于【結構。(。(2005年9月)

列屬于【】結構。(年月答案：存儲結構。答案：存儲結構。

第32頁

常見數據結構的邏輯結構

線性表棧隊列

也是一種操作受限的特殊的線性表線性結構是特殊的線性表

樹型結構）樹（樹型結構）

是一種重要的非線形數據結構

第33頁

數據存儲結構方面的考題

1：數據的存儲結構是指（2005年4月）：年月A）存儲在

外存中的數據0數據在計算機中的順序存儲方式2.下列敘述中

正確的是（2009年3月）年月A）棧是“先進先出”的線性表）

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

進后出"C）循環隊列是非線性結構）D）有序線性表既可以采用

順序存儲結構，也可以采用鏈式存儲結構）有序線性表既可以采用

順序存儲結構，B）數據所占的存儲空間量D）數據的邏輯結構在計

算機中的表示

答案：Do答案：。

答案：Do答案：。

3.數據結構分為線性結構和非線性結構，帶鏈的隊列屬于數據

結構分為線性結構和非線性結構，帶鏈的隊列屬于[4,下列數據結

構中，屬于非線性結構的是下列數據結構中，A）循環隊列）C）二

叉樹B）帶鏈隊列D）帶鏈棧）

]oo答案：線性結構。答案：線性結構。答案：答案：c第

34頁

5o下列敘述中正確的是（）。（2008年9月）。下列敘述中

正確的是（年月

答案：。答案：Ao

A）順序存儲結構的存儲一定是連續的，鏈式存儲結構的存儲空）

順序存儲結構的存儲一定是連續的，間不一定是連續的B）順序存

儲結構只針對線性結構，鏈式存儲結構只針對非線性）順序存儲結

構只針對線性結構，結構O順序存儲結構能存儲有序表，鏈式存

儲結構不能存儲有序表）順序存儲結構能存儲有序表，D）鏈式存

儲結構比順序存儲結構節省存儲空間）

答案：。6o下列關于棧的敘述正確的是（2008年4月）年

月棧按“先進先出"B）棧按先進后出"棧按"A）棧按“先進先

出”組織數據B）棧按“先進后出”組織數據C）只能在棧底插入數

據D）不能刪除數據答案：Bo答案：。

7.一個隊列的初始狀態為空。現將元素A,B,C,D,E,F,5,

4,3,一個隊列的初始狀態為空。現將元素，，，，，，，，，

2,1依次入隊，然后再依次退隊，則元素退隊的順序為【1】。（2010,

依次入隊，然后再依次退隊，】。（依次入隊年3月）月答

案：，，，，，，，，，，答案：A,B,C,D,E,F,5,

4,3,2,1第35頁

8o假設用一個長度為50的數組（數組元索的下標從。假設用

一個長度為的數組數組元索的下標從0的數組（到49）作為棧的

存儲空間，棧底指針）作為棧的存儲空間，棧底指針bottom指間棧

底指間棧底元素，棧頂指針top指向棧頂元素，如果bottom=49,

元素，棧頂指針指向棧頂元素，如果，指向棧頂元素top=30（數

組下標），則棧中具有【1個元素。），則棧中具有個元素。（數

組下標），則棧中具有【

（2009年3月）年月

答案：答案：19

9.設某循環隊列的容量為，如果頭指針設某循環隊列的容量

為50,如果頭指針front=45（指向指向隊頭元素的前一位置），尾

指針rear=10（指向隊尾元素，指向隊尾元素），隊頭元素的前一

位置，尾指針指向隊尾元素則該循環隊列中共有【2】個元素。

（2010年3月）】個元素。年月

答案：答案：15第36頁

線性結構與非線性結構

線性表、線性表、棧和隊列都是線性結構一個數據結構不是線

性結構，則稱其為非線性結一個數據結構不是線性結構，則稱其為

非線性結構。

一個非空的數據結構若滿足下面的兩個條件，一個非空的數據

結構若滿足下面的兩個條件，則這種數據結構即為線性結構線性結

構。構即為線性結構。有且僅有一個根結點；①有且僅有一個根

結點；除第一個結點外，每一個結點最多有一個直接前驅結點；②

除第一個結點外，每一個結點最多有一個直接前驅結點；除最后一

個結點外，每一個結點最多有一個直接后繼結點。③除最后一個結

點外，每一個結點最多有一個直接后繼結點。

3HEAD19510

al

a2

a3

a4

a5

第37頁

線性鏈表的邏輯狀態

3.樹與二叉樹

樹型結構是一種重要的非線性結構。樹型結構是一種重要的非

線性結構。樹的概念二叉樹的概念二叉樹的存儲二叉樹的遍歷

第38頁

樹的概念

樹的定義：個結點的有限集。（n>=0）個結點的有限集。（樹

的定義：n個結點的有限集。（）根：onlyone若n=0,則稱為空

樹；，則稱為空樹；否則，否則，當n>l時，其余結時點被分

成m（點被分成（m>0）個互不）相交的子集T1,,,相交的

子集，T2,……，Tm,每個子集又是一棵樹。，每個子集又是一

棵樹。由此可以看出，由此可以看出，樹的定義是遞歸的。遞歸

的。Question：如何辨別根？：如何辨別根？

第39頁EBFJACGKDHMI

只有一個結點的樹

A

樹型結構的常用術語

結點的度一個結點的子樹的個數；：結點A、的度數的度

數？個數；Q：結點、G的度數？樹的度樹中所有結點度的最大

值；：右圖中樹的度？大值；Q：右圖中樹的度？終端結點度為的

結點；度為0的結點的結點；Q：圖中葉子結點有兒個？7：圖中

葉子結點有兒個？非終端結點度不為的結點；度不為0的結點

的結點；Q：圖中非終端結點有兒個？5：圖中非終端結點有兒個？

孩子結點、雙親結點、兄弟結點、結點的子孫、孩子結點、雙

親結點、兄弟結點、結點的子孫、結點的祖先

第40頁BEFJACGKDHMI

樹型結構的常用術語

結點的層次樹中根結點的層①次為1,根結點子樹的根為第2

層次為，根結點子樹的根為第層，②以此類推；以此類推；Q：

圖中結點F的層次？：圖中結點的層次的層次？

③

EABFJCGKDHMI

樹的深度樹中所有結點層次的最大值；：圖中樹的深度？的

最大值；Q：圖中樹的深度？有序樹、無序樹如果樹中每有序樹、

棵子樹從左向右的排列擁有一定的順序，不得互換，的順序，不得

互換，則稱為有序否則稱為無序樹。樹，否則稱為無序樹。

④

第41頁

二叉樹的概念

定義：二叉樹是一種有序的樹形結構。定義：二叉樹是一種有

序的樹形結構。它與一般樹形結構的區別是：樹形結構的區別是：

每個結點最多有兩棵子樹；每個結點最多有兩棵子樹；子樹有

左右之分，次序不能任意顛倒。子樹有左右之分，次序不能任意顛

倒。

二叉樹的5種基本形態二叉樹的種基本形態

第42頁

二叉樹的性質

【性質1】在二叉樹的第層上最多有iT個結點（iNl）在

二叉樹的第i層上最多有個結點（》）層上最多有2

ABEFGH

第43頁

CD

【性質2］深度為的二叉樹最多有2h-1個結點（h21）深

度為h的二叉樹最多有個結點（）深度為的二叉樹最多有個結

點滿二叉樹：如果一個深度為的二叉樹擁有滿二叉樹：如果一個

深度為h的二叉樹擁有h-1個結的二叉樹擁有2個結點，則將它

稱為滿二叉樹。則將它稱為滿二叉樹。滿二叉樹完全二叉樹：有

一棵深度為，具有個結點的二叉樹，完全二叉樹：有一棵深度為

h,具有n個結點的二叉樹，個結點的二叉樹若將它與一棵同深度

的滿二叉樹中的所有結點按從上到下，從左到右的順序分別進行編

號，到下，從左到右的順序分別進行編號，且該二叉樹中的每個結

點分別與滿二叉樹中編號為1?n的結點位置的結點位置的每個結

點分別與滿二叉樹中編號為一一對應，則稱這棵二叉樹為完全二叉

樹。一一對應，則稱這棵二叉樹為完全二叉樹。完全二叉樹

第44頁

滿二叉樹滿二叉樹也是完滿全二二叉樹完全二

叉樹

第45頁

完全二叉樹是叉樹

非完全二叉樹

深度為4的深度為的完全二叉樹

第46頁

【性質3】二叉樹上葉子結點數比度為的結點數多二叉樹上葉

子結點數比度為2的結點數多二叉樹上葉子結點數比度為的結點

數多1

ABEFGHCD葉子結點度為2的結點

第47頁

【性質4】具有個結點的完全二叉樹的深度為？log2(n+1)?具

有n個結點的完全二叉樹的深度為具有其中，其中，？log2n?的

結果是不大于？的結果是不大于log2n的最大整數的最大整數

深度為4的深度為的滿二叉樹深度為4的深度為的完全

二叉樹

log2(8+1)?=In9/In2=4?log2(15+1)?=Inl6/In2=4?深

度為3的完全二叉樹具有4?深度為的完全二叉樹具有?7深

度為4的完全二叉樹具有8?深度為的完全二叉樹具有?15深

度為5的完全二叉樹具有15?深度為的完全二叉樹具有?31

深度為6的完全二叉樹深度為的完全二叉樹深度為7的完全

二叉樹深度為的完全二叉樹深度為8的完全二叉樹深度為的完

全二叉樹深度為9的完全二叉樹深度為的完全二叉樹深度為10

的完全二叉樹深度為的完全二叉樹深度為11的完全二叉樹深度

為的完全二叉樹

具有32?具有?63具有64?具有?127具有128?255具

有?具有256?511具有?具有512?1023具有?具有

1024~2047具有?第48頁

樹型結構方面的考題

1：在深度為7的滿二叉樹中，葉子結點的個數為(2006年4月)

在深度為7的滿二叉樹中，葉子結點的個數為(2006年A)32A)32

B)31B)31C)64C)64D)63D)63

1答案：Co答案：。答案

2：在深度為7的滿二叉樹中，度為2的結點個數為【在深度為

7的滿二叉樹中，度為2的結點個數為【

07年】。(07年4月)

2答案：63o答案：。答案

一棵二叉樹中共有70個葉子結點與80個度為1的結點，70個

葉子結點與80個度為3：一棵二叉樹中共有70個葉子結點與80個

度為1的結點，則該二叉樹中的總07年結點數為（07年9月）A）

219B）221C）229

3答案：Ao答案：。答案

D）231個葉子結點。】個葉子結點。】個。（2005

4答案：19。答案：。答案

某二叉樹中度為2的結點有1818個4：某二叉樹中度為2的

結點有18個，則該二叉樹中有【（2005年4月）2005年年9月）

一棵二叉樹第六層（根結點為第一層）的結點數最多為【5：一

棵二叉樹第六層（根結點為第一層）的結點數最多為【

5答案：32。答案：。答案第49頁

二叉樹的存儲

在計算機中，二叉樹通常采用鏈式存儲結構。在計算機中，二

叉樹通常采用鏈式存儲結構。

LlinkinfoRlink

t

二叉樹的存儲結點的結構

ABDG

A

ACBF

AA

C

A

E

DG

A

E

A

A

F

A

第50頁

二叉樹的遍歷

遍歷指不重復地訪問二叉樹中的所有結點。遍歷指不重復地訪

問二叉樹中的所有結點。不重復地訪問二叉樹中的所有結點二叉樹

的遍歷的次序與樹型結構上的大多數運算有聯系。數運算有聯系。

遍歷的方式有三種序遍歷（（1）先（前）序遍歷（DLR）））（2）

中序遍歷（LDR））中序遍歷（）（3）后序遍歷（LRD））后序

遍歷（）

H

第51頁

ACFGD

BE

二叉樹的遍歷

遍歷指不重復地訪問二叉樹中的所有結點。遍歷指不重復地訪

問二叉樹中的所有結點。不重復地訪問二叉樹中的所有結點序遍歷

((1)先(前)序遍歷(DLR)))若二叉樹為空，則結束遍歷

操作；若二叉樹為空，則結束遍歷操作；否則訪問根結點；訪問

根結點；先序遍歷左子樹；先序遍歷左子樹；遍歷左子樹先序遍

歷右子樹。先序遍歷右子樹。遍歷右子樹

GEBFACD

先序遍歷的結果：先序遍歷的結果：ABECFGHD

H

第52頁

(2)中序遍歷(LDR))中序遍歷()若二叉樹為空，則結

束遍歷操作；若二叉樹為空，則結束遍歷操作；否則中序遍歷左子

樹；中序遍歷左子樹；訪問根結點；訪問根結點；中序遍歷右子

樹。中序遍歷右子樹。中序遍歷的結果：中序遍歷的結果：EBA

FHGCD(3)后序遍歷(LRD))后序遍歷()若二叉樹為空,

則結束遍歷操作；若二叉樹為空，則結束遍歷操作；否則后序遍歷

左子樹；后序遍歷左子樹；后序遍歷右子樹；后序遍歷右子樹；訪

問根結點。訪問根結點。后序遍歷的結果：后序遍歷的結果：EB

HGFDCA

第53頁

ABEFGHCD

練習：練習：

下圖所示的二叉樹經過三種遍歷得到的順序分別為？下圖所示

的二叉樹經過三種遍歷得到的順序分別為？

ABDGEHCF

先序序列：先序序列：ABDGCEFH中序序列：中序序列：

DGBAECHF后序序列：后序序列：GDBEHFCA

根據先序遍歷序列，根據先序遍歷序列，建立二叉樹

第54頁

樹型結構方面的考題2

1:設二叉樹如下：設二叉樹如下：設二叉樹如下（2010年3

月）年月對該二叉樹進行后序遍歷的結果為[3]]

EDBGHFCA

ABCFEGH

D

2:對如下二叉樹（2006年4月）對如下二叉樹（年月進行

后序遍歷的結果為A）ABCDEFB）DBEAFCDC）ABDECFD）DEBFCA

第55頁

5.查找技術

查找是數據處理的重要內容。查找是數據處理的重要內容。查

找指在一個給定的數據結構中查找指定的元素，查找指在一個給定

的數據結構中查找指定的元素，該元素也稱關鍵字。該元素也稱關

鍵字。若找到了滿足條件的結點，稱查找成功；若找到了滿足條件

的結點，稱查找成功；否則稱查找失敗。找失敗。衡量一個查找

算法的主要標準是查找過程中對關鍵字進行的平均比較次數。字進

行的平均比較次數。通常根據不同的數據結構，采用不同的查找方

法：通常根據不同的數據結構，采用不同的查找方法：順序查找二

分查找

第56頁

順序查找

線性表中最簡單的查找方法。線性表中最簡單的查找方法。方

法：從線性表的第一個元素開始，方法：從線性表的第一個元素開

始，依次將線性表中的元素與關鍵字進行比較，若相等，則查找成

功；中的元素與關鍵字進行比較，若相等，則查找成功；若將所有

元素都與關鍵字進行了比較但不相等，則若將所有元素都與關鍵字

進行了比較但不相等，查找失敗。查找失敗。順序查找法的適用

場合：順序查找法的適用場合：對線性表中元素的排列次序沒有要

求；對線性表中元素的排列次序沒有要求；對線性表的存儲結構沒

有要求，對線性表的存儲結構沒有要求，鏈式結構和順序結構均可。

序結構均可。

第57頁

二分查找（折半查找）

是一種效率較高的查找方法，但是只適合順序存儲是一種效率

較高的查找方法，但是只適合順序存儲的有序表。的有序表。二

分查找的方法：二分查找的方法：首先將關鍵字與線性表中間位置

的結點比較，相等則查找成功；不相等則根據比較的結點比較，相

等則查找成功；結果確定下一步查找應在哪個子表中進行；結果確

定下一步查找應在哪個子表中進行；重復上述過程，直至查找成功

或子表長度為Oo述過程，直至查找成功或子表長度為。二分查

找法的適用場合：二分查找法的適用場合：線性表中的元素按關鍵

字值遞增或遞減的次序排歹U；線性表采用順序存儲結構。線性表

采用順序存儲結構。

第58頁

折半查找算法舉例

對給定數列(有序)3,11,17,21,23,28,對給定數列(有

序){3,5,11,17,21,23,28,30,32,50},按折半查找算法,

查找關鍵字值為3030,32,50),按折半查找算法，查找關鍵字值

為30的數據元素。的數據元素。

ala2a3a4a5a6a7a8a9alO3,11,17,21,23,28,

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

midl=(1+10)midl=(1+10)/2=5

low

mid

high

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

23,28,30,32,第2次：{23,28,30,32,50

low

上一頁下一頁停止放映

}

high

mid

mid2=(6+10)/2=86+10)

K=a(mid2)=a(8)=30

第59|92頁59|92頁|92

練習

假設待查有序(升序)順序表中數據元素的關鍵字序列為

(8,18,27,42,47,50,56,68,95,120),用折半查找方法查找關鍵字

值為27的數據元素.

對于長度為n的有序線性表，最壞情況只需比較log2n次對于

長度為n的有序線性表，最壞情況只需比較log2n次。log2n

第60頁

6.排序技術

排序指將一個無序序列整理成按關鍵字值遞增或遞減排列的有

序排序指將一個無序序列整理成按關鍵字值遞增或遞減排列的有序

序列。序列。順序存儲的線性表排序方法中其排序對象一般是順

序存儲的線性表。排序方法中其排序對象一般是順序存儲的線性表。

根據排序序列的規模以及數據處理的要求，根據排序序列的規模以

及數據處理的要求，可以采用不同的排序方法：

交換類排序法

冒泡排序快速排序

插入類排序法

簡單插入排序希爾排序

選擇類排序法

簡單選擇排序堆排序

第61頁

冒泡排序

冒泡排序的方法：冒泡排序的方法：掃描整個線性表，掃描

整個線性表，逐次對相鄰的兩個元素進行比若為逆序，則交換；較,

若為逆序，則交換；第一趟掃描的結果使最或最小）的元素排到表的

最后或最前）大（或最小的元素排到表的最后或最前；或最小

的元素排到表的最后（或最前除最后（或最前）一個元素除最后（或

最前）一個元素，對剩余的元素重復上或最前一個元素，述過程，

將次大（或次小的數排到表的倒數（或正或次小）的數排到表的倒數

述過程，將次大或次小的數排到表的倒數或正第二個位置；數）

第二個位置；第二個位置重復上述過程；重復上述過程；對于長

度為n的線性表，對于長度為的線性表，冒泡排序需要對表掃描的

線性表n-1遍。遍

第62頁

冒泡排序的方法

設待排數據元素的關鍵字為（，，，設待排數據元素的關鍵

字為(18,20,15,32,4,25),第一趟冒泡排序后的序列狀),

第一趟，，)，第一趟冒泡排序后的序列狀態如圖所示：

181818181818

上一頁下一頁停止放映

2015324201532415203241520324152043215

20425

252525252532最大數

第63|92頁63|92頁|92

第二趟冒泡排序

Q：第二趟冒泡排序后的結果是什么樣的？達到：第二趟冒泡排

序后的結果是什么樣的？

了最終的排序目標嗎？了最終的排序目標嗎？一共需要多少次

能夠最后成為有序序列？后成為有序序列？Q：你覺得冒泡排序的

效率如何？如果是你，你：你覺得冒泡排序的效率如何？如果是你,

會用什么方法來排序？會用什么方法來排序？冒泡排序比較簡單，

當初始序列基本有序時，冒泡排序比較簡單，當初始序列基本有序

時，冒泡排序有較高的效率，反之效率較低。冒泡排序有較高的效

率，反之效率較低。冒泡排序終止條件：冒泡排序終止條件

本趟排序未發生交換，本趟排序未發生交換，終止排序算法

上一頁下一頁停止放映

第64|92頁64|92頁|92

設待排數據元素的關鍵字為(26,18,32,54,47,9,15)

初始序列第一趟排序后第二趟排序后第三趟排序后第

四趟排序后第五趟排序后

2618325447915

上一頁下一頁停止放映

1826324791554

182691532

1891526

91518

冒泡排序法，需要比較的次數為n(nT)/2；冒泡排序法，需要

比較的次數為n(n-1)/2；n(n

第65192頁65192頁|92

選擇排序

選擇排序的方法：選擇排序的方法：掃描整個線性表，從中找

出最小的元素，掃描整個線性表，從中找出最小的元素，與第一個

元素交換；一個元素交換；除第一個元素，對剩下的子表采用相同

的方法除第一個元素，找出次小的數，與第二個數交換；找出次

小的數，與第二個數交換；重復上述過程；重復上述過程；對于

長度為n的線性表，對于長度為的線性表，選擇排序需要對表掃的

線性表描n-1遍。遍

簡單選擇排序法，最壞情況需要n(n1)/2次比較n(n次比較；

簡單選擇排序法，最壞情況需要n(n-1)/2次比較;

第66頁

例：設待排數據元素的關鍵字為（15,14,22,30,設待排數

據元素的關鍵字為（，，，，37,11）,每一趟排序后的序列狀

態如圖所示：），每一趟排序后的序列狀態如圖所示，），每一趟

排序后的序列狀態如圖所示：

初態：初態：

[15,14,22,30,37,15,11],,,,,,

第一趟：第一趟：[11][14,22,30,37,15,15],,,,,

第二趟：第二趟：[11,14][22,30,37,15,15],,,,,

第三趟：[11,14,[30,37,22,第三趟：[11,14,15][30,

37,22,15]第四趟：[11,14,15,15][37,22,30]第四

趟：，，，