1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 2 及答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.以下序列不是堆的是( )。【西安电子科技大学 2001 计算机应用一、5(2 分)】（分数：2.00）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，
2、40，84)，则利用堆排序的方法建立大顶堆的初始堆为( )。【北京交通大学 2006 一、8(2 分)】（分数：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，383.在对，z 个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。【西安电子科技大学 2001 计算机应用一、10(2 分)】（分数：2.00）A.O(log 2 n)B.D(1)C.O(n)D.()(nlog 2 n)4.对 n 个记录的文件进行堆排序，最坏情况下的执行时间是多少? ( )。【北京交通大学 2001
3、 一、9(2 分)】（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n)D.O(n*n)5.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。【南京理工大学 1996 二、5(2 分)】（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，1 5，7，9D.A，B，C 均不对6.归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19(15 分)】（分数：2.00）A.O(n)B.O(logn)C.O(nlogn)D.O(n*n)7.在
4、排序算法中每一项都与其他各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( )。【北京邮电大学 2000 二、6(208 分)】（分数：2.00）A.插入排序B.枚举排序C.选择排序D.交换排序8.就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( )。【哈尔滨工业大学 2004二、6(1 分)】（分数：2.00）A.堆分类归并分类快速分类D.堆分类快速分类归并分类9.对给出的一组关键字13，6，19，30，10，18)，若按关键字非递减排序，第一趟排序结果为13，6，18，30，10，19，问可能采用的排序算法是( )。【电子科技大学 2005 一、5(1 分)】（
5、分数：2.00）A.单选择排序B.快速排序C.希尔排序D.2 路归并排序10.(多选)在下列排序中，( )方法的平均时间复杂度为 O(nlogn)。【华中科技大学 2007 二、20(2 分)】（分数：2.00）A.选择排序B.快速排序C.归并排序D.基数排序二、填空题(总题数：8，分数：16.00)11.下列程序是归并排序的递归算法。【北京交通大学 2006 七、1(6 分)】 #define maxsize 1000 #define 131310 #include int rrm+1，r2rm+1；r0闲置 int a10=17，1，23，77，51，1_3，3 9，11，19，1 5)；
6、 void merge(int r， int low， int m， int high， int r2 ) int i， j，k； k：i；10w； j=m+1； while(im) while(j=1；i-) s=i；x=as; for(j=2*s；jlink=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) )；
7、( (5) ) ； p=head；head=head 一link；free(p)；return(head)； （分数：2.00）_14.表插入排序的基本思想是在结点中设一指针字段，插入 Ri 时 Rl 到 Ri 一 1 已经用指针按排序码不减次序链接起来，这时采用顺序比较的方法找到 Ri 应插入的位置，做链表插入。如此反复，直到把 Rn 插入为止。【山东工业大学 2000 五(16 分)】【山东大学 1998 五】(1)(6 分)请完成下列表插入的算法； R0LINK(1)；R INLINl(2)； 循环，I 以一 1 为步长，从(3)到(4)执行 A.pR0LINK; Q0B.循环，当 P0
8、 且(5) 时，反复执行 QP； P(6)C.RQLINKI； RILINKp (2)(2 分)表插入排序的最大比较次数是(7) ； (3)(2 分)表插入排序的最小比较次数是(8) ； (4)(2 分)记录移动的次数是(9)； (5)(2 分)需要附加的存储空间是(10)； (6)(2 分)该排序算法是否是稳定的(11)。（分数：2.00）_15.建立在单链表上的一个 c 语言描述算法如下，其中 L 为链表头结点的指针。请填充算法中下划线的空白之处，并简述算法完成的功能。 typedef struct node(int data；struct node*next；)Lnode，link； v
9、oid 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 一data=minp-data ; minp-data=temp；) (6) ； 【北京科技大学 2003 三(20分)】（分数：2.00）_16.下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的 i，将 ai和 ai+1进行比较，第二趟对所有偶数的 i，将 af和 ai+
10、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;ai，ai=t ； )while (5) ； 【上海大学 2000 一、1(10 分)】（分数：2.00）_17.填空并回答相关问题。 (1)下面是将任意序列调整为最大堆(MAXHEAP)的算法，请将空白部分填上。将任意序列调整为最大堆通过不断调
11、用 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 child，rootkey； rootkey=listroot； child=2*root； while(chiIddata； q 一data=p 一data； p 一data=tmp ； p= (6) ； （
12、分数：2.00）_三、综合题(总题数：2，分数：10.00)设待排序的关键字分别为 28，13，72，85，39，41，6，20。按二分法插入排序算法已使前 7 个记录有序，中间结果如下： （分数：4.00）(1).使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关?（分数：2.00）_(2).在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗?【山东工业大学 1996 七(10 分)】（分数：2.00）_算法模拟(15 分，问题 1、2 各 6 分，问题 3 占 3 分)设待排序的记录共 7 个，排序码分别为8，3，2，5，9，1，6。（分数：6.
13、00）(1).用直接插入排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。（分数：2.00）_(2).用直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。（分数：2.00）_(3).直接插入排序算法和直接选择排序算法的稳定性如何?【山东工业大学 1997 四(15 分)】（分数：2.00）_四、设计题(总题数：6，分数：12.00)19.设单链表头结点指针为 L，结点数据值为整型，试写出对链表 L 按“插入方法”排序的算法：LINSORT(L)。【北京科技大学 1999 十、1(10 分)2000 十、1(10 分)】（分数：
14、2.00）_20.二路插入排序是将待排关键字序列 r1n中关键字分二路分别按序插入到辅助向量 d1n前半部和后半部(注：向量 d 可视为循环表)，其原则为，先将 r1赋给 d1，再从 r2记录开始分二路插入。编写实现二路插入排序算法。【北京工业大学 1998 八(10 分)】（分数：2.00）_21.2 路归并排序的另一种策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子序列，将这些子序列作为初始归并段，设计算法在链表结构上实现这一策略。【大连理工大学 2005 三、1(453分)】（分数：2.00）_22.编写程序，对单链表结构的线性表进行排序，并详细说明排序算法，分析时间复杂度。
15、【南京航空航天大学 2003 四(10 分)】（分数：2.00）_23.辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用 K1，K2，Kn表示 n 个结点的值，用 T1，T2，Tn表示辅助地址表。初始时 Ti：=i，在排序中，凡需对结点交换就用它的地址来进行。例如当 n=3 时，对K(31，11，19)则有 T(2，3，1)。试编写实现辅助地址表排序(按非递减序)算法的语句序列。【重庆大学2000 四、2】（分数：2.00）_24.输入 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，然后按成绩由高到低的次序输出
16、(每行 10 个记录)。排序方法采用选择排序。【北京师范大学 1999 五】（分数：2.00）_计算机专业基础综合数据结构（排序）历年真题试卷汇编 2 答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：10，分数：20.00)1.以下序列不是堆的是( )。【西安电子科技大学 2001 计算机应用一、5(2 分)】（分数：2.00）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，4
17、0，77，80，60，66，98，82，10，20) 解析：2.一组关键字为(46，79，56，38，40，84)，则利用堆排序的方法建立大顶堆的初始堆为( )。【北京交通大学 2006 一、8(2 分)】（分数：2.00）A.79，46，56，38，40，84B.84，79，56，38，40，46 C.84，79，56，46，40，38D.84，56，79，40，46，38解析：3.在对，z 个元素的序列进行排序时，堆排序所需要的附加存储空间是( )。【西安电子科技大学 2001 计算机应用一、10(2 分)】（分数：2.00）A.O(log 2 n)B.D(1) C.O(n)D.()(nl
18、og 2 n)解析：4.对 n 个记录的文件进行堆排序，最坏情况下的执行时间是多少? ( )。【北京交通大学 2001 一、9(2 分)】（分数：2.00）A.O(log 2 n)B.O(n)C.O(nlog 2 n) D.O(n*n)解析：5.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。【南京理工大学 1996 二、5(2 分)】（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，1 5，7，9 D.A，B，C 均不对解析：6.归并排序中，归并的趟数是( )。【南
19、京理工大学 2000 一、19(15 分)】（分数：2.00）A.O(n)B.O(logn) C.O(nlogn)D.O(n*n)解析：7.在排序算法中每一项都与其他各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( )。【北京邮电大学 2000 二、6(208 分)】（分数：2.00）A.插入排序B.枚举排序 C.选择排序D.交换排序解析：8.就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是( )。【哈尔滨工业大学 2004二、6(1 分)】（分数：2.00）A.堆分类归并分类快速分类D.堆分类快速分类归并分类解析：9.对给出的一组关键字13，6，19，30，10，
20、18)，若按关键字非递减排序，第一趟排序结果为13，6，18，30，10，19，问可能采用的排序算法是( )。【电子科技大学 2005 一、5(1 分)】（分数：2.00）A.单选择排序B.快速排序C.希尔排序 D.2 路归并排序解析：解析：步长为 3 的希尔排序。10.(多选)在下列排序中，( )方法的平均时间复杂度为 O(nlogn)。【华中科技大学 2007 二、20(2 分)】（分数：2.00）A.选择排序B.快速排序 C.归并排序 D.基数排序解析：二、填空题(总题数：8，分数：16.00)11.下列程序是归并排序的递归算法。【北京交通大学 2006 七、1(6 分)】 #defin
21、e maxsize 1000 #define 131310 #include int 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) while(j=1；i-) s=i；x=as; for(j=2*s；jlink=head；head=p； while(P 一link!=null) (q=p-link；r=p； while( (1) ) if(q
22、-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 一li
23、nk=s (5)p=p 一link)解析：14.表插入排序的基本思想是在结点中设一指针字段，插入 Ri 时 Rl 到 Ri 一 1 已经用指针按排序码不减次序链接起来，这时采用顺序比较的方法找到 Ri 应插入的位置，做链表插入。如此反复，直到把 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)(
24、2 分)表插入排序的最大比较次数是(7) ； (3)(2 分)表插入排序的最小比较次数是(8) ； (4)(2 分)记录移动的次数是(9)； (5)(2 分)需要附加的存储空间是(10)； (6)(2 分)该排序算法是否是稳定的(11)。（分数：2.00）_正确答案：(正确答案：(1)N (2)0 (3)N 一 1 (4)1 (5)RPKEY解析：15.建立在单链表上的一个 c 语言描述算法如下，其中 L 为链表头结点的指针。请填充算法中下划线的空白之处，并简述算法完成的功能。 typedef struct node(int data；struct node*next；)Lnode，link；
25、 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 一data=minp-data ; minp-data=temp；) (6) ； 【北京科技大学 2003 三(20分)】（分数：2.00）_正确答案：(正确答案：本算法是在单链表上的简单选择排序程序，每趟找到最小值后，交换结点数据。 (1)p (2)minp=p (3)q
26、(4)minp=q (5)minp!=p (6)p=p 一next)解析：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;ai，ai=t ； )while (
27、5) ； 【上海大学 2000 一、1(10 分)】（分数：2.00）_正确答案：(正确答案：(1)1 (2)ai=t (3)(i 2；in；i+=2) (4)1(5)flag)解析：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) *将
28、以 root 为下标的对应元素作为待调整堆的根，待调整元素放在 list 数组中，最大元素下标为 n* int child，rootkey； rootkey=listroot； child=2*root； while(chiIddata； 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)
29、p 一next)解析：三、综合题(总题数：2，分数：10.00)设待排序的关键字分别为 28，13，72，85，39，41，6，20。按二分法插入排序算法已使前 7 个记录有序，中间结果如下： （分数：4.00）(1).使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关?（分数：2.00）_正确答案：(正确答案： )解析：(2).在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗?【山东工业大学 1996 七(10 分)】（分数：2.00）_正确答案：(正确答案：一些特殊情况下，折半插入排序要比直接插入排序要执行更多的比较。例如，在待排序序列已有序的
30、情况下就是如此。)解析：算法模拟(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).用
31、直接选择排序。试以排序码序列的变化描述形式说明排序全过程(动态过程)要求按递减顺序排序。（分数：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）_正确答案：(正确答案：直接插
32、入排序是稳定排序，直接选择排序是不稳定排序。)解析：四、设计题(总题数：6，分数：12.00)19.设单链表头结点指针为 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 的
33、后继结点 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; 暂存记录 Ki while(Tj!=i) 调整 KTj到 Tj=i 为止 m=Tj；Kj=Km；Tj=j；j=m； Kj=rc；Tj=j ； 记录 Ri到位 if Rearrange)解析：24.输入 50 个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，然后按成绩由高到低的次序输出(每行 10 个记录)。排序方法采用选择排序。【北京师范大学 1999 五】（分数：2.00）_正确答案：(正确答案：使用简单选择排序，核心语句段如下： for(i=i; iR Ekscore) k=j； if(i!=k) RiRk； 与第 i 个记录交换 for for(i=i；i=n；i+) 输出成绩 cout(Rinum解析：
