2.敘述四類基本數(shù)據(jù)結(jié)構(gòu)的名稱與含義。3.敘述算法的定義與特性。4.敘述算法的時間復(fù)雜度。6.敘述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的差別。7.敘述面向?qū)ο蟪绦蛟O(shè)計語言的特點。9.敘述參數(shù)傳遞的主要方式及特點。3.在高級語言（如C或PAS三、計算下列程序段中X=X+1的語句頻度for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)【解答】…i=n時：1+2+3+……+n=(1+n)×n/2=(n+n2)/2每一語句的執(zhí)行次數(shù)和整個算法的時間復(fù)雜度，要求時間復(fù)雜度盡可能小，規(guī)定算法中不能使用求冪函數(shù)。注意：本題中的輸入ai(i=0,1,…,n),x和n，輸出為Pn(x0)。通常算法的輸入和輸出可采用下列兩種方式之一：（1）通過參數(shù)表中的參數(shù)顯式傳遞。（2）通過全局變量隱式傳遞。試討論這兩種方法的優(yōu)缺點，并在本題算法中以你認為較好的一種方式實現(xiàn)輸入和輸出【解答】（1）通過參數(shù)表中的參數(shù)顯式傳遞優(yōu)點：當沒有調(diào)用函數(shù)時，不占用內(nèi)存，調(diào)用結(jié)束后形參被釋放，實參維持，函數(shù)通缺點：形參須與實參對應(yīng)，且返回值數(shù)量有限。（2）通過全局變量隱式傳遞優(yōu)點：減少實參與形參的個數(shù)，從而減少內(nèi)存空間以及傳遞數(shù)據(jù)時的時間消耗缺點：函數(shù)通用性降低，移植性差算法如下：通過全局變量隱式傳遞參數(shù)PolyValue()floatx,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<n;i++)scanf(“%f”,&a[i]);/*執(zhí)行次數(shù)：n次*/p=a[0];for(i=1;i<=n;i++){p=p+a[i]*x;/*執(zhí)行次數(shù)：n次*/x=x*x;}printf(“%f”,p);}算法的時間復(fù)雜度：T(n)=O(n)通過參數(shù)表中的參數(shù)顯式傳遞floatPolyValue(floata[],float{floatp,s;s=a[0];for(i=1;i<=n;i++){s=s+a[i]*p;p=p*x;}return(p);}算法的時間復(fù)雜度：T(n)=O(n)/*執(zhí)行次數(shù):n次*/2.1描述以下三個概念的區(qū)別：頭指針，頭結(jié)點，首元素結(jié)點。（1）在順序表中插入或刪除一個元素，需要平均移動＿＿一半＿＿元素，具體移動的元素個數(shù)與＿＿插入或刪除的位置＿＿有關(guān)。（2）在順序表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。在單鏈表中，邏輯上相鄰的元素，其物理位置＿＿＿＿＿＿相鄰。（3）在帶頭結(jié)點的非空單鏈表中，頭結(jié)點的存儲位置由＿＿＿＿＿＿指示，首元素結(jié)點的存儲位置由＿＿＿＿＿＿指示，除首元素結(jié)點外，其它任一元素結(jié)點的存儲位置＿＿＿＿2.3已知L是無表頭結(jié)點的單鏈表，且P結(jié)點既不是首元素結(jié)點，求從下列語句中選擇合適的語句序列。：＿（）＿2.4已知線性表L遞增有序。試寫一算法，將X插入到L的適當位置上，以保持線性表L{for(i=va.length-1;va.elem[i]>x&&i>=0;i2.5寫一算法，從順序表中刪除自第i個元素開始的k個元素。[提示]：注意檢查i和k的合法性。<方法2>同時以待移動元素下標m和應(yīng)移入位置j為中心：<方法2>以應(yīng)移入位置j為中心，計算待移動元素下標：2.6已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結(jié)構(gòu)。試寫一高效{{}[方法1]:在原頭結(jié)點后重新頭插一遍[方法2]:可設(shè)三個同步移動的指針p,q,r，將q的后繼r改為p2.8假設(shè)兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)，請編寫算法，將A表和B表歸并成一個按元素值遞減有序的排列的線性表C，并要求利用原表（即A表和B表的）結(jié)點空間存放表C.voidmerge(LinkListA;LinkListB;LinkList*C)*C=A;(*C)－>next=NULL;while(pa!=NULL&&pb!=NULL)}}while(pa!=NULL)}while(pb!=NULL)}LinkListmerge(LinkListA;LinkListB){……LinkListC；{{}{}}分析:本算法的思想是,按從小到大的順序依次把A和B的元素插入新表某個結(jié)點的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點的前趨結(jié)點。{2.10已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其且利用原表中的結(jié)點空間作為這三個表的結(jié)點空間，頭結(jié)點可另辟空間。StatusLinkList_Divide(Lin{{{}{}{}線性表A、B、C均以單鏈表作為存儲結(jié)構(gòu)，且C注意：單鏈表的長度值m和n均未顯式存儲。[提示]：voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB){while(p&&q){{} 2.12將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式中各自僅含奇次項或偶次項，并要求利用原鏈表中的結(jié)點空間來構(gòu)成這兩個鏈表。[提示]：注明用頭指針還是尾指針。voidDivide_LinkedPoly({{{}{}2.13建立一個帶頭結(jié)點的線性鏈表，用以存放輸入的二進制數(shù)，鏈表中每個結(jié)點的data域存放一個二進制位。并在此鏈表上實現(xiàn)對二進制數(shù)加1的運算。[提示]：可將低位放在前面。2.14設(shè)多項式P(x)采用課本中所述鏈接方法存儲。寫一算法，對給定的x值，求P(x)的值。[提示]：floatPolyValue(Polylistp;floatx){……}1.按圖3.1(b)所示鐵道（兩側(cè)鐵道均為單向行駛道）進行車廂調(diào)度，回答：【解答】（1）可能得到的出站車廂序列是：123、132、213、231、321。(2)不能得到435612的出站序列。因為有S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此時按照“后進先出”的原則，出棧的順序必須為X(2)X(1)。因為有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。2.設(shè)隊列中有A、B、C、D、E這5個元素，其中隊首元素為A。如果對這個隊列重復(fù)執(zhí)直到隊列成為空隊列為止，則是否可能得到輸出序列：[提示]：3.給出棧的兩種存儲結(jié)構(gòu)形式名稱，在這兩種棧的存儲結(jié)構(gòu)中如何判別?？张c棧滿？4.按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：A－B*C/D+E↑F【解答】5.試寫一個算法，判斷依次讀入的一個以@為結(jié)束符的字母序列，是否為形如‘序列1&的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘1+3&3-1’則不是。[提示]：（1）邊讀邊入棧，直到&（2）邊讀邊出棧邊比較，直到……{{}6.假設(shè)表達式由單字母變量和雙目四則運算算符構(gòu)成。試寫一個算法，將一個通常書寫形{{if(*p是字母))*q++=*p;//直接輸出{{{7.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè){{}{來區(qū)分頭尾指針相同時的隊列狀態(tài)的空與滿，請編寫與此結(jié)構(gòu)相應(yīng)的入隊與出隊算法。[提示]：……[問題]：如何明確區(qū)分隊空、隊滿、非空非滿三種情況？9.簡述以下算法的功能（其中棧和隊列的元素類型均為int{inti,n,A[255];{n++;Pop(&S,&A[n]);}for(i=1;i<=n;i++)}InitStack(&T);}{Pop(&T,&d);}}{}}}1.設(shè)s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。給出下列操作的結(jié)果：StrIndex(s,’A’,4);StrReplace(s,’STUDENT’,q);[參考答案]StrLength(s)=14;SubString(sub1,s,1,7)sub1=’IAMA’;SubString(sub2,s,7,1)sub2=’’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q);s=’IAMAWORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q))sub1=’IAMAGOODWORKER’。StrCat(S,T)；SubStrin{{for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++);if(k>T[0])//找到了與T匹配的子串:分三種情況處理{if(T[0]==V[0])for(l=1;l<=T[0];l++)//新子串長度與原子串相同時:直接替換S[i+l-1]=V[l];elseif(T[0]<V[0])//新子串長度大于原子串時:先將后部右移{for(l=S[0];l>=i+T[0];l--)S[l+V[0]-T[0]]=S[l];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}{for(l=i+V[0];l<=S[0]+V[0]-T[0];l++)S[l]=S[l-V[0]+T[0]];for(l=1;l<=V[0];l++)S[i+l-1]=V[l];}i+=V[0];n++;}//if}//for3.假設(shè)以塊鏈結(jié)構(gòu)表示串，塊的大小為1，且附設(shè)頭結(jié)點。試編寫算法，實現(xiàn)串的下列基本操作：[說明]：用單鏈表實現(xiàn)。StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T{{}{{}{}{if(!p&&!q)return0;{{{{}//for//復(fù)制串t{{4．敘述以下每對術(shù)語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名{for(i=1;i<=s[0]&&i<=t[0]&&s[i]==t[i];i++);if(i>s[0]&&i>t[0])return0;{{{{S[i+l]=V[l];}{S[i+l]=V[l];}}//if}//for7．S是用結(jié)點大小為4的單鏈表存儲的串,分別編寫算法在第k個字符后插入串T，及（2）將順序串r中所有字符按照相反的次序仍存放在r中。（4）從順序串r1中第index個字符起求出首次與串r2相同的子串的起始位置。[提示]1）用靜態(tài)順序串（2）先移位，后復(fù)制[提示]：（1）被替換子串定位（相當于第9題中i）（2）被替換子串后面的字符左移或右移（為替換子串準備房間）（4）重復(fù)上述，直到……{{if(i==j){}}//for1．假設(shè)有6行8列的二維數(shù)組A，每個元素占用6個字節(jié)，存儲器按字節(jié)編址。已知A的[注意]：本章自定義數(shù)組的下標從1開始。（1）用i,j表示k的下標變換公式；3.假設(shè)稀疏矩陣A和B均以三元組表作為存儲結(jié)構(gòu)。試寫出矩陣相加的算法，另設(shè)三元組{{{{{}}//if{}{}{}{}}//for4．在稀疏矩陣的快速轉(zhuǎn)置算法5.2中，將計算position[col]的方法稍加改動，使算法只占用一個輔助向量空間。（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];(d){{for(min=A[i][0],j=0;j<n;j++)if(A[i][j]<min)min=A[i][j];//求一行中的最小值if(A[i][j]==min)//判斷這個(些)最小值是否鞍點{if(min<A[k][j])flag=0;if(flag)}}//for2．對題1所得各種形態(tài)的二叉樹，分別寫出前序、中序和后序遍歷的序列。4.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列[提示]：一個葉子結(jié)點，總結(jié)點數(shù)至多有多少個？可壓縮一度結(jié)點。c)前序和后序相同[提示]：去異存同。a)DLR與LDR的相同點：DR，如果無L，則完全相同,如果無LR，…。b)LDR與LRD的相同點：LD，如果無R，則完全相同。c)DLR與LRD的相同點：D，如果無LR，則完全相同。（如果去D，則為空樹）8．畫出與下列已知序列對應(yīng)的樹T:樹的先根次序訪問序列為GFKDAIEBCHJ；樹的后根次序訪問序列為DIAEKFCJHBG。[提示]：（1）先畫出對應(yīng)的二叉樹（2）樹的后根序列與對應(yīng)二叉樹的中序序列相同9．假設(shè)用于通訊的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為：10．已知二叉樹采用二叉鏈表存放,要求返回二叉樹T的后序序列中的第一個結(jié)點的指針,是否可不用遞歸且不用棧來完成?請簡述原因.[提示]：無右子的“左下端”12．已知二叉樹按照二叉鏈表方式存儲，編寫算法，計算二叉樹中葉子結(jié)點的數(shù)目。13．編寫遞歸算法：對于二叉樹中每一個元素值為x的結(jié)點，刪去以它為根的子樹，并釋放[提示]：[方法1]1）按先序查找2）超前查看子結(jié)點（3）按后序釋放；{if(*bt!=NULL&&(*bt)->data==x)*bt=NULL;}{if(bt){if(bt->LChild&&bt->LChild->data==x)bt->LChild=NULL;}bt->RChild=NULL;}}}[方法2]1）先序查找2）直接查看當前根結(jié)點（3）用指針參數(shù)；[方法3]1）先序查找2）直接查看當前根結(jié)點14．分別寫函數(shù)完成：在先序線索二叉樹T中，查找給定結(jié)點*p在先序序列中的后繼。在后序線索二叉樹T中，查找給定結(jié)點*p在后序序列中的前驅(qū)。[提示]：（1）先查看線索，無線索時用下面規(guī)律：（2）結(jié)點*p在先序序列中的后繼為其左子或右子；（3）結(jié)點*p在后序序列中的前驅(qū)也是其左子或右子。15．分別寫出算法，實現(xiàn)在中序線索二叉樹中查找給定結(jié)點*p在中序序列中的前驅(qū)與后繼。16．編寫算法，對一棵以孩子-兄弟鏈表表示的樹統(tǒng)計其葉子的個數(shù)。[提示]：（1）可將孩子-兄弟鏈表劃分為根、首子樹、兄弟樹，遞歸處理。（2）可利用返回值，或全局變量。17．對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。19．設(shè)二叉樹按二叉鏈表存放，寫算法判別一棵二叉樹是否是一棵正則二叉樹。正則二叉樹[提示]：可利用任何遞歸、非遞歸遍歷算法。20．計算二叉樹最大寬度的算法。二叉樹的最大寬度是指：二叉樹所有層中結(jié)點個數(shù)的最大[提示]：[方法一]：（1）利用隊列，初值為根（2）出隊訪問，并將左、右子入隊，直到隊空（3）記錄每一層中最后一個結(jié)點在隊中的位置（4）第i層最后一個結(jié)點的右子，必是第i+1層的最后一個結(jié)點[方法二]：利用層號和全局數(shù)組，任意遍歷、統(tǒng)計22.證明：給定一棵二叉樹的前序序列與中序序列，可唯一確定這棵二叉樹；給定一棵二叉樹的后序序列與中序序列，可唯一確定這棵二叉樹；23.二叉樹按照二叉鏈表方式存儲，編寫算法將二叉樹左右子樹進行交換。7.1已知如圖所示的有向圖，請給出該圖的：7.2已知如圖所示的無向圖，請給出該圖的：（1）每個事件的最早發(fā)生時間和最晚發(fā)生時間；（2）每個活動的最早開始時間和最晚開始時間；并給出算法執(zhí)行過程中各步的狀態(tài)。7.5編寫算法，由依次輸入的頂點數(shù)目、弧的數(shù)目、各頂點的信息和各條弧的信息建立{{{}}//Build_AdjList7.6試在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的基本操作：InsertVertex(G,v);InsertArc(G,v,w);DeleteVertex(G,v)和DeleteArc({{{}{{}著大量元素的移動,時間復(fù)雜度也會大大增加.{{}7.7試對鄰接表存儲結(jié)構(gòu)重做題6。{{}7.8試基于圖的深度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中，是否j是否有路徑,是則返回1,否則返回0{if(i==j)return1;//i就是j{{}//for7.9同上題要求。試基于圖的廣度優(yōu)先搜索策略寫一算法。j是否有路徑,是則返回1,否則返回0{{{}//for}//while7.10試利用棧的基本操作，編寫按深度優(yōu)先策略遍歷一個強連通圖的、非遞歸形式的算法。算法中不規(guī)定具體的存儲結(jié)構(gòu)，而將圖Graph看成是一種抽象數(shù)據(jù)類型。{{{if(j&&!visited[j]){visit(j);}{if(k&&!visited[k]){}}//if是強連通圖,所以從第一個結(jié)點出發(fā)一定能夠訪問到7.11采用鄰接表存儲結(jié)構(gòu)，編寫一個判別無向圖中任意給定的兩個頂點之間是否存在一條長度為k的簡單路徑（指頂點序列中不含有重現(xiàn)的頂點）的算法。[提示]：利用深度搜索，增設(shè)一個深度參數(shù)，深度超過k則停止對該結(jié)點的搜索。頂點i到j(luò)是否存在長度為k的簡單路徑{{{if(!visited[l])}//for7.12下圖是帶權(quán)的有向圖G的鄰接表表示法。從結(jié)點V1出發(fā)，深度遍歷圖G所得結(jié)點①V1,V2,V3,V4,V5,V6,V7,V8②V1,V2,V4,V6,V5,V3,V7,V8③V1,V2,V4,V6,V3,V5,V7,V8④V1,V2,V4,V6,V7,V3,V5,V8⑤V1,V2,V3,V8,V4,V5,V6,V7⑥V1,V2,V3,V8,V4,V5,V7,V6⑦V1,V2,V3,V8,V5,V7,V4,V6①V1,V2,V4,V5,V3,V8②V1,V6,V5,V3,V8③V1,V6,V7,V8EQ\*jc3\*hps31\o\al(\s\up4(V2),v1){{}8.1若對大小均為n的有序的順序表和無序的順序表分別進行查找，試在下列三種情況下分（1）查找不成功，即表中沒有關(guān)鍵字等于給定值K的記錄。（2）查找成功，且表中只有一個關(guān)鍵字等于給定值K的記錄。（3）查找成功，且表中有若干個關(guān)鍵字等于給定值K的記錄，一次查找要求找出[提示]：均用順序查找法。8.2畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查[提示]：根據(jù)P.191ASL定義計算平均查找長度。8.3試推導(dǎo)含12個結(jié)點的平衡二叉樹的最大深度并畫出一棵這樣的樹。[提示]：沿最左分支生長，前提是：其任一祖先的右分支與左分支等深，如不等深，則先生長右分支，而生長右分支的前提是：其任一祖先的左分支與右分支等深，如不等深，則先生長左分支，如此交互考慮，逐步生長，直到12個結(jié)點。30，50，52，60，68，70。如果此后刪除50和68，畫出每一步執(zhí)行后2-3樹的狀態(tài)。8.5選取哈希函數(shù)H(k)=(3k)%11，用線性探測再散列法處理沖突。試在0～10的散列地址空間中，對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，并求等概率情況下查找成功與不成功時的平均查找長度。succASLunsucc8.6試為下列關(guān)鍵字建立一個裝載因子不小于0.75的哈希表，并計算你所構(gòu)造的哈希表的JIN）[提示]1）由裝填因子求出表長2）可利用字母序號設(shè)計哈希函數(shù)，（3）確定解決沖突的方法。8.7試編寫利用折半查找確定記錄所在塊的分塊查找算法。8.8試寫一個判別給定二叉樹是否為二叉排序樹的算法。設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)，且樹中結(jié)點的關(guān)鍵字均不同。[方法1]：用非遞歸中序遍歷算法，設(shè)雙指針pre,p一旦pre->data>p->data則返回假[方法2]：用遞歸中序遍歷算法，設(shè)全局指針pre參中序線索化算法）一旦pre->data>p->data則返回假[方法3]：用遞歸（中序或后序）算法（1）空樹是（2）單根樹是（3）左遞歸真（4）右遞歸真（5）左子樹的右端小于根（6）右子樹的左端大于根{8.9編寫算法，求出指定結(jié)點在給定的二叉排序樹中所在的層數(shù)。8.10編寫算法，在給定的二叉排序樹上找出任意兩個不同結(jié)點的最近公共祖先（若在兩結(jié)8.11編寫一個函數(shù)，利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序[提示]1）表中已經(jīng)有x2）表中沒有x（1）試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹并求其等概率的情況下查找成功的平均查找長度。（2）若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。（3）按表中元素的順序依次構(gòu)造一棵平衡二叉排序樹，并求其等概率的情況下查找成功的平均查找長度。[提示]：畫出判定樹或排序樹，根據(jù)P.191ASL定義計算平均查找長度。8.13含有9個葉子結(jié)點的3階B-樹中至少有多少個非葉子結(jié)點？含有10個葉子結(jié)點的3[提示]：葉子結(jié)點對應(yīng)空指針。8.14寫一時間復(fù)雜度為O(log2n+m)的算法，刪除二叉排序樹中所有關(guān)鍵字不小于x的結(jié)點，并釋放結(jié)點空間。其中n為樹中的結(jié)點個數(shù)，m為被刪除的結(jié)點個數(shù)。（2）如果p->key大于、等于x，則（3）左走一步，轉(zhuǎn)（2）{8.15在平衡二叉排序樹的每個結(jié)點中增加一個lsize域，其值為它的左子樹中的結(jié)點數(shù)加1。編寫一時間復(fù)雜度為O(logn)的算法，確定樹中第k個結(jié)點的位置。[提示]：先畫圖手工求。（1）sum=0,（2）從當前根開始沿左鏈找sum+lsize<=k的最大結(jié)點a，（3）沿a的右鏈求sum=sum+lsize，直到結(jié)點b，sum+lsize(b)>=k{9.1以關(guān)鍵碼序列（503，087，512，061，908，170，897，275，653，426）為例，手工執(zhí)行以下排序算法，寫出（前三趟）每一趟排序結(jié)束時的關(guān)鍵碼狀態(tài)：（1）直接插入排序2）希爾排序（增量d[1]=5（3）快速排序4）堆排序；（5）歸并排序6）基數(shù)排序。9.2一組關(guān)鍵字碼，40，27，28，12，15，50，7，采用快速排序或堆排序，寫出每趟9.3不難看出，對長度為n的記錄序列進行快速排序時，所需進行的比較次數(shù)依賴于這n個元素的初始排列。n=7時在最好情況下需進行多少次比較？請說明理由。對n=7給出一個最好情況的初始排列實例。（保證每個基準記錄都是中間記錄）9.4假設(shè)序列由n個關(guān)鍵字不同的記錄構(gòu)成，要求不經(jīng)排序而從中選出關(guān)鍵字從大到小順序的前k(k<<n)個記錄。試問如何進行才能使所作的關(guān)鍵字間比較次數(shù)達到最??？（簡單選擇、冒泡排序、堆排序均有可能）9.5插入排序中找插入位置的操作可以通過二分查找的方法來實現(xiàn)。試據(jù)此寫一個改進后9.6編寫一個雙向起泡的排序算法，即相鄰兩遍向相反方向起泡。{{if(a[i]>a[i+1]){}if(a[i]<a[i-1]){}9.7編寫算法，對n個關(guān)鍵字取整數(shù)值的記錄序列進行整理，以排在關(guān)鍵字為非負值的記錄之前，要求：采取順序存儲結(jié)構(gòu)，至多使用一個記錄的輔助存儲空間；算法的時間復(fù)雜度O(n)；討論算法中記錄的最大移動次數(shù)。[提示]：r[0]=r[1]，以0為分界值，參快速排序劃分過程，但不要求對元素排序。{{}9.8試以單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單選擇排序的算法{{{}{}//for9.9假設(shè)含n個記錄的序列中，其所有關(guān)鍵字為值介于v和w之間的整數(shù)，且其中很多關(guān)鍵字的值是相同的。則可按如下方法排序：另設(shè)數(shù)組number[v...w]且令number[i]為統(tǒng)計關(guān)鍵字取整數(shù)I的記錄數(shù)，之后按number重排序列以達到有序，編寫算法實現(xiàn)