1、计算机专业基础综合数据结构（排序）历年真题试卷汇编 10 及答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：7，分数：18.00)设要将序列(q，h，c，y，p，a，m，s，r，d，f，x，)中的关键码按字母升序重新排序，从下面供选择的答案中选出正确答案填入括号内。Af，h，c，d,p，m，q，r，s，y，xBp，a，c，s，q，d，x，rh，m，yCa，d，c，r，f，q，m，s，y，p，h，x Dh，c，q，p，a，m，s，r，d，x，yEh，q，c，y，a，p，m，s，d，r,f，x【厦门大学2000 六、3(163 分)】（分数：6.00）(1).( )是初始
2、步长为 4 的 Shell 排序一趟扫描的结果；（分数：2.00）A.B.C.D.E.(2).( )是对排序初始建堆的结果；（分数：2.00）A.B.C.D.E.(3).( )是以第一个元素为分界元素的快速一趟扫描的结果。（分数：2.00）A.B.C.D.E.1.n 个英文单词，每个单词长度基本相等，为 m。当 n50、mA.快速排序B.归并排序C.基数排序D.直接插入排序2.将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是( )。【中科院计算所 1998 二、7(2 分)】【中国科技大学 1998 二、7(2 分)】（分数：2.00）A.NB.2N-1C.2ND.N-13.
3、基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是 ( )。【南京理工大学 1996 一、2(2 分)】（分数：2.00）A.O(nlogn)B.O(logn)C.O(n)D.O(n*n)4.已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。【中国科技大学 1998 二、9(2 分)】【中科院计算所 1998 二、9(2 分)】（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 k)C.O(klog 2 n)D.O(kl
4、og 2 k)5.采用败者树进行 K 路平衡归并时，总的(包括访外)归并效率与 K( )。【北京工业大学 2001 一、4(2 分)】（分数：2.00）A.有关B.无关6.对05，46，13，55，94，17，42)进行基数排序，一趟排序的结果是：( )。【武汉理工大学 2004 一、10(3 分)】（分数：2.00）A.05，46，13，55，94，17，42B.05，13，17，42，46，55，94C.42，13，94，05，55，46，17D.05，13，46，55，1 7，42，94二、综合题(总题数：8，分数：24.00)7.对下面数据表，写出采用 Shell 排序算法排序的每一趟
5、的结果，并标出数据移动情况。(125，11，22，34，1 5，44，76，66，100，8，14，20，2，5，1)。【合肥工业大学 1999 四、4(5 分)】（分数：2.00）_8.快速排序的最大递归深度是多少?最小递归深度是多少?【清华大学 1999 一、1(2 分)】（分数：2.00）_9.已知某文件的记录关键字集为50，10，50，40，45，85，80，选择一种从平均性能而言是最佳的排序方法进行排序，且说明其稳定性。 【西安电子科技大学 1996 五(10 分)】（分数：2.00）_我们知道，对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序
6、有关。问：（分数：8.00）(1).当 n=7 时，在最好情况下需进行多少次比较?请说明理由。（分数：2.00）_(2).当 n=7 时，给出一个最好情况的初始排序的实例。（分数：2.00）_(3).当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。（分数：2.00）_(4).当 n=7 时，给出一个最坏情况的初始排序的实例。【西安电子科技大学 2001 计算机应用五(12 分)】【中国矿业大学 2000 六(10 分)】（分数：2.00）_10.对给定文件(28，07，39，10，65，14，61，17，50，21)选择第一个元素 28 进行划分，写出其快速排序第一遍的排序过程。【厦
7、门大学 1998 七、1(8 分)】（分数：2.00）_11.用一个栈可将递归形式的“快速排序算法”转变成非递归的迭代形式。转变的策略是：每趟确定“枢轴”元素之后，把当前右部数据区间的上界和下界入栈(上界、下界相等时则无须进栈)，并继续处理当前的左部数据区。如果一个待排序的关键字序列(21，08，12，25，49，27，18，38，06，33)存放于R110之中，请画出整个排序过程中的栈动态变化情况。【北京工业大学 2005 三、4(8 分)】（分数：2.00）_12.举例并说明：在最坏情况下，快速排序的时间复杂度为 O(n 2 )。【南京航空航天大学 2005 一(5 分)】（分数：2.00
8、）_对于待排序序列12，11，13，49，26，14，8，7（分数：4.00）(1).以快速排序方法对该序列进行排序，写出各趟排序后的结果。(5 分)（分数：2.00）_(2).以该序列为输入序列建立平衡二叉搜索树(即 AVL 树)，并求出其搜索成功的平均搜索长度ASLsucc。(5 分)【天津大学 2006 1(10 分)】（分数：2.00）_三、设计题(总题数：9，分数：18.00)13.按由大到小的顺序对一含有 N 个元素的数组 AN进行排序，利用如下改进的简单选择排序方法：第一次选出最大者存入 A1，第二次选出最小者存入 AN，第三次选出次大者存入 A2，第四次选出次小者存入 AN-1
9、，如此大小交替地选择，直到排序完毕。【东华大学 2001 十(10 分)】（分数：2.00）_14.设待排序的文件用单链表作存储结构，其形式如下： TYPE pointer=node； node=RECORD key：integer： next：pointer； END； 写出以 head 为头指针的选择排序算法。【中山大学 1999 二(10分)】（分数：2.00）_15.选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选一个值最小的元素，将其与未排好的那些元素的第一个元素交换位置。根据这个原理，请写出对一个带有头结点的单链表按数据域从小到大进行选择排序的算法。约定：链结点构造为(
10、data，link)，每一个链结点的数据域中存一个整型数，但是头结点数据域中不存放任何信息；设头结点指针为 list。限制：排序过程中不得不申请任何链结点空间，也不得改变任何链结点的数据域内容。【北京航空航天大学 2006 三(10 分)】（分数：2.00）_16.有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小，假设针对某一个记录，统计出的计数值为
11、 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。(1)(3 分)给出适用于计数排序的数据表定义；(2)(7 分)使用 Pascal 或 C 语言编写实现计数排序的算法；(3)(4 分)对于有 n 个记录的表，关键字比较次数是多少?(4)(3 分)与简单选择排序相比较，这种方法是否更好?为什么?【清华大学 2000 三(17 分)】（分数：2.00）_17.在数组 A0,n 一 1中存放有 n 个不同的整数，其值均在 1 到 n 之间。写出一个函数或过程，将 A 中的n 个数从大到小排序后存入 B0,n 一 1数组中，要求算法的时间复杂度为 O(n)。【中山大学 2003 四、3(5
12、 分)】（分数：2.00）_18.结点类型和存储结构如下：typedef 8truct int key； datatype data； int count； node；node Rn；试设计一个排序算法，要求不移动结点的存储位置，只在结点的 count 字段记录结点在排序中的序号，并将排序结果按升序输出。【哈尔滨工业大学 2005 五、2(12 分)】（分数：2.00）_19.请给出快速排序的排序算法，并说明算法思路。【北京理工大学 2006 七、2(152 分)】（分数：2.00）_20.快速分类算法中，如何选取一个界值(又称为轴元素)，影响着快速分类的效率，而且界值也并不一定是被分类序列中
13、的一个元素。例如，我们可以用被分类序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。【石油大学 1 998 五(1 8 分)】（分数：2.00）_21.编写程序将一整数序列中所有负数移到所有正数之前，要求时间复杂度为 O(n)。【电子科技大学 2005四、1(10 分)】（分数：2.00）_计算机专业基础综合数据结构（排序）历年真题试卷汇编 10 答案解析(总分：60.00，做题时间：90 分钟)一、单项选择题(总题数：7，分数：18.00)设要将序列(q，h，c，y，p，a，m，s，r，d，f，x，)中的关键码按字母升序重新排序，从下面供选择的答案中选出正确答案填入括
14、号内。Af，h，c，d,p，m，q，r，s，y，xBp，a，c，s，q，d，x，rh，m，yCa，d，c，r，f，q，m，s，y，p，h，x Dh，c，q，p，a，m，s，r，d，x，yEh，q，c，y，a，p，m，s，d，r,f，x【厦门大学2000 六、3(163 分)】（分数：6.00）(1).( )是初始步长为 4 的 Shell 排序一趟扫描的结果；（分数：2.00）A.B. C.D.E.解析：解析：假定本题的答案是唯一且正确的，应这样来快速求解。(1)步长为 4 的希尔排序，分组时第1 组元素是 q，p，r，排序后是 p，q 和 r。供选择的答案中，B 是以 p 开头的序列，故答案
15、选 B。(2)是初始建堆的结果。题目要求按字母升序排序，应建大堆。字母 y 应在堆顶，但是答案中没有以 y 开头的。如果建小堆，字母 a 在堆顶，答案 C 就是，故选 C。(3)是以第一个元素分界的一趟快速排序，字母 f 应调到最前面，故选 A。这样解答，抓住了每种排序方法的本质，节省了很多时间。(2).( )是对排序初始建堆的结果；（分数：2.00）A.B.C. D.E.解析：(3).( )是以第一个元素为分界元素的快速一趟扫描的结果。（分数：2.00）A. B.C.D.E.解析：1.n 个英文单词，每个单词长度基本相等，为 m。当 n50、mA.快速排序B.归并排序C.基数排序 D.直接插
16、入排序解析：解析：快速排序和归并排序的时间复杂度都是 O(nlogn)，直接插入排序的时间复杂度是 O(n 2 )，基数排序的时间复杂度是 O(m * (rd+n)，其中 m 是“分配”和“收集”的趟数，rd 是基数，因字母共 26个，所以 rd 取 26。在 n 较大，m 较小时，基数排序最有效。2.将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是( )。【中科院计算所 1998 二、7(2 分)】【中国科技大学 1998 二、7(2 分)】（分数：2.00）A.N B.2N-1C.2ND.N-1解析：3.基于比较方法的 n 个数据的内部排序。最坏情况下的时间复杂度能达到的
17、最好下界是 ( )。【南京理工大学 1996 一、2(2 分)】（分数：2.00）A.O(nlogn) B.O(logn)C.O(n)D.O(n*n)解析：4.已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。【中国科技大学 1998 二、9(2 分)】【中科院计算所 1998 二、9(2 分)】（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 k) C.O(klog 2 n)D.O(klog 2 k)解析：解析：因组与组之间已有序，故将 n/k
18、 个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog 2 k)，全部时间下界为 O(nlog 2 k)。5.采用败者树进行 K 路平衡归并时，总的(包括访外)归并效率与 K( )。【北京工业大学 2001 一、4(2 分)】（分数：2.00）A.有关 B.无关解析：解析：从归并次数的公式log 2 m(n 一 1)看，比较次数与归并路数 k 无关，似乎 k 越大越好。但对于具体机器来说，内存是固定的，k 越大，缓冲区越多，每个缓冲区就越小，甚至小于一次 IO 读写空间。因而总的归并效率仍与尼有关。k 应取折中值，并非越大越好。6.对05，46，13，55，94，17，42)进行基
19、数排序，一趟排序的结果是：( )。【武汉理工大学 2004 一、10(3 分)】（分数：2.00）A.05，46，13，55，94，17，42B.05，13，17，42，46，55，94C.42，13，94，05，55，46，17 D.05，13，46，55，1 7，42，94解析：解析：先对个位数排序，分到 09 的 10 个桶中，再收集起来。序列中个位数最小的是 2(元素 42)，故 C 为所求，不需一趟排序结束就可以得出结论。二、综合题(总题数：8，分数：24.00)7.对下面数据表，写出采用 Shell 排序算法排序的每一趟的结果，并标出数据移动情况。(125，11，22，34，1 5
20、，44，76，66，100，8，14，20，2，5，1)。【合肥工业大学 1999 四、4(5 分)】（分数：2.00）_正确答案：(正确答案： )解析：8.快速排序的最大递归深度是多少?最小递归深度是多少?【清华大学 1999 一、1(2 分)】（分数：2.00）_正确答案：(正确答案：设待排序记录的个数为 n，则快速排序的最小递归深度为log 2 n+1，最大递归深度 n。)解析：9.已知某文件的记录关键字集为50，10，50，40，45，85，80，选择一种从平均性能而言是最佳的排序方法进行排序，且说明其稳定性。 【西安电子科技大学 1996 五(10 分)】（分数：2.00）_正确答案
21、：(正确答案：平均性能最佳的排序方法是快速排序，该排序方法不稳定。 初始序列： 50，10，50，40，45，85，80 第一趟排序： 45，1 O，50，405085，80 第二趟排序： 40，104550508085 第三趟排序： 10，40，45，50，50，80，85)解析：我们知道，对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：（分数：8.00）(1).当 n=7 时，在最好情况下需进行多少次比较?请说明理由。（分数：2.00）_正确答案：(正确答案：在最好情况下，每次划分能得到两个长度相等的子文件。假设文件的长度 n=2 k 1，
22、那么第一趟划分得到两个长度均为n2的子文件，第二趟划分得到 4 个长度均为n4的子文件，以此类推，总共进行 k=log 2 (n+1)趟划分，各子文件的长度均为 1，排序完毕。当 n=7 时，k=3，在最好情况下，第一趟需比较 6 次，第二趟分别对两个子文件(长度均为 3，k=2)进行排序，各需 2 次，共 10 次即可。)解析：(2).当 n=7 时，给出一个最好情况的初始排序的实例。（分数：2.00）_正确答案：(正确答案：在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。)解析：(3).当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。（分数：2.00）_正确答案：
23、(正确答案：在最坏情况下，若每次用来划分的记录的关键字具有最大(或最小)值，那么只能得到左(或右)子文件，其长度比原长度少 1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为 O(n 2 )。所以当 n=7 时，最坏情况下的比较次数为 21 次。)解析：(4).当 n=7 时，给出一个最坏情况的初始排序的实例。【西安电子科技大学 2001 计算机应用五(12 分)】【中国矿业大学 2000 六(10 分)】（分数：2.00）_正确答案：(正确答案：在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排
24、序。)解析：10.对给定文件(28，07，39，10，65，14，61，17，50，21)选择第一个元素 28 进行划分，写出其快速排序第一遍的排序过程。【厦门大学 1998 七、1(8 分)】（分数：2.00）_正确答案：(正确答案：快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴(也称支点)，凡其关键字不大于枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。使得一趟排序之后，记录的无序序列 Rsf将被分割成两部分：Rsi-1和 Ri+1t，且 RjkeyRikeyRkkey(sjAk)k=j； 选第 i 个最大元素
25、 if(k!=i)AiAk； 选出第 i 个最大元素 k=ni； k 记最小元素下标 for(j=ni ; jnext； while(p) (q=p-next； r=p； 设 r 是指向关键字最小的结点的指针 while(q!=null) (if(q 一datadata)r=q； q=q 一next； if(r!=p)r 一datap 一data； p=p 一next； )解析：15.选择排序法每一趟排序的基本原理是从当前未排好序的那些元素中选一个值最小的元素，将其与未排好的那些元素的第一个元素交换位置。根据这个原理，请写出对一个带有头结点的单链表按数据域从小到大进行选择排序的算法。约定：链结
26、点构造为(data，link)，每一个链结点的数据域中存一个整型数，但是头结点数据域中不存放任何信息；设头结点指针为 list。限制：排序过程中不得不申请任何链结点空间，也不得改变任何链结点的数据域内容。【北京航空航天大学 2006 三(10 分)】（分数：2.00）_正确答案：(正确答案：上题是按“交换结点值”进行选择排序，本题要求交换结点。因此必须知道“值最小的元素”和“未排好的那些元素的第一个元素”前驱的指针。设“值最小的元素”的前驱的指针是start，待排序的第一个元素的指针是 P，其前驱的指针是 pre。则结点交换的核心语句段是：pre 一link=start 一link；start
27、 一link 一link=p 一link；pre=pre 一link；前驱后移 P 一link=start 一link 一link；start 一link=p；)解析：16.有一种简单的排序算法，叫做计数排序(count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小，假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。(1)(3 分)给出适用于计数排
28、序的数据表定义；(2)(7 分)使用 Pascal 或 C 语言编写实现计数排序的算法；(3)(4 分)对于有 n 个记录的表，关键字比较次数是多少?(4)(3 分)与简单选择排序相比较，这种方法是否更好?为什么?【清华大学 2000 三(17 分)】（分数：2.00）_正确答案：(正确答案：(2)核心语句段如下： for(i=0 ； in； i+) 对每一个元素 for(j=0，cnt=0 ； jn； j+) if(ajkeyaikey)cnt+; 比当前元素的关键字小的元素个数 bcnt=ai; (3)对于有 n 个记录的表，关键码比较，12 次。 (4)简单选择排序算法比本算法好。简单选
29、择排序比较次数是 n(n 一 1)2，且只用一个交换记录的空间；而这种方法比较次数是 n 2 ，且需要另一数组空间。因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是 n 2 次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为： for(i=0; in；i+)aicount=0； 各元素再增加一个计数域，初始化为 0 for(i=0；in；i+) for(j=i+1；jn；j+) if(aikeyajkey)ajcount+； else aicount+；)解析：17.在数组 A0,n 一 1中存放有 n 个不同的整数，其值均在 1 到 n 之
30、间。写出一个函数或过程，将 A 中的n 个数从大到小排序后存入 B0,n 一 1数组中，要求算法的时间复杂度为 O(n)。【中山大学 2003 四、3(5 分)】（分数：2.00）_正确答案：(正确答案：值为 i(1in)的元素就是数组下标为 n 一 i 的元素。核心语句是： for(i=0； i解析：18.结点类型和存储结构如下：typedef 8truct int key； datatype data； int count； node；node Rn；试设计一个排序算法，要求不移动结点的存储位置，只在结点的 count 字段记录结点在排序中的序号，并将排序结果按升序输出。【哈尔滨工业大学
31、2005 五、2(12 分)】（分数：2.00）_正确答案：(正确答案：题目“要求不移动结点的存储位置，只在结点的 count 字段记录结点在排序中的序号”，并且给出了顺序存储结构。这里我们使用静态链表实现。先把 count 当作指针域，进行“地址排序”，具体可以参见第 8 题。)解析：19.请给出快速排序的排序算法，并说明算法思路。【北京理工大学 2006 七、2(152 分)】（分数：2.00）_正确答案：(正确答案：一趟快速排序的思想是由枢轴元素把待排序元素分成两部分，枢轴左面的元素不大于枢轴，枢轴右面的元素不小于枢轴。再对左右两部分分别进行快速排序。 int Partition(Rec
32、Type R，int 1，inth) 快速排序的一趟划分的算法 (交换记录子序列 R1h中的记录，使枢轴元素到位并返回其所在位置 int i=l； j=h； 用变量 i，j 记录待排序元素首尾位置 R0=Ri； 以子表的第一个元素作枢轴，将其暂存到记录 R0中 x=Rikey； 用变量 x 存放枢轴元素的关键字 while(icj) 从表的两端交替地向中间扫描 while(i=x) j 一一； Ri=Rj； 将比枢轴小的元素移到低端(不交换) while(i=x) i+； Rj=Ri； 将比枢轴大的元素移到高端(不交换) while Ri=R0； 枢轴元素到位 return i； 返回枢轴位置
33、 partition void QuickSort(RecType R，int s，int t)对元素序列 Rst进行快速排序 if(s解析：20.快速分类算法中，如何选取一个界值(又称为轴元素)，影响着快速分类的效率，而且界值也并不一定是被分类序列中的一个元素。例如，我们可以用被分类序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。【石油大学 1 998 五(1 8 分)】（分数：2.00）_正确答案：(正确答案：首先求出平均值作“虚”枢轴，去进行划分。“虚”枢轴的含义是可能没有该元素。)解析：21.编写程序将一整数序列中所有负数移到所有正数之前，要求时间复杂度为 O(n)。【电子科技大学 2005四、1(10 分)】（分数：2.00）_正确答案：(正确答案：第一个元素为枢轴，但比较时小于零的数前移，大于等于零的数后移。)解析：
