專升本數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)與算法北上數(shù)據(jù)結(jié)構(gòu)考前復(fù)習(xí)輔導(dǎo)課需要具備的先導(dǎo)知識輔導(dǎo)課的側(cè)重點、難度輔導(dǎo)課的時間、內(nèi)容安排輔導(dǎo)課需要具備的先導(dǎo)知識C語言的基本概念，至少能夠看懂簡單的C語言代碼。最好有上過數(shù)據(jù)結(jié)構(gòu)課程，未上過數(shù)據(jù)結(jié)構(gòu)課程會有些吃力。有一點點高等數(shù)學(xué)基礎(chǔ)更好。專升本數(shù)據(jù)結(jié)構(gòu)的特點課本的組織形式基本上是以代碼來講解理論，這給讀書帶來一定難度。專升本的考試重點不在代碼實現(xiàn)，而在理論知識的掌握。09級的數(shù)據(jù)結(jié)構(gòu)課程按照理論+題庫的講解模式，應(yīng)試能力明顯增強。輔導(dǎo)課的側(cè)重點、難度基本上講解理論知識+題目，盡量不涉及C語言(必要的C語言結(jié)構(gòu)會進行講解)。講解過程采用新課+復(fù)習(xí)模式，按照新課講授，例子可能采用后面

2、的章節(jié)。希望大家在過程中做好筆記。難度與專升本考試難度持平，相當于學(xué)習(xí)期間，中游同學(xué)可以掌握的難度。考試大綱見word文檔數(shù)據(jù)結(jié)構(gòu)的主體內(nèi)容線性數(shù)據(jù)結(jié)構(gòu)集合(散列數(shù)據(jù)結(jié)構(gòu)) 樹形(層次)數(shù)據(jù)結(jié)構(gòu)圖(網(wǎng)狀)數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度排序查找相關(guān)數(shù)據(jù)結(jié)構(gòu)(二叉排序樹、堆)遞歸及其他輔導(dǎo)課的時間、內(nèi)容安排7月26日上午：算法數(shù)據(jù)結(jié)構(gòu)概念、時間復(fù)雜度、線性數(shù)據(jù)結(jié)構(gòu)(表)7月26日下午：線性數(shù)據(jù)結(jié)構(gòu)(棧、隊列)、排序7月28日下午：樹形數(shù)據(jù)結(jié)構(gòu)7月29日上午：集合（散列數(shù)據(jù)結(jié)構(gòu)）、二叉排序樹、堆、哈夫曼7月29日下午：圖（網(wǎng)狀）數(shù)據(jù)結(jié)構(gòu)7月30日上午：其它內(nèi)容（編程題目）、復(fù)習(xí)、測驗開篇：數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)元素

3、是數(shù)據(jù)的基本單位，但數(shù)據(jù)元素是可分的，數(shù)據(jù)元素由數(shù)據(jù)項組成。數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，基本結(jié)構(gòu)有4類：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)存儲結(jié)構(gòu)，即數(shù)據(jù)的物理結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示。包括數(shù)據(jù)元素的表示和關(guān)系的表示。主要有順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、索引存儲方法和散列存儲方法等。習(xí)題要表示高校的校，系，班級的有關(guān)數(shù)據(jù)及其關(guān)系，選擇_比較合適?！?福建 2009 專升本】A 線性結(jié)構(gòu) B 樹結(jié)構(gòu) C 圖結(jié)構(gòu) D 集合結(jié)構(gòu)_是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。【 福建 2009 專升本】A 數(shù)據(jù)結(jié)構(gòu) B 數(shù)據(jù)項 C 數(shù)據(jù)元素 D 數(shù)據(jù)對象答案:

4、B C習(xí)題以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)_ 【 福建 2007 專升本】A 隊列 B 靜態(tài)數(shù)組 C 線索二叉樹 D 雙向鏈表答案: A算法定義及復(fù)雜度的概念需要掌握的知識點 算法的定義及其五條基本性質(zhì) 時間復(fù)雜度的概念、時間復(fù)雜度與什么有關(guān) 最壞、最好、平均情況下的時間復(fù)雜度時間復(fù)雜度的O表示 給定函數(shù)式，可以用O表示。能夠比較兩個函數(shù)式代表的復(fù)雜度。給出C簡單代碼，能夠計算復(fù)雜度（O表示）。熟記常用算法的復(fù)雜度(O表示)。算法(Algorithm)算法是指解決問題的一種方法或一個過程。算法是若干指令的有窮序列，滿足性質(zhì)：(1)輸入：有外部提供的量作為算法的輸入。(2)輸出：算法產(chǎn)生至少一

5、個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。(5)可行性：任意合法輸入都對應(yīng)正確輸出算法復(fù)雜性分析 算法復(fù)雜性 = 算法所需要的計算機資源。算法的時間復(fù)雜性T(n)。算法的空間復(fù)雜性S(n)。數(shù)據(jù)結(jié)構(gòu)主要討論時間復(fù)雜性。時間復(fù)雜性與問題規(guī)模和數(shù)據(jù)初始狀態(tài)有關(guān)，與其它內(nèi)容無關(guān)。最壞情況、最好情況和平均情況下時間復(fù)雜性三種情況下時間復(fù)雜性是針對初始數(shù)據(jù)進行分類的，與n沒有關(guān)系。漸近分析的記號對所有n，f(n) 0，g(n) 0。漸近上界記號O的定義O(g(n) = f(n) | 存在正常數(shù)c和n0使得

6、對所有n n0有：0 f(n) cg(n) O符號具有的特點：O符號忽略所有的系數(shù)。O符號僅在乎整個表達式的主項（值最大的項）。習(xí)題下列函數(shù)中漸進時間復(fù)雜度最小的是_。【 2009 專升本】答:A若一個算法中的語句頻度之和為T(n) = 3720n+4nlogn，則算法的時間復(fù)雜度為_ ?！?2007 專升本】 O(nlogn)習(xí)題算法的計算量的大小稱為計算的_【北京郵電大學(xué)2000 二、3 】A 效率 B 復(fù)雜性 C 現(xiàn)實性 D 難度算法的時間復(fù)雜度取決于_【中科院計算所 1998 二、1】A僅和問題的規(guī)模有關(guān) B 僅和待處理數(shù)據(jù)的初態(tài)有關(guān)C和問題的規(guī)模及待處理數(shù)據(jù)的初態(tài)有關(guān)D和問題的規(guī)模、

7、待處理數(shù)據(jù)的初態(tài)、CPU的執(zhí)行速度有關(guān)一個算法的定義是_。 【中山大學(xué) 1998 二、1】A 程序 B 問題求解步驟的描述 C 滿足五個基本特性的東西答:B C B算法的時間復(fù)雜性及看C代碼寫復(fù)雜度見其它課件常用算法的時間復(fù)雜性的大小關(guān)系為：常數(shù)級 對數(shù)級 多項式級 =0)個同一類型的元素(element)a(1),a(2),a(n)組成的有限序列。其中，元素的個數(shù)n定義為表的長度。長度等于0的表是空表。表中的數(shù)據(jù)關(guān)系是一對一的線性關(guān)系。線性表和數(shù)組的差別在于線性表的長度是動態(tài)變化的。線性表的主要操作包括添加元素、刪除元素、根據(jù)元素查找位置、根據(jù)位置查找元素等。表的常用運算ListEmpty(

8、L):測試表L是否為空。ListLength(L):表L的長度。ListLocate(x,L):元素x在表L中的位置。若x在表中重復(fù)出現(xiàn)多次，則返回最前面的x的位置。ListRetrieve(K,L):返回表L的位置k處的元素。表中沒有位置k時，該運算無定義。 ListInsert(k,x,L):在表L的位置k之后插入元素x,并將原來占據(jù)該位置的元素及其后面的元素都向后推移一個位置。ListDelete(k,L)；從表L中刪除位置k處的元素，并返回被刪除的元素。線性表的兩種實現(xiàn)方式線性表的實現(xiàn)主要有順序?qū)崿F(xiàn)和鏈式實現(xiàn)。順序?qū)崿F(xiàn)就是順序表，也就是數(shù)組實現(xiàn)。 在這種實現(xiàn)方式下表的容量是固定的。鏈式

9、實現(xiàn)是指針實現(xiàn)方式，分為單鏈表、雙鏈表、循環(huán)鏈表、帶頭結(jié)點鏈表等。提示：棧和隊列等線性結(jié)構(gòu)也都是這兩種實現(xiàn)方式。順序表（數(shù)組實現(xiàn)表）數(shù)組實現(xiàn)表就是用一段連續(xù)的存儲空間依次存放表元素。這種實現(xiàn)方式的優(yōu)點有：存儲密度大(無需額外空間)根據(jù)位置查找元素方便在尾部添加刪除元素方便這種實現(xiàn)方式的缺點有：插入刪除可能需要移動元素表容量固定順序表(數(shù)組實現(xiàn)表)的C語言結(jié)構(gòu)typedef struct alist *List;typedef struct alist int n; int maxsize; ListItem *table;Alist;書上20頁中的table 應(yīng)改為：*table;順序表(數(shù)組

10、實現(xiàn)表)的插入操作102030405060 xxx012345678在第2個元素后面添加70的過程,表中有6個元素(L-n=6)：順序表(數(shù)組實現(xiàn)表)的插入操作10203040506060 xx012345678在第2個元素后面添加70的過程,表中有6個元素(L-n=6)：對應(yīng)C代碼：L-table6=L-table5順序表(數(shù)組實現(xiàn)表)的插入操作10203040505060 xx012345678在第2個元素后面添加70的過程,表中有6個元素(L-n=6)：對應(yīng)C代碼：L-table5=L-table4順序表(數(shù)組實現(xiàn)表)的插入操作10203040405060 xx012345678在第2個

11、元素后面添加70的過程,表中有6個元素(L-n=6)：對應(yīng)C代碼：L-table4=L-table3順序表(數(shù)組實現(xiàn)表)的插入操作10203030405060 xx012345678在第2個元素后面添加70的過程,表中有6個元素(L-n=6)：對應(yīng)C代碼：L-table3=L-table2順序表(數(shù)組實現(xiàn)表)的插入操作10207030405060 xx012345678在第2個元素后面添加70的過程,表中有6個元素(L-n=6)：對應(yīng)C代碼：L-table2=70;L-n+;插入操作移動元素的平均次數(shù)最少情況為表尾插入，移動0次。最多情況為表首插入，移動n次。平均次數(shù)= 移動的總次數(shù)/位置個數(shù)

12、順序表(數(shù)組實現(xiàn)表)的刪除操作10207030405060 xx012345678刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：順序表(數(shù)組實現(xiàn)表)的刪除操作10203030405060 xx012345678刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：L-table2=L-table3順序表(數(shù)組實現(xiàn)表)的刪除操作10203040405060 xx012345678刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：L-table3=L-table4順序表(數(shù)組實現(xiàn)表)的刪除操作10203040505060 xx012345678

13、刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：L-table4=L-table5順序表(數(shù)組實現(xiàn)表)的刪除操作10203040506060 xx012345678刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：L-table5=L-table6順序表(數(shù)組實現(xiàn)表)的刪除操作102030405060 xxx012345678刪除表中第三個元素的過程,表中有7個元素(L-n=7)：對應(yīng)C代碼：L-n-刪除操作移動元素的平均次數(shù)最少情況為表尾刪除，移動0次。最多情況為表首刪除，移動n-1次。平均次數(shù)= 移動的總次數(shù)/位置個數(shù)單鏈表（指針實現(xiàn)表）單鏈表采用指針

14、的方式將物理上并不相鄰的單元串聯(lián)起來。這種實現(xiàn)方式的優(yōu)點有：插入刪除不需要移動元素表容量可任意變化這種實現(xiàn)方式的缺點有：需要額外的指針空間查找指定位置元素的復(fù)雜度高單鏈表（指針實現(xiàn)表）a(1)a(2)a(3)a(n)first單鏈表：表的定義typedef struct node *link;typedef struct node ListItem element; link next;Node;typedef struct llist *List;typedef struct llist link first;Llist;單鏈表：第2個結(jié)點后插入y指向的結(jié)點a(1)a(2)a(3)a(n)f

15、irstxy單鏈表：第2個結(jié)點后插入y指向的結(jié)點a(1)a(2)a(3)a(n)firstxy對應(yīng)代碼：p=L-firstp單鏈表：第2個結(jié)點后插入y指向的結(jié)點a(1)a(2)a(3)a(n)firstxy對應(yīng)代碼：p=p-nextp單鏈表：第2個結(jié)點后插入y指向的結(jié)點a(1)a(2)a(3)a(n)firstxy對應(yīng)代碼：y-next=p-nextp單鏈表：第2個結(jié)點后插入y指向的結(jié)點a(1)a(2)a(3)a(n)firstxy對應(yīng)代碼：p-next=yp單鏈表：刪除第3個結(jié)點a(1)a(2)a(3)a(n)first對應(yīng)代碼：p=L-firstp單鏈表：刪除第3個結(jié)點a(1)a(2)a(

16、3)a(n)first對應(yīng)代碼：p=p-nextp單鏈表：刪除第3個結(jié)點a(1)a(2)a(3)a(n)first對應(yīng)代碼：p-next=p-next-nextp其它鏈表形式a(1)a(2)a(1)a(2)a(3)a(n)first循環(huán)鏈表a(3)雙鏈表a(1)a(2)a(3)first頭結(jié)點表章節(jié)重點理解表所代表的線性關(guān)系的意義。了解表的順序和鏈式實現(xiàn)的優(yōu)缺點。清楚表的插入刪除查詢過程中移動元素比較元素的次數(shù)。能夠根據(jù)要求填寫（至少判斷）簡單的C實現(xiàn)代碼。表習(xí)題線性表是一個_【 福建 2009 專升本】 A 有限序列，可以為空 B 有限序列，不能為空 C 無限序列，可以為空 D 無限序列，不

17、能為空某鏈表中最常見的操作是在已知的一個結(jié)點之前插入一個新的結(jié)點和刪除其之前一個結(jié)點，則采用 _存儲方式最節(jié)省運算時間【 福建 2009 專升本】 A 雙向鏈表 B 帶頭指針的單向鏈表 C 帶尾指針的單向鏈表 D 單向循環(huán)鏈表答案：A A表習(xí)題下述哪一條是順序存儲方式的優(yōu)點_【 福建 2007 專升本】 A 存儲密度大 B 插入運算方便 C 刪除運算方便 D 可方便地用于各種邏輯結(jié)構(gòu)的存儲表示對于只在表的首、尾進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為_【 福建 2007 專升本】 A 順序表 B 用頭指針表示的單循環(huán)鏈表 C 用尾指針表示的單循環(huán)鏈表 D 單鏈表在長度為n的順序表的第i ( 1

18、 i n+1 )個位置上插入一個元素，元素的移動次數(shù)為_【 福建 2007 專升本】 A n-i+1 B n-i C i D i-1答案：A C A表習(xí)題鏈表的結(jié)點類型定義如下:typedef struct node *link;struct node ListItem element; link left; link right;*p,*q,*r;刪除雙鏈表中結(jié)點p(由p指向的結(jié)點)的操作是_【 福建 2008 專升本】 A q=p-left;r=p-right;q-right=r;r-left=q; B q=p-right;r=p-left;q-right=r;r-left=q; C q=

19、p-left;r=p-right;q-left=r;r-right=q; D q=p-left;r=p-right;q-right=r-left;答案：A表習(xí)題已知單鏈表結(jié)點構(gòu)造為struct node int data;struct node *next; *p,*q,*r;刪除單鏈表中結(jié)點p(由p指向的結(jié)點)后面的結(jié)點的操作不正確的是_【 福建 2006 專升本】 A q=p-next;p-next=q-next; B p-next=p-next-next; C r=p-next;p-next=q-next; D q=p-next;r=q-next;p-next=r;單鏈表中有n個結(jié)點,在

20、其中查找值為x的結(jié)點,查找成功時,需比較的平均次數(shù)是_【 福建 2006 專升本】 A n B (n-1)/2 C n/2 D (n+1)/2線形表采用鏈式存儲時,結(jié)點的存儲地址_【 福建 2006 專升本】 A 必須是不連續(xù)的 B 連續(xù)與否均可 C 必須是連續(xù)的 D 和頭結(jié)點的存儲地址相連續(xù)答案：C D B第三章：棧（線性數(shù)據(jù)結(jié)構(gòu)）棧是一種特殊的表，這種表只在表的一端進行插入和刪除操作。因此，這一端對于棧來說具有特殊的意義，稱為棧頂。相應(yīng)地，另外一端稱為棧底。不含任何元素的棧稱為空棧。棧是限定僅在表一端進行插入或刪除操作的線性表，又稱后進先出（LIFO）的線性表。棧頂棧底a(n).a(2)a

21、(1)棧的常用運算StackEmpty(S):測試棧S是否為空StackFull(S):測試棧S是否已滿StackTop(S):返回棧S的棧頂元素Push(x,S):在棧S的棧頂插入元素x,簡稱為將元素x入棧Pop(S):刪除并返回S的棧頂元素，簡稱為拋棧。提示：這些代碼基本上是一句話，希望大家能夠掌握棧的實現(xiàn)棧的實現(xiàn)也有順序和鏈式兩種方式。數(shù)組實現(xiàn)棧中，棧元素存儲在數(shù)組data中。用top指向當前棧頂位置。棧頂元素存儲在datatop中。棧的容量為maxtop+1。兩個?？梢怨蚕硪粋€數(shù)組data。指針實現(xiàn)棧時用top指針指向棧頂。數(shù)組實現(xiàn)棧的結(jié)構(gòu)typedef struct astack *

22、Stack;typedef struct astack int top,maxtop; StackItem *data;Astack;指針實現(xiàn)棧的結(jié)構(gòu)typedef struct snode *slink;typedef struct snode StackItem element;slink next;StackNode;棧的應(yīng)用表達式求值、括號匹配、進制轉(zhuǎn)換、圖的深度優(yōu)先遍歷等。實際上，凡是滿足先進后出的應(yīng)用都可用棧實現(xiàn)。棧的進出順序一個棧的進棧順序是123n,在進棧的過程中允許出棧，那么出棧的順序會如何？判斷：有n 個數(shù)順序進棧，出棧序列有 種。輸出序列中不可能出現(xiàn)”大、小、中”的情況。

23、要會記錄出入棧的情況。棧的習(xí)題假設(shè)進棧的元素序列依次是a、b、c、d,指出不可能的出棧序列_【 福建2006專升本】 A abcd B adbc C acbd D dcba有6個元素6,5,4,3,2,1的順序進棧，問下列哪一個不是合法的出棧序列_【 福建 2007 專升本】 A 5,4,3,6,1,2 B 4,5,3,1,2,6 C 3,4,6,5,2,1 D 2,3,4,1,5,6遞歸方法實現(xiàn)遞歸算法時通常需要使用_【 福建 2008 專升本】 A 循環(huán)隊列 B 棧 C 二叉樹 D 雙向隊列答案：B C B 第四章：隊列(線性數(shù)據(jù)結(jié)構(gòu))隊列是一種特殊的表，這種表只在表首進行刪除操作，在表尾

24、進行插入操作。隊列的修改是按先進先出的原則進行的，所以隊列又稱為先進先出表，簡稱FIFO表。假設(shè)隊列為a(1),a(2),a(n),那么a(1)就是隊首元素，a(n)為隊尾元素。隊列的常用運算QueueEmpty(Q):測試隊列Q是否為空。QueueFull(Q):測試隊列Q是否已滿。QueueFirst(Q):返回隊列Q的隊首元素。QueueLast(Q):返回隊列Q的隊尾元素。EnterQueue(x,S):在隊列Q的隊尾插入元素x。DeleteQueue(Q):刪除并返回Q的隊首元素。指針實現(xiàn)隊列的結(jié)構(gòu)typedef struct qnode *qlink;typedef struct

25、qnode QItem element; qlink next;Qnode;typedef struct lque *Queue;typedef struct lque qlink front; qlink rear;Lqueue;循環(huán)數(shù)組實現(xiàn)隊列的結(jié)構(gòu)typedef struct aque *Queue;typedef struct aque int maxsize; int front; int rear; QItem *queue;Aqueue;循環(huán)數(shù)組實現(xiàn)隊列添加元素的過程A10B2C34567DEFfrontrear隊列添加G:循環(huán)數(shù)組實現(xiàn)隊列添加元素的過程A10B2C34567DE

26、Ffrontrear隊列添加G:Q-rear=(Q-rear+1)%Q-maxsize循環(huán)數(shù)組實現(xiàn)隊列添加元素的過程A10B2C34567DEFfrontrear隊列添加G:Q-queueQ-rear=xG循環(huán)數(shù)組實現(xiàn)隊列刪除元素的過程10B2C34567DEFfrontrear隊列刪除:Q-front=(Q-front+1)%Q-maxsizeG循環(huán)數(shù)組實現(xiàn)隊列刪除元素的過程102C34567DEFfrontrear隊列刪除:Q-front=(Q-front+1)%Q-maxsizeG循環(huán)數(shù)組實現(xiàn)隊列刪除元素的過程10234567DEFfrontrear隊列刪除:Q-front=(Q-fro

27、nt+1)%Q-maxsizeG循環(huán)數(shù)組實現(xiàn)隊列添加元素的過程10234567DEFfrontrear隊列添加:Q-rear=(Q-rear+1)%Q-maxsizeGX循環(huán)數(shù)組實現(xiàn)隊列添加元素的過程10234567DEFfrontrear隊列添加:Q-rear=(Q-rear+1)%Q-maxsizeGXY第四章隊列的重點理解先進先出的數(shù)據(jù)結(jié)構(gòu)。循環(huán)數(shù)組實現(xiàn)隊列是本章節(jié)重點。重點掌握front和rear游標如何判空、判滿、計算隊列長度、入隊、出隊等。隊列的習(xí)題設(shè)數(shù)組queuem作為循環(huán)隊列Q的存儲空間,front為隊頭指針,rear為隊尾指針,則執(zhí)行出隊操作后其頭指針front的值為_【 福

28、建 2006 專升本】 A front=(front+1)%m B front=(front-1)%m C front=(front+1)%(m-1) B front=front+1以下哪一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)_ 【 福建 2007 專升本】 A 隊列 B 靜態(tài)數(shù)組 線索二叉樹 D 雙向鏈表會引起循環(huán)隊列隊頭位置發(fā)生變化的操作是_【 福建 2008 專升本】A) 取隊首元素B) 入隊列C) 取隊尾元素D) 出隊列答案：隊列的習(xí)題若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為_【浙江

29、大學(xué)1999 四、1】A) 4和2B) 1和 5C) 5和1D) 2和4判斷：無論如何實現(xiàn)，也無法使隊列的入隊、出隊兩個操作的時間復(fù)雜度同時將為O(1)。判斷：雙端隊列在邏輯上是隊列。答案：錯錯排序算法概述在一般情況下，排序問題的輸入是n個數(shù)a0,a1an-1的一個序列，要設(shè)計一個有效的排序算法，產(chǎn)生輸入序列的一個重排，使序列元素從小到大的順序排列。掌握排序算法重點是掌握每種排序每趟過程、復(fù)雜度（最好最壞平均）、移動元素、交換元素的個數(shù)等問題。重點考的排序算法：冒泡、插入、選擇、快速。希望掌握的其它排序：合并、希爾、堆排序。第六章排序外部排序 外部排序指的是大文件的排序，即待排序的記錄存儲在外

30、存儲器上，待排序的文件無法一次裝入內(nèi)存，需要在內(nèi)存和外部存儲器之間進行多次數(shù)據(jù)交換，以達到排序整個文件的目的。外部排序最常用的算法是多路歸并排序，即將原文件分解成多個能夠一次性裝人內(nèi)存的部分，分別把每一部分調(diào)入內(nèi)存完成排序。然后，對已經(jīng)排序的子文件進行歸并排序。內(nèi)部排序： 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。 內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。 第六章排序若待排序的序列中，存在多個具有相同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對次序保持不變，則稱該算法是穩(wěn)定的；若經(jīng)排序后，記錄的相對 次序發(fā)生了改變，則稱該算法是不穩(wěn)定的。 假定在待排序的記錄序

31、列中，存在多個具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，ki=kj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。 快速排序、希爾排序、堆排序、選擇排序不是穩(wěn)定的排序算法，而基數(shù)排序、冒泡排序、插入排序、歸并排序是穩(wěn)定的排序算法 冒泡排序過程演示2510301273024615原序列：冒泡排序過程演示2510301273024615第一趟：冒泡排序過程演示1025301273024615第一趟：25和10進行交換冒泡排序過程演示1025301273024615第一趟：冒泡排序過程演示1025301273024

32、615第一趟：冒泡排序過程演示1025123073024615第一趟：30和12進行交換冒泡排序過程演示1025123073024615第一趟：冒泡排序過程演示1025127303024615第一趟：30和7進行交換冒泡排序過程演示1025127303024615第一趟：保持穩(wěn)定，相等不交換。冒泡排序過程演示1025127303024615第一趟：冒泡排序過程演示1025127302430615第一趟：30和24交換冒泡排序過程演示1025127302430615第一趟：冒泡排序過程演示1025127302463015第一趟：30和6交換冒泡排序過程演示1025127302463015第一趟：

33、冒泡排序過程演示1025127302461530第一趟：30和15交換，第一趟結(jié)束，30確定位置冒泡排序過程演示1025127302461530第一趟結(jié)束，30確定位置冒泡排序過程演示1025127302461530第二趟冒泡排序過程演示1025127302461530第二趟冒泡排序過程演示1012257302461530第二趟冒泡排序過程演示1012257302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725243061530第二趟

34、冒泡排序過程演示1012725243061530第二趟冒泡排序過程演示1012725246301530第二趟冒泡排序過程演示1012725246301530第二趟冒泡排序過程演示1012725246153030第二趟冒泡排序過程演示1012725246153030第二趟結(jié)束冒泡排序過程演示1012725246153030第三趟冒泡排序過程演示1012725246153030第三趟冒泡排序過程演示1071225246153030第三趟冒泡排序過程演示1071225246153030第三趟冒泡排序過程演示1071225246153030第三趟冒泡排序過程演示1071224256153030第三趟冒

35、泡排序過程演示1071224256153030第三趟冒泡排序過程演示1071224625153030第三趟冒泡排序過程演示1071224625153030第三趟冒泡排序過程演示1071224615253030第三趟冒泡排序過程演示1071224615253030第三趟結(jié)束冒泡排序過程演示1071224615253030第四趟冒泡排序過程演示7101224615253030第四趟冒泡排序過程演示7101224615253030第四趟冒泡排序過程演示7101224615253030第四趟冒泡排序過程演示7101224615253030第四趟冒泡排序過程演示7101262415253030第四趟冒泡

36、排序過程演示7101262415253030第四趟冒泡排序過程演示7101261524253030第四趟冒泡排序過程演示7101261524253030第四趟結(jié)束冒泡排序過程演示7101261524253030第五趟冒泡排序過程演示7101261524253030第五趟冒泡排序過程演示7101261524253030第五趟冒泡排序過程演示7106121524253030第五趟冒泡排序過程演示7106121524253030第五趟冒泡排序過程演示7106121524253030第五趟結(jié)束冒泡排序過程演示7106121524253030第六趟冒泡排序過程演示7106121524253030第六趟冒

37、泡排序過程演示7610121524253030第六趟冒泡排序過程演示7610121524253030第六趟冒泡排序過程演示7610121524253030第六趟結(jié)束冒泡排序過程演示7610121524253030第七趟冒泡排序過程演示6710121524253030第七趟冒泡排序過程演示6710121524253030第七趟結(jié)束冒泡排序過程演示6710121524253030第八趟冒泡排序過程演示6710121524253030第八趟結(jié)束，冒泡排序完成插入排序過程演示2510301273124615原序列：插入排序過程演示2510301273124615第一趟：10插入排序過程演示251030

38、1273124615第一趟：10插入排序過程演示2525301273124615第一趟：10插入排序過程演示1025301273124615第一趟結(jié)束10插入排序過程演示1025301273124615第二趟30插入排序過程演示1025301273124615第二趟結(jié)束30插入排序過程演示1025301273124615第三趟12插入排序過程演示1025303073124615第三趟12插入排序過程演示1025303073124615第三趟12插入排序過程演示1025253073124615第三趟12插入排序過程演示1025253073124615第三趟12插入排序過程演示1012253073

39、124615第三趟結(jié)束12插入排序過程演示1012253073124615第四趟7插入排序過程演示10122530303124615第四趟7插入排序過程演示10122525303124615第四趟7插入排序過程演示10121225303124615第四趟7插入排序過程演示10101225303124615第四趟7插入排序過程演示7101225303124615第四趟結(jié)束插入排序過程演示7101225303124615第五趟31插入排序過程演示7101225303124615第五趟結(jié)束插入排序過程演示7101225303124615第六趟24插入排序過程演示7101225303131615第六趟

40、24插入排序過程演示7101225303031615第六趟24插入排序過程演示7101225253031615第六趟24插入排序過程演示7101224253031615第六趟結(jié)束24插入排序過程演示7101224253031615第七趟6插入排序過程演示71012242530313115第七趟6插入排序過程演示71012242530303115第七趟6插入排序過程演示71012242525303115第七趟6插入排序過程演示71012242425303115第七趟6插入排序過程演示71012122425303115第七趟6插入排序過程演示71010122425303115第七趟6插入排序過程演

41、示7710122425303115第七趟6插入排序過程演示6710122425303115第七趟結(jié)束插入排序過程演示6710122425303115第八趟15插入排序過程演示6710122425303131第八趟15插入排序過程演示6710122425303031第八趟15插入排序過程演示6710122425253031第八趟15插入排序過程演示6710122424253031第八趟15插入排序過程演示6710121524253031第八趟結(jié)束，插入排序結(jié)束15選擇排序過程演示原序列：數(shù)組2510301273124615下標012345678目前最小下標：選擇排序過程演示第一趟：數(shù)組25103

42、01273124615下標012345678目前最小下標：0選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：1選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：1選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：1選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：4選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：4選擇排序過程演示第一趟：數(shù)組25103012731

43、24615下標012345678目前最小下標：4選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：7選擇排序過程演示第一趟：數(shù)組2510301273124615下標012345678目前最小下標：7選擇排序過程演示第一趟：結(jié)束數(shù)組6103012731242515下標012345678目前最小下標：7選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：1選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：1選擇排序過程演示第二趟：數(shù)組610301273124251

44、5下標012345678目前最小下標：1選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：4選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：4選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：4選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：4選擇排序過程演示第二趟：數(shù)組6103012731242515下標012345678目前最小下標：4選擇排序過程演示第二趟：結(jié)束數(shù)組6730121031242515下標0

45、12345678目前最小下標：4選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：2選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：3選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：4選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：4選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：4選擇排序過程演示第三趟：數(shù)組6730121031242515下標0123456

46、78目前最小下標：4選擇排序過程演示第三趟：數(shù)組6730121031242515下標012345678目前最小下標：4選擇排序過程演示第三趟：結(jié)束數(shù)組6710123031242515下標012345678目前最小下標：4選擇排序過程演示第四趟：數(shù)組6710123031242515下標012345678目前最小下標：3選擇排序過程演示第五趟：數(shù)組6710123031242515下標012345678目前最小下標：4選擇排序過程演示第五趟：數(shù)組6710123031242515下標012345678目前最小下標：4選擇排序過程演示第五趟：數(shù)組6710123031242515下標012345678目前

47、最小下標：6選擇排序過程演示第五趟：數(shù)組6710123031242515下標012345678目前最小下標：6選擇排序過程演示第五趟：數(shù)組6710123031242515下標012345678目前最小下標：8選擇排序過程演示第五趟：結(jié)束數(shù)組6710121531242530下標012345678目前最小下標：8選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標：5選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標：6選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標

48、：6選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標：6選擇排序過程演示第六趟：結(jié)束數(shù)組6710121524312530下標012345678目前最小下標：6選擇排序過程演示第七趟：數(shù)組6710121524312530下標012345678目前最小下標：6選擇排序過程演示第七趟：數(shù)組6710121524312530下標012345678目前最小下標：7選擇排序過程演示第七趟：數(shù)組6710121524312530下標012345678目前最小下標：7選擇排序過程演示第七趟：結(jié)束數(shù)組6710121524253130下標012345678目前最小下標：7

49、選擇排序過程演示第八趟：數(shù)組6710121524253130下標012345678目前最小下標：7選擇排序過程演示第八趟：數(shù)組6710121524253130下標012345678目前最小下標：8選擇排序過程演示第八趟：結(jié)束，選擇排序結(jié)束數(shù)組6710121524253031下標012345678目前最小下標：8快速排序過程演示原序列：數(shù)組2510301273124615下標012345678快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組2510301273124615下標012345678大數(shù)下標：0 小數(shù)下標：7 交換快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組61030127

50、31242515下標012345678大數(shù)下標：0 小數(shù)下標：7 交換快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6103012731242515下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6103012731242515下標012345678大數(shù)下標： 2 小數(shù)下標：快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6103012731242515下標012345678大數(shù)下標： 2 小數(shù)下標：快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6103012731242515下標012345678大數(shù)下標： 2 小數(shù)下標：快速排

51、序過程演示第一趟：以最后一個元素15為基準數(shù)組6103012731242515下標012345678大數(shù)下標： 2 小數(shù)下標：4 交換快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6107123031242515下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6107123031242515下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第一趟：以最后一個元素15為基準數(shù)組6107123031242515下標012345678大數(shù)下標：4 小數(shù)下標：無快速排序過程演示第一趟：結(jié)束數(shù)組6107121531242530下標01234

52、5678大數(shù)下標：4 小數(shù)下標：無快速排序過程演示第二趟：以12為基準數(shù)組6107121531242530下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第二趟：以12為基準數(shù)組6107121531242530下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第二趟：以12為基準數(shù)組6107121531242530下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第二趟：以12為基準數(shù)組6107121531242530下標012345678大數(shù)下標：3 小數(shù)下標：無快速排序過程演示第二趟：以30為基準數(shù)組6107121531242530下標012345678大數(shù)

53、下標：5 小數(shù)下標：7 交換快速排序過程演示第二趟：以30為基準數(shù)組6107121525243130下標012345678大數(shù)下標： 小數(shù)下標：快速排序過程演示第二趟：以30為基準數(shù)組6107121525243130下標012345678大數(shù)下標：7 小數(shù)下標：無快速排序過程演示第二趟：結(jié)束數(shù)組6107121525243031下標012345678大數(shù)下標：7 小數(shù)下標：無快速排序過程演示第三趟：分別以7、24、31為基準數(shù)組6107121525243031下標012345678快速排序過程演示第三趟：結(jié)束數(shù)組6710121524253031下標012345678快速排序過程演示第四趟結(jié)束，排

54、序宣告結(jié)束數(shù)組6710121524253031下標012345678合并排序思想 合并排序算法是用分治策略實現(xiàn)對n個元素進行排序的算法。其基本思想是：當n=1時終止排序，否則將待排序元素分成大小大致相同的兩個子集，分別對兩個子集進行排序，最終將排好序的子集合并成為所要求的排好序的集合。 自底向上的合并排序：可以首先將數(shù)組中相鄰元素兩兩配對，用合并算法將它們排序，構(gòu)成n/2組長度為2的排好序的子數(shù)組段，然后再將它們排序成長度為4的排好序的子數(shù)組段，如此繼續(xù)下去，直至整個數(shù)組排好序。排序章節(jié)總結(jié)冒泡、插入、選擇是簡單排序，平均復(fù)雜度 ?？焖?、合并是較快的排序算法，平均復(fù)雜度 ?？焖倥判蛟谧顗那闆r下

55、的時間復(fù)雜度為 ，合并為快速排序的最壞情況是排好序的情況，與其它排序算法不同。簡單排序中，插入排序的復(fù)雜度與初態(tài)有關(guān)，另外兩個無關(guān)。插入排序可能在最后一趟之前，所有元素都不在最終位置。選擇、快速排序不穩(wěn)定，其它穩(wěn)定。 第六章排序：習(xí)題若待排序?qū)ο笮蛄性谂判蚯耙寻雌潢P(guān)鍵字遞增排列，則采用_比較次數(shù)最少【福建2006專升本】 A 直接插入排序 B 快速排序 C 合并排序 D 簡單選擇排序在下列排序算法中，時間復(fù)雜度為O(nlogn)的是_【福建2006專升本】 A 冒泡排序 B 簡單選擇排序 C 直接插入排序 D 堆排序答案 ：A D第六章排序：習(xí)題在待排序記錄已基本有序的前提下，下述排序方法中效

56、率最高的是_【福建2007專升本】 A 直接插入排序 B 簡單選擇排序 C 快速排序 D 歸并排序平均排序效率最好的排序方法是_【福建2009專升本】 A 直接插入排序 B 快速排序 C 簡單選擇排序 D 冒泡排序答案 ：A B第七章樹(層次數(shù)據(jù)結(jié)構(gòu))樹章節(jié)的重點內(nèi)容：樹的相關(guān)概念(度、高度、深度、層)。樹和二叉樹的三序遍歷。已知二叉樹前中或中后序畫二叉樹。樹中結(jié)點和度之間的關(guān)系。樹和二叉樹的轉(zhuǎn)換。(左兒子右兄弟)線索二叉樹（了解即可）。樹的定義樹是一個具有層次結(jié)構(gòu)的集合，它在客觀世界中廣泛存在。樹是由一個集合以及在該集合上定義的一種層次關(guān)系構(gòu)成的。集合中的元素是樹的結(jié)點，結(jié)點間的關(guān)系為父子關(guān)

57、系。樹結(jié)點之間的父子關(guān)系建立了樹的層次結(jié)構(gòu)。在這種層次結(jié)構(gòu)中，有一個結(jié)點具有特殊的地位，這個結(jié)點稱為該樹的根結(jié)點，或簡稱為樹根。樹的定義樹的遞歸定義單個結(jié)點是一棵樹，樹根就是該結(jié)點本身。設(shè)T1Tk是樹，他們的根結(jié)點為n1,nk。用一個新結(jié)點n作為n1,nk的父親，則得到一棵新樹。結(jié)點n就是新樹的根。結(jié)點n1,nk成為一組兄弟結(jié)點，它們都是結(jié)點n的兒子結(jié)點。還稱T1,Tk為結(jié)點n的子樹。為方便起見，將空集合也看作是樹，成為空樹，用表示?？諛渲袥]有結(jié)點。樹的定義及相關(guān)概念A(yù)左圖所示的樹，由結(jié)點的有限集A,B,C,D,E,F,G,H,I,J構(gòu)成。其中A是根結(jié)點。T中其余結(jié)點分成3個互不相交的子集T1

58、=B,E,F,I,JT2=C T3=D,G,HT1,T2,T3是根A的三棵子樹，且本身又都是一棵樹。CBEJIHGDF樹的定義及相關(guān)概念A(yù)一個結(jié)點的兒子結(jié)點個數(shù)稱為該結(jié)點的度。一棵樹的度是指該樹中結(jié)點最大度數(shù)。樹中度為零的結(jié)點稱為葉結(jié)點或終端結(jié)點。樹中度不為零的結(jié)點稱為分枝結(jié)點或非終端結(jié)點。除根結(jié)點外的分枝結(jié)點統(tǒng)稱為內(nèi)部結(jié)點。在左圖中，A,B,E的度分別為3，2，0其中A為根結(jié)點，B為內(nèi)部結(jié)點，E為葉結(jié)點，樹的度為3。CBEJIHGDF樹的定義及相關(guān)概念A(yù)4. 如果存在樹中的一個結(jié)點序列k1,k2,kj,使得結(jié)點ki是結(jié)點k(i+1)的父結(jié)點，則稱該結(jié)點序列是樹中從結(jié)點k1到結(jié)點kj的一條路徑

59、或道路。稱這條路經(jīng)的長度為j-1,它是該路徑所經(jīng)過的邊的數(shù)目。樹中任一結(jié)點有一條到其自身的長度為0的路徑。左圖中，結(jié)點A到結(jié)點I有一條路經(jīng)ABFI,它的長度為3CBEJIHGDF樹的定義及相關(guān)概念A(yù)5. 如果在樹中存在一條從結(jié)點k到結(jié)點m的路徑，則稱結(jié)點k是結(jié)點m的祖先，也稱結(jié)點m是結(jié)點k的子孫或后裔。在左圖中，結(jié)點F的祖先有A,B和F自己，而它的子孫包括F,I和J。6. 將樹中一個結(jié)點的非自身的祖先和子孫分別稱為該結(jié)點的真祖先和真子孫。在一棵樹中，樹根是唯一沒有真祖先的結(jié)點。葉結(jié)點是沒有真子孫的結(jié)點。子樹是樹中某一結(jié)點及其所有真子孫組成的一棵樹。CBEJIHGDF樹的定義及相關(guān)概念A(yù)7. 樹

60、中一個結(jié)點的高度是指從該結(jié)點到各葉結(jié)點的最長路經(jīng)的長度。樹的高度是指根結(jié)點的高度。在左圖中，B,C,D的高度分別為2,0,1,而樹的高度與結(jié)點A的高度相同為3。從樹根到任意結(jié)點n有唯一的一條路經(jīng)，稱這條路經(jīng)的長度為結(jié)點n的深度或?qū)訑?shù)。根結(jié)點的深度為0，其余結(jié)點的深度為其父結(jié)點的深度加1。深度相同的結(jié)點屬于同一層。在左圖中，A的深度為0，結(jié)點B,C,D的深度為1，結(jié)點E,F,G,H的深度為2，結(jié)點I,J的深度為3。在樹的第2層結(jié)點有E,F,G和H,樹的第0層只有一個根結(jié)點A.CBEJIHGDF樹的遍歷樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結(jié)點的系統(tǒng)的訪問，即依次對樹中每個結(jié)點訪問一