1、全國計算機等級考試二級公共基礎(chǔ)知識,考試形式,1、公共基本知識部份只考選擇題，沒有操作題。 2、公共基本知識占10分，共10道題，每題1分。,注意事項,公共基礎(chǔ)知識部份的內(nèi)容是屬于計算機專業(yè)本科生的專業(yè)課，知識點特別散，而且有一定的難度。所以考生在學(xué)習(xí)的過程中，一定要克服畏難情緒，跟上老師的節(jié)奏。老師讓記的，要記住。沒做要求的，要學(xué)會放棄。 放棄該放棄的，選擇輕裝上陣,一、 數(shù)據(jù)結(jié)構(gòu)與算法,1. 算法的基本概念；算法復(fù)雜度的概念和意義（時間復(fù)雜度與空間復(fù)雜度）。 2. 數(shù)據(jù)結(jié)構(gòu)的定義；數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)的圖形表示；線性結(jié)構(gòu)與非線性結(jié)構(gòu)的概念。 3. 線性表的定義；線性表的順序存

2、儲結(jié)構(gòu)及其插入與刪除運算。 4. 棧和隊列的定義；棧和隊列的順序存儲結(jié)構(gòu)及其基本運算。 5. 線性單鏈表、雙向鏈表與循環(huán)鏈表的結(jié)構(gòu)及其基本運算。 6. 樹的基本概念；二叉樹的定義及其存儲結(jié)構(gòu)；二叉樹的前序、中序和后序遍歷。 7. 順序查找與二分法查找算法；基本排序算法（交換類排序，插入類排序，選擇類排序）。,1.1 算法,1.1.1 算法(algorithm)基本概念,它是指令的有限序列，其中每一條指令表示一個或多個操作。,對解題方案準(zhǔn)確而完整的描述稱為算法。,計算機解題的過程實際上是在實施某種算法，這種算法稱為計算機算法。,算法的基本特征: (1)有窮性 (2)確定性 (3)可行性 (4)擁

3、有足夠的情報,（有零個或多個輸入，有一個或多個輸出） 一個算法有零個或多個輸入，以刻畫運算對象的初始情況，所謂零個輸入是指算法本身定出了初始條件； 一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無意義的；,偽代碼: S1:輸入圓的半徑R; S2:求面積 R2; S3:輸出面積;,例1:已知圓的半徑,求圓的面積.,描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、偽代碼等。,傳統(tǒng)流程圖,第8頁,算法與計算機程序 算法是一組邏輯步驟 程序用計算機語言描述的算法,算法不等于程序，也不等于計算方法，程序的編制不可能優(yōu)于算法的設(shè)計。,算法是程序設(shè)計的核心,算法: S1:輸入

4、圓的半徑R; S2:求面積R2; S3:輸出面積;,例題:已知圓的半徑,求圓的面積.,程序,#include #define PI 3.14159 int main() float r, s; do printf(Please input r:); scanf(%f, ,1.1.2 算法的基本要素 1、對數(shù)據(jù)對象的運算和操作 算術(shù)運算 邏輯運算 關(guān)系運算 數(shù)據(jù)傳輸 2、算法的控制結(jié)構(gòu) 算法中各操作之間的執(zhí)行順序 一個算法一般可以用順序、選擇、循環(huán)3種基本結(jié)構(gòu)組合而成。,算術(shù)運算 邏輯運算 關(guān)系運算 數(shù)據(jù)傳輸,順序、選擇、循環(huán)3種基本結(jié)構(gòu),#include #define PI 3.14159

5、int main() float R, S; do printf(Please input R:); scanf(%f, ,1.1.3 算法設(shè)計基本方法 列舉法 歸納法 遞推 遞歸（以簡潔的形式設(shè)計和描述算法） 減半遞推技術(shù) 回溯法,1.2 算法復(fù)雜度,1.2.1 時間復(fù)雜度 是指執(zhí)行算法所需要的計算工作量。 通常有事后統(tǒng)計法和事前分析估算法。 算法的工作量用算法所執(zhí)行的基本運算次數(shù)來度量. 算法所執(zhí)行的基本運算次數(shù)與問題的規(guī)模n有關(guān)（即算法所執(zhí)行的基本次數(shù)是問題規(guī)模的函數(shù)）.,執(zhí)行算法所需要的計算工作量和f(n)同步增長，記為:,算法的工作量=f(n),時間復(fù)雜度=O(f(n),而對于一個固

6、定的規(guī)模，算法所執(zhí)行的基本次數(shù)還與特定的輸入有關(guān)。,例子4：for ( i=2;i=n;+i) for (j=2;j=i-1;+j) +x ;,基本運算： 基本運算的執(zhí)行次數(shù)：,X增1,i=2 0 i=3 1 i=4 2 i=n n-2,1+2+3+(n-2),= (n-1)(n-2)/2,O（ ）,例子2：+x;,O（ 1 ）,例子3： for (i=1;i=n;+i) +x;,O（ n ）,時間復(fù)雜度：,O(n*n-3n+2)/2),基本運算： 基本運算的執(zhí)行次數(shù)： 時間復(fù)雜度：,1,X增1,基本運算： 基本運算的執(zhí)行次數(shù)： 時間復(fù)雜度：,X增1,n,1.2.2 算法的空間復(fù)雜度 一般是指

7、執(zhí)行這個算法所需要的內(nèi)存空間 一個算法所占用的內(nèi)存空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法在執(zhí)行過程中所需要的額外空間這3部分。,算法的時間復(fù)雜度是指 A) 執(zhí)行算法程序所需要的時間 B) 算法程序的長度 C) 算法執(zhí)行過程中所需要的基本運算次數(shù) D) 算法程序中的指令條數(shù) 算法的基本特征是可行性、確定性、 【1】 和擁有足夠的情報。 算法的空間復(fù)雜度是指 A) 算法程序的長度 B) 算法程序中的指令條數(shù) C) 算法程序所占的存儲空間 D) 執(zhí)行過程中所需要的存儲空間 在計算機中，算法是指 A) 加工方法B) 解題方案的準(zhǔn)確而完整的描述 C) 排序方法D) 查詢方法,例

8、題講解,有窮性,算法分析的目的是 A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) 分析算法的效率以求改進(jìn) 算法的工作量大小和實現(xiàn)算法所需的存儲單元多少分別稱為算法的 【1】 。,時間復(fù)雜度和空間復(fù)雜度,1.2 數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的圖形表示 線性結(jié)構(gòu)與非線性結(jié)構(gòu),能輸入到計算機中 并能被計算機程序處理的 符號的集合。,整數(shù)(1,2)、實數(shù)(1.1,1.2) 字符串(Beijing)、 圖形、聲音。,1.2.2 基本概念和術(shù)語,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,計算機管理圖書問

9、題 在圖書館里有各種卡片：有按書名編排的、 有按作者編排的、有按分類編排 如何將查詢圖書的這些信息存入計算機中 既要考慮查詢時間短，又要考慮節(jié)省空間,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,最簡單的辦法之一是建立一張表， 每一本書的信息在表中占一行，如,如何將0,1,2,3,4,5,6,7,8,9這10個數(shù)存放在 計算機中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲方方法就不同。 從大到小排列：9,8,7,6,5,4,3,2,1,0 輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9,數(shù)據(jù)元素在 計算機中的表示,數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲和運算的一般方法的學(xué)科。,對

10、數(shù)據(jù)結(jié)構(gòu)中的節(jié)點進(jìn)行 操作處理 (插入、刪除、修改、查找、排序),數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）,1.數(shù)據(jù)的邏輯結(jié)構(gòu)：是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。它包括數(shù)據(jù)元素的集合和數(shù)據(jù)元素之間的前后關(guān)系兩個因素。,有限個數(shù)據(jù)元素的集合,有限個數(shù)據(jù)元素間關(guān)系的集合,數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱數(shù)據(jù)結(jié)構(gòu)。,數(shù)據(jù)元素(Data Element),數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。 有時一個數(shù)據(jù)元素可由若干數(shù)據(jù)項(Data Item)組成。數(shù)據(jù)項是數(shù)據(jù)的最小單位。,數(shù)據(jù)元素亦稱結(jié)點或記錄。,常用數(shù)據(jù)結(jié)構(gòu):,A.線性結(jié)構(gòu),(A , B , C , ，X ,Y , Z),例:學(xué)生成績表,線性表

11、,棧后進(jìn)先出 隊列先進(jìn)先出,例:英文字母表,數(shù)據(jù)結(jié)構(gòu)S=(D,R) D=春,夏,秋,冬 R=,什么型的數(shù)據(jù)結(jié)構(gòu)?,線性結(jié)構(gòu),數(shù)據(jù)元素：用中間標(biāo)有元素值的方框表示，稱為結(jié)點 邏輯關(guān)系：用有向線段從前件指向后件（不引起誤會情況下，箭頭可以省去）,樹形結(jié)構(gòu),例:家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成,例:計算機文件管理系統(tǒng)也是典型的樹形結(jié)構(gòu),B非線性結(jié)構(gòu),沒有前件的結(jié)點稱為根結(jié)點； 沒有后件的結(jié)點稱為終端結(jié)點（葉子結(jié)點）,例:數(shù)據(jù)結(jié)構(gòu)B(D,R) D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3), (3,4) , (2,4) ,例:數(shù)據(jù)結(jié)構(gòu)C(D,R) D= 1 ,

12、 2 , 3 R= , , , ,圖形結(jié)構(gòu),Loc(ai)=Lo+（i-1)*m,1、順序存儲,每個元素所占用 的存儲單元個數(shù),（3）存儲結(jié)構(gòu),例：線性表(zhao,qian,sun,li,zhou,wu,zheng,wang),順序存儲結(jié)構(gòu)：,順序存儲結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元里,具有以下特點: 1.隨機存取。 2.作插入或刪除操作時，需移動大量元數(shù)。 3.長度變化較大時，需按最大空間分配。 4.表的容量難以擴充。,2、鏈?zhǔn)酱鎯?每個節(jié)點都由兩部分組成： 數(shù)據(jù)域和指針域。 數(shù)據(jù)域存放元素本身的數(shù)據(jù)， 指針域存放指針。 數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。,例：線

13、性表(zhao,qian,sun,li,zhou,wu,zheng,wang),鏈?zhǔn)酱鎯Y(jié)構(gòu)：,通常我們把鏈表畫成用箭頭相鏈接的結(jié)點的序列，結(jié)點之間的箭頭表示鏈域中的指針。,1.比順序存儲結(jié)構(gòu)多用空間(存儲密度小) (每個節(jié)點都由數(shù)據(jù)域和指針域組成)。 2.邏輯上相鄰的節(jié)點物理上不必相鄰。 3.插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針)。 4.非隨機存取。,鏈接存儲結(jié)構(gòu)特點：,1數(shù)據(jù)的邏輯結(jié)構(gòu),2、數(shù)據(jù)的存儲結(jié)構(gòu),3、數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。,A線性結(jié)構(gòu),B非線性結(jié)構(gòu),A 順序存儲,B 鏈?zhǔn)酱鎯?線性表,棧,隊,樹形結(jié)構(gòu),圖形結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)的三個方面,(亦稱物理

14、結(jié)構(gòu)),鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【1】 。 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的 A) 存儲結(jié)構(gòu)B) 物理結(jié)構(gòu) C) 邏輯結(jié)構(gòu)D) 物理和存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【1】 兩大類。 數(shù)據(jù)的存儲結(jié)構(gòu)是指 A）數(shù)據(jù)所占的存儲空間 B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示 C）數(shù)據(jù)在計算機中的順序存儲方式 D）存儲在外存中的數(shù)據(jù),例題講解,存儲結(jié)構(gòu),非線性結(jié)構(gòu),順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【2】 的存儲單元中。

15、 數(shù)據(jù)處理的最小單位是 A) 數(shù)據(jù) B) 數(shù)據(jù)元素 C) 數(shù)據(jù)項D) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運算，以及 A) 數(shù)據(jù)的存儲結(jié)構(gòu) B) 計算方法 C) 數(shù)據(jù)映象 D) 邏輯存儲 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu),相鄰,根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

16、C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【2】 以及對數(shù)據(jù)的操作運算。 數(shù)據(jù)的基本單位是 【5】 。 下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),存儲結(jié)構(gòu),數(shù)據(jù)元素,1.3 線性表,1.3.1 線性表的概念 線性表的定義： 線性表是n個元素的有限序列，它們之間的關(guān)系可以排成一 個線性序列： (a1，a2， ，ai， ，an) 其中n稱作表的長度，當(dāng)n=0時，稱作空表。,線性表的特點

17、： 1.線性表中所有元素的性質(zhì)相同。 2.除第一個和最后一個數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼.第一個數(shù)據(jù)元素?zé)o前驅(qū),最后一個數(shù)據(jù)元素?zé)o后繼。 3.數(shù)據(jù)元素在表中的位置只取決于它自身的序號。 在線性表上常用的運算有： 初始化、求長度、取元素、修改、前插、刪除、查找、排序。,1.4 線性表的順序存儲結(jié)構(gòu)及其插入與刪除操作,特點： 1.線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲空間利用率高。 2.所有元素所占的存儲空間是連續(xù)的 3.各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的 4. 做插入、刪除時需移動大量元素。 5. 空間估計不明時，按最大空間分配。,順序存儲結(jié)構(gòu)：,元素an,

18、.,元素ai,.,元素a2,元素a1,b,b+m,b+(i-1)*m,b+(maxlen-1)*m,存儲地址,內(nèi)存狀態(tài),Loc(元素i)=b +（i-1)*m,順序存儲結(jié)構(gòu)示意圖(順序表)：,首地址 起始地址 基地址,每個元素所占用 的存儲單元個數(shù),1- 1插入運算,ai-1,.,a2,a1,alength,ai+1,ai,x,ai-1,.,a2,a1,alength,ai+1,ai,X,插入算法的分析: 假設(shè)線性表中含有n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為：,1- 2刪除運算,ai-1,.,a2,a1,alength,ai+1,a

19、i,ai-1,.,a2,a1,alength,ai+1,刪除算法的分析: 在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為：,總結(jié): 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點需要值得考慮。,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 順序存儲方法是把邏輯上相鄰的結(jié)點存儲在物理位置 【2】 的存儲單元中。 長度為n的順序存儲線性表中，當(dāng)在任何位置上插入一個元素概率都相等時，插

20、入一個元素所需移動元素的平均個數(shù)為 【1】 。 線性表若采用順序存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址 A) 必須是連續(xù)的 B) 部分地址必須是連續(xù)的 C) 一定是不連續(xù)的 D) 連續(xù)不連續(xù)都可以,例題講解,相鄰,線性表L=(a1,a2,a3,ai，an)，下列說法正確的是 A) 每個元素都有一個直接前件和直接后件 B) 線性表中至少要有一個元素 C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個元素和最后一個元素外，其余每個元素都有一個 且只有一個直接前件和直接后件 線性表的順序存儲結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)分別是 A) 順序存取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) B) 隨機存

21、取的存儲結(jié)構(gòu)、順序存取的存儲結(jié)構(gòu) C) 隨機存取的存儲結(jié)構(gòu)、隨機存取的存儲結(jié)構(gòu) D) 任意存取的存儲結(jié)構(gòu)、任意存取的存儲結(jié)構(gòu) 下列敘述中，錯誤的是 A) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) 數(shù)據(jù)的存儲結(jié)構(gòu)與數(shù)據(jù)處理的效率無關(guān) C) 數(shù)據(jù)的存儲結(jié)構(gòu)在計算機中所占的空間不一定是連續(xù)的 D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲結(jié)構(gòu),根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成 A) 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 當(dāng)線性表采用順序存儲結(jié)構(gòu)實現(xiàn)存儲時，其主要特點是 【1】 。,隨機存取,1.5線性表的

22、鏈?zhǔn)酱鎯Y(jié)構(gòu)及其插入與刪除操作,單鏈表,P,1-1單鏈表的插入運算,在P所指向的結(jié)點之后插入新的結(jié)點,1-2單鏈表刪除運算,要求:刪除結(jié)點ai。,1-3. 循環(huán)鏈表: 首尾相接的鏈表。 將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一結(jié)點出發(fā)均可找到其它結(jié)點。,L,.,帶頭結(jié)點的單鏈表,L,.,循環(huán)單鏈表,特點: 可以從任何一個結(jié)點開始訪問鏈表的所有結(jié)點.,1-4 雙向鏈表 在每個結(jié)點中設(shè)置兩個指針，一個指向后繼，一個指向前驅(qū)?？芍苯哟_定一個結(jié)點的前驅(qū)和后繼結(jié)點。可提高效率。,data,next,before,鏈表不具有的特點是 A) 不必事先估計存儲空間 B) 可隨機訪問任一元素 C) 插入刪除

23、不需要移動元素D) 所需空間與線性表長度成正比 用鏈表表示線性表的優(yōu)點是 A) 便于隨機存取 B) 花費的存儲空間較順序存儲少 C) 便于插入和刪除操作 D) 數(shù)據(jù)元素的物理順序與邏輯順序相同 長度為n的順序存儲線性表中,當(dāng)在任何位置上插入一個元素概率都相等時,插入一個元素所需移動元素的平均個數(shù)為 【1】 。 在單鏈表中，增加頭結(jié)點的目的是 A) 方便運算的實現(xiàn) B) 使單鏈表至少有一個結(jié)點 C) 標(biāo)識表結(jié)點中首結(jié)點的位置 D) 說明單鏈表是線性表的鏈?zhǔn)酱鎯崿F(xiàn),例題講解,非空的循環(huán)單鏈表head的尾結(jié)點(由p所指向) ，滿足 A) p-next=NULLB) p=NULL C) p-next

24、=head D) p=head 循環(huán)鏈表的主要優(yōu)點是 A) 不再需要頭指針了 B) 從表中任一結(jié)點出發(fā)都能訪問到整個鏈表 C) 在進(jìn)行插入、刪除運算時，能更好的保證鏈表不斷開 D) 已知某個結(jié)點的位置后，能夠容易的找到它的直接前件 當(dāng)循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進(jìn)行入隊運算。這種情況稱為 【2】 。 用鏈表表示線性表的突出優(yōu)點是 【1】 。,上溢,插入、刪除靈活,1.6 棧和隊列,1.6.1 棧和隊列的定義 棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。,1 .棧,棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 棧頂表尾

25、。 棧底表頭。 空棧不含元素的空表。,進(jìn)棧,出棧,棧s=(a1,a2,an),后進(jìn)先出（LIFO）,2. 棧的順序存儲結(jié)構(gòu)及其基本運算,用順序存儲結(jié)構(gòu)表示的棧: 順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量top指示棧頂位置，稱為棧頂指針，它始終指向待插入元素的位置。,基本運算： 壓（進(jìn)）棧：PUSH 出棧：POP 讀棧頂元素：gettop,例子：,空桟：topbase 非空桟：top始終在桟頂元素的后一個位置,桟的元素個數(shù)：,top-base,上溢,下溢,3. 隊列 定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在 表的另一端進(jìn)行刪除的線

26、性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。,4.隊列的順序存儲結(jié)構(gòu)及其基本運算,空隊列: 非空隊列: 隊列元素個數(shù):,rear=front=-1,front始終指向隊頭元素前一個位置，而rear始終指向隊尾元素的位置,rear-front,循環(huán)隊列,基本思想：把隊列設(shè)想為一個循環(huán)的表，臆想elem0接在elemmaxsize-1之后.,上溢,下溢,front=rear 隊滿,front=rear 隊空,棧和隊列的共同特點是 A)都是先進(jìn)先出 B) 都是先進(jìn)后出 C) 只允許在端點處插入和刪除元素 D) 沒有共同點 如果進(jìn)棧序列為e1,e2,e3,e4，則可能的出棧序列是 A) e3,e1,e

27、4,e2 B) e2,e4,e3,e1 C) e3,e4,e1,e2D) 任意順序 一些重要的程序語言(如C語言和Pascal語言) 允許過程的遞歸調(diào)用。而實現(xiàn)遞歸調(diào)用中的存儲分配通常用 A) 棧B) 堆 C) 數(shù)組 D) 鏈表,例題講解,棧底至棧頂依次存放元素A、B、C、D，在第五個元素E入棧前，棧中元素可以出棧，則出棧序列可能是 A) ABCED B) DCBEA C) DBCEA D) CDABE 棧通常采用的兩種存儲結(jié)構(gòu)是 A) 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B) 散列方式和索引方式 C) 鏈表存儲結(jié)構(gòu)和數(shù)組 D) 線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu) 棧和隊列通常采用的存儲結(jié)構(gòu)是 【1】 。 下

28、列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是 A) 線性鏈表 B) 棧 C) 循環(huán)鏈表 D) 順序表 當(dāng)循環(huán)隊列非空且隊尾指針等于隊頭指針時，說明循環(huán)隊列已滿，不能進(jìn)行入隊運算。這種情況稱為 【2】 。,鏈表存儲結(jié)構(gòu)和數(shù)組,上溢,由兩個棧共享一個存儲空間的好處是 A) 減少存取時間，降低下溢發(fā)生的機率 B) 節(jié)省存儲空間，降低上溢發(fā)生的機率 C) 減少存取時間，降低上溢發(fā)生的機率 D) 節(jié)省存儲空間，降低下溢發(fā)生的機率,下列關(guān)于棧的敘述中正確的是 ）在棧中只能插入數(shù)據(jù) B）在棧中只能刪除數(shù)據(jù) C）棧是先進(jìn)先出的線性表 D）棧是后進(jìn)先出的線性表 下列關(guān)于隊列的敘述中正確的是 ）在隊列中只能插入數(shù)據(jù)

29、B）在隊列中只能刪除數(shù)據(jù) C）隊列是先進(jìn)先出的線性表 D）隊列是后進(jìn)先出的線性表,1.7.1 樹的定義 由一個或多個結(jié)點組成的有限集合。僅有一個根結(jié)點，結(jié)點間有明顯的層次結(jié)構(gòu)關(guān)系。,現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子： 學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。,1.7 樹,介紹幾個概念： 結(jié)點（Node）：樹中的元素，包含數(shù)據(jù)項及若干指向其子樹的分支。 結(jié)點的度（Degree）：結(jié)點擁有的子樹數(shù)。 結(jié)點的層次：從根結(jié)點開始算起，根為第一層。 葉子（Leaf）：度為零的結(jié)點，也稱端結(jié)點。 孩子（Child）：結(jié)點子樹的根稱為該結(jié)點的孩子結(jié)點。 兄弟（Sibling）：同一雙親的孩子。

30、 雙親（Parent）：孩子結(jié)點的上層結(jié)點，稱為這些結(jié)點的 雙親。 樹的深度（Depth)： 樹中結(jié)點的最大層次數(shù)。 樹的度：結(jié)點所具有的最大的度. 森林（Forest）：M棵互不相交的樹的集合。,1.7.2 二叉樹 （Binary Tree）,1 、二叉樹的定義及其性質(zhì) (1) 二叉樹的定義,二叉樹的五種基本形態(tài),二叉樹一種特殊的樹形結(jié)構(gòu)，特點是樹中每個結(jié)點最多只能有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點)，且子樹有左右之分，次序不能顛倒。,二叉樹是n(n0)個結(jié)點的有限集合。它或為空數(shù)(n=0),或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。,特別要注意：二叉樹不

31、是一般樹的特殊情況,而是另一種樹形結(jié)構(gòu).,a,a,b,b,兩棵不同的二叉樹,一棵樹,性質(zhì)1:二叉樹的第i層上至多有2 i-1（i 1）個結(jié)點。,(2) 二叉樹的基本性質(zhì),第三層上(i=3)，有23-1=4個節(jié)點。 第四層上(i=4)，有24-1=8個節(jié)點。,性質(zhì)2: 深度為k的二叉樹中至多含有2k-1個結(jié)點。,性質(zhì)：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0,度 為2的結(jié)點數(shù)為n2,則n0=n2+1。,證明： 設(shè)n1為二叉樹T中度為1的結(jié)點數(shù)； 二叉樹中所有結(jié)點的度均小于或等于2 其結(jié)點總數(shù)為： n=n0+n1+n2 二叉樹中除了根結(jié)點外，其余結(jié)點都有一個分支進(jìn)入 設(shè)分支總數(shù)為B； 則 n=B

32、+1; 二叉樹的分支是由度為1或2的結(jié)點射出的 B=n1+2*n2 n=n1+2*n2+1=n0+n1+n2 n0=n2+1,滿二叉樹,特點：每一層上都含有最大結(jié)點數(shù)。,完全二叉樹,特點： (1)除最后一層外，每一層都取最 大結(jié)點數(shù)， (2)最后一層結(jié)點都集中在該層最左邊的若干位置。,性質(zhì)：具有n個結(jié)點的完全二叉樹的深度為,例：n=2 k=2 n=6 k=3 n=7 k=3 n=8 k=4 n=12 k=4,性質(zhì)：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層 序編號，則對任一結(jié)點i(1=i=n)有：,(2)如果2in,則結(jié)點i無左孩子(結(jié)點i為葉子結(jié)點); 否則其左孩子Lchild(i)是結(jié)點2

33、i。 (3)如果2i+1n,則結(jié)點i無右孩子; 否則其右孩子Rchild(i)是結(jié)點2i+1。,例：,i=1 是樹的根,無雙親;其左孩子為2*i=2,右孩子為2*i+1=3 .,2*i=1812 2*i+1=1912 其無左、右孩子。,2*i+1=1312 其無右孩子。,樹與二叉樹的區(qū)別,A樹和二叉樹的結(jié)點個數(shù)最少都可為0。 B樹中結(jié)點的最大度數(shù)沒有限制，二叉樹結(jié)點最大度數(shù)為2。 C樹的結(jié)點無左、右之分，二叉樹的結(jié)點子樹有明確的左、右之分。,3個結(jié)點的樹,3個結(jié)點的 二叉樹,2、二叉樹的存儲結(jié)構(gòu),(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu),T16,若父結(jié)點在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。

34、,(1) 順序存儲結(jié)構(gòu),(1) 順序存儲結(jié)構(gòu),2h-1=,24-1 = 15,用一組連續(xù)的存儲單元存放二叉樹的數(shù)據(jù)元素。結(jié)點在數(shù)組中的相對位置蘊含著結(jié)點之間的關(guān)系。,一般二叉樹必須按完全二叉樹的形式存儲，將造成存儲的浪費。,(2)、鏈?zhǔn)酱鎯Y(jié)構(gòu),鏈?zhǔn)酱鎯Y(jié)構(gòu),二叉鏈表 三叉鏈表,二叉鏈表：,二叉鏈表的結(jié)點包含三個域：數(shù)據(jù)域、左、右指針域。,例：,三叉鏈表：,三叉鏈表的結(jié)點包含四個域： 數(shù)據(jù)域、左、右、雙親指針域。,例：,鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點： （1）操作便于實現(xiàn) （2）結(jié)構(gòu)復(fù)雜,1.7.3 二叉樹的遍歷 查找某個結(jié)點，或?qū)Χ鏄渲腥拷Y(jié)點進(jìn)行某種處理，就需要遍歷。 （1）遍歷定義及遍歷算法 遍歷

35、是指按某條搜索路線尋訪樹中每個結(jié)點，且每個結(jié)點只被訪 問一次。 按先左后右的原則，一般使用三種遍歷： 先序遍歷(D L R): 訪問根結(jié)點，按先序遍歷左子樹，按先序遍歷右子樹。 中序遍歷(L D R): 按中序遍歷左子樹，訪問根結(jié)點，按中序遍歷右子樹。 后序遍歷(L R D): 按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點。 二叉樹為空時，執(zhí)行空操作，即空二叉樹已遍歷完。,（2）遍歷算法,先序遍歷：D L R 中序遍歷：L D R 后序遍歷：L R D,A,D,B,C,D L R,以先序遍歷D L R為例演示遍歷過程,ABDC,BDAC,DBCA,L D R,L D R,a,+,L D R,

36、b,*,LDR,c,-,d,-,LDR,e,/,f,中序遍歷示圖,已知二叉樹后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是 A) acbed B) decab C) deabc D) cedba 已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為 A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG 樹是結(jié)點的集合，它的根結(jié)點數(shù)目是 A) 有且只有1B) 1或多于1 C) 0或1D) 至少2 下列敘述中正確的是 A) 線性表是線性結(jié)構(gòu)B) 棧與隊列是非線性結(jié)構(gòu) C) 線性鏈表是非線性

37、結(jié)構(gòu)D) 二叉樹是線性結(jié)構(gòu),例題講解,在深度為5的滿二叉樹中，葉子結(jié)點的個數(shù)為 A) 32B) 31 C) 16 D) 15 若某二叉樹的前序遍歷訪問順序是abdgcefh，中序遍歷訪問順序是dgbaechf，則其后序遍歷的結(jié)點訪問順序是 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca 在樹結(jié)構(gòu)中，樹根結(jié)點沒有 【1】 。 具有3個結(jié)點的二叉樹有 A) 2種形態(tài) B) 4種形態(tài) C) 7種形態(tài) D) 5種形態(tài) 設(shè)一棵二叉樹中有3個葉子結(jié)點，有8個度為1的結(jié)點，則該二叉樹中總的結(jié)點數(shù)為 A) 12 B) 13 C) 14D) 15,雙親結(jié)點,設(shè)有下

38、列二叉樹： 對此二叉樹前序遍歷的結(jié)果為 A) ZBTTCPXA B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT 設(shè)有下列二叉樹： 對此二叉樹的中序遍歷的結(jié)果為 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,設(shè)樹T的度為4,其中度為1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1。則T中的葉子結(jié)點數(shù)為 A）8 B）7 C）6 D）5 設(shè)一棵完全二叉樹共有700個結(jié)點，則該二叉樹中有（ ）個葉子結(jié)點。,350,解法一：根據(jù)二叉樹的性質(zhì)3可知：葉子結(jié)點數(shù)n0n2+1，根據(jù)完全二叉樹的概念可知，度為1的結(jié)點數(shù)要么為1，要么為0，二叉樹總結(jié)點數(shù)Nn0

39、+n1+n22n0+n11，得出n0（N+1n1）/2N/2向上取整，所以本題答案是350個葉子結(jié)點。 解法二：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=log2N向上取整 =10;且前9層總結(jié)點數(shù)為29-1=511 (完全二叉樹的前k-1層肯定是滿的)所以末層葉子數(shù)為700-511=189個。請注意葉子結(jié)點總數(shù)末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層（靠右邊）的0度結(jié)點個數(shù)。末層的189個葉子只占據(jù)了上層的95個結(jié)點（189/2 )，上層（k=9)右邊的0度結(jié)點數(shù)還有2(9-1)-95=161個。所以，全部葉子數(shù)189(末層)161(k-1層)=350個。,在一個容量為15的循環(huán)隊列中，若頭指針front

40、=6，尾指針rear=9，則該循環(huán)隊列中共有（ ）個元素。 設(shè)一棵二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為（ ）。,3,DEBFCA,1.8 查找和排序,順序查找與二分查找算法 基本排序算法（交換類排序、選擇類排序、插入類排序）,1.8.1 查找,查找是在一個給定的數(shù)據(jù)結(jié)構(gòu)中，根據(jù)給定的條件查找滿足條件的結(jié)點。不同的數(shù)據(jù)結(jié)構(gòu)采用不同的查找方法。查找的效率直接影響數(shù)據(jù)處理的效率。 查找的結(jié)果： 查找成功：找到滿足條件的結(jié)點 查找失?。赫也坏綕M足條件的結(jié)點。,1.8.1.1 順序查找（線性查找）,查找過程： 對給定的一關(guān)鍵字K，從線性表的一端開始，逐個進(jìn)行記

41、錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于K的記錄或到達(dá)表的另一端。 可以采用從前向后查，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較，效率較低。平均查找長度較大。 最好情況：1 最壞情況：n 在下面兩種情況下只能采取順序查找： a. 線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。,1.8.1.2 折半查找（二分法查找）,思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。 前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進(jìn)行。 分三種情況： 1）若中間項的值等于x,則說明已查到。 2）若x小于中間項的值

42、,則在線性表的前半部分查找； 3）若x大于中間項的值，則在線性表的后半部分查找。 特點：比順序查找方法效率高。最壞的情況下，需要比較 log2n次。,1.8.2 排序,1.8.2.1 概述 1、排序的功能： 將一個數(shù)據(jù)元素（或記錄）的 任意序 列，重新排成 一個按關(guān)鍵字有序的序列。 2、排序過程的組成步驟： 首先比較兩個關(guān)鍵字的大?。?然后將記錄從一個位置移動到另一個位置。,排序方法,插入類排序,選擇類排序,交換類排序,歸并排序,簡單插入排序,希爾排序,簡單選擇排序,堆排序,起泡排序,快速排序,1.8.2.2 交 換 排 序 交換排序的特點在于交換。有冒泡和快速排序兩種。 1、冒泡排序（起泡排

43、序） 思想：小的浮起，大的沉底。從左端開始比較。 第一趟：第1個與第2個比較，大則交換；第2個與第3個比較， 大則交換，關(guān)鍵字最大的記錄交換到最后一個位置上； 第二趟：對前n-1個記錄進(jìn)行同樣的操作，關(guān)鍵字次大的記錄交換 到第n-1個位置上； 依次類推，則完成排序。,第 六 趟 排 序 后,第 五 趟 排 序 后,第 四 趟 排 序 后,第 三 趟 排 序 后,第 二 趟 排 序 后,第 一 趟 排 序 后,初 始 關(guān) 鍵 字,思想：小的浮起，大的沉底。,排序n個記錄最多需要n-1趟冒泡排序 正序：比較次數(shù)為O(n-1) 逆序：比較次數(shù)為O(n(n-1)/2) 適合于數(shù)據(jù)較少的情況。,2、快速

44、排序 (對冒泡排序的改進(jìn)） 思想：通過一趟排序?qū)⒋判蛄蟹殖蓛刹糠?，使其中一部分記錄的關(guān)鍵字均比另一部分小，再分別對這兩部分排序，以達(dá)到整個序列有序。,如，經(jīng)過“一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,2、快速排序 (對冒泡排序的改進(jìn)） 時間復(fù)雜度：O(nlog2n) 當(dāng)待排序列逆序時，蛻變成冒泡排序，時間復(fù)雜度: O(n(n-1)/2),1.8.2.3 插入排序 簡單插入、希爾排序,1、簡單插入排序: 基本思想：從數(shù)組的第2號元素開始，順

45、序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當(dāng)位置上。,該算法適合于n 較小的情況，時間復(fù)雜度為O(n2).,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 直接插入排序示例,對于有n個數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1趟,最壞情況下： 需要n(n-1)/2次比較 最好： n-1次比較,希爾排序：,希爾排序的基本思想: 先將整個待排記錄序列分割成為若干子序