數(shù)據(jù)結(jié)構(gòu)考試大綱

1、第一章概述一、概念一、數(shù)據(jù)結(jié)構(gòu)的要緊研究內(nèi)容：一般是研究數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))和邏輯 結(jié)構(gòu)，以及它們之間的彼此聯(lián)系；對每種結(jié)構(gòu)概念相適應(yīng)的各類運(yùn)算，設(shè)計(jì) 出相應(yīng)的算法，分析算法的效率。二、從邏輯上能夠把數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)、非線性結(jié)構(gòu)兩大類。即：數(shù)據(jù)邏輯 結(jié)構(gòu)除集合之外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。3、數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。4、數(shù)據(jù)的存儲結(jié)構(gòu)形式包括順序存儲、鏈?zhǔn)酱鎯Α⑺饕鎯蜕⒘写鎯?。二、算法一、程序和算法原那么上是有區(qū)別的。二、算法分析的兩個(gè)要緊方面是：時(shí)刻復(fù)雜度和空間復(fù)雜度第二章線性表一、順序表一、順序表中的地址計(jì)算公式：第一個(gè)元素的存儲地址是LOC

2、(ai),每一個(gè)元素占用L個(gè)存儲單元，并以所占的第一個(gè)單元的存儲地址作為數(shù)據(jù)元素 的存儲位置，那么第i個(gè)元素的存儲地址為：LOC(ai)=LOC(ai)+(i-1)* L (1 i next=p-next; p-next=q;二、刪除結(jié)點(diǎn)P后的結(jié)點(diǎn)q的語句：p-next=q-next; free(q);3、鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間：分兩部份，一部份寄存結(jié)點(diǎn)值，另一 部份寄存表示結(jié)點(diǎn)間關(guān)系的指針4、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并非必 然緊鄰。三、雙向鏈表一、在雙向鏈表存儲結(jié)構(gòu)中，刪除 p所指的結(jié)點(diǎn)時(shí)可修改指針：p-next-prior=p-prior; p-p

3、rior-next=p-next;二、雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是：q- next =p;q- prior =p- prior ;p- prior - next =q;p- prior =q;四、各類存儲結(jié)構(gòu)綜合一、順序表結(jié)構(gòu)適宜于進(jìn)行隨機(jī)存取，而鏈表適宜于進(jìn)行順序存取。二、單鏈表的每一個(gè)結(jié)點(diǎn)包括一個(gè)指針域，雙向鏈表的每一個(gè)結(jié)點(diǎn)包括兩個(gè)指 針域。五、例題和算法設(shè)計(jì)例1:順序表中第一個(gè)元素的存儲地址是50,每一個(gè)元素的長度為4,那么第10 個(gè)元素的地址是：LOC(M =LOC(a)+(10-1)* 4 =86例2:在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)最小值結(jié)點(diǎn)的算法。void del

4、ete (Linklist *L ) Linklist *p,*q;p=L；q= L-next ;while (q&q-next) if (q-next-datanext-data )p= q;q= q-next ;if(p-next) q=p-next ;p-next=q-next;free (q); /終止算法delete。例3：已知不帶頭結(jié)點(diǎn)的線性鏈表list ,鏈表中結(jié)點(diǎn)構(gòu)造為(data、link ),其中data為數(shù)據(jù)域，link為指針域。請寫一算法，將該鏈表按結(jié)點(diǎn)數(shù)據(jù)域的值 的大小從小到大從頭鏈接。LinkedList LinkListSort(LinkedList list)/

5、list是不帶頭結(jié)點(diǎn)的線性鏈表，鏈表結(jié)點(diǎn)構(gòu)造為 data和link兩個(gè)域， data是數(shù)據(jù)域，link是指針域。本算法將該鏈表按結(jié)點(diǎn)數(shù)據(jù)域的值的大 小，從小到大從頭鏈接。p=list-link;/p是工作指針，指向待排序的當(dāng)前元素。list-link=null;/假定第一個(gè)元素有序，即鏈表中現(xiàn)只有一個(gè)結(jié)點(diǎn)。while(p!=null)r=p-link;/ r 是 p 的后繼。q=list;if(q-datap-data、口處置待排序結(jié)點(diǎn)p比第一個(gè)元素結(jié)點(diǎn)小的情形p-link=list;list=p; /鏈表指針指向最小元素。else /查找元素值最小的結(jié)點(diǎn)。while(q-link!=null

6、&q-link-datadatA、q=q-link;p-link=q-link;/將當(dāng)前排序結(jié)點(diǎn)鏈入有序鏈表中。q-link=p; p=r; / p指向下個(gè)待排序結(jié)點(diǎn)。例4:將一個(gè)帶頭結(jié)點(diǎn)、數(shù)據(jù)項(xiàng)遞增有序的單向鏈表，從頭排列鏈表，使數(shù)據(jù) 項(xiàng)遞減有序。void invert(Linklist *la ) linklist *p,*q;p=la-next ；la-next= NULL ；while (p!= NULL)q= p-next ;p-next=la-next ;la-next=p ； p= q;)第3章棧和隊(duì)列一、棧一、棧的特點(diǎn)：先進(jìn)后出或稱作后進(jìn)先出二、入棧與出棧序列3、空棧：是不包括

7、任何元素的棧4、棧的應(yīng)用(1)在判別表達(dá)式中左，右括號是不是配對顯現(xiàn)的算法中，采納棧作為數(shù)據(jù) 結(jié)構(gòu)最正確。(2)在表達(dá)式求值、進(jìn)制轉(zhuǎn)換、函數(shù)或進(jìn)程的挪用等算法中，都要用到棧。二、隊(duì)列一、隊(duì)列的特點(diǎn)：先進(jìn)先出，在隊(duì)列中，通常許諾刪除的一端稱為隊(duì)頭，許諾插入的一端稱為隊(duì)尾。二、隊(duì)列的應(yīng)用：解決運(yùn)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打 印數(shù)據(jù)緩沖區(qū)，該緩沖區(qū)的邏輯結(jié)構(gòu)確實(shí)是一個(gè)隊(duì)列。3、循環(huán)隊(duì)列中的元素個(gè)數(shù)計(jì)算公式。4、對順序棧作操作運(yùn)算時(shí)，進(jìn)棧應(yīng)先判別棧是不是滿，出棧時(shí)應(yīng)先判別棧是不 是空。且順序隊(duì)列和循環(huán)隊(duì)列關(guān)于隊(duì)滿和隊(duì)空的判定條件是不一樣的。五、設(shè)循環(huán)隊(duì)列寄存在向量M+1中，設(shè)：隊(duì)頭指

8、針為，隊(duì)尾指針為，采用捐軀一個(gè)單元的方法來區(qū)分隊(duì)滿和隊(duì)空。那么：出隊(duì)操作時(shí)，隊(duì)頭指針轉(zhuǎn)變可表示為：=(s.front+1)%(M+1)；隊(duì)滿的條件為：(s.rear+1)%(M+1)=；三、棧與隊(duì)列的存儲棧和隊(duì)列都是操作受限的線性結(jié)構(gòu)，都能夠用順序存儲和鏈?zhǔn)酱鎯?。四、例題分析例1：有六個(gè)元素6, 5, 4, 3, 2, 1的順序進(jìn)棧，那么：(5 4 3 6 1 2 )不是合法的出棧序列例2:設(shè)一個(gè)棧的輸入序列是1 , 2, 3, 4, 5,以下序列中，(D )是棧的合 法輸出序列。A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 4例3:數(shù)組Q n

9、用來表示一個(gè)循環(huán)隊(duì)列，front為當(dāng)前隊(duì)列頭元素的前一名 置,rear為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于n ,計(jì)算隊(duì)列中元 素個(gè)數(shù)的公式為：(n+rear-fron)%n例4:假設(shè)為循環(huán)隊(duì)列分派的向量空間為Q25(下標(biāo)從0開始)，假設(shè)隊(duì)列的長度和隊(duì)頭指針值別離為15和20,那么當(dāng)前隊(duì)尾指針的值為：10。例5:循環(huán)隊(duì)列存儲在數(shù)組 A0.m中，那么入隊(duì)時(shí)的操作為(D )。A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)第4、5章串和數(shù)組一、用一、用的長度的概念：是指

10、用中所含字符的個(gè)數(shù)二、子用的概念，例如：“DTA不是“DATAA的子用。3、用的存儲結(jié)構(gòu)中，堆分派存儲是一種動態(tài)存儲結(jié)構(gòu)。4、空審是任意用的字申。二、數(shù)組一、數(shù)組的地址計(jì)算公式：設(shè)二維數(shù)組是 Ac1.d1, c2.d2,那個(gè)地址c1,c2不必然是0。那么行優(yōu)先存儲時(shí)的地址公式為：LOC同 尸LOC(a1,c2)+(i-c 1)*(d 2-c2+1)+j-c 2*L二維數(shù)組列優(yōu)先存儲的通式為：LOC(a 尸LOC(a1,c2)+(j-c 2)*(d 1-C1+1)+i-c i*L二、特殊矩陣的緊縮存儲及其地址映射公式三、例題分析例1:設(shè)有數(shù)組Ai,j,數(shù)組的每一個(gè)元素長度為4字節(jié)，i的值為1到7

11、, j的值為1到10,數(shù)組從內(nèi)存首地址Loc開始順序寄存，當(dāng)用以行為主寄存 時(shí)，元素A4,6的存儲首地址為(Loc+140 );當(dāng)用以列為主寄存時(shí)， 元素A4,6的存儲首地址為(Loc+152 )。例2:設(shè)有一個(gè)9階的對稱矩陣，采納緊縮存儲方式，以行序?yàn)橹鞔鎯Γ琣-為第一元素，其存儲地址為1,每一個(gè)元素占2個(gè)地址空間，那么a 5的 地址為(51 )，則a5,7的地址為(51 )。例3:設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的 順序寄存在一維數(shù)組 B1.n(n+1)中，對上述任一元素aij (1 i ,j lchild=null & p-rchlid=null3、在二叉樹

12、中，每一個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。二、二叉樹的性質(zhì)、性質(zhì)2:二叉的高與結(jié)點(diǎn)之間的關(guān)系、性質(zhì)5:完全二叉樹中雙親、左小孩與右小孩之間的關(guān)系及其應(yīng)用3、完全二叉樹和滿二叉樹的關(guān)系：滿二叉樹必然是完全二叉樹，完全二叉樹 不必然是滿二叉樹。4、在滿二叉樹中，只有度為0或度為2的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)。五、性質(zhì)3:度為0、一、2三類結(jié)點(diǎn)間的關(guān)系三、二叉樹的遍歷一、由二叉樹的先序序列和中序序列能夠唯一確信一棵二叉樹。由二叉樹的后序序列和中序序列能夠唯一確信一棵二叉樹。但由二叉樹的先序序列和后 序序列不能唯一確信一棵二叉樹。二、在二叉樹結(jié)點(diǎn)的先序序列、中序序列和后序序列中，所有葉子結(jié)點(diǎn)的前 后順序完全相同

13、。四、樹的存儲結(jié)構(gòu)、樹的遍歷、樹與二叉樹之間的轉(zhuǎn)換一、把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的，且沒有右子樹。即：由樹轉(zhuǎn)化為二叉樹，其根結(jié)點(diǎn)的右子樹老是空的。二、樹轉(zhuǎn)換成二叉樹3、樹的存儲形式有：雙親表示法、小孩鏈表表示法、小孩兄弟表示法等，但 沒有順序存儲表示法。4、樹的遍歷五、叢林轉(zhuǎn)換成二叉樹：注意其左右子樹上的結(jié)點(diǎn)個(gè)數(shù)。設(shè)叢林F對應(yīng)的二叉樹為B,它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié) 點(diǎn)個(gè)數(shù)為n,叢林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是 m-n。若是叢林F中有三棵樹， 第一,第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)別離為 M1, M2和M3那么與叢林F對應(yīng) 的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是 M2+M 3

14、五、哈夫曼樹一、特點(diǎn)二、組成和應(yīng)用六、例題分析一、二叉樹性質(zhì)應(yīng)用例1： 一個(gè)具有1000個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)介于10至1000之間，一個(gè)具有 1000個(gè)結(jié)點(diǎn)的完全二叉樹的高h(yuǎn)等于10。例2:具有256個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 9 （注意：不能是8）。例3:如某二叉樹有30個(gè)葉子結(jié)點(diǎn)，有40個(gè)結(jié)點(diǎn)僅有一個(gè)小孩，那么該叉樹的總結(jié)點(diǎn)數(shù)為：99例4: 一棵完全二叉樹上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是 500個(gè)，若是有1000個(gè)結(jié)點(diǎn)，那么其葉子結(jié)點(diǎn)的個(gè)數(shù)是 501個(gè)。、已知中序序列和后序序列確信一棵樹，已知中序序列和先序序列確信一棵樹例1:已知一棵二叉樹的先序序列是DBFEACG H青畫出這棵二

15、叉樹，并給出后序序列。答：該二叉樹如右圖后序序歹h DFEBHGCAABDEFCG也序序歹U是例2:已知一棵二叉樹的中序序列是DFEBHGC A青畫出這棵二叉樹，并給出先序序列答：該二叉樹如右圖DBEFAGH Ct序序列J是0ACGHF先序序歹h DFEBHGCA3、樹和二叉之間的轉(zhuǎn)換例：請按小孩兄弟表示法將以下樹結(jié)構(gòu)轉(zhuǎn)換為對應(yīng)的二叉樹，并給出該樹的一種先序遍歷序列和后序遍歷序列答：對應(yīng)的二叉樹:樹的一種先序遍歷序列：ABEFGCDHI樹的一種后序遍歷序列：EFGBCHIDA4、哈夫曼樹生成及哈夫曼編碼例：假設(shè)用于通信的電文僅由 7個(gè)字母組成，字母在電文中顯現(xiàn)的次數(shù)別離為這8個(gè)字母設(shè)計(jì)哈夫曼編

16、碼016:011 8:10010 : 101 24 : 11答：哈夫曼樹如下（形狀不唯一）5,30,8 , 10,7,16,24 。請依照各個(gè)字符的顯現(xiàn)概率構(gòu)造一棵哈夫曼樹，并為哈夫曼編碼（編碼不唯一）30:00 5: 0100 7 : 0101一、圖的概念和存儲結(jié)構(gòu)一、圖能夠沒有邊，但不能沒有極點(diǎn)。二、鄰接表和鄰接矩陣都可用于存儲有向圖和無向圖。3、在有向圖中，丫1、2與丫2田 是兩條不同的邊。4、在無向圖G的鄰接矩陣A中，假設(shè)Aij 等于1,那么Aji 等于1五、完全圖中，極點(diǎn)數(shù)和邊數(shù)的關(guān)系二、圖的遍歷一、圖的遍歷方式：深度優(yōu)先遍歷、廣度優(yōu)先遍歷二、假設(shè)從無向圖的任意一個(gè)極點(diǎn)動身進(jìn)行一次深

17、度優(yōu)先搜索能夠訪問圖中 所有的極點(diǎn)，那么該圖必然是連通圖。3、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助隊(duì)列來實(shí)現(xiàn)算法。4、深度優(yōu)先遍歷算通常采納遞歸或借助棧來實(shí)現(xiàn)。三、最小生成樹一、帶權(quán)圖最小生成樹不必然是唯一的，能夠有一棵或多棵，但其最小生成樹的代價(jià)是唯一的二、最小生成樹的兩種生成算法四、AOM與 AOEW一、拓?fù)渑判蚍绞侥軌蚺卸ǔ鲆粋€(gè)有向圖是不是有環(huán)。五、例題分析例1:具有9個(gè)極點(diǎn)的有向完全圖有72條弧。具有9個(gè)極點(diǎn)的無向圖，邊的總數(shù)最多為 36。例2:圖的鄰接矩陣如右圖所示，那么從極點(diǎn) V0動身按10 0 1 。I 0 0 0 110 10 10110 10 0 10例3:已知一個(gè)圖的

18、采納二維數(shù)組表示的鄰接矩陣如下圖所示，請回答以深度優(yōu)先遍歷的結(jié)果是(0,3,6,1,5,4,2)下問題：(1)畫出該鄰接矩陣對應(yīng)的圖。(2)請畫出自極點(diǎn)v1動身進(jìn)行遍歷所得的深度優(yōu)先遍歷生成樹例4:已知一個(gè)圖的采納二維數(shù)組表示的鄰接表如下圖所示，請回答以下問題:(1)畫出該鄰接表對應(yīng)的圖(2)請畫出自極點(diǎn)v1動身進(jìn)行遍歷所得的廣度優(yōu)先遍歷生成樹廣度優(yōu)先遍歷生成樹如下圖第9章查找一、順序查找和索引（分塊）查找的算法思想一、索引查找中，數(shù)據(jù)的組織特點(diǎn)是：塊內(nèi)可無序，塊間要有序。二、假設(shè)查找表的長度為n,那么順序查找法的平均查找長度為（n+1） /23、順序查找算法能夠適用于有序表、無序表，能夠采納

19、順序存儲和鏈?zhǔn)酱鎯Α?二、折半查找一、適用于折半查找的表的存儲方式及元素排列要求：順序方式存儲，元素有序二、折半查找中，元素的比較次數(shù)3、對有序表而言，采納折半查找并非是總比采納順序查找法速度快。三、二叉排序樹、概念：二叉排序樹的左子樹不為空，那么左子樹上所有結(jié)點(diǎn)的值均小于 它的根結(jié)點(diǎn)值，右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根 結(jié)點(diǎn)的值。二、關(guān)于一個(gè)二叉排序樹，按二叉樹層次進(jìn)行遍歷能夠取得一個(gè)有序序列。3、關(guān)于兩棵具有相同關(guān)鍵字但形狀不同的二叉排序樹，按中序遍歷它們?nèi)〉?的序列的順序是一樣的。4、平穩(wěn)二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的平穩(wěn) 因子。四、哈希查找一、

20、散列法是一種將關(guān)鍵字轉(zhuǎn)換為存儲地址的存儲方式。二、哈希函數(shù)的選擇要視情形而定，不存在專門好與壞的哈希函數(shù)。3、哈希表的生成五、例題分析一、折半查找例一、在有序表A1.25中，按二分查找方式進(jìn)行查找，查找長度為5的元 素個(gè)數(shù)是10個(gè)例2:在有序表(3, 5, 8, 15, 25, 34, 55, 78, 90, 100)中采納折半查 找方式，查找表中元素 58,那么它將依次與表中(25 , 78, 340, 55 ) 比較大小，查找結(jié)果是失敗。二、二叉排序樹構(gòu)造例1:別離以以下序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不 同的是(B )。(105, 85, 95 , 60 , 125, 1

21、10, 140)(105, 60, 85 , 95 , 125, 110, 140)(105, 125, 110, 140, 85, 60 , 95)(105, 85, 60 , 95 , 125, 140, 110)例2:給定關(guān)鍵字序列21, 88, 20, 10, 13, 12, 24, 31,若采納二叉排序 樹查找，請回答以下問題：(1)畫出二叉排序樹查找的二叉排序樹。(2)假定每一個(gè)元素的查找概率相等，那么查找成功時(shí)的平均查找長度是多少？答：(1)二叉排序樹(關(guān)鍵字順序已確信，該二叉排序樹唯一)如以下圖所示:(2)從上圖能夠取得二叉排序樹查找的成功平均查找長度為：ASL=(1+2*2+

22、3*2+4*2+5*1)/8=33、哈希表構(gòu)造例1:設(shè)哈希表長為15,哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵 字為26, 38, 72, 84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用 線性探測再散列法解決沖突，那么放入的位置是：8;用二次探測法解決沖突，那么放入的位置是：9。例2:設(shè)哈希(Hash)表的地址范圍為017,哈希函數(shù)為：H(K)=K MOD 16。K為關(guān)鍵字，用線性探測法再散列法處置沖突，輸入關(guān)鍵字序列：(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)造出Hash表，試回答以下問題：(1)按關(guān)鍵字的輸入順序構(gòu)造哈希表，畫

23、出所構(gòu)造哈希表的示用意。(2)求所構(gòu)造哈希表查找成功時(shí)的平均查找長度 ASL答：(1)最后取得的哈希表示用意如下表所示：012345678910111213141516173217634924401030314647(2) ASL=1/11 (6+ 2+3X3) = 17/11=1.5454545454例3、設(shè)關(guān)鍵字的輸入序列為：(47, 7, 29, 11, 16, 92, 22, 8, 3),哈希表 的地址范圍為010,哈希函數(shù)為：H (K) =K MOD 11 K為關(guān)鍵字值，采納 線性探測法處置沖突，請回答下面兩個(gè)問題：(1)按關(guān)鍵字的輸入順序構(gòu)造哈希表，畫出所構(gòu)造哈希表的示用意。（2）

24、求所構(gòu)造哈希表查找成功時(shí)的平均查找長度 ASL答：（1）最后取得的哈希表示用意如下表所示：地址編號012345678910關(guān)鍵字值112247921637298(2) AS上(1+2+1+1+1+4+1+2+2 19=5/3=第10章排序一、各類排序的算法思想一、內(nèi)部排序的概念：內(nèi)部排序確實(shí)是整個(gè)排序進(jìn)程完全在內(nèi)存中進(jìn)行的排 序。二、算法穩(wěn)固性的概念。二、插入排序一、直接插入排序時(shí)，關(guān)鍵字的比較次數(shù)與記錄的初始排列有關(guān)，初始序列順 序時(shí)比較次數(shù)最少，初始序列倒序時(shí)比較次數(shù)最多。二、直接插入排序的思想。3、希爾排序的算法思想，能寫出每一趟排序的結(jié)果序列。4、希爾排序是不是是穩(wěn)固的排序方式，并能說

25、明緣故。三、選擇排序一、概念：從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方式，稱為選擇排序二、堆排序：關(guān)于一個(gè)堆，按二叉樹層次進(jìn)行遍歷不能取得一個(gè)有序序列。四、互換排序一、對n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在從大到小排列好（倒序） 的情形下比較的次數(shù)最多，屬于最壞的情形，其需要的時(shí)刻是O （n2）在從小到大排列好（順序）的情形下比較的次數(shù)最少。二、快速排序算法思想及其應(yīng)用,能寫出每一趟排序的結(jié)果序列。3、快速排序是不是是穩(wěn)固的排序方式，并能說明緣故。五、歸并排序一、對n個(gè)記錄的集合進(jìn)行歸并排序，所需要的時(shí)刻是 O（nlog2n）。六、例題分析與算法描述一、插入

26、排序例 1:給定一組關(guān)鍵字序列15, 25, 10, 40, 25*, 35, 12, 30, 20, 24, 5),其中20和20*表示值相同的兩個(gè)關(guān)鍵字，采納希爾排序方式由小到 大排序，dk依次取5, 3, 1。(1)請寫出排序進(jìn)程(每趟排序的結(jié)果序列)。(2)希爾排序是不是穩(wěn)固的排序？什么緣故？答：(1)每趟排序的結(jié)果序列為： TOC o 1-5 h z 初態(tài)：15 , 25,10,40,25*, 35,12,30,20,24, 5第一趟(Dk=5): 5 ,12,10,20, 25*,15,25,30,40, 24,35第二趟(Dk=3):5, 12,10,20,25*, 15, 25

27、,30,40,24,35第三趟(Dk=1):5, 10,12,20,15, 25*, 25,24,30,35,40最后取得的排序序列為：5, 10, 12, 20, 15, 25*, 25, 24, 30, 35, 40(2)希爾排序不是穩(wěn)固的排序，因?yàn)橹迪嗤膬蓚€(gè)關(guān)鍵字25和25*在排序前后位置發(fā)生了改變。例2:對序列16, 10, 7, 8, 22, 1 , 5進(jìn)行排序，進(jìn)行一趟排序后，取得的排列為10, 16, 7, 8, 22, 1 , 5),那么采納的是(C )排序算法。A.簡單選擇B, 希爾 C.直接插入D. 歸并二、堆排序例1:假設(shè)一組記錄的排序碼為(50, 79, 56, 38

28、, 40, 90),那么利用堆排 序的方式成立的初始堆為(90, 79, 50, 38, 40, 46)。例2:以下關(guān)鍵字序列中，(D )是堆。A . 16, 72, 31,23, 94, 53 B. 94, 23, 31, 72, 16, 53C. 16, 53, 23, 94, 31, 72 D . 16, 23, 53, 31, 94, 723、快速排序和冒泡排序例1:假設(shè)一組記錄的排序碼為(50, 79 , 56, 38, 40, 85),那么利用快速 排序的方式，以第一個(gè)記錄為基準(zhǔn)取得的一次劃分結(jié)果為：40 38 50 56 79 85例2：設(shè)有一個(gè)整型數(shù)組中寄存了一個(gè)無序的序列k

29、一、k二、kn?，F(xiàn)要求將kn放在將元素排序后的正確位置上，要求比較關(guān)鍵字的次數(shù)不超過n0那么可用快速排序算法例3：設(shè)有一個(gè)整型數(shù)組中寄存了一個(gè)序列 k、k二、kn。實(shí)現(xiàn)該序列的升序排列。要求：該算法在最好情形下(原始序列為升序時(shí))一趟排序能夠終止，時(shí)刻復(fù)雜度為 O(n)。那么可用冒泡排序算法。例 4:關(guān)鍵字序列為20, 14, 20*, 33, 87, 22, 2, 10, 72,其中，18和* .一 一一 . . . .18表示兩個(gè)值相等的關(guān)鍵字，采納快速排序算法由小到大進(jìn)行排序， 請 回答下面兩個(gè)問題：(1)寫出排序進(jìn)程(每趟排序后的關(guān)鍵字序列)(2)快速排序是不是穩(wěn)固的排序算法？什么緣故?答：(1)每趟排序結(jié)果初始序列：20, 14, 第一趟：10 14 20