1、计算机专业基础综合（排序）-试卷 1及答案解析(总分：68.00，做题时间：90 分钟)一、单项选择题(总题数：17，分数：34.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_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.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 D(nlog 2 n)的是( )。（分数：2.00）A.堆排序B.冒泡排序C.直接选择排序D.快速排序7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.00）A.选择排序B.冒泡排序C.归并排序D.堆排序8.下列排序算法中，在每一趟都
3、能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（分数：2.00）A.直接插入排序B.归并排序C.直接选择排序D.堆排序9.对初始状态为递增序列的表按递增顺序排序最费时间的是( )算法。（分数：2.00）A.堆排序B.快速排序C.插入排序D.归并排序10.对初始状态为递增序列的表按递增顺序排序，最省时间的是( )算法。（分数：2.00）A.堆排序B.快速排序C.插入排序D.归并排序11.如果只想得到 1000个元素组成的序列中第 5个最小元素之前的部分排序的序列，用( )方法最快。（分数：2.00）A.冒泡排序B.快速排序C.简单选择排序D.堆排序12.数据表 A中
4、有 10000个元素，如果仅要求求出其中最大的 10个元素，则采用( )方法最节省时间。（分数：2.00）A.堆排序B.希尔排序C.快速排序D.直接选择排序13.若对序列(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，bai，deng，wang，sh
5、i，liu，tang，fang14.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（分数：2.00）A.插入B.选择C.希尔D.二路归并15.若用冒泡排序方法对序列10，14，26，29，41，52从大到小排序，需进行( )次比较。（分数：2.00）A.3B.10C.15D.2516.下列( )是一个堆。（分数：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，7517.若一组记录的关键码为(46，79，56
6、，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二、综合应用题(总题数：15，分数：34.00)18.综合应用题 41-47小题。_19.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。（分数：2.00）_20.设有一个数组中存放了一个无序的关键字序列 K 1 ，K 2 ，K n 。现要求将 K
7、n 放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。（分数：2.00）_21.已知关键字序列(K 1 ，K 2 ，K 3 ，K N-1 )是大根堆。试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。（分数：2.00）_最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。 （分数：6.00）(1).画出在图中插入关键字为 5的结点后的最小最
8、大堆。（分数：2.00）_(2).画出在图中插入关键字为 80的结点后的最小最大堆。（分数：2.00）_(3).编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。（分数：2.00）_22.输入 N个只含一位数字的整数，试用基数排序的方法，对这 N个数排序。（分数：2.00）_23.试构造对 5个元素进行排序，最多只用 7次比较的算法。（分数：2.00）_24.设有 15000个无序的元素，希望用最快的速度挑选出其中前 10最大的元素。 在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?（分数：2.00）_对一个具有 7个记录的文件进行快速
9、排序，请问：（分数：4.00）(1).在最好情况下需进行多少次比较?说明理由，并给出相应实例。（分数：2.00）_(2).在最坏情况下需进行多少次比较?为什么?请给出相应实例。（分数：2.00）_25.判断下列序列是否为堆，若不是堆，则把它们调整为堆。(1)(100，85，95，75，80，60，82，40，20，10，65)(2)(100，95，85，82，80，75，65，60，40，20，10)(3)(100，85，40，75，80，60，65，95，82，10，20)(4)(10，20，40，60，65，75，80，82，85，95，100)（分数：2.00）_26.将十进制的关键字用
10、二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?（分数：2.00）_27.写出快速排序的非递归算法。（分数：2.00）_28.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。（分数：2.00）_29.写一个 HeapInsert(R，key)算法，将关键字插入到堆 R中，并保证插入后 R仍是堆。请分析算法的时间复杂度。提示：将 key先插入 R中已有元素的尾部(即原堆的长度加 1的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。（分数：2.00）_30.写一个建立堆的算法：从
11、空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。（分数：2.00）_计算机专业基础综合（排序）-试卷 1答案解析(总分：68.00，做题时间：90 分钟)一、单项选择题(总题数：17，分数：34.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下面给出的 4种排序方法中，( )排序法是不稳定性排序法。（分数：2.00）A.插入B.冒泡C.二路归并D.堆 解析：解析：此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则
12、称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项 A、B、C 都是相邻元素比较，是稳定的。所以选 D。3.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序 D.冒泡排序解析：解析：此题考查的知识点是各类排序算法的思想。 冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D 错。 直接插入排序思想是假设待排序的记
13、录存放在数组 Rn+1中，排序过程中的某一时刻，尺被分成两个子区间R1，Ri一 1和Ri，Rn，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第 i个记录 Ri插入到有序区中的适当位置，使得 R1到Ri变为新的有序区。首先比较 Ri和 Ri一 1，如果 Ri一 1Ri，则 R1i已排好序，第 i遍处理就结束了；否则交换 Ri与 Ri一 1的位置，继续比较 Ri一 1和 Ri一 2，直到找到某一个位置 j(1ji 一 1)使得 RjRj+1时为止。与序列初态有关，B 错。 快速排序是通过基准元素 v把表(文件，数据集合)划分成左、右
14、两部分，使得左边的各记录的关键字都小于 v：右边的各记录的关键字都大于等于 v；重复该过程直到排好序。与序列初态有关，A 错。 二路归并是首先把每个记录看成是一个有序序列，共 n个，将它们两两合并成n2个分类序列，每个序列长度为 2(当 n为奇数时，最后一个序列长度为 1)；对n2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为 n的分类序列为止。与序列初态无关，所以选 C。4.下列内部排序算法中，在初始序列已基本有序(除去 n个元素中的某 k个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。（分数：2.00）A.冒泡排序B.堆排序C.直接插入排序 D.二路归并排序解析
15、：解析：此题考查的知识点是各类排序算法的效率。起泡排序比较 n(n一 1)2 次，没有交换次数；堆排序一次比较 log 2 n次，共需要 n轮；直接插入排序比较 n一 1次，没有交换；二路归并排序一次比较 log 2 n次，共需要 n轮。综上，应选 C。5.下列排序算法中，( )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.简单选择排序 D.直接插入排序解析：解析：本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。6.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 D(nlog 2 n)的是( )。（分数：2.00）A.堆排
16、序 B.冒泡排序C.直接选择排序D.快速排序解析：解析：由这些排序方法的特点可知本题答案为 A。7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.00）A.选择排序B.冒泡排序C.归并排序 D.堆排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 C。8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（分数：2.00）A.直接插入排序 B.归并排序C.直接选择排序D.堆排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 A。9.对初始状态为递增序列的表按递增顺序排序最费时间的是( )
17、算法。（分数：2.00）A.堆排序B.快速排序 C.插入排序D.归并排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 B。10.对初始状态为递增序列的表按递增顺序排序，最省时间的是( )算法。（分数：2.00）A.堆排序B.快速排序C.插入排序 D.归并排序解析：解析：此题考查的知识点是各类排序算法的思想。应选 C。11.如果只想得到 1000个元素组成的序列中第 5个最小元素之前的部分排序的序列，用( )方法最快。（分数：2.00）A.冒泡排序B.快速排序C.简单选择排序D.堆排序 解析：解析：此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较 ni次，快速排序
18、结束后才能得到结果，堆排序可以在选择 5次后得到结果，每次比较元素次数为 log 2 n。所以应选 D。12.数据表 A中有 10000个元素，如果仅要求求出其中最大的 10个元素，则采用( )方法最节省时间。（分数：2.00）A.堆排序 B.希尔排序C.快速排序D.直接选择排序解析：解析：只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为 A。13.若对序列(tang，deng，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（分
19、数：2.00）A.an，bai，deng，wang，tang，fang，shi，liuB.an，bai，deng，wang，shi，tang，fang，liu C.an，bai，deng，wang，fang，shi，tang，liuD.an，bai，deng，wang，shi，liu，tang，fang解析：解析：本题根据简单选择排序法的算法思想可得答案 B。14.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（分数：2.00）A.插入 B.选择C.希尔D.二路归并解析：解析：此题考查的知识点是各类排序算法的思想。
20、应选 A。15.若用冒泡排序方法对序列10，14，26，29，41，52从大到小排序，需进行( )次比较。（分数：2.00）A.3B.10C.15 D.25解析：解析：此题考查的知识点是冒泡算法的思想及过程。第一趟比较 5次，第 2趟比较 4次，第 3趟比较 3次，第 4趟比较 2次，第 5趟比较 1次，结束。共 15次，应选 C。16.下列( )是一个堆。（分数：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 解析：解析：完全二叉树中所有非终端结点的值均不大于(或不小于)其左、
21、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：17.若一组记录的关键码为(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，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，
22、84)，将 46插入得到(40，38，46，56，79，84)，本题答案为 C。二、综合应用题(总题数：15，分数：34.00)18.综合应用题 41-47小题。_解析：19.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。（分数：2.00）_正确答案：(正确答案：int Partition(RecType R，int n , int h) 一趟快速排序算法，枢轴记录到位，并返回其所在位置 int i=n，j=h，R 0=Ri，x=Rikey； while(i=x)j一一； if(i=x)j-； if(i解
23、析：21.已知关键字序列(K 1 ，K 2 ，K 3 ，K N-1 )是大根堆。试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。（分数：2.00）_正确答案：(正确答案：void sift(RecType R，int n) 把 Rn调成大堆 int j=n；R0=Rj； for(i=n2；i=1；i=i2) if(R0keyRikey)Rj=Ri；j=i； else break； Rj=R0； void HeapBuilder(RecType R，int n) for(i=2；iRi) Ri=Rj；i=j；j=i4； 调小
24、堆 Ri=R0； else 插入元素大于双亲，调大堆 i=n；j=i4； while(j0 MaxNum 是一个常量 int len； SeqList； HeapInsert(SeqList R，KeyType key) int i，j； RRec+R1enkey=key； 增加新值到原堆中已有元素的尾部且堆的长度加 1 i=R1en2；j=Rlen； while(i0) 调整为堆 if(RRecikey 2Rlen，调整是自底向上查找，最多查找到树根，所以时间复杂度为 O(log2Rlen)。)解析：30.写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。（分数：2.00）_正确答案：(正确答案：建立堆的算法如下： void BuildHeap(SeqList R，KeyType An) 类型定义 int i； Rlen=0： 初始化 for(i=0；i解析：
