專升本數(shù)據(jù)結構

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

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

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

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

5、個量作為輸出。(3)確定性：組成算法的每條指令是清晰，無歧義的。(4)有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。(5)可行性：任意合法輸入都對應正確輸出算法復雜性分析 算法復雜性 = 算法所需要的計算機資源。算法的時間復雜性T(n)。算法的空間復雜性S(n)。數(shù)據(jù)結構主要討論時間復雜性。時間復雜性與問題規(guī)模和數(shù)據(jù)初始狀態(tài)有關，與其它內(nèi)容無關。最壞情況、最好情況和平均情況下時間復雜性三種情況下時間復雜性是針對初始數(shù)據(jù)進行分類的，與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符號僅在乎整個表達式的主項（值最大的項）。習題下列函數(shù)中漸進時間復雜度最小的是_?！?2009 專升本】答:A若一個算法中的語句頻度之和為T(n) = 3720n+4nlogn，則算法的時間復雜度為_ 。【 2007 專升本】 O(nlogn)習題算法的計算量的大小稱為計算的_【北京郵電大學2000 二、3 】A 效率 B 復雜性 C 現(xiàn)實性 D 難度算法的時間復雜度取決于_【中科院計算所 1998 二、1】A僅和問題的規(guī)模有關 B 僅和待處理數(shù)據(jù)的初態(tài)有關C和問題的規(guī)模及待處理數(shù)據(jù)的初態(tài)有關D和問題的規(guī)模、

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

8、L):測試表L是否為空。ListLength(L):表L的長度。ListLocate(x,L):元素x在表L中的位置。若x在表中重復出現(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)主要有順序實現(xiàn)和鏈式實現(xiàn)。順序實現(xiàn)就是順序表，也就是數(shù)組實現(xiàn)。 在這種實現(xiàn)方式下表的容量是固定的。鏈式

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

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

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

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

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

14、的方式將物理上并不相鄰的單元串聯(lián)起來。這種實現(xiàn)方式的優(yōu)點有：插入刪除不需要移動元素表容量可任意變化這種實現(xiàn)方式的缺點有：需要額外的指針空間查找指定位置元素的復雜度高單鏈表（指針實現(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個結點后插入y指向的結點a(1)a(2)a(3)a(n)f

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

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

17、能為空某鏈表中最常見的操作是在已知的一個結點之前插入一個新的結點和刪除其之前一個結點，則采用 _存儲方式最節(jié)省運算時間【 福建 2009 專升本】 A 雙向鏈表 B 帶頭指針的單向鏈表 C 帶尾指針的單向鏈表 D 單向循環(huán)鏈表答案：A A表習題下述哪一條是順序存儲方式的優(yōu)點_【 福建 2007 專升本】 A 存儲密度大 B 插入運算方便 C 刪除運算方便 D 可方便地用于各種邏輯結構的存儲表示對于只在表的首、尾進行插入操作的線性表，宜采用的存儲結構為_【 福建 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表習題鏈表的結點類型定義如下:typedef struct node *link;struct node ListItem element; link left; link right;*p,*q,*r;刪除雙鏈表中結點p(由p指向的結點)的操作是_【 福建 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表習題已知單鏈表結點構造為struct node int data;struct node *next; *p,*q,*r;刪除單鏈表中結點p(由p指向的結點)后面的結點的操作不正確的是_【 福建 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個結點,在

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

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

23、要會記錄出入棧的情況。棧的習題假設進棧的元素序列依次是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ù)結構)隊列是一種特殊的表，這種表只在表首進行刪除操作，在表尾

24、進行插入操作。隊列的修改是按先進先出的原則進行的，所以隊列又稱為先進先出表，簡稱FIFO表。假設隊列為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)隊列的結構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)隊列的結構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ù)結構。循環(huán)數(shù)組實現(xiàn)隊列是本章節(jié)重點。重點掌握front和rear游標如何判空、判滿、計算隊列長度、入隊、出隊等。隊列的習題設數(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ù)據(jù)的存儲結構無關_ 【 福建 2007 專升本】 A 隊列 B 靜態(tài)數(shù)組 線索二叉樹 D 雙向鏈表會引起循環(huán)隊列隊頭位置發(fā)生變化的操作是_【 福建 2008 專升本】A) 取隊首元素B) 入隊列C) 取隊尾元素D) 出隊列答案：隊列的習題若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為_【浙江

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

30、存儲器上，待排序的文件無法一次裝入內(nèi)存，需要在內(nèi)存和外部存儲器之間進行多次數(shù)據(jù)交換，以達到排序整個文件的目的。外部排序最常用的算法是多路歸并排序，即將原文件分解成多個能夠一次性裝人內(nèi)存的部分，分別把每一部分調(diào)入內(nèi)存完成排序。然后，對已經(jīng)排序的子文件進行歸并排序。內(nèi)部排序： 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。 內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。 第六章排序若待排序的序列中，存在多個具有相同關鍵字的記錄，經(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交換，第一趟結束，30確定位置冒泡排序過程演示1025127302461530第一趟結束，30確定位置冒泡排序過程演示1025127302461530第二趟冒泡排序過程演示1025127302461530第二趟冒泡排序過程演示1012257302461530第二趟冒泡排序過程演示1012257302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725302461530第二趟冒泡排序過程演示1012725243061530第二趟

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

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

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

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

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

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

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

41、示7710122425303115第七趟6插入排序過程演示6710122425303115第七趟結束插入排序過程演示6710122425303115第八趟15插入排序過程演示6710122425303131第八趟15插入排序過程演示6710122425303031第八趟15插入排序過程演示6710122425253031第八趟15插入排序過程演示6710122424253031第八趟15插入排序過程演示6710121524253031第八趟結束，插入排序結束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選擇排序過程演示第一趟：結束數(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選擇排序過程演示第二趟：結束數(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選擇排序過程演示第三趟：結束數(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選擇排序過程演示第五趟：結束數(shù)組6710121531242530下標012345678目前最小下標：8選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標：5選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標：6選擇排序過程演示第六趟：數(shù)組6710121531242530下標012345678目前最小下標

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

49、選擇排序過程演示第八趟：數(shù)組6710121524253130下標012345678目前最小下標：7選擇排序過程演示第八趟：數(shù)組6710121524253130下標012345678目前最小下標：8選擇排序過程演示第八趟：結束，選擇排序結束數(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ù)下標：無快速排序過程演示第一趟：結束數(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ù)下標：無快速排序過程演示第二趟：結束數(shù)組6107121525243031下標012345678大數(shù)下標：7 小數(shù)下標：無快速排序過程演示第三趟：分別以7、24、31為基準數(shù)組6107121525243031下標012345678快速排序過程演示第三趟：結束數(shù)組6710121524253031下標012345678快速排序過程演示第四趟結束，排

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

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

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

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

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

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

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