#以鄰接表作為存儲結(jié)構(gòu)，本題只給出Insert_Arc算法.其余算法類似。StatusInsert_Arc(ALGraph&G,charv,charw)// 在鄰接表表示的圖G上插入邊(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;p=newArcNode;p->adjvex=j;p->nextarc=NULL;if(!G.vertices.firstarc)G.vertices.firstarc=p;else{for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc)if(q->adjvex==j)returnERROR;// 邊已經(jīng)存在q->nextarc=p;}G.arcnum++;returnOK;}//Insert_Arc(2)一個連通圖采用鄰接表作為存儲結(jié)構(gòu)，設(shè)計一個算法，實現(xiàn)從頂點v出發(fā)的深度優(yōu)先遍歷的非遞歸過程。[算法描述]VoidDFSn(GraphG,intv){//從第v個頂點出發(fā)非遞歸實現(xiàn)深度優(yōu)先遍歷圖GStacks;SetEmpty(s);Push(s,v);While(!StackEmpty(s)){ //?？諘r第v個頂點所在的連通分量已遍歷完P(guān)op(s,k);If(!visited[k]){visited[k]=TRUE;VisitFunc(k);//訪問第k個頂點//將第k個頂點的所有鄰接點進棧for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w)){if(!visited[w]&&w!=GetTop(s))Push(s,w);//圖中有環(huán)時w==GetTop(s)(3)設(shè)計一個算法，求圖 G中距離頂點v的最短路徑長度最大的一個頂點，設(shè)v可達其余各個頂點。[題目分析]利用Dijkstra算法求v0到其它所有頂點的最短路徑，分別保存在數(shù)組D[i]中，然后求出D[i]中值最大的數(shù)組下標m即可。[算法描述]intShortestPath_MAX(AMGraphG,intv0){//用Dijkstra算法求距離頂點v0的最短路徑長度最大的一個頂點mn=G.vexnum; //n為G中頂點的個數(shù)for(v=0;v<n;++v){//n個頂點依次初始化S[v]=false; //S初始為空集D[v]=G.arcs[v0][v]; //將v0到各個終點的最短路徑長度初始化if(D[v]<MaxInt) Path[v]=v0;//如果v0和v之間有弧，則將v的前驅(qū)置為v0elsePath[v]=-1;//如果v0和v之間無弧，則將v的前驅(qū)置為-1}//forS[v0]=true;//將v0加入SD[v0]=0;//源點到源點的距離為0/*開始主循環(huán)，每次求得v0到某個頂點v的最短路徑，將v加到S集*/for(i=1;i<n;++i){//對其余n-1個頂點，依次進行計算min=MaxInt;for(w=0;w<n;++w)if(!S[w]&&D[w]<min){v=w;min=D[w];}//選擇一條當前的最短路徑，終點為 vS[v]=true;//將v加入Sfor(w=0;w<n;++w)//更新從V0到V-S上所有頂點的最短路徑長度if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){D[w]=D[v]+G.arcs[v][w];//更新D[w]Path[w]=v;//更改w的前驅(qū)為v}//if}//for/*最短路徑求解完畢，設(shè)距離頂點v0的最短路徑長度最大的一個頂點為m*/Max=D[0];m=0;for(i=1;i<n;i++)if(Max<D[i])m=i;returnm;}(4)試基于圖的深度優(yōu)先搜索策略寫一算法， 判別以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點vj的路徑(i豐j)。[題目分析]引入一變量level來控制遞歸進行的層數(shù)[算法描述]intvisited[MAXSIZE];//指示頂點是否在當前路徑上intlevel=1;//遞歸進行的層數(shù)intexist_path_DFS(ALGraphG,inti,intj)// 深度優(yōu)先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回 1,否則返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--){level++;k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i 下游的頂點到j(luò)有路徑}//for}//elseif(level==1)return0;}//exist_path_DFS(5)采用鄰接表存儲結(jié)構(gòu)，編寫一個算法，判別無向圖中任意給定的兩個頂點之間是否存在一條長度為為k的簡單路徑。[算法描述]intvisited[MAXSIZE];intexist_path_len(ALGraphG,inti,intj,intk)//判斷鄰接表方式存儲的有向圖 G的頂點i到j(luò)是否存在長度為 k的簡單路徑{if(i==j&&k==0)return1;//找到了一條路徑 ,且長度符合要求elseif(k>0){visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex;if(!visited[l])if(exist_path_len(G,l,j,k-1))return1;//剩余路徑長度減一}//forvisited[i]=0;//本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中}//elsereturn0;//沒找到}//exist_path_len第7章查找1．選擇題（1）對n個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為）。A．（n-1）/2 B．n/2 C．（n+1）/2 D．n答案：C解釋：總查找次數(shù) N=1+2+3+…+n=n（n+1）/2，則平均查找長度為 N/n=（n+1）/2。（2）適用于折半查找的表的存儲方式及元素排列要求為（ ）。A．鏈接方式存儲，元素?zé)o序 B．鏈接方式存儲，元素有序C.順序方式存儲，元素?zé)o序 D.順序方式存儲，元素有序答案：D解釋：折半查找要求線性表必須采用順序存儲結(jié)構(gòu)， 而且表中元素按關(guān)鍵字有序排列。（3）如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，最好采用 （ ）查找法。A?順序查找 B?折半查找C?分塊查找 D?哈希查找答案：C解釋：分塊查找的優(yōu)點是：在表中插入和刪除數(shù)據(jù)元素時， 只要找到該元素對應(yīng)的塊，就可以在該塊內(nèi)進行插入和刪除運算。由于塊內(nèi)是無序的，故插入和刪除比較容易，無需進行大量移動。如果線性表既要快速查找又經(jīng)常動態(tài)變化，則可采用分塊查找。（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ ）比較大小，查找結(jié)果是失敗。A.20,70,30,50 B.30,88,70,50D.30,88,50CD.30,88,50解釋：表中共10個元素,第一次取（1+10）/2 =5,與第五個元素20比較,58大于20,再?。?+10）（5）對A.答案：/2 =8,與第八個元素 70比較,依次類推再與 30、50比較,最終查找失敗。22個記錄的有序表作折半查找, 當查找失敗時, 至少需要比較（ ）次關(guān)鍵字。3 B.4 C.5 D.6B解釋：22個記錄的有序表,其折半查找的判定樹深度為 log222+1=5,且該判定樹不是滿二叉樹,即查找失敗時至多比較 5次,至少比較4次。6）折半搜索與二叉排序樹的時間性能（ ）A.相同CA.相同C.有時不相同D.數(shù)量級都是O（log2n）

答案：C7）分別以下列序列構(gòu)造二叉排序樹， 與用其它三個序列所構(gòu)造的結(jié)果不同的是（）A．（100，80，90，60，120，110，130)B．（100，120，110，130，80，60，90)C．（100，60，80，90，120，110，130)D．(100，80，60，90，120，130，110)答案：C解釋：A、B、C、D四個選項構(gòu)造二叉排序樹都以 100為根，易知A、B、D三個序列中第一個比100小的關(guān)鍵字為80，即100的左孩子為80，而C選項中100的左孩子為60，故選C。8）在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為 A，并已知A的左孩子的平衡因子為0右孩子的平衡因子為 1，則應(yīng)作（）型調(diào)整以使其平衡。A．LLB．LR C．RLD．RR答案：C（9）下列關(guān)于m階B-樹的說法錯誤的是（ ）。A．根結(jié)點至多有m棵子樹B．所有葉子都在同一層次上C．非葉結(jié)點至少有 m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹D．根結(jié)點中的數(shù)據(jù)是有序的答案：D（10）下面關(guān)于B-和B+樹的敘述中，不正確的是（ ）A.A.B-樹和B+樹都是平衡的多叉樹C.B-樹和B+樹都能有效地支持順序檢索答案：CB.B-樹和B+樹都可用于文件的索引結(jié)構(gòu)D．B-樹和B+樹都能有效地支持隨機檢索（11）m階B-樹是一棵（ ）A．m叉排序樹BA．m叉排序樹D．m+1叉平衡排序樹）。D．m+1叉平衡排序樹）。答案：B12）下面關(guān)于哈希查找的說法，正確的是（A?哈希函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機性好，沖突小B?除留余數(shù)法是所有哈希函數(shù)中最好的C.不存在特別好與壞的哈希函數(shù)，要視情況而定D?哈希表的平均查找長度有時也和記錄總數(shù)有關(guān)答案：C13）下面關(guān)于哈希查找的說法，不正確的是（ ）A?采用鏈地址法處理沖突時，查找一個元素的時間是相同的B．采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈首，則插入任一個元素的時間是相同的C.用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象D.用鏈地址法處理沖突，適合表長不確定的情況答案：ATOC\o"1-5"\h\z解釋：在同義詞構(gòu)成的單鏈表中，查找該單鏈表表中不同元素，所消耗的時間不同 。（14）設(shè)哈希表長為 14，哈希函數(shù)是H（key）=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為 15,38，61，84共四個，現(xiàn)要將關(guān)鍵字為 49的元素加到表中，用二次探測法解決沖突，則放入的位置是（ ）。A.8 B.3 C.5 D.9答案：D解釋：關(guān)鍵字15放入位置4，關(guān)鍵字38放入位置5,關(guān)鍵字61放入位置6,關(guān)鍵字84放入位置7,再添加關(guān)鍵字 49，計算得到地址為 5，沖突，用二次探測法解決沖突得到新地址為6，仍沖突，再用用二次探測法解決沖突，得到新地址為 4，仍沖突，再用用二次探測法解決沖突，得到新地址為 9，不沖突，即將關(guān)鍵字 49放入位置9。（15） 采用線性探測法處理沖突，可能要探測多個位置，在查找成功的情況下，所探測的這些位置上的關(guān)鍵字 （ ）。A?不一定都是同義詞 B?一定都是同義詞C.一定都不是同義詞 D?都相同答案：A解釋：所探測的這些關(guān)鍵字可能是在處理其它關(guān)鍵字沖突過程中放入該位置的。?應(yīng)用題（1）假定對有序表： （3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找,試回答下列問題：畫岀描述折半查找過程的判定樹；若查找元素54，需依次與哪些元素比較？若查找元素90,需依次與哪些元素比較？假定每個元素的查找概率相等，求查找成功時的平均查找長度。答案：先畫岀判定樹如下（注：mid=（1+12）/2 =6）：424547295②查找元素54,需依次與30,63,42,54元素比較;③查找元素90,需依次與30,63,87,95元素比較；④求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前 3層共查找1+2X2+4X3=17次；但最后一層未滿，不能用 8X4，只能用5X4=20次，所以ASL=1/12(17+20)=37/12~3.08在一棵空的二叉排序樹中依次插入關(guān)鍵字序列為 12,7,17,11,16,2,13,9,21，4，請畫岀所得到的二叉排序樹。答案：12TOC\o"1-5"\h\z7 17/ 、 /X2111621\ X /9 13驗算方法：用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17,21已知如下所示長度為12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫岀插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。答案：<1>求得的二叉排序樹如下圖所示，在等槪率情況F査找成功的平均査找長度為ASF—=書(IXl-k2X2+3X3+4X3+5X2H-6Xl)^^i“12

經(jīng)排序后的表及在折半住找吋找到段中元盧所經(jīng)比較的慶釵科腿如NAprAugDecFebJanJulyJuneMarMayNo*OctSept

342341342434等穩(wěn)率tft況下査找成功時的平均査找棧度為! 37ASL^=豈(1X1+2X2+3X4+^X5)=Y2G) 平衡二叉樹為它在等概率情況下的平均查找民度為t 38ASL=A(1X14-2X2+3X4+4X4+5X"=而對圖7.31所示的3階B-樹，依次執(zhí)行下列操作，畫岀各步操作的結(jié)果25③插入45④刪除60(1)25③插入45④刪除60(1)揃入範 (2)?AZ5 (3)插人45(4J刪除(4J刪除BO(5、刪馳設(shè)哈希表的地址范圍為 0?17,哈希函數(shù)為：H(key)=key%16。用線性探測法處理沖突，輸入關(guān)鍵字序列： (10，24，32，17，31，30，46，47，40，63，49)，構(gòu)造哈希表，試回答下列問題：畫岀哈希表的示意圖；若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。答案：①畫表如下：012345678910111213141516173217634924401030314647查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即 63與31比較，不匹配；然后順移，與46,47,32,17,63 相比，一共比較了 6次！查找60,首先要與H(60)=60%16=12 號單元內(nèi)容比較，但因為12號單元為空(應(yīng)當有空標記)，所以應(yīng)當只比較這一次即可。對于黑色數(shù)據(jù)元素，各比較 1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。 “63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11 (6+2+3X3+6)=23/11設(shè)有一組關(guān)鍵字( 9，01，23，14，55，20，84，27)，采用哈希函數(shù)： H(key)=key%7，表長為10,用開放地址法的二次探測法處理沖突。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并計算查找成功的平均查找長度。答案:散列地址0123456789關(guān)鍵字14192384275520比較次數(shù)11123412平均查找長度： ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8以關(guān)鍵字27為例：H(27)=27%7=6(沖突) H1=(6+1)%10=7(沖突)H2=(6+22)%10=0(沖突) H3=(6+33)%10=5所以比較了4次。設(shè)哈希函數(shù) H(K)=3Kmod11，哈希地址空間為 0?10，對關(guān)鍵字序列( 32,13,49,24,38,21,4,12),按下述兩種解決沖突的方法構(gòu)造哈希表，并分別求岀等概率下查找成功時和查找失敗時的平均查找長度 ASLsucc和ASLunsucc。線性探測法；鏈地址法。答案：①散列地址012345678910關(guān)鍵字412493813243221比較次數(shù)11121212ASLsucc= (1+1+1+2+1+2+1+2)/8=11/8ASLunsucc=(1+2+1+8+7+6+5+4+3+2+1 )/11=40/11②441AI10—?12A八A1AAft丨t|厲f1英丨p|21丨八|ASLsucc=(1*5+2*3)/8=11/8ASLunsucc=(1+2+1+2+3+1+3+1+3+1+1 )/11=19/11?算法設(shè)計題(1)試寫出折半查找的遞歸算法。[算法描述]intBinSrch (rectyper[] ,intk,low,high)//在長為n的有序表中查找關(guān)鍵字 k，若查找成功，返回 k所在位置，查找失敗返回 0{if(low<high)//low和high分別是有序表的下界和上界{mid=(low+high)/2；if(r[mid].key==k)return(mid)；elseif(r[mid].key>k)return(BinSrch(r,k,mid+1,high));elsereturn (BinSrch (r,k,low,mid-1));elsereturn (0)；//查找失敗。}//算法結(jié)束(2)試寫一個判別給定二叉樹是否為二叉排序樹的算法。[題目分析]根據(jù)二叉排序樹中序遍歷所得結(jié)點值為增序的性質(zhì)，在遍歷中將當前遍歷結(jié)點與其前驅(qū)結(jié)點值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre(初值為null)和全局變量flag，初值為true。若非二叉排序樹，則置flag為false。[算法描述]#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*lchild,*rchild;}*BTree;voidJudgeBST(BTreeT,intflag)//判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。{if(T!=null&&flag ){Judgebst (T->lchild,flag )；//中序遍歷左子樹if(pre==null)pre=T；//中序遍歷的第一個結(jié)點不必判斷elseif (pre->data<T->data )pre=T；//前驅(qū)指針指向當前結(jié)點else{flag=flase ；}//不是完全二叉樹Judgebst (T->rchild,flag )；//中序遍歷右子樹}//JudgeBST算法結(jié)束(3)已知二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，根結(jié)點的指針為T，鏈結(jié)點的結(jié)構(gòu)為(lchild,data,rchild)，其中l(wèi)child，rchild分別指向該結(jié)點左、右孩子的指針，data域存放結(jié)點的數(shù)據(jù)信息。請寫出遞歸算法，從小到大輸出二叉排序樹中所有數(shù)據(jù)值>=x的結(jié)點的數(shù)據(jù)。要求先找到第一個滿足條件的結(jié)點后，再依次輸出其他滿足條件的結(jié)點。[題目分析]本題算法之一是如上題一樣，中序遍歷二叉樹，在“訪問根結(jié)點”處判斷結(jié)點值是否》x，如是則輸岀，并記住第一個》 x值結(jié)點的指針。這里給岀另一個算法，利用二叉排序樹的性質(zhì)，如果根結(jié)點的值>=x,則除左分枝中可能有<x的結(jié)點外都應(yīng)輸出。所以從根結(jié)點開始查找，找到結(jié)點值<x的結(jié)點后，將其與雙親斷開輸岀整棵二叉排序樹。如果根結(jié)點的值VX,則沿右子樹查找第一個》 x的結(jié)點，找到后，與上面同樣處理。voidPrint(BSTreet)// 中序輸岀以t為根的二叉排序樹的結(jié)點{if(t){Print(t->lchild )；Cout<<t-data5Print(}t->rchild)；}voidPrintAllx(BSTreebst ，datatypex)

//在二叉排序樹 //在二叉排序樹 bst中，查找值》x的結(jié)點并輸岀{p=bst；if（p）{while（p&&p->data<x）p=p->rchild；//沿右分枝找第一個值》 x的結(jié)點bst=p;//bst 所指結(jié)點是值》 x的結(jié)點的樹的根if(pif(p){f=p;p=p->lchild5//找第一個值<x的結(jié)點while(p&&p->data>x）//沿左分枝向下，找第一個值 VX的結(jié)點{f=p；p=p->lchild；}//f是p的雙親結(jié)點的指針，指向第一個值A(chǔ) x的結(jié)點if(p)f->lchild=null;//雙親與找到的第一個值 <x的結(jié)點斷開Print(bst) ；//輸岀以bst為根的子樹}//while}//內(nèi)層if(p)}//第一層if(p)}//PrintAllx4）已知二叉樹T的結(jié)點形式為（lling,data,count,rlink），在樹中查找值為 X的結(jié)點，則記數(shù)（count)加1，否則，作為一個新結(jié)點插入樹中，插入后仍為二叉排序樹，寫若找到，岀其非遞歸算法。[算法描述]voidSearchBST(BiTree&T,inttarget){BiTrees,q,f;//以數(shù)據(jù)值target,新建結(jié)點ss=newBiTNode;s->data.x=target;s->data.count=0;s->lchild=s->rchild=NULL;if(!T){T=s;return;} //如果該樹為空則跳岀該函數(shù)f=NULL;q=T;while(q){if(q->data.x==target){q->data.count++;return;} //如果找到該值則計數(shù)加一

f=q;if（q->data.x>target） //如果查找值比目標值大，則為該樹左孩子q=q->lchild;else //否則為右孩子q=q->rchild;}//將新結(jié)點插入樹中if（f->data.x>target）f->lchild=s;elsef->rchild=s;}（5）假設(shè)一棵平衡二叉樹的每個結(jié)點都表明了平衡因子 b，試設(shè)計一個算法，求平衡二叉樹的高度。[題目分析]因為二叉樹各結(jié)點已標明了平衡因子 b，故從根結(jié)點開始記樹的層次。根結(jié)點的層次為1，每下一層，層次加 1，直到層數(shù)最大的葉子結(jié)點，這就是平衡二叉樹的高度。當結(jié)點的平衡因子b為0時，任選左右一分枝向下查找，若b不為0，則沿左（當b=1時）或右（當b=-1時）向下查找。[算法描述]intHeight（BSTreet）//求平衡二叉樹t的高度{level=0while；p=t；（p）{level++；//樹的高度增1if(p->bf<0)if(p->bf<0)p=p->rchild//bf是平衡因子，是二叉樹elsep=p->lchild；t結(jié)點的一個域，因篇幅所限，沒有寫出其存儲定義//bf>=0沿左分枝向下}//whilereturn（level）；//平衡二叉樹的高度}//算法結(jié)束（6（6）分別寫出在散列表中插入和刪除關(guān)鍵字為解決沖突的方法為鏈地址法。[算法描述]K的一個記錄的算法，設(shè)散列函數(shù)為 H，boolinsert(){intdata;cin>>data;boolinsert(){intdata;cin>>data;intant=hash(data);LinkListp=HT[ant];//初始化散列表while(p->next){if(p->next->data==data)returnfalse;p=p->next;}//找到插入位置LinkLists;s=newLNode;s->data=data;s->next=p->next;p->next=s;//插入該結(jié)點returntrue;}booldeletes(){intdata;cin>>data;intant=hash(data);LinkListp=HT[ant]; //初始化散列表while(p->next){if(p->next->data==data){LinkLists=p->next;p->next=s->next;deletes;//刪除該結(jié)點returntrue;}//找到刪除位置p=p->next；//遍歷下一個結(jié)點}returnfalse;}第8章排序1．選擇題（1）從未排序序列中依次取出元素與已排序序列中的元素進行比較， 將其放入已排序序列的正確位置上的方法，這種排序方法稱為（）。A?歸并排序 B?冒泡排序 C?插入排序 D?選擇排序答案：C（2）從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（）。A?歸并排序 B?冒泡排序 C?插入排序 D?選擇排序答案：D（3）對n個不同的關(guān)鍵字由小到大進行冒泡排序，在下列（ ）情況下比較的次數(shù)最多。A?從小到大排列好的A?從小到大排列好的B?從大到小排列好的D?元素基本有序CD?元素基本有序答案：B解釋：對關(guān)鍵字進行冒泡排序，關(guān)鍵字逆序時比較次數(shù)最多4）對4）對n個不同的排序碼進行冒泡排序，在元素?zé)o序的情況下比較的次數(shù)最多為A?n+1 B?A?n+1 B?n答案：D解釋：比較次數(shù)最多時，第一次比較次，即卩（n-1）+（n-2）+…+1=n（n-1）/2。C?n-1D．n(n-1)/2n-1次，第二次比較n-2次……最后一次比較1）快速排序在下列（ ）情況下最易發(fā)揮其長處。A．被排序的數(shù)據(jù)中含有多個相同排序碼B?被排序的數(shù)據(jù)已基本有序C.被排序的數(shù)據(jù)完全無序D．被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解釋：B選項是快速排序的最壞情況。6）對n個關(guān)鍵字作快速排序，在最壞情況下，算法的時間復(fù)雜度是（ ）A．O（n） BA．O（n） B．O（n2）答案：B解釋：快速排序的平均時間復(fù)雜度為序的情況下，時間復(fù)雜度為 O（n2）。（7）若一組記錄的排序碼為（ 46,79，一個記錄為基準得到的一次劃分結(jié)果為（C．O（nlog2n） D．O（n3）O（nlog2n），但在最壞情況下，即關(guān)鍵字基本排好56，38，40，84），則利用快速排序的方法，以第A?38,40，46，56，79，84B?40，38，46，79，56，84C．40，38，46，56，79，84D?40，38，46，84，56，79答案：C8）下列關(guān)鍵字序列中，（）是堆。A?16,72，31，23，94，53B?94，23，31，72，16，53C．16，53，23，94，31，72D?16，23，53，31，94，72答案：D解釋：D選項為小根堆9）堆是一種（）排序。A?插入B?選擇C?交換D?歸并答案：B10）堆的形狀是一棵（）。A?二叉排序樹B?滿二叉樹C?完全二叉樹D?平衡二叉樹答案：C（11）若一組記錄的排序碼為（ 46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為（）。A?79,46,56,38,40,84B?84,79,56,38,40,46C.84,79,56,46,40,38D?84,56,79,40,46,38答案：B12）下述幾種排序方法中,要求內(nèi)存最大的是（）。A?希爾排序 B?快速排序C?歸并排序D?堆排序答案：C解釋：堆排序、希爾排序的空間復(fù)雜度為O（1），快速排序的空間復(fù)雜度為 O（log2n），歸并排序的空間復(fù)雜度為O（n）。（13）下述幾種排序方法中， （）是穩(wěn)定的排序方法。A?希爾排序 B?快速排序 C?歸并排序 D?堆排序答案：C解釋：不穩(wěn)定排序有希爾排序、簡單選擇排序、快速排序、堆排序；穩(wěn)定排序有直接插入排序、折半插入排序、冒泡排序、歸并排序、基數(shù)排序。（14）數(shù)據(jù)表中有10000個元素，如果僅要求求出其中最大的10個元素，則采用（）算法最節(jié)省時間。A?冒泡排序B?快速排序C?簡單選擇排序D?堆排序答案：D（15）下列排序算法中,（）不能保證每趟排序至少能將一個元素放到其最終的位置上。A?希爾排序B?快速排序C?冒泡排序D?堆排序答案：A解釋：快速排序的每趟排序能將作為樞軸的元素放到最終位置；冒泡排序的每趟排序能將最大或最小的元素放到最終位置；堆排序的每趟排序能將最大或最小的元素放到最終位置。2．應(yīng)用題（1）設(shè)待排序的關(guān)鍵字序列為 {12，2，16，30，28，10，16*，20，6，18}，試分別寫出使用以下排序方法，每趟排序結(jié)束后關(guān)鍵字序列的狀態(tài)。直接插入排序折半插入排序希爾排序（增量選取 5，3，1）冒泡排序快速排序簡單選擇排序堆排序二路歸并排序答案：①直接插入排序[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]②折半插入排序排序過程同①③希爾排序（增量選取5，3，1）102166181216*203028（增量選取5）621210181616*203028（增量選取3）2610121616*18202830（增量選取1）④冒泡排序21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]

21012616[16*18202830]210612[1616*18202830]2610[121616*18202830]2610121616*18202830]⑤快速排序12[6210]12[283016*201618]6[2]6[10]|12[283016*201618]2826，1012[181616*20]28[30]18261012[16*16]18[20]28 3016*26101216*[16]18202830左子序列遞歸深度為1,右子序列遞歸深度為3⑥簡單選擇排序2[121630281016*20618]26[1630281016*201218]2610[30281616*201218]261012[281616*203018]26101216[2816*203018]2610121616*[28203018]2610121616*18[203028]2610121616*1820[2830]2610121616*182028[30]⑧二.路歸并排序2121630102816*2061821216301016*2028618210121616*202830 6182610121616*18202830(2)給岀如下關(guān)鍵字序列｛ 321,156,57,46,28,7,331,33,34,63匕試按鏈式基數(shù)排序方法，列出每一趟分配和收集的過程。答案：按最低位優(yōu)先法 t321t156t57t46f28f7f331f33f34f63分配[0][1][2][3][4][5][6][7][8][9]321 3334 1565728331 63467

331 63467收集f321f331f33f63f34f156f46f57f7f28(3)對輸入文件( 101,51,19,61,3,71,31,17,19,100,55,20,9,30,50,,90);當k=6時，使用置換-選擇算法，寫岀建立的初始敗者樹及生成的初始歸并段。答案：初始敗者樹3 4 53 4 5初始歸并段： Ri：3,19,31,51,61,71,100,101R 2：9丿7,19,20,30,50,55,90R3:631?算法設(shè)計題(1)試以單鏈表為存儲結(jié)構(gòu)，實現(xiàn)簡單選擇排序算法。［算法描述］:void LinkedListSelectSort(LinkedListhead);若要交換指針,//;若要交換指針,則須記下//當前結(jié)點和最小結(jié)點的前驅(qū)指針p=head->next;while(p!=null){q=p->next;r=p;// 設(shè)r是指向關(guān)鍵字最小的結(jié)點的指針while(q!=null){if(q->data<r->data)r=q;q:=q_>next;}if(r!=p)r->data<-->p->data;p=p->next;

（2）有n個記錄存儲在帶頭結(jié)點的雙向鏈表中， 現(xiàn)用雙向冒泡排序法對其按上升序進行排序，請寫出這種排序的算法。（注：雙向冒泡排序即相鄰兩趟排序向相反方向冒泡）[算法描述]：typedefstructnode{ElemTypedata;structnode*prior,*next;}node，*DLinkedList;voidTwoWayBubbleSort(DLinkedListla)//對存儲在帶頭結(jié)點的雙向鏈表//對存儲在帶頭結(jié)點的雙向鏈表la中的元素進行雙向起泡排序。{intexchange=1;//設(shè)標記DLinkedListp,temp,tail;head=la//雙向鏈表頭，算法過程中是向下起泡的開始結(jié)點tail=null;DLinkedListp,temp,tail;head=la//雙向鏈表頭，算法過程中是向下起泡的開始結(jié)點tail=null;//雙向鏈表尾，算法過程中是向上起泡的開始結(jié)點while(exchange){p=head->next;//pexchange=0;//while(exchange){p=head->next;//pexchange=0;//是工作指針，指向當前結(jié)點假定本趟無交換while(p->next!=tail)//向下（右）起泡，一趟有一最大元素沉底if(p->data>p->next->data)//交換兩結(jié)點指針，涉及 6條鏈{temp=p->next;exchange=1;// 有交換p->next=temp->next;temp->next->prior=p//while(p->next!=tail)//向下（右）起泡，一趟有一最大元素沉底if(p->data>p->next->data)//交換兩結(jié)點指針，涉及 6條鏈{temp=p->next;exchange=1;// 有交換p->next=temp->next;temp->next->prior=p//temp->next=p;p->prior->next=temp;//temp->prior=p->prior;p->prior=temp;先將結(jié)點從鏈表上摘下將temp插到p結(jié)點前}elsep=p->next;//無交換，指針后移tail=p;//準備向上起泡p=tail->prior;while(exchange&&p->prior!=head)//向上(左)起泡，一趟有一最小元素冒出if(p->data<p->prior->data)//{temp=p->prior;exchange=1;//交換兩結(jié)點指針，涉及6條鏈有交換p->prior=temp->prior;temp->prior->next=p//先將temp結(jié)點從鏈表上摘下temp->prior=p;p->next->prior=temp;5//將temp插到p結(jié)點后（右）temp->next=p->next;p->next=temp;}elsep=p->prior;// 無交換，指針前移head=p;// 準備向下起泡}//while(exchange)}//算法結(jié)束(3)設(shè)有順序放置的 n個桶，每個桶中裝有一粒礫石，每粒礫石的顏色是紅，白，藍之一。要求重新安排這些礫石，使得所有紅色礫石在前，所有白色礫石居中，所有藍色礫石居后，重新安排時對每粒礫石的顏色只能看一次，并且只允許交換操作來調(diào)整礫石的位置。[題目分析]利用快速排序思想解決。由于要求“對每粒礫石的顏色只能看一次”，設(shè)3個指針i,j和k，分別指向紅色、白色礫石的后一位置和待處理的當前元素。從 k=n開始，從右向左搜索，若該元素是蘭色，則元素不動，指針左移(即k-1)；若當前元素是紅色礫石，分i>=j (這時尚沒有白色礫石)和i<j兩種情況。前一情況執(zhí)行第 i個元素和第k個元素交換，之后i+1；后一情況，i所指的元素已處理過(白色)，j所指的元素尚未處理，應(yīng)先將i和j所指元素交換，再將i和k所指元素交換。對當前元素是白色礫石的情況，也可類似處理。為方便處理，將三種礫石的顏色用整數(shù) 1、2和3表示。[算法描述]：voidQkSort(rectyper[],intn){//r為含有n個元素的線性表，元素是具有紅、白和蘭色的礫石，用順序存儲結(jié)構(gòu)存儲，//本算法對其排序，使所有紅色礫石在前，白色居中，蘭色在最后。inti=1,j=1,k=n,temp;while(k!=j){while(r[k].key==3)k--;// 當前元素是蘭色礫石，指針左移if(r[k].key==1) // 當前元素是紅色礫石if(i>=j){temp=r[k];r[k]=r[i];r[i]=temp;i++;}//左側(cè)只有紅色礫石，交換r[k]和r[i]else{temp=r[j];r[j]=r[i];r[i]=temp;j++;//左側(cè)已有紅色和白色礫石，先交換白色礫石到位temp=r[k];r[k]=r[i];r[i]=temp;i++;//白色礫石(i所指)和待定礫石(j所指)}//再交換r[k]和r[i]，使紅色礫石入位。if(r[k].key==2)if(i<=j){temp=r[k];r[k]=r[j];r[j]=temp;j++;}//左側(cè)已有白色礫石，交換r[k]和r[j]else{temp=r[k];r[k]=r[i];r[i]=temp;j=i+1;}//i 、j分別指向紅、白色礫石的后一位置}//whileif(r[k]==2)j++;/* 處理最后一粒礫石elseif(r[k]==1){temp=r[j];r[j]=r[i];r[i]=temp;i++;j++;}

//最后紅、白、蘭色礫石的個數(shù)分別為:i-1;j-i;n-j+1r[j..k-1]為紅色，則。算法進行}//r[j..k-1]為紅色，則。算法進行[算法討論]若將j(上面指向白色)看作工作指針，將 r[1..j-1] 作為紅色，為白色，r[