1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 7 及答案与解析一、单项选择题1 以下序列不是堆的是( )。【西安电子科技大学 2001 计算机应用一、5(2 分)】（A）(100 ，85，98，77，80，60，82，40，20，lO，66)（B） (100，98，85，82，80，77，66，60，40，20，10)（C） (10，20，40，60，66，77，80，82，85，98，100)（D）(100 ，85，40，77，80，60，66，98，82，10，20)2 一组关键字为(46，79，56，38，40，84)，则利用堆排序的方法建立大顶堆的初始堆为( ) 。 【北京交通大
2、学 2006 一、8(2 分) 】（A）79，46，56，38，40，84（B） 84，79，56，38，40，46（C） 84，79，56，46，40，38（D）84，56，79，40，46，383 在对，z 个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。【西安电子科技大学 2001 计算机应用一、10(2 分)】（A）O(log 2n)（B） D(1)（C） O(n)（D）()(nlog 2n)4 对 n 个记录的文件进行堆排序，最坏情况下的执行时间是多少? ( )。【北京交通大学 2001 一、9(2 分) 】（A）O(log 2n)（B） O(n)（C） O(nlog2n
3、)（D）O(n*n)5 有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。【南京理工大学 1996 二、5(2 分) 】（A）一 1，4，8，9，20，7，15，7（B）一 1，7，15，7，4，8，20，9（C）一 1，4，7，8，20，1 5，7，9 （D）A，B，C 均不对6 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19(15 分)】（A）O(n)（B） O(logn)（C） O(nlogn)（D）O(n*n)7 在排序算法中每一项都与其他各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( ) 。【北京邮电大学
4、2000 二、6(208 分)】（A）插入排序（B）枚举排序（C）选择排序（D）交换排序8 就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( )。【哈尔滨工业大学 2004 二、6(1 分)】（A）堆分类 归并分类 快速分类（D）堆分类快速分类归并分类9 对给出的一组关键字13，6，19，30，10，18)，若按关键字非递减排序，第一趟排序结果为13，6，18 ，30，10，19 ，问可能采用的排序算法是 ( )。【电子科技大学 2005 一、5(1 分)】（A）单选择排序（B）快速排序（C）希尔排序（D）2 路归并排序10 (多选 )在下列排序中，( ) 方法的平均时间复杂
5、度为 O(nlogn)。【华中科技大学2007 二、20(2 分) 】（A）选择排序（B）快速排序（C）归并排序（D）基数排序二、填空题11 下列程序是归并排序的递归算法。【北京交通大学 2006 七、1(6 分)】#define maxsize 1000#define 13 1310#includeint rrm+1，r2rm+1；r0闲置int a10=17，1，23，77，51，1_3，3 9，11，19，1 5)；void merge(int r， int low， int m， int high， int r2 )int i， j，k； k：i；10w； j=m+1；while(im
6、)while(j=1；i-)s=i；x=as;for(j=2*s； jaj) (2) ；aS=aj；s= ( ) ；aS=(4)；13 下面的 C 函数实现对链表 head 进行选择排序的算法，排序完毕，链表中的结点按结点值从小到大链接。请在空框处填上适当内容，每个空框只填一个语句或一个表达式。【复旦大学 1999 六(1 5 分)】#includetypedef struct nodechar data；struct node*link；)node ；node*select(node*head)(node*p，*q， *r，*s；p=(node*)malloc(sizeof(node)；P
7、一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)；14 表插入排序的基本思想是在结点中设一指针字段，插入 Ri 时 Rl 到 Ri 一 1 已经用指针按排序码不减次序链接起来，这时采用顺序比较的方法找到 Ri 应插入
8、的位置，做链表插入。如此反复，直到把 Rn 插入为止。【山东工业大学 2000 五(16 分)】【山东大学 1998 五】(1)(6 分) 请完成下列表插入的算法；R0LINK(1) ；R INLINl(2)；循环，I 以一 1 为步长，从 (3)到(4)执行 A.pR0LINK;Q0B.循环，当 P0 且(5) 时，反复执行QP；P(6)C.RQLINKI；RILINKp(2)(2 分) 表插入排序的最大比较次数是 (7) ；(3)(2 分) 表插入排序的最小比较次数是 (8) ；(4)(2 分) 记录移动的次数是 (9)；(5)(2 分) 需要附加的存储空间是 (10)；(6)(2 分)
9、该排序算法是否是稳定的 (11)。15 建立在单链表上的一个 c 语言描述算法如下，其中 L 为链表头结点的指针。请填充算法中下划线的空白之处，并简述算法完成的功能。typedef struct node(int data；struct node*next；)Lnode ，link；void SelectSort(1ink L)link P，q ，minp； int temp；p=L 一next；while( (1) )( (2) ； q=p 一next；while( (3) )if(q-datadata)(4) ；q=q 一next；if( (5) )(temp=p 一 data；p 一da
10、ta=minp-data ; minp-data=temp；)(6) ； 【北京科技大学 2003 三(20 分) 】16 下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的 i，将 ai和 ai+1进行比较，第二趟对所有偶数的 i，将 af和 ai+1进行比较，每次比较时若 aiaf+1，将二者交换；以后重复上述二趟过程，直至整个数组有序。void oesort(int an)(int flag，i，t；doflag=0;for(i=l； iai+1)flag=(1)； t=ai+1；ai+1=ai；(2)；)for (3)if(aiai+1)flag=(4)； t=ai+1；ai+1;a
11、i，ai=t ；)while (5) ；【上海大学 2000 一、1(10 分)】17 填空并回答相关问题。(1)下面是将任意序列调整为最大堆(MAXHEAP)的算法，请将空白部分填上。将任意序列调整为最大堆通过不断调用 adjust 函数，即for(i=n2；i0 ；i 一一)adjust(1ist，i，n)；其中 list 为待调整序列所在数组(从下标 1 开始)，n 为序列元素个数，adjust 函数为：void adjust(int 1ist，int root，int n)*将以 root 为下标的对应元素作为待调整堆的根，待调整元素放在 list 数组中，最大元素下标为 n*int
12、child，rootkey ；rootkey=listroot；child=2*root；while(chiId1i8tchild)break；elseList=listchild；child*=2：listchild2 ：r00tkey ；(2)判断下列序列能否构成最大堆：(12，70，33，65，24，56，48，92，86，33)；若不能，按上述算法将其调整为堆，调整后的结果_为。【浙江大学 1998 七(11 分) 】18 用链表表示的数据的简单选择排序，结点的域为数据域 data，指针域 next；链表首指针为 head，链表无头结点。 【南京理工大学 2000 三、2(6 分)】S
13、electsoe t(head)p=head；while (p(1) )q=p； r=(2)while(3) )if (4) ) q=r；r=(5) ；tmp=q 一data； q 一data=p 一data； p 一data=tmp ； p= (6) ；三、综合题18 设待排序的关键字分别为 28，13，72，85，39，41，6，20。按二分法插入排序算法已使前 7 个记录有序，中间结果如下：试在此基础上，沿用上述表达方式，给出继续采用二分法插入第 8 个记录的比较过程。19 使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关?20 在一些特殊情况下，二分法插入排序比直
14、接插入排序要执行更多的比较。这句话对吗?【山东工业大学 1996 七(10 分) 】20 算法模拟(15 分，问题 1、2 各 6 分，问题 3 占 3 分)设待排序的记录共 7 个，排序码分别为 8，3，2，5，9，1，6。21 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。22 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。23 直接插入排序算法和直接选择排序算法的稳定性如何?【山东工业大学 1997 四(15 分)】四、设计题24 设单链表头结点指针为 L，结点数据值为整型，试写出对链表 L 按“插入
15、方法”排序的算法：LINSORT(L)。【北京科技大学 1999 十、1(10 分)2000 十、1(10 分) 】25 二路插入排序是将待排关键字序列 r1n中关键字分二路分别按序插入到辅助向量 d1n前半部和后半部(注：向量 d 可视为循环表)，其原则为，先将 r1赋给d1，再从 r2记录开始分二路插入。编写实现二路插入排序算法。【北京工业大学 1998 八(10 分) 】26 2 路归并排序的另一种策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子序列，将这些子序列作为初始归并段，设计算法在链表结构上实现这一策略。【大连理工大学 2005 三、1(453 分)】27 编写程序，
16、对单链表结构的线性表进行排序，并详细说明排序算法，分析时间复杂度。【南京航空航天大学 2003 四(10 分)】28 辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用 K1，K2 ，Kn表示 n 个结点的值，用 T1，T2，Tn表示辅助地址表。初始时 Ti：=i，在排序中，凡需对结点交换就用它的地址来进行。例如当 n=3 时，对 K(31，11，19)则有T(2，3，1)。试编写实现辅助地址表排序 (按非递减序)算法的语句序列。【重庆大学 2000 四、2】29 输入 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数
17、组，然后按成绩由高到低的次序输出(每行 10 个记录)。排序方法采用选择排序。【北京师范大学 1999 五】计算机专业基础综合数据结构（排序）历年真题试卷汇编 7 答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 B3 【正确答案】 B4 【正确答案】 C5 【正确答案】 C6 【正确答案】 B7 【正确答案】 B8 【正确答案】 A9 【正确答案】 C【试题解析】 步长为 3 的希尔排序。10 【正确答案】 B,C二、填空题11 【正确答案】 (1)k+ (2)m=(low+high)2 (3)r,r2，m+1，high12 【正确答案】 (1)j+沿右侧向下筛 (2)break
18、 结束 (3)j (4)x最初被调整结点放入正确位置13 【正确答案】 题中为操作方便，先增加头结点(最后删除)，p 指向无序区的前一记录，r 指向最小值点的前驱，一趟排序结束，无序区第一个记录与 r 所指结点的后继交换指针。 (1)q 一link!=null (2)r!=p (3)p 一link (4)p 一link=s (5)p=p一link14 【正确答案】 (1)N (2)0 (3)N 一 1 (4)1 (5)RPKEYnext16 【正确答案】 (1)1 (2)ai=t (3)(i 2；in；i+=2) (4)1(5)flag17 【正确答案】 (1) child=child+1；
19、child2 (2) 原序列不能构成大堆。调整后的大堆是：92，86，56，70，33，33，48，65，12，2418 【正确答案】 题中 p 指向无序区第一个记录，q 指向最小值结点，一趟排序结束，p 和 q 所指结点值交换，同时向后移 p 指针。 (1)!=null (2)p 一next (3)r!=nun (4)r 一datadata (5)r 一next (6)p 一next三、综合题19 【正确答案】 将 r+1(即第 3 个)后的元素向后移动，并将 20 放入 r+1 处，整个序列有序。(1)使用折半插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不论待排序序列是否有序
20、，已形成的部分子序列是有序的。折半插入首先查找插入位置，插入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。20 【正确答案】 一些特殊情况下，折半插入排序要比直接插入排序要执行更多的比较。例如，在待排序序列已有序的情况下就是如此。21 【正确答案】 直接插入排序第一趟 (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，-122 【正确答案】 直接选择排序(第六趟后仅剩一个元素，是最小的，直
21、接选择排序结束)第一趟 (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，123 【正确答案】 直接插入排序是稳定排序，直接选择排序是不稳定排序。四、设计题24 【正确答案】 原理同上，只是在链表上进行。核心语句段如下：P=L 一link 一link ； 链表至少一个结点，P 初始指向链表中第 2 结点(若存在)L 一link 一1ink：null； 初始假定第一个记录有序while(p!=null)fq
22、=p 一link； q 指向 P 的后继结点S=L：while(s 一link Tj=Tj+1；Tj+1=t；exchange=0 ；if(exchange)break； 一趟排序无交换发生，结束 sort上述算法得到辅助地址表，Ti的值是排序后 K 的第 i 个记录，要使序列 K 有序，则要按 T 再物理地重排 K 的各记录。算法如下：void Rearrange(RecType K，int T，n)对有 n 个记录的序列 K，按其辅助地址表 T 进行物理非递减排序for(i=1；i(=n；i+)if(Ti!=i)(j=ij rc=Ki; 暂存记录 Kiwhile(Tj!=i) 调整 KTj到 Tj=i 为止m=Tj； Kj=Km； Tj=j；j=m；Kj=rc；Tj=j ； 记录 Ri到位 if Rearrange29 【正确答案】 使用简单选择排序，核心语句段如下：for(i=i; iR Ek score) k=j；if(i!=k) RiRk； 与第 i 个记录交换forfor(i=i；i=n；i+) 输出成绩 cout” “(Rinum” ”(Riscore) ；if(i10=0)coutendlj for
