【正文】 }。 [high]=[low]。amp。 [low]=[high]。amp。 pivotkey=[low]。[j]=temp。void quickpass(Sqlist l,int low,int high,int j){ //本算法將第j個(gè)記錄快速放到它排序后的位置上 if(j!=low) { temp=[w]。分析：此問(wèn)題考查對(duì)各種排序算法的理解，能夠?qū)Ω鞣N排序算法進(jìn)行比較，選擇適合此問(wèn)題的排序算法。 b。 a[w]=a[b]。}else if(a[w]==1) w++。 //紅色移到最左邊r++。 a[w]=a[r]。void flag(int a[], int len){ int r=0,w=0,b=len1,temp。}}2．荷蘭國(guó)旗問(wèn)題設(shè)有一個(gè)僅由紅、白、藍(lán)三種顏色的條塊組成的條塊序列，用一個(gè)時(shí)間復(fù)雜度為O(n)的算法，使得這些條塊按紅、白、藍(lán)的順序排列，即排成荷蘭國(guó)旗圖案。j++) if([j][i]) count++。i++) { for(j=0,count=0。void countsort(Sqlist la,Sqlist lb){ for(i=0。A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．簡(jiǎn)單選擇排序（二）綜合題1．計(jì)數(shù)排序思想：對(duì)一個(gè)待排序的表進(jìn)行排序，將排序結(jié)果存放到另一個(gè)新的表中（關(guān)鍵字不同）。A．希爾排序 B. 堆排序 C. 選擇排序 D. 歸并排序 6．下列排序算法中，在待排序數(shù)據(jù)已有序時(shí)，花費(fèi)時(shí)間反而最多的是( C )排序。A．直接插入 B. 二分法插入 C. 快速排序 D. 歸并排序 4．下列排序算法中( C )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。 A．插入 B. 選擇 C. 冒泡 D. 快速2．下面給出的四種排序方法中，排序過(guò)程中的比較次數(shù)與初始序列有關(guān)的是 ( B ) 。分析：這一章主要是講各種排序方法，大綱中列出的方法比較多，因?yàn)橹R(shí)點(diǎn)相對(duì)來(lái)說(shuō)比較小也比較零散，一般情況下出選擇題的概率要多一些，要掌握各種方法的思想并能區(qū)別，如果出綜合題實(shí)在也是第2章內(nèi)容的應(yīng)用。（二）綜合題近兩年沒(méi)有出綜合題，此章綜合題一般會(huì)和第二章聯(lián)合來(lái)出，單獨(dú)出綜合題的可能性不大。 分析：答案是B，此題考查排序的調(diào)整過(guò)程。6．（11年）已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過(guò)程中元素之間進(jìn)行的比較次數(shù)是（ ）。 分析：答案是A，此題考查起泡排序、希爾排序、歸并排序和基數(shù)排序的思想。 4.（10年）對(duì)一組數(shù)據(jù)（2，12，16，88，5，10）進(jìn)行排序，若前三趟排序結(jié)果如下（ ）。3.（10年）采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（ ）。2.（09年）若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是（ ）。第10章 內(nèi)部排序一、考研知識(shí)點(diǎn)（一）排序的基本概念（二）插入排序（三）氣泡排序（bubble sort）（四）簡(jiǎn)單選擇排序（五）希爾排序（shell sort）（六）快速排序（七）堆排序（八）二路歸并排序（merge sort）（九）基數(shù)排序（十）各種內(nèi)部排序算法的比較（十一）內(nèi)部排序算法的應(yīng)用二、考研真題（一）選擇題1.（09年）已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（ ）。分析：考查平衡二叉樹的構(gòu)造過(guò)程，注意在構(gòu)造時(shí)結(jié)點(diǎn)失去平衡先調(diào)整最下層的失衡結(jié)點(diǎn)。分析：考查哈希表的構(gòu)造過(guò)程。 （2）存放元素59需要搜索的次數(shù)是（ C ）。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。4. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是( C ) 。 3．二叉查找樹的查找效率與二叉樹的(（1）A )有關(guān), 在 (（2）C)時(shí)其查找效率最低。四、練習(xí)題（一）選擇題1．當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度( C )。分析：這一章可以認(rèn)為是線性表和二叉樹在查找中的應(yīng)用，利用前面所學(xué)知識(shí)來(lái)解決新的問(wèn)題，重點(diǎn)是分析各種查找方式下的時(shí)間效率，選擇題和綜合題都可以出。分析：此題考查哈希表的構(gòu)造和沖突解決，以及裝填因子的計(jì)算。（二）綜合題1.（10年）將關(guān)鍵字序列（1114）散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組散列函數(shù)維：H（key）=（key3）MOD T，處理沖突采用線性探測(cè)再散列法，要求裝填（載）。 、III分析：答案是B，此題考查哈希表的構(gòu)造和查找。6．（11年）為提高散列表的查找效率，可以采取的正確措施是（ ）。 ,25,71,68,33,34分析：答案為A，此題考查二叉排序樹的查找。5．（11年）對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是（ ）。 ,48 ,48 ,53 ,90分析：答案是C，此題考查平衡二叉樹的調(diào)整過(guò)程。分析：答案是D，此題考查B樹的定義，題目出的不太嚴(yán)格，但是利用排除法可以得到答案。分析：答案是B，此題考查平衡二叉樹的定義。5．下表給出了某工程各工序之間的優(yōu)先關(guān)系和各工序所需時(shí)間（1）畫出相應(yīng)的AOE網(wǎng)（2）列出各事件的最早發(fā)生時(shí)間,最遲發(fā)生時(shí)間（3）找出關(guān)鍵路徑并指明完成該工程所需最短時(shí)間. 工序代號(hào)ABC DEFGHIJKLMN所需時(shí)間1510508154030015 1206015302040先驅(qū)工作A,BBC,DBEG,IEIF,IH,J,KLG分析：此題考查關(guān)鍵路徑的求解過(guò)程，求解過(guò)程略。表1設(shè)備年初價(jià)格第1年第2年第3年第4年第5年1111121213表2 維修費(fèi)用使用年數(shù)0112233445維修費(fèi)用5681118分析：此問(wèn)題同樣可以歸為最短路徑問(wèn)題，假定每年年初都購(gòu)置新設(shè)備，可以把每年年初作為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間的連線表示設(shè)備的使用情況，權(quán)值用使用過(guò)程中的費(fèi)用表示，這樣可以構(gòu)造一個(gè)圖，在圖中求從第一年年初到第五年末的最短路徑，路徑上的頂點(diǎn)就是設(shè)備更新計(jì)劃。若購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)用；若繼續(xù)使用舊設(shè)備，則需支付一定的維修費(fèi)用。解答：先求出任意兩點(diǎn)間的最短路徑下表所示：ABCDEFA0267811B204569C640125D751014E862103F1195430將每行數(shù)字分別乘以各村小學(xué)生人數(shù)得下表：ABCDEFA0100300350400550B800160200240360C360240060120300D1401002002080E560420140700210F9908104503602700按列相加其總和最小的列所對(duì)應(yīng)村子即是所求村子。擬合建一所小學(xué)，已知A處有小學(xué)生50人，B處40人，C處60人，C處20人，E處70人，F(xiàn)處90人，問(wèn)小學(xué)應(yīng)該建在哪個(gè)村子，是學(xué)生上學(xué)最為方便（走的總路程最短）。分析：每個(gè)頂點(diǎn)到其余各頂點(diǎn)最短路徑之和最短的一個(gè)。A．求關(guān)鍵路徑是以拓?fù)渑判驗(yàn)榛A(chǔ)的B．一個(gè)事件的最早開始時(shí)間同以該事件為尾的弧的活動(dòng)最早開始時(shí)間相同C．一個(gè)事件的最遲開始時(shí)間為以該事件為尾的弧的活動(dòng)最遲開始時(shí)間與該活動(dòng)的持續(xù)時(shí)間的差D．關(guān)鍵活動(dòng)一定位于關(guān)鍵路徑上（二）綜合題1．給定n個(gè)村莊之間的交通圖，若村莊i和j之間有道路，則將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長(zhǎng)度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問(wèn)這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短? 分析：每個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑中最長(zhǎng)的有n條，求這n條中最短的一條。A．逆拓?fù)溆行? B．拓?fù)溆行? C．無(wú)序的4. 下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（ AB ）。A．a(chǎn),b,e,c,d,f B．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,d D．a(chǎn),e,d,f,c,b，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是（ D ）。這一章考算法的可能性不大，但那兩個(gè)最基本的遍歷算法最好掌握。分析：這一章的內(nèi)容也比較多，尤其大的知識(shí)點(diǎn)比較多，容易出綜合題，特別是圖的應(yīng)用。（3）關(guān)鍵路徑為01235（如下圖粗線所示），長(zhǎng)度為16。（1）圖G的鄰接矩陣A如下所示。（3）求圖G的關(guān)鍵路徑，并計(jì)算該 關(guān)鍵路徑的長(zhǎng)度。46∞∞∞5∞∞∞43∞∞33要求：（1）寫出圖G的鄰接矩陣A。例如，對(duì)于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為ABC，事實(shí)上其最短路徑為ADC。分析：此題考查最短路徑的求解思路，只是沒(méi)有直接考書上的最短路徑的求解過(guò)程，而是換個(gè)角度考查對(duì)最短路徑求解的理解。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問(wèn)題的方法：（1）設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；（2）選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；（3）重復(fù)步驟（2），直到u是目標(biāo)頂點(diǎn)為止?；芈穼?duì)應(yīng)于路徑，簡(jiǎn)單回路對(duì)應(yīng)于簡(jiǎn)單路徑；II剛好說(shuō)反了，III是拓?fù)溆行虻谋匾獥l件。 I．回路是簡(jiǎn)單路徑II．存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間III．若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路 分析：答案是B，此題考查圖的拓?fù)渑判颉? 3.（10年）對(duì)下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是（ ）。 分析：答案是C，此題考查無(wú)向連通圖的特點(diǎn)，解題時(shí)需要注意保證圖G在任何情況下都是連通的這句話，這是關(guān)鍵。 2.（10年）若無(wú)向圖G（）中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（ ）。第7章 圖一、考研知識(shí)點(diǎn)（一）圖的基本概念（二）圖的存儲(chǔ)及基本操作（三）圖的遍歷（四）圖的基本應(yīng)用（代價(jià)）生成樹二、考研真題（一）選擇題1.（09年）下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是（ ）。分析：考查哈夫曼樹的構(gòu)造和哈夫曼編碼，過(guò)程略。例如，任何結(jié)點(diǎn)只有左子樹的二叉樹和任何結(jié)點(diǎn)只有右子樹的二叉樹，其前序序列相同，后序序列相同，但卻是兩棵不同的二叉樹。根據(jù)前序遍歷中“根—左子樹—右子樹”的順序，則由從第二元素開始的l個(gè)結(jié)點(diǎn)序列和中序序列根左邊的l個(gè)結(jié)點(diǎn)序列構(gòu)造左子樹，由前序序列最后r個(gè)元素序列與中序序列根右邊的r個(gè)元素序列構(gòu)造右子樹。分析：給定二叉樹結(jié)點(diǎn)的前序序列和對(duì)稱序（中序）序列，可以唯一確定該二叉樹。如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和后序序列，能否構(gòu)造出此二叉樹?若能，請(qǐng)證明之。4．如果給出了一個(gè)二叉樹結(jié)點(diǎn)的前序序列和中序序列，能否構(gòu)造出此二叉樹?若能，請(qǐng)證明之。3．從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 tag