1、计算机专业基础综合（排序）模拟试卷 1 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 下面给出的 4 种排序方法中，( )排序法是不稳定性排序法。（A）插入（B）冒泡（C）二路归并（D）堆2 下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（A）快速排序（B）直接插入排序（C）二路归并排序（D）冒泡排序3 下列内部排序算法中，在初始序列已基本有序(除去 n 个元素中的某 k 个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。（A）冒泡排序（B）堆排序（C）直接插入排序（
2、D）二路归并排序4 下列排序算法中，( ) 每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（A）冒泡排序（B）希尔排序（C）简单选择排序（D）直接插入排序5 下列排序方法中，时间复杂性不受数据初始状态影响，恒为 D(nlog2n)的是( )。（A）堆排序（B）冒泡排序（C）直接选择排序（D）快速排序6 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（A）选择排序（B）冒泡排序（C）归并排序（D）堆排序7 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（A）直接插入排序（B）归并排序（C）直接选择排序（D
3、）堆排序8 对初始状态为递增序列的表按递增顺序排序最费时间的是( )算法。（A）堆排序（B）快速排序（C）插入排序（D）归并排序9 对初始状态为递增序列的表按递增顺序排序，最省时间的是( )算法。（A）堆排序（B）快速排序（C）插入排序（D）归并排序10 如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( )方法最快。（A）冒泡排序（B）快速排序（C）简单选择排序（D）堆排序11 数据表 A 中有 10000 个元素，如果仅要求求出其中最大的 10 个元素，则采用( )方法最节省时间。（A）堆排序（B）希尔排序（C）快速排序（D）直接选择排序12 若对序列(
4、tang，deng ，an，wang，shi，bai，fang，liu)采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（A）an，bai，deng，wang，tang，fang ，shi，liu（B） an，bai ，deng ，wang，shi，tang，fang，liu（C） an，bai ，deng ，wang，fang，shi，tang，liu（D）an，bai，deng，wang，shi，liu，tang，fang13 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（A
5、）插入（B）选择（C）希尔（D）二路归并14 若用冒泡排序方法对序列10，14，26，29，41，52 从大到小排序，需进行( )次比较。（A）3（B） 10（C） 15（D）2515 下列( ) 是一个堆。（A）19，75，34，26，97，56（B） 97，26，34，75，19，56（C） 19，56，26，97，34，75（D）19，34，26，97，56，7516 若一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第 1 个记录为基准得到的一次划分结果为( )。（A）38，40，46，56，79，84（B） 40，38，46，79，56，84（C）
6、40，38，46，56，79，84（D）40，38，46，84，56，79二、综合应用题41-47 小题，共 70 分。17 某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。18 设有一个数组中存放了一个无序的关键字序列 K1，K 2，K n。现要求将 Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。19 已知关键字序列(K 1，K 2，K 3，K N-1)是大根堆。试写出一算法将(K1，K 2，K 3，K n-1，K n)调整为大根堆，并利用调整算法写一个建大根堆
7、的算法。19 最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大) 。如图所示为一最小最大堆。20 画出在图中插入关键字为 5 的结点后的最小最大堆。21 画出在图中插入关键字为 80 的结点后的最小最大堆。22 编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。23 输入 N 个只含一位数字的整数，试用基数排序的方法，对这 N 个数排序。24 试构造对 5 个元素进行排序，最多只用 7 次比较的算法。25 设有 15000 个无序的元素，希
8、望用最快的速度挑选出其中前 10 最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?25 对一个具有 7 个记录的文件进行快速排序，请问：26 在最好情况下需进行多少次比较?说明理由，并给出相应实例。27 在最坏情况下需进行多少次比较?为什么? 请给出相应实例。28 判断下列序列是否为堆，若不是堆，则把它们调整为堆。(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，
9、20，40，60，65，75，80，82，85，95，100)29 将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少 ?30 写出快速排序的非递归算法。31 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。32 写一个 HeapInsert(R， key)算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。33 写
10、一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。计算机专业基础综合（排序）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不
11、稳定。选项 A、B 、C 都是相邻元素比较，是稳定的。所以选 D。【知识模块】 排序2 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的思想。冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D 错。直接插入排序思想是假设待排序的记录存放在数组 Rn+1中，排序过程中的某一时刻，尺被分成两个子区间R1 ，Ri 一 1和Ri，Rn，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第 i 个记录 Ri插入到有序区中的适当位置，使得 R1到 Ri变为新的有序区。
12、首先比较 Ri和 Ri 一 1，如果 Ri 一 1Ri，则R1 i已排好序，第 i 遍处理就结束了；否则交换 Ri与 Ri 一 1的位置，继续比较 Ri 一 1和 Ri 一 2，直到找到某一个位置 j(1ji 一 1)使得 RjRj+1时为止。与序列初态有关，B 错。快速排序是通过基准元素 v 把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于 v：右边的各记录的关键字都大于等于 v；重复该过程直到排好序。与序列初态有关，A 错。二路归并是首先把每个记录看成是一个有序序列，共 n 个，将它们两两合并成n2个分类序列，每个序列长度为 2(当 n 为奇数时，最后一个序列长度为
13、 1)；对n2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为 n 的分类序列为止。与序列初态无关，所以选 C。【知识模块】 排序3 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的效率。起泡排序比较 n(n 一 1)2 次，没有交换次数；堆排序一次比较 log2n 次，共需要 n 轮；直接插入排序比较 n 一 1 次，没有交换；二路归并排序一次比较 log2n 次，共需要 n 轮。综上，应选 C。【知识模块】 排序4 【正确答案】 C【试题解析】 本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。【知识模块】 排序5 【正确答案】 A【试题解析】 由这些排
14、序方法的特点可知本题答案为 A。【知识模块】 排序6 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的思想。应选 C。【知识模块】 排序7 【正确答案】 A【试题解析】 此题考查的知识点是各类排序算法的思想。应选 A。【知识模块】 排序8 【正确答案】 B【试题解析】 此题考查的知识点是各类排序算法的思想。应选 B。【知识模块】 排序9 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的思想。应选 C。【知识模块】 排序10 【正确答案】 D【试题解析】 此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较 ni 次，快速排序结束后才能得到结果，堆排
15、序可以在选择 5 次后得到结果，每次比较元素次数为 log2n。所以应选 D。【知识模块】 排序11 【正确答案】 A【试题解析】 只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆顶元素总是当前剩下元素的最大或最小的，本题答案为A。【知识模块】 排序12 【正确答案】 B【试题解析】 本题根据简单选择排序法的算法思想可得答案 B。【知识模块】 排序13 【正确答案】 A【试题解析】 此题考查的知识点是各类排序算法的思想。应选 A。【知识模块】 排序14 【正确答案】 C【试题解析】 此题考查的知识点是冒泡算法的思想及过程。第一趟比较 5 次，第2 趟比较 4
16、次，第 3 趟比较 3 次，第 4 趟比较 2 次，第 5 趟比较 1 次，结束。共 15次，应选 C。【知识模块】 排序15 【正确答案】 D【试题解析】 完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：得出答案为 D。【知识模块】 排序16 【正确答案】 C【试题解析】 对于(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 插入
17、得到(40，38 ，46，56，79，84)，本题答案为 C。【知识模块】 排序二、综合应用题41-47 小题，共 70 分。17 【正确答案】 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=1；i=i 2)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=
18、i4； 调小堆 Ri=R0； else 插入元素大于双亲，调大堆 i=n ；j=i4； while(j0 & RjRikey) 插入元素大于双亲，先与双亲交换，然后调大堆 Rj=Ri；j=i4； while(j0&R-j0&RjRi) Ri=Rj；i=j；j=i4； Ri=R0； 【知识模块】 排序23 【正确答案】 typedef structint key；int next；SLRecType；SLRecType RN+1；typedef structint f，e；SLQueue；SLQueue B10；int Radixsort(SLRecType RE，int n) 设备关键字已输入
19、到 R 数组中for(i=1；ib，cd(ad，则有序 abd；若 bdb，此时已进行了 3 次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4 次比较，从而共需 7 次比较。【知识模块】 排序25 【正确答案】 上面所说的几种排序方法中，排序速度都很快，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部序列，而排序过程中无法知道部分连续位置上的最终元素。而堆排序则是每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆进行再调整，保证堆顶元素总是当前剩下元素的最大或最小的，从而可知，如果在一个大量数据的文件中，如含有 15000 个元素的记录
20、文件中选取前 10 个最大的元素，宜采用堆排序。【知识模块】 排序【知识模块】 排序26 【正确答案】 在最好情况下，由于快速排序是一个划分子区间的排序，每次划分时最好能得到两个长度相等的子文件。设文件的长度为 n=2k 一 1，显然，第一遍划分得到两个长度均为n2的子文件。第二遍划分得到 4 个长度均为n4的子文件，以此类推，总共进行后=log 2(n+1)遍划分，各文件的长度均为 1，此时排序结束。由于 n=7，k=3 ，在最好情况下，第一遍经过 6 次，可找到一个基元是正中间的元素；第二遍分别对两个子文件(此时长度为 3)进行排序，各需要 2 次，这样就可将整个文件排序完毕，从而知 n=
21、7 的最好情况下需进行 10 次比较。例如：4，7，5，6，3，1，2。【知识模块】 排序27 【正确答案】 在最坏情况下，若每次划分时用的基元，它的关键字值是当前记录中最大(或最小) ，那么每次划分只能得到左子文件(或右子文件)。子文件长度只比原文件减少一个。因此，若初始排列的记录是按关键字递增或递减，而所得的结果必须为递减或递增排列，那么此时，快速排序就退化为与冒泡排序相似，而且时间复杂度为 O(n2)，反而不快了。对于 n=7 的记录文件，显然最坏情况下的比较次数为 21。例如：7，6，5，4，3，2，1。【知识模块】 排序28 【正确答案】 依据堆定义可知：序列(1)、(2) 、(4)
22、是堆，(3) 不是堆，从而可对其调整使之成为大根堆(100，95，65，85，80，60，40，75，82，10，20)。【知识模块】 排序29 【正确答案】 因为基数排序所需的时间不仅与文件的大小 n 有关，而且与关键字的位数和关键字的基数有关。设关键字的基数为厂，显然，十进制数基数为10，二进制数的基数为 2。要建立 r 个空队列所需时间为 O(r)；把 n 个记录分放到各个队列中，重新收集起来需要的时间为 O(n)，因此一趟排序所需的时间复杂度为 O(n+r)；若每个关键字有 d 位，则总共要进行 d 遍排序，所以基数排序的时间复杂度为 O(d(n+r)。由于关键字的位数 d 与基数 r
23、 和最大关键字取值有关。因此不同的 r 和关键字将需要不同的时间。所以，本题中总的时间复杂度为 O(d(n+2)，d 为关键字最大值对应的二进制数位数，即将十进制的关键字用二进制数表示时，复杂度增大了。另外只需要设置两个指针队列，即将十进制的关键字用二进制数表示时，空间复杂性减少了。【知识模块】 排序30 【正确答案】 设对记录 R1n进行快速排序，要求用非递归算法。利用一个包含有 low 和 high 两个整数成员的记录数组 stack作为栈，low 和 high 成员分别指示某个子文件的首、尾记录的下标号。算法如下：void quicksort(SeqList R，int n)设待排序记录
24、放在 R1n中，下标从 1开始int i，j，low，high，top=0；structint low，high；stackMax； Max 为一个大于 n 的常量RecType temp；top=1；stacktoplow=1；stacktophigh=n；k 栈while(top0) 栈非空，则取出一个子文件进行划分low=stacktoplow；high=stacktophigh；top-；出栈i=low；j=high；temp=Ri；dowhile(itempkey)j 一一；if(i=0)j-； 从右向左找负数while(i0) 调整为堆 if(RRecikey 2Rlen，调整是自底向上查找，最多查找到树根，所以时间复杂度为 O(log2Rlen)。【知识模块】 排序33 【正确答案】 建立堆的算法如下：void BuildHeap(SeqList R，KeyType An) 类型定义int i；R len=0： 初始化for(i=0；in；i+)Heaplnsert(R ，Ai)；【知识模块】 排序
