计算机专业基础综合数据结构历年真题试卷汇编2

计算机专业基础综合数据结构（排序）历年真题试卷汇编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；//准备向下起泡}／）解析：辅助地址表的排序是不改变结