計算機專業基礎綜合數據結構（排序）歷年真題試卷匯編2（總分:58.00，做題時間：90分鐘）、單項選擇題（總題數：10，分數：20.00）以下序列不是堆的是（）。【西安電子科技大學2001計算機應用一、5（2分）】（分數：2.00）（100， 85，98，77，80， 60， 82， 40， 20，10，66）（100， 98，85，82，80， 77， 66， 60， 40，20，10）（10，20，40，60，66，77，80，82，85，98，100）（100，85，40，77，80，60，66，98，82，10，20）V解析：一組關鍵字為（46,79,56,38,40，84），則利用堆排序的方法建立大頂堆的初始堆為（）。【北京交通大學2006一、8（2分）】（分數：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46VC.84，79，56，46，40，38D.84，56，79，40，46，38解析：在對，z個元素的序列進行排序時，堆排序所需要的附加存儲空間是（）。【西安電子科技大學2001計算機應用一、10（2分）】（分數：2.00）O(log2n)D(1) O(log2n)D(1) VO(n)()(nlogn)解析：對n個記錄的文件進行堆排序，(分數：2.00)O(log2n)O(n)O(nlog2n)VO(n*n)解析：有一組數據(15,9，7學1996二、5(2分)】20，最壞情況下的執行時間是多少？（）。【北京交通大學2001一、9（2分）】一1,7,4）,用堆排序的篩選方法建立的初始堆為（）。【南京理工大（分數：2.00)A.一■1,4，8，9，20，B.一1,7，15，7，4，C.一1,4，7，8，20，D.A，B，C均不對，，17815，20，5，7解析：歸并排序中，歸并的趟數是（）。【南京理工大學2000一、19（1.5分）】（分數：2.00）O（n）O（logn）VO（nlogn）O（n*n）解析：在排序算法中每一項都與其他各項進行比較，計算出小于該項的項的個數，以確定該項的位置叫()。【北京郵電大學2000二、6(20/8分)】(分數：2.00)插入排序枚舉排序V選擇排序交換排序解析：就分類算法所用的輔助空間而言，堆分類、快速分類和歸并分類的關系是()。【哈爾濱工業大學2004二、6(1分)】(分數：2.00)堆分類〈快速分類〈歸并分類V堆分類〈歸并分類〈快速分類堆分類>歸并分類>快速分類堆分類>快速分類>歸并分類解析：對給出的一組關鍵字{13,6,19,30,10,18),若按關鍵字非遞減排序，第一趟排序結果為{13,6,18,30,10,19},問可能采用的排序算法是()。【電子科技大學2005一、5(1分)】(分數：2.00)單選擇排序快速排序希爾排序V2路歸并排序解析：解析：步長為3的希爾排序。(多選)在下列排序中，()方法的平均時間復雜度為O(nlogn)°【華中科技大學2007二、20(2分)】(分數：2.00)選擇排序快速排序V歸并排序V基數排序解析：二、填空題(總題數：8,分數：16.00)下列程序是歸并排序的遞歸算法。【北京交通大學2006七、1(6分)】#definemaxsize1000#define13.13.10#includeintr[rm+1],r2[rm+1]；//r[0]閑置inta[10]={17,1,23,77,51,1_3,39,11,19,15)；voidmerge(intr[],intlow,intm,inthigh,intr2[]){intij,k；k：i；10w；j=m+1；while(i<=m&&j<=high){if(r[i]<=r[j]){r2[k]=r[i]；i++；)elSe{r2[k]=r[j]；j++；)(1)；}if(i>m)while(j<=high){r2[k]=r[j；j++；k++；}elsewhile(i<=m){r2[k]=r[i]；i++；k++j}}voidmergesort(intr[],intr1[],int：low,inthigh){int：m,r2Inn+1]；if(low==high)r1[low]=r[1ow]；el8e{(2);mergesort(rr2,low,m)；mergesort((3))；merge(2：2,low,m,high,r1)；}}main(){inti；for(i=0；i<=9;i++)r[i+1];a[i]；mergesort(r,r2,1,3.0)；for(i=1；i<=10；i++)print：f("%d”,r2[i]);printf("\n”)；}(分數：2.00)正確答案：(正確答案：(1)k++(2)m=(low+high)/2(3)r,r2,m+1,high)解析：算法填空。[中國海洋大學2005四(8分)】設n個數的數列存放在數組a[1..n](下標1?n)中，下列算法將變為一個堆，注意：本算法不是完整的堆排序算法，僅將a變為堆頂元素具有最大值的“大堆”，是初始堆。voidadjust(ina口，int13.){inti,j,8,x：；for(i=n/2;i>=1；i ){s=i；x=a[s];for(j=2*s；j<11&&a[j]a[j])(2)；a[S]=a[j]；s=()；}a[S]=(4)；}}(分數：2.00)正確答案：(正確答案：(1)j++//沿右側向下篩(2)break//結束(3)j(4)x//最初被調整結點放入正確位置)解析：下面的C函數實現對鏈表head進行選擇排序的算法，排序完畢，鏈表中的結點按結點值從小到大鏈接。請在空框處填上適當內容，每個空框只填一個語句或一個表達式。【復旦大學1999六(15分)】#includetypedefstructnode{chardata；structnode*link；)node；node*select(node*head)(node*p,*q,*r,*s；p=(node*)malloc(sizeof(node))；P一>link=head；head=p；while(P一>link!=null)(q=p->link；r=p；while((1)){if(q->link—>datalink—>data)r=q；q=q->link；}if((2))(s=r—>link；r一>link=s—>link；S一>link=((3))； ((4))；}((5))；}p=head；head=head一>link；free(p)；return(head)；}(分數：2.00)正確答案：(正確答案：題中為操作方便，先增加頭結點(最后刪除)，p指向無序區的前一記錄，r指向最小值點的前驅，一趟排序結束，無序區第一個記錄與r所指結點的后繼交換指針。(1)q—>link!==null(2)r!=p(3)p一>link(4)p一>link==s(5)p=p一>link)解析：表插入排序的基本思想是在結點中設一指針字段，插入Ri時Rl到Ri一1巳經用指針按排序碼不減次序鏈接起來，這時采用順序比較的方法找到Ri應插入的位置，做鏈表插入。如此反復，直到把Rn插入為止。【山東工業大學2000五(16分)】【山東大學1998五】(1)(6分)請完成下列表插入的算法；①R[0]LINK—⑴)；RIN].LINl-(2)；②循環，I以一1為步長，從(3)到⑷執行A.p—R[0].LINK;Q—0B.循環，當P>0且(5)時，反復執行Q-P；P-(6)C.R[Q].LINK-I；R[I]LINK-p(2)(2分)表插入排序的最大比較次數是(7)；(3)(2分)表插入排序的最小比較次數是(8)；(4)(2分)記錄移動的次數是(9)；(5)(2分)需要附加的存儲空間是(10)； (6)(2分)該排序算法是否是穩定的(11)。(分數：2.00)正確答案：(正確答案：(1)N⑵0(3)N一1(4)1(5)R[P].KEY解析：建立在單鏈表上的一個c語言描述算法如下，其中L為鏈表頭結點的指針。請填充算法中下劃線的空白之處，并簡述算法完成的功能。typedefstructnode(intdata；structnode*next；)Lnode，‘link；voidSelectSort(1inkL){linkP，q，minp；inttemp；p=L—>next；while((1))((2))；q=p—>next；while((3)){if(q->datadata)(4)；q=q—>next；}if((5))(temp=p—>data；p—>data=minp->data;minp-~data=temp；)(6)；}}【北京科技大學2003三(20分)】(分數：2.00)正確答案：(正確答案：本算法是在單鏈表上的簡單選擇排序程序，每趟找到最小值后，交換結點數據。(1)p(2)minp=p(3)q(4)minp=q(5)minp!=p(6)p=p—>next)解析：下列算法為奇偶交換排序，思路如下：第一趟對所有奇數的i，將a[i]和a[i+1]進行比較，第二趟對所有偶數的i，將a[f]和a[i+1]進行比較，每次比較時若a[i]>a[f+1]，將二者交換；以后重復上述二趟過程，直至整個數組有序。voidoesort(inta[n])(intflagi，t；do{flag=0;for(i=l；ia[i+1]){flag=(1)；t=a[i+1]；a[i+1]=a[i]；(2)；)for(3)if(a[i]>a[i+1]){flag=(4)；t=a[i+1]；a[i+1];a[i]，a[i]=t；})while(5)；}【上海大學2000一、1(10分)】(分數：2.00)正確答案：(正確答案：(1)1(2)a[i]=t(3)(i2；iWn；i+=2)(4)1(5)flag)解析：

填空并回答相關問題。(1)下面是將任意序列調整為最大堆(MAXHEAP)的算法，請將空白部分填上。將任意序列調整為最大堆通過不斷調用adjust函數，即for(i=n/2；i>0；i一一)adjust(1ist,i,n)；其中list為待調整序列所在數組(從下標1開始),n為序列元素個數,adjust函數為：voidadjust(int1ist[],introot,intn)/*將以root為下標的對應元素作為待調整堆的根，待調整元素放在list數組中，最大元素下標為n*/{intchild，rootkey；rootkey=list[root]；child=2*root；while(chiId<=n){if(child<n)&&(1ist[child]1i8t[child])break；else{List[②]=list[child]；child*=2：}}list[child/2]：r00tkey；}(2)判斷下列序列能否構成最大堆：(12,70，33，65，24，56，48，92，86,33)；若不能，按上述算法將其調整為堆，調整后的結果為。【浙江大學1998七(11分)】(分數：2.00)正確答案：(正確答案：(1)①child=child+1；②child/2(2)原序列不能構成大堆。調整后的大堆是：92,86，56，70，33，33，48，65，12，24)解析：用鏈表表示的數據的簡單選擇排序，結點的域為數據域data，指針域next；鏈表首指針為head，鏈表無頭結點。【南京理工大學2000三、2(6分)】Selectsoet(head)p=head；while(p(1)){q=p；r=(2)while((3)){if((4))q=；r=(5)；}tmp=q—>data；q—>data=p—>data；p—>data=tmp；p=(6)；}(分數：2.00)正確答案：(正確答案：題中p指向無序區第一個記錄，q指向最小值結點，一趟排序結束，p和q所指結點值交換，同時向后移p指針。(1)!=null(2)p—>next(3)r!=nun(4)r—>datadata(5)r—>next(6)p—>next)解析：三、綜合題(總題數：2,分數：10.00)設待排序的關鍵字分別為28,13,72,85,39,41，6,20。按二分法插入排序算法巳使前7個記錄有序，中間結果如下：——試在此基礎上，沿用上述表達方式，給出繼續采用二分法插入第8個記錄的比較過程。(分數：4.00)(1).使用二分法插入排序所要進行的比較次數，是否與待排序的記錄的初始狀態有關？(分數：2.00)正確答案：(正確答案：將r+1(正確答案：(正確答案：將r+1(即第3個)后的元素向后移動，并將20放入r+1處，整個序列有序。使用折半插入排序所要進行的比較次數，與待排序的記錄的初始狀態無關。不論待排序序列是否有序，巳形成的部分子序列是有序的。折半插入首先查找插入位置，插入位置是判定樹查找失敗的位置。失敗位置只能在判定樹的最下兩層上。)解析：.在一些特殊情況下，二分法插入排序比直接插入排序要執行更多的比較。這句話對嗎？【山東工業大學1996七(10分)】(分數：2.00)正確答案：(正確答案：一些特殊情況下，折半插入排序要比直接插入排序要執行更多的比較。例如，在待排序序列巳有序的情況下就是如此。)解析：算法模擬(15分，問題1、2各6分，問題3占3分)設待排序的記錄共7個，排序碼分別為8,3,2,5,9,1,6。(分數：6.00)(1).用直接插入排序。試以排序碼序列的變化描述形式說明排序全過程(動態過程)要求按遞減順序排序。(分數：2.00)正確答案：(正確答案：直接插入排序第一趟(3)[8,3],2,5,9,1,6第二趟(2)[8,3,2],5,9,1,6第三趟（5）[8,5,3,2],9,1,6第四趟（9）[9,8,5,3,2],1,6第五趟（1）[9,8,5,3,2,1],6第六趟（6）[9,8,6,5,3,2,-1]）解析：（2）.用直接選擇排序。試以排序碼序列的變化描述形式說明排序全過程（動態過程）要求按遞減順序排序。（分數：2.00）正確答案：（正確答案:直接選擇排序（第六趟后僅剩一個元素，是最小的，直接選擇排序結束）第一趟（9）[9],3,2,5,8,1,6第二趟（8）[9,8],2,5,3,1,6第三趟（6）[9，8,6],5,3,1,2第四趟（5）[9,8,6,5],3,1,2第五趟（3）[9，8,6,5,3],1,2第六趟（2）[9，8,6,5,3,2],1）解析：（3）.直接插入排序算法和直接選擇排序算法的穩定性如何？【山東工業大學1997四（15分）】（分數：2.00）正確答案：（正確答案：直接插入排序是穩定排序，直接選擇排序是不穩定排序。）解析：四、設計題（總題數：6,分數：12.00）設單鏈表頭結點指針為L，結點數據值為整型，試寫出對鏈表L按“插入方法”排序的算法:LINSORT（L）。【北京科技大學1999十、1（10分）2000十、1（10分）】（分數：2.00）正確答案：（正確答案：原理同上，只是在鏈表上進行。核心語句段如下：P=L一>link—>link；//鏈表至少一個結點，P初始指向鏈表中第2結點（若存在）L一>link—>1ink：null； //初始假定第一個記錄有序while（p!=null）fq=p一>link； //q指向P的后繼結點S=L：while（s一>link&&s—>link—>keykey）s—s一>link；//向后找插入位置P一>link=s—>link；s一>link=p；//插入結點p=q；//恢復p指向當前結點｝//while）解析：二路插入排序是將待排關鍵字序列r[1..n]中關鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注：向量d可視為循環表），其原則為，先將r[1]賦給d[1],再從r[2]記錄開始分二路插入。編寫實現二路插入排序算法。【北京工業大學1998八（10分）】（分數：2.00）正確答案：（正確答案:二路插入排序是對直接插入的改進，特別注意在前半部插入時元素的移動。for（i=2；i<=n；i++）//初始化：d[1]=R[1]；first=1；final=1；if（R[i].key>=d[1].key）//插入后部｛low=1；high=final；while（low<=high）//折半查找插入位置｛m=（low+high）/2；if（R[i].key=high+l；j—-）d[j+1]=d[j]； //移動元素d[high+1]：R[i]；final++； //插入有序位置｝//ifelse//插入前部｛if（first==1）（first=n；d[n]=R[i]；｝else（low=first；high=n；while（low<=high）｛m=（10w+high）/2；if（R[i].key<=high；J++｝d[j一1]=d[j]； //移動元素d[high]=R[i]；first一一；｝//if｝//ifR[1]=dcfirst]；for（i=first%n+1,j=2；i!=fisrt;i=i%n+1,j++）R[j]=d[i]；//將序列復制回去）解析：21.2路歸并排序的另一種策略是，先對待排序序列掃描一遍，找出并劃分為若干個最大有序子序列，將這些子序列作為初始歸并段，設計算法在鏈表結構上實現這一策略。【大連理工大學2005三、1（45/3分）】（分數：2.00）正確答案：（正確答案：用向量存儲各最大有序子序列的首元指針，從鏈表頭開始兩兩歸并，當兩個中的一個子序列的指針等于下個序列開始指針時，該子序列結束，將另一序列剩余部分鏈入。記住每次形成的新序列首尾指針。設初始有n個有序子序列，經過logn趟合并，形成一個有序序列。）解析：編寫程序，對單鏈表結構的線性表進行排序，并詳細說明排序算法，分析時間復雜度。【南京航空航天大學2003四（10分）】（分數：2.00）正確答案：（正確答案：可以使用鏈表的直接插入排序。exchange=1；tail=null； //tail是雙向鏈表尾，算法過程中是向上起泡的開始結點while（exchange）fp=head—>next； //P是工作指針，指向當前結點exchange=0； //假定本趟無交換while（p—>next!=tail）//向下（右）起泡，一趟有一最大元素沉底if（p—>data>p—>next—>data）//交換兩結點指針，涉及6條鏈（temp=p—>next；exchange=1； //有交換P—>next=temp—>next；temp—>next—>prior=p//先將結點從鏈表上摘下temp—>next=p；P—>prior—>next=temp；//將temp插到P結點前temp—>prior=p—>prior；P—>prior=temp；}elsep=p—>next； //無交換，指針后移tail=p； //準備向上起泡p=tail—>prior；while（exchange&&P—>prior!=head）//向上起泡，一趟有一最小元素冒出head=P；//準備向下起泡}／）解析：輔助地址表的排序是不改變結