1、计算机专业基础综合（数据结构）模拟试卷 7及答案解析(总分：110.00，做题时间：90 分钟)一、单项选择题(总题数：31，分数：62.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。_2.下面给出的 4种排序方法中，( )排序法是不稳定性排序法。（分数：2.00）A.插入B.冒泡C.二路归并D.堆3.下列内部排序算法中，其比较次数(或交换次数)与序列初态无关的算法是( )。（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序D.冒泡排序4.下列内部排序算法中，在初始序列已基本有序(除去 n个元素中的某 k个元素后即呈有序，kn)的情况
2、下，排序效率最高的算法是( )。（分数：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.堆排序10.数据表
4、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，bai，deng，wang
5、，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.若一组记录的关键码为(46，79
6、，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，7916.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n)D.O(nlog 2 n)，O(n)17.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序快速排序归并排
7、序B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序18.一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5个长度为 2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，8219.已知 10个数据元素为(54，28，16，34，73，62，95，60
8、，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数：2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，9520.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，
9、21，25，35，27，47，68，84 (4) 15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序B.希尔排序C.归并排序D.快速排序21.在对一组记录(50，40，95，20，15，70，60，45，80)进行直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3D.422.将两个各有 N个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.NB.2N一 1C.2ND.N一 123.已知待排序的 n个元素可分为 nk 个组，每个组包含
10、 k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 n)C.O(klog 2 n)D.O(klog 2 k)24.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1925
11、.归并排序中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n)C.O(nlog 2 n)D.O(n 2 )26.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7，9D.A、B、C 均不对27.基于比较方法的 n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00）A.O(nlog 2 n)B.O(log 2 n)C.O(n)D.O(n 2 )28.以下排序
12、方法中，稳定的排序方法是( )。（分数：2.00）A.直接插入排序B.直接选择排序C.堆排序D.基数排序29.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40)D.(15，20，80，70)30.在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（分数：2.00）A.5
13、，4，8B.6，3，9C.7，4，3D.3，8，2二、综合应用题(总题数：24，分数：48.00)31.综合应用题 41-47小题。（分数：2.00）_32.在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?（分数：2.00）_33.设有 5个互不相同的元素 a，b，c，d，e，能否通过 7次比较就将其排好序?如果能，请列出其比较过程；如果不能，则说明原因。（分数：2.00）_34.对一个由 n个关键字不同的记录构成的序列，能否用比 2n一 3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏
14、的情况下至少要进行多少次比较?（分数：2.00）_35.利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。（分数：2.00）_36.已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1 key 2 key n )；(2)关键字自大到小逆序(key 1 key 2 key n )； (3)奇数关键字顺序有序，偶数关键字顺序有序(key 1 key 3 ，key 2 key 4 )； (4)前半部分元素按关键字顺序有序，后半部分元素按关键字
15、顺序逆序(key 1 key 2 key m ，key m+1 key m+2 key n ，m 为中间位置)。（分数：2.00）_37.对于 n个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n个元素的初始排序有关。问：(1)当 n=7时，在最好情况下需进行多少次比较?请说明理由。 (2)当 n=7时，给出一个最好情况的初始排序的实例。 (3)当 n=7时，在最坏情况下需进行多少次比较?请说明理由。 (4)当 n=7时，给出一个最坏情况的初始排序的实例。（分数：2.00）_38.关于堆的一些问题： (1)堆的存储表示是顺序的，还是链接的? (2)设有一个最小堆，即堆中任意结点的关键
16、字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方? (3)对 n个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 O表示法)?（分数：2.00）_39.若有 N个元素已构成一个小根堆，那么如果增加一个元素为 K n+1 ，请用文字简要说明如何在 log 2 n的时间内将其重新调整为一个堆。（分数：2.00）_40.冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。（分数：2.00）_41.有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对一个待排序的表(用数组表示
17、)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。 设计实现计数排序的算法。对于有 n个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?（分数：2.00）_42.某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。（分数：2.00）_43.设有
18、一个数组中存放了一个无序的关键字序列 K 1 ，K 2 ，K n 。现要求将 K n ，放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。（分数：2.00）_44.已知关键字序列(K 1 ，K 2 ，K 3 ，K n-1 )是大根堆。试写出一算法将(K 1 ，K 2 ，K 3 ，K n-1 ，K n )调整为大根堆，并利用调整算法写一个建大根堆的算法。（分数：2.00）_45.最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图
19、所示为一最小最大堆。 （分数：2.00）_46.输入 N个只含一位数字的整数，试用基数排序的方法，对这 N个数排序。（分数：2.00）_47.设有 15 000个无序的元素，希望用最快的速度挑选出其中前 10个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?（分数：2.00）_48.对一个具有 7个记录的文件进行快速排序，请问： (1)在最好情况下需进行多少次比较?说明理由，并给出相应实例。 (2)在最坏情况下需进行多少次比较?为什么?请给出相应实例。（分数：2.00）_49.判断下列序列是否为堆，若不是堆，则把它们调整为堆。 (1)(100，85，9
20、5，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）_50.将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少?（分数：2.00）_51.写出快速排序的非递归算法。（分数：2.00）_52.试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。（
21、分数：2.00）_53.写一个 HeapInsert(R，key)算法，将关键字插入到堆 R中，并保证插入后 R仍是堆。请分析算法的时间复杂度。提示：将 key先插入 R中已有元素的尾部(即原堆的长度加 1的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。（分数：2.00）_54.写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。（分数：2.00）_计算机专业基础综合（数据结构）模拟试卷 7答案解析(总分：110.00，做题时间：90 分钟)一、单项选择题(总题数：31，分数：62.00)1.单项选择题 1-40小题。下列每题给出的四个选
22、项中，只有一个选项是最符合题目要求的。_解析：2.下面给出的 4种排序方法中，( )排序法是不稳定性排序法。（分数：2.00）A.插入B.冒泡C.二路归并D.堆 解析：解析：此题考查的知识点是排序算法的稳定性问题。如果待排序的文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项 A、B、C 都是相邻元素比较，是稳定的。所以选 D。3.下列内部排序算法中，其比较次数(或交换
23、次数)与序列初态无关的算法是( )。（分数：2.00）A.快速排序B.直接插入排序C.二路归并排序 D.冒泡排序解析：解析：此题考查的知识点是各类排序算法的思想。 冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D 错。 直接插入排序思想是假设待排序的记录存放在数组 Rn+1中，排序过程中的某一时刻，R 被分成两个子区间R1，Ri一 1/和Ri，Rn/，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第 i个记录 Ri插入到有序区中的适当位置，使得 R1到 Ri变为新
24、的有序区。首先比较 Ri和 Ri一 1，如果 Ri一 1Ri，则 R1i已排好序，第 i遍处理就结束了：否则交换 Ri与 Ri一 1的位置，继续比较 Ri1和 Ri一 2，直到找到某一个位置 j(1ji 一 1)使得 RjRj+1时为止。与序列初态有关，B 错。 快速排序是通过基准元素 v把表(文件，数据集合)划分成左、右两部分，使得左边的各记录的关键字都小于 v;右边的备记录的关键字都大于等于 v；重复该过程直到排好序。与序列初态有关，A 错。 二路归并是首先把每个记录看成是一个有序序列，共 n个，将它们两两合并成n2个分类序列，每个序列长度为 2(当 n为奇数时，最后一个序列长度为 1)；
25、对n2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为 n的分类序列为止。与序列初态无关，所以选 C。4.下列内部排序算法中，在初始序列已基本有序(除去 n个元素中的某 k个元素后即呈有序，kn)的情况下，排序效率最高的算法是( )。（分数：2.00）A.冒泡排序B.堆排序C.直接插入排序 D.二路归并排序解析：解析：此题考查的知识点是各类排序算法的效率。起泡排序比较 n(n一 1)2 次，没有交换次数；堆排序一次比较 log 2 n次，共需要 n轮；直接插入排序比较 n一 1次，没有交换；二路归并排序一次比较 log 2 n次，共需要 n轮。综上，应选 C。5.下列排序算法中，(
26、 )每一趟都能选出一个元素放在最终位置上，并且是不稳定的。（分数：2.00）A.冒泡排序B.希尔排序C.简单选择排序 D.直接插入排序解析：解析：本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。6.下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog 2 n)的是( )。（分数：2.00）A.堆排序 B.冒泡排序C.直接选择排序D.快速排序解析：解析：由这些排序方法的特点可知本题答案为 A。7.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（分数：2.00）A.选择排序B.冒泡排序C.归并排序 D.堆排序解析：解析：此题考查的知识点是各类排
27、序算法的思想。应选 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.堆排序B.快速排序 C.插入排序D.归并排序解析：解析：此题考查的知识点是各类排序算法的思想
28、。应选 C，B。9.如果只想得到 1 000个元素组成的序列中第 5个最小元素之前的部分排序的序列，用( )方法最快。（分数：2.00）A.冒泡排序B.快速排序C.简单选择排序D.堆排序 解析：解析：此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较 n一 i次，快速排序结束后才能得到结果，堆排序可以在选择 5次后得到结果，每次比较元素次数为 log 2 n。所以应选 D。10.数据表 A中有 10 000个元素，如果仅要求求出其中最大的 10个元素，则采用( )方法最节省时间。（分数：2.00）A.堆排序 B.希尔排序C.快速排序D.直接选择排序解析：解析：只有堆排序每次
29、输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆项元素总是当前剩下元素的最大或最小的，本题答案为 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，fang，shi，tang，liuD.an，bai，deng，wang，shi，liu，tang，fang解
30、析：解析：本题根据简单选择排序法的算法思想可得答案 B。12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。（分数：2.00）A.插入 B.选择C.希尔D.二路归并解析：解析：此题考查的知识点是各类排序算法的思想。应选 A。13.若用冒泡排序方法对序列10，14，26，29，41，52从大到小排序，需进行( )次比较。（分数：2.00）A.3B.10C.15 D.25解析：解析：此题考查的知识点是冒泡算法的思想及过程。第一趟比较 5次，第 2趟比较 4次，第 3趟比较 3次，第 4趟比较 2次，第 5趟比较 1次，
31、结束。共 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个记录为基准得到的一次划分结果为( )。（分数：2.00）A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，
32、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。16.采用简单选择排序，比较次数与移动次数分别为( )。（分数：2.00）A.O(n)，O(log 2 n)B.O(log 2 n)，O(n 2 )C.O(n 2 )，O(n) D.O(nlog 2 n)，O(n)解析：解析：
33、简单选择排序的关键字比较次数 KCN与对象的初始排列无关。第 i趟选择具有最小关键字对象所需的比较次数总是 ni一 1次(此处假定整个待排序对象序列有 n个对象)。因此，总的关键字比较次数为：17.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（分数：2.00）A.堆排序快速排序归并排序 B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序解析：解析：此题考查的知识点为排序的空间复杂性。堆排序辅助空间为 O(1)，快速排序为 O(log 2 n)，归并排序为 O(n)。应选 A。18.一组记录的关键码为(25，48，16，35，79，82，2
34、3，40，36，72)，其中，含有 5个长度为 2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。（分数：2.00）A.16，25，35，48，23，40，79，82，36，72 B.16，25，35，48，79，82，23，36，40，72C.16，25，48，35，79，82，23，36，40，72D.16，25，35，48，79，23，36，40，72，82解析：解析：对于(25，48，16，35，79，82，23，40，36，72)，(25，48)和(16，35)归并的结果为(16，25，35，48)。(79，82)和(23，40)归并后的结果为(23，40，79，82
35、)，余下的两个记录不归并，所以一趟归并后的结果为(16，25，35，48，23，40，79，82，36，72)，本题答案为 A。19.已知 10个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（分数：2.00）A.16，28，34，54，73，62，60，26，43，95B.28，16，34，54，62，73，60，26，43，95 C.28，16，34，54，62，60，73，26，43，95D.16，28，34，54，62，60，73，26，43，95解析：解析：冒泡排序每趟经过比较、交换，从无序区中产生
36、一个最大的元素，所以选 B。20.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下： (1)25，84，21，47，15，27，68，35，20 (2)20，15，21，25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4) 15，20，21，25，27，35，47，68，84 其所采用的排序方法是( )。（分数：2.00）A.直接选择排序 B.希尔排序C.归并排序D.快速排序解析：解析：可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为 A。21.在对一组记录(50，40，
37、95，20，15，70，60，45，80)进行直接插入排序时，当把第 7个记录 60插入到有序表时，为寻找插入位置需比较( )次。（分数：2.00）A.1B.2C.3 D.4解析：解析：第 6趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入 60，要与 95、70 和 50进行比较，共比较 3次，本题答案为 C。22.将两个各有 N个元素的有序表归并成一个有序表，其最少的比较次数是( )。（分数：2.00）A.N B.2N一 1C.2ND.N一 1解析：解析：此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，
38、比较次数最少为。23.已知待排序的 n个元素可分为 nk 个组，每个组包含 k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（分数：2.00）A.O(nlog 2 n)B.O(nlog 2 n) C.O(klog 2 n)D.O(klog 2 k)解析：解析：此题考查的知识点是分块排序的思想。因组与组之间已有序，故将 nk 个组分别排序即可，基于比较的排序方法每组的时间下界为 O(klog 2 k)。可以用二叉树分治形式描述，最好的情况是树的高度为 log 2 k。全部时间下界为 O(nlog 2 k)。应选 B。2
39、4.已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字 3，调整后得到的小根堆是( )。（分数：2.00）A.3，5，12，8，28，20，15，22，19 B.3，5，12，19，20，15，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，19解析：解析：根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：25.归并排序中，归并的趟数是( )。（分数：2.00）A.O(n)B.O(log 2 n) C.O(nlog 2 n)D.O(n 2 )解析：解析：此题考查的知识点是归并排序。
40、第 1遍归并的子序列长度为 2 0 ，第 2遍为 2 1 ，第i遍为 2 i-1 ，所以由 2 i-1 n 知，对 n个记录的数据集合，总共需要归并 log 2 n次。应选 B。26.有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（分数：2.00）A.一 1，4，8，9，20，7，15，7B.一 1，7，15，7，4，8，20，9C.一 1，4，7，8，20，15，7，9 D.A、B、C 均不对解析：解析：此题考查的知识点是堆排序。应选 c。27.基于比较方法的 n个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( )。（分数：2.00
41、）A.O(nlog 2 n) B.O(log 2 n)C.O(n)D.O(n 2 )解析：解析：此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行 log 2 (n!)次比较。由 Stirling公式可知，log 2 (n!)nlog 2 n144n+O(log 2 n)。所以基于关键字比较的分类时间的下界是 O(nlog 2 n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选 A。28.以下排序方法中，稳定的排序方法是( )。（分数：2.00）A.直接插入排序 B.直接选择排序C.堆排序D.基数排序解析：解析：下表为各种排序方法的性能比较。由表可知，本题答案为 A。29.在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定 d 0 =9，d 1 =4，d 2 =2，d 3 =1，则第二趟排序结束后前 4条记录为( )。（分数：2.00）A.(50，20，15，70)B.(60，45，80，50)C.(15，20，50，40) D.(15，20，80，70)解析：解析：t=3，d 0 =9，d 1 =4，d 2 =2，d 3 =1，第 1趟(d 1
