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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、 i n+1 )個(gè)位置上插入一個(gè)元素，元素的移動(dòng)次數(shù)為_(kāi)【 福建 2007 專(zhuān)升本】 A n-i+1 B n-i C i D i-1答案：A C A表習(xí)題鏈表的結(jié)點(diǎn)類(lèi)型定義如下:typedef struct node *link;struct node ListItem element; link left; link right;*p,*q,*r;刪除雙鏈表中結(jié)點(diǎn)p(由p指向的結(jié)點(diǎn))的操作是_【 福建 2008 專(zhuān)升本】 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é)點(diǎn)構(gòu)造為struct node int data;struct node *next; *p,*q,*r;刪除單鏈表中結(jié)點(diǎn)p(由p指向的結(jié)點(diǎn))后面的結(jié)點(diǎn)的操作不正確的是_【 福建 2006 專(zhuān)升本】 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個(gè)結(jié)點(diǎn),在

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

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

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

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

24、進(jìn)行插入操作。隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的，所以隊(duì)列又稱(chēng)為先進(jìn)先出表，簡(jiǎn)稱(chēng)FIFO表。假設(shè)隊(duì)列為a(1),a(2),a(n),那么a(1)就是隊(duì)首元素，a(n)為隊(duì)尾元素。隊(duì)列的常用運(yùn)算QueueEmpty(Q):測(cè)試隊(duì)列Q是否為空。QueueFull(Q):測(cè)試隊(duì)列Q是否已滿。QueueFirst(Q):返回隊(duì)列Q的隊(duì)首元素。QueueLast(Q):返回隊(duì)列Q的隊(duì)尾元素。EnterQueue(x,S):在隊(duì)列Q的隊(duì)尾插入元素x。DeleteQueue(Q):刪除并返回Q的隊(duì)首元素。指針實(shí)現(xiàn)隊(duì)列的結(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ù)組實(shí)現(xiàn)隊(duì)列的結(jié)構(gòu)typedef struct aque *Queue;typedef struct aque int maxsize; int front; int rear; QItem *queue;Aqueue;循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列添加元素的過(guò)程A10B2C34567DEFfrontrear隊(duì)列添加G:循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列添加元素的過(guò)程A10B2C34567DE

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

52、5678大數(shù)下標(biāo)：4 小數(shù)下標(biāo)：無(wú)快速排序過(guò)程演示第二趟：以12為基準(zhǔn)數(shù)組6107121531242530下標(biāo)012345678大數(shù)下標(biāo)： 小數(shù)下標(biāo)：快速排序過(guò)程演示第二趟：以12為基準(zhǔn)數(shù)組6107121531242530下標(biāo)012345678大數(shù)下標(biāo)： 小數(shù)下標(biāo)：快速排序過(guò)程演示第二趟：以12為基準(zhǔn)數(shù)組6107121531242530下標(biāo)012345678大數(shù)下標(biāo)： 小數(shù)下標(biāo)：快速排序過(guò)程演示第二趟：以12為基準(zhǔn)數(shù)組6107121531242530下標(biāo)012345678大數(shù)下標(biāo)：3 小數(shù)下標(biāo)：無(wú)快速排序過(guò)程演示第二趟：以30為基準(zhǔn)數(shù)組6107121531242530下標(biāo)012345678大數(shù)

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

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

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

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

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

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

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

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