計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)歷年真題試卷匯編2

計(jì)算機(jī)專業(yè)基礎(chǔ)綜合數(shù)據(jù)結(jié)構(gòu)（排序）歷年真題試卷匯編2（總分:58.00，做題時(shí)間：90分鐘）、單項(xiàng)選擇題（總題數(shù)：10，分?jǐn)?shù)：20.00）以下序列不是堆的是（）?！疚靼搽娮涌萍即髮W(xué)2001計(jì)算機(jī)應(yīng)用一、5（2分）】（分?jǐn)?shù)：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解析：一組關(guān)鍵字為（46,79,56,38,40，84），則利用堆排序的方法建立大頂堆的初始堆為（）?！颈本┙煌ù髮W(xué)2006一、8（2分）】（分?jǐn)?shù)：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個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲(chǔ)空間是（）?！疚靼搽娮涌萍即髮W(xué)2001計(jì)算機(jī)應(yīng)用一、10（2分）】（分?jǐn)?shù)：2.00）O(log2n)D(1) O(log2n)D(1) VO(n)()(nlogn)解析：對n個(gè)記錄的文件進(jìn)行堆排序，(分?jǐn)?shù)：2.00)O(log2n)O(n)O(nlog2n)VO(n*n)解析：有一組數(shù)據(jù)(15,9，7學(xué)1996二、5(2分)】20，最壞情況下的執(zhí)行時(shí)間是多少？（）?！颈本┙煌ù髮W(xué)2001一、9（2分）】一1,7,4）,用堆排序的篩選方法建立的初始堆為（）?！灸暇├砉ご螅ǚ?jǐn)?shù)：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解析：歸并排序中，歸并的趟數(shù)是（）。【南京理工大學(xué)2000一、19（1.5分）】（分?jǐn)?shù)：2.00）O（n）O（logn）VO（nlogn）O（n*n）解析：在排序算法中每一項(xiàng)都與其他各項(xiàng)進(jìn)行比較，計(jì)算出小于該項(xiàng)的項(xiàng)的個(gè)數(shù)，以確定該項(xiàng)的位置叫()。【北京郵電大學(xué)2000二、6(20/8分)】(分?jǐn)?shù)：2.00)插入排序枚舉排序V選擇排序交換排序解析：就分類算法所用的輔助空間而言，堆分類、快速分類和歸并分類的關(guān)系是()?！竟枮I工業(yè)大學(xué)2004二、6(1分)】(分?jǐn)?shù)：2.00)堆分類〈快速分類〈歸并分類V堆分類〈歸并分類〈快速分類堆分類>歸并分類>快速分類堆分類>快速分類>歸并分類解析：對給出的一組關(guān)鍵字{13,6,19,30,10,18),若按關(guān)鍵字非遞減排序，第一趟排序結(jié)果為{13,6,18,30,10,19},問可能采用的排序算法是()?！倦娮涌萍即髮W(xué)2005一、5(1分)】(分?jǐn)?shù)：2.00)單選擇排序快速排序希爾排序V2路歸并排序解析：解析：步長為3的希爾排序。(多選)在下列排序中，()方法的平均時(shí)間復(fù)雜度為O(nlogn)°【華中科技大學(xué)2007二、20(2分)】(分?jǐn)?shù)：2.00)選擇排序快速排序V歸并排序V基數(shù)排序解析：二、填空題(總題數(shù)：8,分?jǐn)?shù)：16.00)下列程序是歸并排序的遞歸算法。【北京交通大學(xué)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”)；}(分?jǐn)?shù)：2.00)正確答案：(正確答案：(1)k++(2)m=(low+high)/2(3)r,r2,m+1,high)解析：算法填空。[中國海洋大學(xué)2005四(8分)】設(shè)n個(gè)數(shù)的數(shù)列存放在數(shù)組a[1..n](下標(biāo)1?n)中，下列算法將變?yōu)橐粋€(gè)堆，注意：本算法不是完整的堆排序算法，僅將a變?yōu)槎秧斣鼐哂凶畲笾档摹按蠖选保浅跏级?。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)；}}(分?jǐn)?shù)：2.00)正確答案：(正確答案：(1)j++//沿右側(cè)向下篩(2)break//結(jié)束(3)j(4)x//最初被調(diào)整結(jié)點(diǎn)放入正確位置)解析：下面的C函數(shù)實(shí)現(xiàn)對鏈表head進(jìn)行選擇排序的算法，排序完畢，鏈表中的結(jié)點(diǎn)按結(jié)點(diǎn)值從小到大鏈接。請?jiān)诳湛蛱幪钌线m當(dāng)內(nèi)容，每個(gè)空框只填一個(gè)語句或一個(gè)表達(dá)式?！緩?fù)旦大學(xué)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)；}(分?jǐn)?shù)：2.00)正確答案：(正確答案：題中為操作方便，先增加頭結(jié)點(diǎn)(最后刪除)，p指向無序區(qū)的前一記錄，r指向最小值點(diǎn)的前驅(qū)，一趟排序結(jié)束，無序區(qū)第一個(gè)記錄與r所指結(jié)點(diǎn)的后繼交換指針。(1)q—>link!==null(2)r!=p(3)p一>link(4)p一>link==s(5)p=p一>link)解析：表插入排序的基本思想是在結(jié)點(diǎn)中設(shè)一指針字段，插入Ri時(shí)Rl到Ri一1巳經(jīng)用指針按排序碼不減次序鏈接起來，這時(shí)采用順序比較的方法找到Ri應(yīng)插入的位置，做鏈表插入。如此反復(fù)，直到把Rn插入為止。【山東工業(yè)大學(xué)2000五(16分)】【山東大學(xué)1998五】(1)(6分)請完成下列表插入的算法；①R[0]LINK—⑴)；RIN].LINl-(2)；②循環(huán)，I以一1為步長，從(3)到⑷執(zhí)行A.p—R[0].LINK;Q—0B.循環(huán)，當(dāng)P>0且(5)時(shí)，反復(fù)執(zhí)行Q-P；P-(6)C.R[Q].LINK-I；R[I]LINK-p(2)(2分)表插入排序的最大比較次數(shù)是(7)；(3)(2分)表插入排序的最小比較次數(shù)是(8)；(4)(2分)記錄移動(dòng)的次數(shù)是(9)；(5)(2分)需要附加的存儲(chǔ)空間是(10)； (6)(2分)該排序算法是否是穩(wěn)定的(11)。(分?jǐn)?shù)：2.00)正確答案：(正確答案：(1)N⑵0(3)N一1(4)1(5)R[P].KEY解析：建立在單鏈表上的一個(gè)c語言描述算法如下，其中L為鏈表頭結(jié)點(diǎn)的指針。請?zhí)畛渌惴ㄖ邢聞澗€的空白之處，并簡述算法完成的功能。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)；}}【北京科技大學(xué)2003三(20分)】(分?jǐn)?shù)：2.00)正確答案：(正確答案：本算法是在單鏈表上的簡單選擇排序程序，每趟找到最小值后，交換結(jié)點(diǎn)數(shù)據(jù)。(1)p(2)minp=p(3)q(4)minp=q(5)minp!=p(6)p=p—>next)解析：下列算法為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i，將a[i]和a[i+1]進(jìn)行比較，第二趟對所有偶數(shù)的i，將a[f]和a[i+1]進(jìn)行比較，每次比較時(shí)若a[i]>a[f+1]，將二者交換；以后重復(fù)上述二趟過程，直至整個(gè)數(shù)組有序。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)；}【上海大學(xué)2000一、1(10分)】(分?jǐn)?shù)：2.00)正確答案：(正確答案：(1)1(2)a[i]=t(3)(i2；iWn；i+=2)(4)1(5)flag)解析：

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