1、计算机专业基础综合数据结构（排序）-试卷 1 及答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数：32.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。_2.下面给出的 4 种排序方法中，( )排序法是不稳定性排序法。（分数：2.00）A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序D.冒泡排序4.下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，k
2、n)的情况下，排序效率最高的算法是( )。（分数：2.00）A.冒泡排序B.堆排序C.直接插入排序D.二路归并排序5.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.简单选择排序D.直接插入排序6.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog 2 n)的是( )。（分数：2.00）A.堆排序B.冒泡排序C.直接选择排序D.快速排序7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.00）A.选择排序B.冒泡排序C.归并排序D.堆排序8.下列排序算法中，在每一趟都
3、能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（分数：2.00）A.直接插入排序B.归并排序C.直接选择排序D.堆排序对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。（分数：4.00）(1).(1)（分数：2.00）A.堆排序B.快速排序C.插入排序D.归并排序(2).(2)（分数：2.00）A.堆排序B.快速排序C.插入排序D.归并排序9.如果只想得到 1 000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( )方法最快。（分数：2.00）A.冒泡排序B.快速排序C.简单选择排序D.堆排序
4、10.数据表 A 中有 10 000 个元素，如果仅要求求出其中最大的 10 个元素，则采用( )方法最节省时间。（分数：2.00）A.堆排序B.希尔排序C.快速排序D.直接选择排序11.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（分数：2.00）A.an ，bai，deng，wang，tang，fang，shi，liuB.an，bai，deng，wang，shi，tang，fang，liuC.an，bai，deng，wang，fang，shi，tang，liuD.an，ba
5、i，deng，wang，shi，liu，tang，fang12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（分数：2.00）A.插入B.选择C.希尔D.二路归并13.若用冒泡排序方法对序列10，14，26，29，41，52从大到小排序，需进行( )次比较。（分数：2.00）A.3B.10C.15D.2514.下列( )是一个堆。（分数：2.00）A.19，75，34，26，97，56B.97，26，34，75，19，56C.19，56，26，97，34，75D.19，34，26，97，56，7515.若一组记录
6、的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第 1 个记录为基准得到的一次划分结果为( )。（分数：2.00）A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79二、综合应用题(总题数：13，分数：26.00)16.综合应用题 41-47 小题。（分数：2.00）_17.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?（分数：2.00）_18.设有 5 个互不相同的元素 a，b，c，d，e，能
7、否通过 7 次比较就将其排好序，7 如果能，请列出其比较过程：如果不能，则说明原因。（分数：2.00）_19.对一个由 n 个关键字不同的记录构成的序列，能否用比 2n 一 3 少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?（分数：2.00）_20.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。（分数：2.00）_21.已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key
8、1 key 2 key n )；(2)关键字自大到小逆序(key 1 key 2 key n )； (3)奇数关键字顺序有序，偶数关键字顺序有序(key 1 key 3 ，key 2 key 4 )； (4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1 key 2 key m ，key m+1 key m+2 key n ，m 为中间位置)。（分数：2.00）_22.对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：(1)当 n=7 时，在最好情况下需进行多少次比较?请说明理由。 (2)当 n=7 时，给出一个最好情况的
9、初始排序的实例。 (3)当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。 (4)当 n=7 时，给出一个最坏情况的初始排序的实例。（分数：2.00）_23.关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对 n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?（分数：2.00）_24.若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 ，请用文字简要说明如何在 log 2 n的时间内将其重新调整为一个堆。（分数
10、：2.00）_25.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。（分数：2.00）_26.有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。 设计实现计数排序的算法。对于有 n
11、 个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?（分数：2.00）_27.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。（分数：2.00）_28.设有一个数组中存放了一个无序的关键字序列 K 1 ，K 2 ，K n 。现要求将 K n 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。（分数：2.00）_计算机专业基础综合数据结构（排序）-试卷 1 答案解析(总分：58.00，做题时间：90 分钟)一、单项选择题(总题数：16，分数
12、：32.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。_解析：2.下面给出的 4 种排序方法中，( )排序法是不稳定性排序法。（分数：2.00）A.插入B.冒泡C.二路归并D.堆 解析：解析：此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序：反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项 A、B、C 都是相邻元素比
13、较，是稳定的。所以选 D。3.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序 D.冒泡排序解析：解析：此题考查的知识点是各类排序算法的思想。 冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D 错。 直接插入排序思想是假设待排序的记录存放在数组 Rn+1中，排序过程中的某一时刻，R 被分成两个子区间R1，Ri 一 1和Ri，Rn，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第
14、 i 个记录 Ri插入到有序区中的适当位置，使得 R1到 Ri变为新的有序区。首先比较 Ri和 Ri1，如果 Ri 一 1Ri，则 R1i已排好序，第 i 遍处理就结束了；否则交换 Ri与 Ri 一 1的位置，继续比较 Ri1和 Ri 一 2，直到找到某一个位置 j(1ji 一 1)使得 RjRj+1时为止。与序列初态有关，B 错。 快速排序是通过基准元素 v 把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于 v；右边的各记录的关键字都大于等于 v；重复该过程直到排好序。与序列初态有关，A 错。 二路归并是首先把每个记录看成是一个有序序列，共 n 个，将它们两两合并成n
15、2个分类序列，每个序列长度为 2(当 n 为奇数时，最后一个序列长度为 1)；对n2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为 n的分类序列为止。与序列初态无关，所以选 C。4.下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。（分数：2.00）A.冒泡排序B.堆排序C.直接插入排序 D.二路归并排序解析：解析：此题考查的知识点是各类排序算法的效率。起泡排序比较 n(n 一 1)2 次，没有交换次数；堆排序一次比较 log 2 n 次，共需要 n 轮；直接插入排序比较 n1 次，没有交换；二路归
16、并排序一次比较 log 2 n 次，共需要 n 轮。综上，应选 C。5.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.简单选择排序 D.直接插入排序解析：解析：本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。6.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog 2 n)的是( )。（分数：2.00）A.堆排序 B.冒泡排序C.直接选择排序D.快速排序解析：解析：由这些排序方法的特点可知本题答案为 A。7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.
17、00）A.选择排序B.冒泡排序C.归并排序 D.堆排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 c。8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（分数：2.00）A.直接插入排序 B.归并排序C.直接选择排序D.堆排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 A。对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。（分数：4.00）(1).(1)（分数：2.00）A.堆排序B.快速排序C.插入排序 D.归并排序解析：(2).(2)（分数：2.00）A.堆
18、排序B.快速排序 C.插入排序D.归并排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 C，B。9.如果只想得到 1 000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( )方法最快。（分数：2.00）A.冒泡排序B.快速排序C.简单选择排序D.堆排序 解析：解析：此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较 n 一 i 次，快速排序结束后才能得到结果，堆排序可以在选择 5 次后得到结果，每次比较元素次数为 log 2 n。所以应选 D。10.数据表 A 中有 10 000 个元素，如果仅要求求出其中最大的 10 个元素，则采用( )方法最
19、节省时间。（分数：2.00）A.堆排序 B.希尔排序C.快速排序D.直接选择排序解析：解析：只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为 A。11.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（分数：2.00）A.an ，bai，deng，wang，tang，fang，shi，liuB.an，bai，deng，wang，shi，tang，fang，liu C.an，bai，deng，wang，
20、fang，shi，tang，liuD.an，bai，deng，wang，shi，liu，tang，fang解析：解析：本题根据简单选择排序法的算法思想可得答案 B。12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（分数：2.00）A.插入 B.选择C.希尔D.二路归并解析：解析：此题考查的知识点是各类排序算法的思想。应选 A。13.若用冒泡排序方法对序列10，14，26，29，41，52从大到小排序，需进行( )次比较。（分数：2.00）A.3B.10C.15 D.25解析：解析：此题考查的知识点是冒泡算法的思
21、想及过程。第一趟比较 5 次，第 2 趟比较 4 次，第 3 趟比较 3 次，第 4 趟比较 2 次，第 5 趟比较 1 次，结束。共 15 次，应选 C。14.下列( )是一个堆。（分数：2.00）A.19，75，34，26，97，56B.97，26，34，75，19，56C.19，56，26，97，34，75D.19，34，26，97，56，75 解析：解析：完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：15.若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第 1 个记录为基准得
22、到的一次划分结果为( )。（分数：2.00）A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84 D.40，38，46，84，56，79解析：解析：对于(46，79，56，38，40，84)，取出 46，对(79，56，38，40，84)进行划分，先将 79 与40 交换，得到(40，56，38，79，84)，再将 56 与 38 交换，得到(40，38，56，79，84)，将 46 插入得到(40，38，46，56，79，84)，本题答案为 C。二、综合应用题(总题数：13，分数：26.00)16.综合应用题 41-47 小题。（
23、分数：2.00）_解析：17.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?（分数：2.00）_正确答案：(正确答案：这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。)解析：18.设有 5 个互不相同的元素 a，b，c，d，e，能否通过 7 次比较就将其排好序，7 如果能，请列出其比较过程：如果不能，则说明原因。（分数：2.00）_正确答案：(正确答案：可以做到。取 a 与 b 进行比较，c 与 d 进行比较。设 ab，cd(
24、ab 和 cd 情况类似)，此时需 2 次比较，取 b 和 d 比较，若 bd，则有序 abd；若 bd 时则有序 cdb，此时已进行了 3 次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4 次比较，从而共需 7 次比较。)解析：19.对一个由 n 个关键字不同的记录构成的序列，能否用比 2n 一 3 少的次数选出该序列中关键字取最大值和关键宇取最小值的记录?请说明如何实现?在最坏的情况下至少要进行多少次比较?（分数：2.00）_正确答案：(正确答案：将 n 个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较比较中的小者放前半部，大者放后半部
25、，用了 n2 次比较。再在前后两部分中分别简单选择最小和最大元素，备用(n2)一 1 次比较。总共用了(3n2)一 2 次比较。显然，当 n3 时，(2n一 3)(3n2)一 2. 用分治法求解再给出另一参考答案。 对于两个数 x 和 y，经一次比较可得到最大值和最小值；对于三个数 x，y，z，最多经 3 次比较可得最大值和最小值；对于 n 个数(n3)，将分成长为n 一 2 和 2 的前后两部分 A 和 B，分别找出最大者和最小者：Max A，Min A，MaxB，Min B，最后Max=Max A，Max B和 Min=Min A，Min B。对 A 使用同样的方法求出最大值和最小值，直到
26、元素个数不超过 3。 设 C(n)是所需的最多比较次数，根据上述原则，当 n3 时有如下关系式： )解析：20.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。（分数：2.00）_正确答案：(正确答案：假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二又树高度是 h，则叶子结点个数最多为 2 h-1 ；反之，若有 u 个叶子结点，则二叉树的高度至少为(log 2 u)+1。这就是说，描述 n 个记录排序的判定树
27、必定存在一条长度为 log 2 (n!)的路径。即任何一个借助“比较”进行排序的算法，在最坏情况下所需进行的比较次数至少是 log 2 (n!)。根据斯特林公式，有 log 2 (n!)=O(nlog 2 n)。即借助于“比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 O(nlog 2 n)。 提示：此题考查的知识点是基于比较的排序算法效率。)解析：21.已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1 key 2 key n )；(2)关键字自大到小逆序
28、(key 1 key 2 key n )； (3)奇数关键字顺序有序，偶数关键字顺序有序(key 1 key 3 ，key 2 key 4 )； (4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1 key 2 key m ，key m+1 key m+2 key n ，m 为中间位置)。（分数：2.00）_正确答案：(正确答案：本题主要考查直接插入法的算法思想及性能分析。 根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。 (1)在关键字自小到大有序的情况下，插入第 i 个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n 一 1。 (
29、2)在关键字自大到小有序的情况下，插入第 i 个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=n(n+1)2一 1=(n 一 1)(n+2)2。 (3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为 n 一 1。 (4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少，此时前半部分的比较次数为 m1，后半部分的比较次数为(nm1)(n 一 m+2)2，因此，总的比较次数为 m 一 1+(nm 一 1)(n 一 m+2)2=(n 一
30、 2)(n+8)8(假设 n 为偶数，m=n2).)解析：22.对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：(1)当 n=7 时，在最好情况下需进行多少次比较?请说明理由。 (2)当 n=7 时，给出一个最好情况的初始排序的实例。 (3)当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。 (4)当 n=7 时，给出一个最坏情况的初始排序的实例。（分数：2.00）_正确答案：(正确答案：(1)在最好情况下，假设每次划分能得到两个长度相等的子文件，文件的长度n=2k 一 1，那么第一遍划分得到两个长度均为n2的子文件，第二遍划分得到 4
31、 个长度均为n4的子文件，以此类推，总共进行 k=log 2 (n+1)遍划分，各子文件的长度均为 1，排序完毕。当 n=7 时，k=3，在最好情况下，第一遍需比较 6 次，第二遍分别对两个子文件(长度均为 3，k=2)进行排序，各需 2 次，共 10 次即可. (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。 (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右) 子文件，其长度比原长度少 1。因此，若原文件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为 O(n 2 )。所
32、以当 n=7 时，最坏情况下的比较次数为 21 次。 (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。 提示：此题考查的知识点是快速排序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。)解析：23.关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对 n
33、个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 0 表示法)?（分数：2.00）_正确答案：(正确答案：(1)堆的存储是顺序的。 (2)最大值元素一定是叶子结点，在最下两层上。 (3)在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下： 由于第 i 层上的结点数至多是 2 i-1 ，以它为根的二叉树的深度为 h 一 i+1，则调用n2次筛选算法时总共进行的关键字比较次数不超过下式之值： )解析：24.若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 ，请用文字简要说明如何在 log 2 n的时间内将其重新调整为一个堆。（分数：2.00）_正
34、确答案：(正确答案：K 1 K n 是堆，在 K n+1 加入后，将 K 1 k n+1 调成堆。设 c=n+1，f=c2，若 k f K c ，则调整完成。否则 K f 与 K c 交换之后，c=f,f=c2，继续比较，直到 K f K c 或f=0，即为根结点，调整结束。)解析：25.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。（分数：2.00）_正确答案：(正确答案：void BubbleSort2(int a，int n) 相邻两趟向相反方向起泡的冒泡排序算法 int change=1；low=0；high
35、=n1； 冒泡的上下界 while(lowhigh 交换标志 for(i=low；ihigh；i+) 从上向下起泡 if(aiai+1)ai+ai+1；change=1； 有交换，修改标志 change high 一一； 修改上界 for(i=high；ilow；i 一一) 从下向上起泡 if(aiai+1ai+ai 一 1；change=1； low+； 修改下界 提示：此题考查的知识点是双向冒泡算法。题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左端来处理。)解析：26.有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示)
36、进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。 设计实现计数排序的算法。对于有 n 个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?（分数：2.00）_正确答案：(正确答案：typedef struct int key； datatype info RecType： void CountSort(RecType a，b，i
37、nt n) 计数排序算法，将 a 中记录排序放入 b 中 int i，j，cnt： for(i=0；in；i+) 对每一个元素 for(j=0，cnt=0；jn；j+) if(aj.keya ikey)cnt+； 统计关键字比它小的元素个数 Bcnt=ai； 对于有 n 个记录的表，关键字比较 n 2 次。 简单选择排序算法比本算法好。简单选择排序的比较次数是 n(n 一 1)2，且只用一个交换记录的空间：而这种方法的比较次数是 n 2 ，且需要另一数组空间。)解析：27.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串
38、序列进行排序。（分数：2.00）_正确答案：(正确答案：int Partition(RecType R，int n，int h) 一趟快速排序算法，枢轴记录到位，并返回其所在位置 int i=n，j=h，R0=Ri，x=Rikey； while(ij) while(ij if(ij)Ri=Rj； while(ij&Rikey=x)i+： jf(jj)Rj=Ri； while Ri=R0； return i； 提示：此题考查的知识点是快速排序的思想。)解析：28.设有一个数组中存放了一个无序的关键字序列 K 1 ，K 2 ，K n 。现要求将 K n 放在将元素排序后的正确位置上，试编写实现该功
39、能的算法，要求比较关键字的次数不超过 n。（分数：2.00）_正确答案：(正确答案：int Partition(RecType K，int m，int n) 交换记录子序列 K1n中的记录，使枢轴记录到位，并返回其所在位置 此时，在它之前(后)的记录均不大(小)于它 int i=m，j=n，K0=Kj，x=Kjkey； while(ij) while(ij&Kikey=x)i+： if(ij)Kj=Ki； while(ij&Kjkey=X)j 一一； if(ij)Ki=Kj： while Ki=K0； return i： 提示：此题考查的知识点是快速排序的思想。以 K n 为枢轴的一趟快速排序。以最后一个关键字为枢轴先从前向后再从后向前快速排序。)解析：
