2024年4月30日发(作者：)

计算机专业基础综合数据结构（排序）历年真题试卷汇编10

(总分60,考试时间90分钟)

1. 单项选择题

设要将序列(q，h，c，y，p，a，m，s，r，d，f，x，)中的关键码按字母升序重新排序，从

下面供选择的答案中选出正确答案填入括号内。A．f，h，c，d,p，m，q，r，s，y，xB．p，

a，c，s，q，d，x，rh，m，yC．a，d，c，r，f，q，m，s，y，p，h，x D．h，c，q，p，a，

m，s，r，d，x，yE．h，q，c，y，a，p，m，s，d，r,f，x【厦门大学2000六、3(16％／3

分)】

1. ( )是初始步长为4的Shell排序一趟扫描的结果；

A. B.

C. D.

E.

2. ( )是对排序初始建堆的结果；

A. B.

C. D.

E.

3. ( )是以第一个元素为分界元素的快速一趟扫描的结果。

A. B.

C. D.

E.

4. n个英文单词，每个单词长度基本相等，为m。当n>>50、m<5时，时间复杂度最佳的为

( )。【大连理工大学2008一、4】

A. 快速排序 B. 归并排序

C. 基数排序 D. 直接插入排序

5. 将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是( )。【中科院

计算所1998二、7(2分)】【中国科技大学1998二、7(2分)】

A. N B. 2N-1

C. 2N D. N-1

6. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是

( )。【南京理工大学1996一、2(2分)】

A. O(nlogn) B. O(logn)

C. O(n) D. O(n*n)

7. 已知待排序的n个元素可分为n／k个组，每个组包含k个元素，且任一组内的各元素均

分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间

下界应为( )。【中国科技大学1998二、9(2分)】【中科院计算所1998二、9(2分)】

A. O(nlog2n)

B. O(nlog2k)

C. O(klog2n)

D. O(klog2k)

8. 采用败者树进行K路平衡归并时，总的(包括访外)归并效率与K( )。【北京工业大学

2001一、4(2分)】

A. 有关 B. 无关

9. 对{05，46，13，55，94，17，42)进行基数排序，一趟排序的结果是：( )。【武汉理

工大学2004一、10(3分)】

A. 05，46，13，55，94，17，42

B. 05，13，17，42，46，55，94

C. 42，13，94，05，55，46，17

D. 05，13，46，55，1 7，42，94

6. 综合题

1. 对下面数据表，写出采用Shell排序算法排序的每一趟的结果，并标出数据移动情况。(125，

11，22，34，1 5，44，76，66，100，8，14，20，2，5，1)。【合肥工业大学1999四、4(5

分)】

2. 快速排序的最大递归深度是多少?最小递归深度是多少?【清华大学1999一、1(2分)】

3. 已知某文件的记录关键字集为{50，10，50，40，45，85，80}，选择一种从平均性能而

言是最佳的排序方法进行排序，且说明其稳定性。 【西安电子科技大学1996五(10分)】

我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素

的初始排序有关。问：

4. 当n=7时，在最好情况下需进行多少次比较?请说明理由。

5. 当n=7时，给出一个最好情况的初始排序的实例。

6. 当n=7时，在最坏情况下需进行多少次比较?请说明理由。

7. 当n=7时，给出一个最坏情况的初始排序的实例。【西安电子科技大学2001计算机应用

五(12分)】【中国矿业大学2000六(10分)】

8. 对给定文件(28，07，39，10，65，14，61，17，50，21)选择第一个元素28进行划分，

写出其快速排序第一遍的排序过程。【厦门大学1998七、1(8分)】

9. 用一个栈可将递归形式的“快速排序算法”转变成非递归的迭代形式。转变的策略是：每

趟确定“枢轴”元素之后，把当前右部数据区间的上界和下界入栈(上界、下界相等时则无须

进栈)，并继续处理当前的左部数据区。如果一个待排序的关键字序列(21，08，12，25，49，

27，18，38，06，33)存放于R[1．．10]之中，请画出整个排序过程中的栈动态变化情况。【北

京工业大学2005三、4(8分)】

10. 举例并说明：在最坏情况下，快速排序的时间复杂度为O(n2)。【南京航空航天大学2005

一(5分)】

对于待排序序列{12，11，13，49，26，14，8，7}

11. 以快速排序方法对该序列进行排序，写出各趟排序后的结果。(5分)

12. 以该序列为输入序列建立平衡二叉搜索树(即AVL树)，并求出其搜索成功的平均搜索长

度ASLsucc。(5分)【天津大学2006 1(10分)】

7. 设计题