1、计算机专业基础综合（数据结构）模拟试卷 7 及答案与解析一、单项选择题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 下列排序方法中，时间复杂性不受数据初始状态影响，恒为 O(nlog2n)的是( )。（A）堆排序（B）冒泡排序（C）直接选择排序（D）快速排序6 下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。（A）选择排序（B）冒泡排序（C）归并排序（D）堆排序7 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是( )。（A）直接插入排序（B）归并排序（C）直接选择排序
3、（D）堆排序7 对初始状态为递增序列的表按递增顺序排序，最省时间的是( (1) )算法，最费时间的是( (2) )算法。8 (1)（A）堆排序（B）快速排序（C）插入排序（D）归并排序9 (2)（A）堆排序（B）快速排序（C）插入排序（D）归并排序10 如果只想得到 1 000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用( ) 方法最快。（A）冒泡排序（B）快速排序（C）简单选择排序（D）堆排序11 数据表 A 中有 10 000 个元素，如果仅要求求出其中最大的 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 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
5、（A）插入（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，7917 采用简单选择排序，比较次数与移动次数分别为( )。（A）O(n)， O(log2n)（B） O(log2n)，O(n 2)（C） O(n2)，O(n)（D）O(nlog 2n)，O(n)18 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是( )。（A）堆排序快速排序归并排序（B）堆排序归并排序快速排序（C）堆排序归并排序快速排序（D）堆排序快速排序归并排序19 一组记录的关键码为(25，48，16，35，79，82，23，40，36，72)，其中，含有 5 个长度为 2 的有序表，按归并排序的
7、方法对该序列进行一趟归并后的结果为( )。（A）16，25，35，48，23，40，79，82，36，72（B） 16，25，35，48，79，82，23，36，40，72（C） 16，25，48，35，79，82，23，36，40，72（D）16，25，35，48，79，23，36，40，72，8220 已知 10 个数据元素为(54，28，16，34，73，62，95，60，26，43)，对该序列按从小到大排序，经过一趟冒泡排序后的序列为( )。（A）16，28，34，54，73，62，60，26，43，95（B） 28，16，34，54，62，73，60，26，43，95（C） 28，1
8、6，34，54，62，60，73，26，43，95（D）16，28，34，54，62，60，73，26，43，9521 用某种排序方法对线性表(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其所采用的排序方法是( )。（A）直接选择排序（B）希尔排序（C）归并排序（D）快速排序22 在对一组记录(50，40，95
9、，20，15，70，60，45，80)进行直接插入排序时，当把第 7 个记录 60 插入到有序表时，为寻找插入位置需比较( )次。（A）1（B） 2（C） 3（D）423 将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是 ( )。（A）N（B） 2N 一 1（C） 2N（D）N 一 124 已知待排序的 n 个元素可分为 nk 个组，每个组包含 k 个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为( )。（A）O(nlog 2n)（B） O(nlog2n)（C） O(klog2n)（D）O(klog 2k)2
10、5 已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。（A）3，5，12，8，28，20，15，22，19（B） 3，5，12，19，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，12，5，8，28，20，15，22，1926 归并排序中，归并的趟数是( )。（A）O(n)（B） O(log2n)（C） O(nlog2n)（D）O(n 2)27 有一组数据(15，9，7，8，20，一 1，7，4)，用堆排序的筛选方法建立的初始堆为( )。（A）一 1，4，8，9，20，7，15，7
11、（B）一 1，7，15，7，4，8，20，9（C）一 1，4，7，8，20，15，7，9（D）A、B、C 均不对28 基于比较方法的 n 个数据的内部排序，最坏情况下的时间复杂度能达到的最好下界是( ) 。（A）O(nlog 2n)（B） O(log2n)（C） O(n)（D）O(n 2)29 以下排序方法中，稳定的排序方法是( )。（A）直接插入排序（B）直接选择排序（C）堆排序（D）基数排序30 在对一组记录(50，40，95，20，15，70，60，45，80)进行希尔排序时，假定d0=9， d1=4， d2=2，d 3=1，则第二趟排序结束后前 4 条记录为( )。（A）(50 ，20
12、，15，70)（B） (60，45，80，50)（C） (15，20，50，40)（D）(15 ，20，80，70)31 在归并排序中，若待排序记录的个数为 20，则共需要进行( )趟归并，在第三趟归并中，是把长度为( )的有序表归并为长度为( )的有序表。（A）5，4，8（B） 6，3，9（C） 7，4，3（D）3，8，2二、综合应用题41-47 小题，共 70 分。32 在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?33 设有 5 个互不相同的元素 a，b，c ，d，e，能否通过 7 次比较就将其排好序?如果能，请
13、列出其比较过程；如果不能，则说明原因。34 对一个由 n 个关键字不同的记录构成的序列，能否用比 2n 一 3 少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现? 在最坏的情况下至少要进行多少次比较?35 利用比较的方法进行排序，在最坏的情况下能达到的最好时间复杂性是什么?请给出详细证明。36 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)? (1)关键字自小到大有序(key 1key 2key n)； (2)关键字自大到小逆序(key1key 2 key n)； (3)奇数关键
14、字顺序有序，偶数关键字顺序有序(key1key 3 ，key 2key 4)； (4) 前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key 1key 2key m， keym+1key m+2key n，m 为中间位置)。37 对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：(1)当 n=7 时，在最好情况下需进行多少次比较?请说明理由。(2)当 n=7 时，给出一个最好情况的初始排序的实例。(3)当 n=7 时，在最坏情况下需进行多少次比较?请说明理由。(4)当 n=7 时，给出一个最坏情况的初始排序的实例。38 关于堆的一些
15、问题：(1)堆的存储表示是顺序的，还是链接的?(2)设有一个最小堆，即堆中任意结点的关键字均大于它的左孩子和右孩子的关键字。其具有最大值的元素可能在什么地方?(3)对 n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大 O 表示法)?39 若有 N 个元素已构成一个小根堆，那么如果增加一个元素为 Kn+1，请用文字简要说明如何在 log2n 的时间内将其重新调整为一个堆。40 冒泡排序方法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)。请给出上浮和下沉过程交替的冒泡排序算法。41 有一种简单的排序算法，叫做计数排序(Count sorting)。这种排序算法对
16、一个待排序的表(用数组表示) 进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。设计实现计数排序的算法。对于有 n 个记录的表，关键字的比较次数是多少?与简单选择排序相比较，这种方法是否更好?为什么?42 某个待排序的序列是一个可变长度的字符串序列，这些字符串一个接一个地存储于唯一的字符数组中。请改写快速排序算法，对这个字符串序列进行排序。43 设有一个数组中存
17、放了一个无序的关键字序列 K1，K 2，K n。现要求将 Kn，放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过 n。44 已知关键字序列(K 1，K 2，K 3，K n-1)是大根堆。试写出一算法将(K1，K 2，K 3，K n-1，K n)调整为大根堆，并利用调整算法写一个建大根堆的算法。45 最小最大堆(min max Heap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大) 。如图所示为一最小最大堆。(1)画出在图中插入关键字为 5 的结点后的最小最大堆。 (2
18、)画出在图中插入关键字为 80 的结点后的最小最大堆。 (3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。46 输入 N 个只含一位数字的整数，试用基数排序的方法，对这 N 个数排序。47 设有 15 000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素。在快速排序、堆排序、归并排序、基数排序和希尔排序中，宜采用哪种方法并说明理由?48 对一个具有 7 个记录的文件进行快速排序，请问：(1)在最好情况下需进行多少次比较? 说明理由，并给出相应实例。(2)在最坏情况下需进行多少次比较? 为什么?请给出相应实例。49 判断下列序列是否为堆，若不是
19、堆，则把它们调整为堆。(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)50 将十进制的关键字用二进制数表示，对基数排序所需的时间和附设空间分别有什么影响?各是多少 ?51 写出快速排序的非递归算法。52 试设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前，并分析算法的时间复杂度。53 写一个 Hea
20、pInsert(R， key)算法，将关键字插入到堆 R 中，并保证插入后 R 仍是堆。请分析算法的时间复杂度。提示：将 key 先插入 R 中已有元素的尾部(即原堆的长度加 1 的位置，插入后堆的长度加 1)，然后自下往上调整，使插入的关键字满足堆性质。54 写一个建立堆的算法：从空堆开始，依次读入元素，调用上题中堆插入算法将其插入堆中。计算机专业基础综合（数据结构）模拟试卷 7 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 此题考查的知识点是排序算法的稳定性问题。如果待排序的
21、文件中，存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序是稳定的排序；反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序是不稳定的排序。是否稳定与算法有关，相邻数据比较的算法是稳定的，不相邻数据比较会出现不稳定。选项 A、B 、C 都是相邻元素比较，是稳定的。所以选 D。【知识模块】 数据结构2 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的思想。冒泡排序方法就是自底向上检查这个序列，若两个相邻的元素的顺序不对，则交换。直到所有元素处理完为止。与序列初态有关，D 错。直接插入排序思想是假设待排序的记录存放在数组 Rn
22、+1中，排序过程中的某一时刻，R 被分成两个子区间R1，Ri 一 1和Ri，Rn，其中，前一个子区间是已排好序的有序区；后一个子区间是当前未排序的无序区。直接插入排序的基本操作是将当前无序区的第 i 个记录 Ri插入到有序区中的适当位置，使得 R1到 Ri变为新的有序区。首先比较 Ri和 Ri 一 1，如果 Ri 一 1Ri，则R1 i已排好序，第 i 遍处理就结束了：否则交换 Ri与 Ri 一 1的位置，继续比较 Ri1和 Ri 一 2，直到找到某一个位置 j(1ji 一 1)使得 RjRj+1时为止。与序列初态有关，B 错。快速排序是通过基准元素 v 把表(文件，数据集合)划分成左、右两部
23、分，使得左边的各记录的关键字都小于 v;右边的备记录的关键字都大于等于 v；重复该过程直到排好序。与序列初态有关，A 错。二路归并是首先把每个记录看成是一个有序序列，共 n 个，将它们两两合并成n2个分类序列，每个序列长度为 2(当 n 为奇数时，最后一个序列长度为 1)；对n2个分类序列，再两两归并在一起；如此进行，直到归并成一个长度为 n 的分类序列为止。与序列初态无关，所以选 C。【知识模块】 数据结构3 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的效率。起泡排序比较 n(n 一 1)2 次，没有交换次数；堆排序一次比较 log2n 次，共需要 n 轮；直接插入排序比较
24、 n 一 1 次，没有交换；二路归并排序一次比较 log2n 次，共需要 n 轮。综上，应选 C。【知识模块】 数据结构4 【正确答案】 C【试题解析】 本题考查各种内部排序算法的比较，考生一定要熟记下面这张表格。【知识模块】 数据结构5 【正确答案】 A【试题解析】 由这些排序方法的特点可知本题答案为 A。【知识模块】 数据结构6 【正确答案】 C【试题解析】 此题考查的知识点是各类排序算法的思想。应选 C。【知识模块】 数据结构7 【正确答案】 A【试题解析】 此题考查的知识点是各类排序算法的思想。应选 A。【知识模块】 数据结构【知识模块】 数据结构8 【正确答案】 C【知识模块】 数据
25、结构9 【正确答案】 B【试题解析】 此题考查的知识点是各类排序算法的思想。应选 C，B 。【知识模块】 数据结构10 【正确答案】 D【试题解析】 此题考查的知识点是各类排序算法的思想。冒泡排序和简单选择排序每次要比较 n 一 i 次，快速排序结束后才能得到结果，堆排序可以在选择 5 次后得到结果，每次比较元素次数为 log2n。所以应选 D。【知识模块】 数据结构11 【正确答案】 A【试题解析】 只有堆排序每次输出一个堆顶元素(即最大或最小值的元素)，然后对堆再进行调整，保证堆项元素总是当前剩下元素的最大或最小的，本题答案为A。【知识模块】 数据结构12 【正确答案】 B【试题解析】 本
26、题根据简单选择排序法的算法思想可得答案 B。【知识模块】 数据结构13 【正确答案】 A【试题解析】 此题考查的知识点是各类排序算法的思想。应选 A。【知识模块】 数据结构14 【正确答案】 C【试题解析】 此题考查的知识点是冒泡算法的思想及过程。第一趟比较 5 次，第2 趟比较 4 次，第 3 趟比较 3 次，第 4 趟比较 2 次，第 5 趟比较 1 次，结束。共 15次，应选 c。【知识模块】 数据结构15 【正确答案】 D【试题解析】 完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值，则此序列可称为堆。据此，可画出二叉树，如下图所示：得出答案为 D。【知识模块】
27、数据结构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 插入得到(40，38 ，46，56，79，84)，本题答案为 C。【知识模块】 数据结构17 【正确答案】 C【试题解析】 简单选择排序的关键字比较次数 KCN 与对象的初始排列无关。第 i趟选择具有最小关键字对象所需的比较次数总是 ni 一 1 次(此处假定整个待排序对象序列有 n 个对象) 。因此，总的关
28、键字比较次数为：最坏情况是每一趟都要进行交换，总的对象移动次数为 RMN=3(n 一 1)。【知识模块】 数据结构18 【正确答案】 A【试题解析】 此题考查的知识点为排序的空间复杂性。堆排序辅助空间为 O(1)，快速排序为 O(log2n)，归并排序为 O(n)。应选 A。【知识模块】 数据结构19 【正确答案】 A【试题解析】 对于(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) ，余下的两个记录不归并，所以一趟归并后的结果为
29、(16，25 ，35，48，23，40，79，82，36，72)，本题答案为 A。【知识模块】 数据结构20 【正确答案】 B【试题解析】 冒泡排序每趟经过比较、交换，从无序区中产生一个最大的元素，所以选 B。【知识模块】 数据结构21 【正确答案】 A【试题解析】 可以看到，每趟从无序区中找出一个最大的元素定位，所以答案为A。【知识模块】 数据结构22 【正确答案】 C【试题解析】 第 6 趟的结果为(15，20，40，50，70，95，60，45，80)，此时插入 60，要与 95、70 和 50 进行比较，共比较 3 次，本题答案为 C。【知识模块】 数据结构23 【正确答案】 A【试题
30、解析】 此题考查的知识点是归并排序思想。当第一个有序表中所有的元素都小于第二个表中元素，或者都大于第二个表中元素时，比较次数最少为。【知识模块】 数据结构24 【正确答案】 B【试题解析】 此题考查的知识点是分块排序的思想。因组与组之间已有序，故将nk 个组分别排序即可，基于比较的排序方法每组的时间下界为 O(klog2k)。可以用二叉树分治形式描述，最好的情况是树的高度为 log2k。全部时间下界为O(nlog2k)。应选 B。【知识模块】 数据结构25 【正确答案】 A【试题解析】 根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：可以得出调整后的小根堆为 3，5，12，8，
31、28，20，15，22，19。【知识模块】 数据结构26 【正确答案】 B【试题解析】 此题考查的知识点是归并排序。第 1 遍归并的子序列长度为 20，第2 遍为 21，第 i 遍为 2i-1，所以由 2i-1n 知，对 n 个记录的数据集合，总共需要归并 log2n 次。应选 B。【知识模块】 数据结构27 【正确答案】 C【试题解析】 此题考查的知识点是堆排序。应选 c。【知识模块】 数据结构28 【正确答案】 A【试题解析】 此题考查的知识点是各类排序的效率。理论上可以证明，对于基于关键字之间比较的分类，无论用什么方法都至少需要进行 log2(n!)次比较。由Stirling 公式可知，
32、log 2(n!)nlog2n144n+O(log 2n)。所以基于关键字比较的分类时间的下界是 O(nlog2n)。因此不存在时间复杂性低于此下界的基于关键字比较的分类。应选 A。【知识模块】 数据结构29 【正确答案】 A【试题解析】 下表为各种排序方法的性能比较。由表可知，本题答案为 A。【知识模块】 数据结构30 【正确答案】 C【试题解析】 t=3，d 0=9， d1=4，d 2=2，d 3=1，第 1 趟(d 1=4)后的结果为(15，40 ，60，20，50，70，95，45，80)，第 2 趟(d 2=2)后的结果为(15，20 ，50，40，60，45，80，70，95)，本
33、题答案为(15，20，50，40)。【知识模块】 数据结构31 【正确答案】 A【试题解析】 n=20，共需进行log 2n=5 趟归并，第 1 趟归并后成为 10 个有序表，第 2 趟归并后成为 5 个有序表(每个长度为 4)，第 3 趟归并将长度为 4 个的有序表归并为长度为 8 的有序表，本题答案为：5，4，8。【知识模块】 数据结构二、综合应用题41-47 小题，共 70 分。32 【正确答案】 这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。【知识模块】 数据结构33 【正确答案】 可以做到
34、。取 a 与 b 进行比较，c 与 d 进行比较。设ab，cd(ab 和 cd 情况类似)，此时需 2 次比较，取 b 和 d 比较，若 bd，则有序 ab d；若 bd 时则有序 cdb，此时已进行了 3 次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需 4 次比较，从而共需 7 次比较。【知识模块】 数据结构34 【正确答案】 将 n 个元素对称比较，即第一个元素与最后一个元素比较，第二个元素与倒数第二个元素比较比较中的小者放前半部，大者放后半部，用了n2 次比较。再在前后两部分中分别简单选择最小和最大元素，各用(n2)一 1 次比较。总共用了(3n2) 一 2 次比较
35、。显然，当 n3 时，(2n 一 3)(3n2)一 2。 用分治法求解再给出另一参考答案。 对于两个数 x 和 y，经一次比较可得到最大值和最小值；对于三个数 x，y，z，最多经 3 次比较可得最大值和最小值；对于 n 个数(n 3)，将分成长为 n 一 2 和 2 的前后两部分 A 和 B，分别找出最大者和最小者：Max A，Min A，Max B，Min B，最后 Max=MaxA，Max B和 Min=Min A，MinB 。对 A 使用同样的方法求出最大值和最小值，直到元素个数不超过 3。 设 C(n)是所需的最多比较次数，根据上述原则，当 n3 时有如下关系式：通过逐步递推，可以得到
36、：C(n)=(3n2)一 2。显然，当 n3 时，2n 一 3(3n2)一 2。事实上(3n2)一 2 是解决这一问题的比较次数的下限。【知识模块】 数据结构35 【正确答案】 假定待排序的记录有 n 个。由于含 n 个记录的序列可能出现的状态有 n!个，则描述 n 个记录排序过程的判定树必须有 n!个叶子结点。因为若少一个叶子，则说明尚有两种状态没有分辨出来。我们知道，若二叉树高度是 h，则叶子结点个数最多为 2h-1；反之，若有 u 个叶子结点，则二叉树的高度至少为(log 2u)+1。这就是说，描述 n 个记录排序的判定树必定存在一条长度为 log2(n!)的路径。即任何一个借助“ 比较
37、” 进行排序的算法，在最坏情况下所需进行的比较次数至少是log2(n!)。根据斯特林公式，有 log2(n!)=O(nlog2n)。即借助于“ 比较”进行排序的算法在最坏情况下能达到的最好时间复杂度为 O(nlog2n)。【知识模块】 数据结构36 【正确答案】 本题主要考查直接插入法的算法思想及性能分析。根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。(1)在关键字自小到大有序的情况下，插入第 i 个(2in) 元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n 一 1.(2)在关键字自大到小有序的情况下，插入第 i 个(2in) 元素的比较次数为 i，因此，总的比较
38、次数为 2+3+4+n=n(n+1)2一 1=(n 一 1)(n+2)2。(3)在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为 n1。(4)在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字时比较次数最少，此时前半部分的比较次数为 m1，后半部分的比较次数为(nm1)(n 一 m+2)2，因此，总的比较次数为 m1+(n 一 m1)(nm+2)2=(n 一 2)(n+8)8(假设 n 为偶数，m=n 2) 。【知识模块】 数据结构37 【正确答案】 (1)在最好情况下，
39、假设每次划分能得到两个长度相等的子文件，文件的长度 n=2k 一 1，那么第一遍划分得到两个长度均为n2的子文件，第二遍划分得到 4 个长度均为n4的子文件，以此类推，总共进行 k=log2(n+1)遍划分，各子文件的长度均为 1，排序完毕。当 n=7 时，k=3，在最好情况下，第一遍需比较 6 次，第二遍分别对两个子文件(长度均为 3，k=2)进行排序，各需 2 次，共 10次即可。 (2)在最好情况下快速排序的原始序列实例：4，1，3，2，6，5，7。 (3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右) 子文件，其长度比原长度少 1。因此，若原文
40、件中的记录按关键字递减次序排列，而要求排序后按递增次序排列时，快速排序的效率与冒泡排序相同，其时间复杂度为 O(n2)。所以当 n=7 时，最坏情况下的比较次数为 21 次。 (4)在最坏情况下快速排序的初始序列实例：7，6，5，4，3，2，1，要求按递增排序。 提示：此题考查的知识点是快速排序的思想。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。【知识模块】 数据结构38 【正确答案】 (1)堆的存储是顺序的。 (2) 最大值
41、元素一定是叶子结点，在最下两层上。 (3)在建含有 n 个元素、深度为 h 的堆时，其比较次数不超过 4n，推导如下： 由于第 i 层上的结点数至多是 2i-1，以它为根的二叉树的深度为 h 一 i+1，则调用n 2 次筛选算法时总共进行的关键字比较次数不超过下式之值：提示：此题考查的知识点是堆的基本定义及效率。堆定义为 n 个关键字序列K1，K 2，K n，当且仅当该序列满足如下性质(简称为堆性质)： (1)k iK2i 且kik2i+1 或 (2)k iK2i 且 kik2i+1(1in)。k i 相当于二叉树的非叶结点，k 2i 则是左孩子，k2i+1 是右孩子。【知识模块】 数据结构3
42、9 【正确答案】 K 1 一 Kn 是堆，在 Kn+1 加入后，将 K1Kn+1 调成堆。设c=n+1，f=c2，若 kfKc，则调整完成。否则 Kf 与 Kc 交换之后，c=f，f=c2，继续比较，直到 kfkc，或 f=0，即为根结点，调整结束。【知识模块】 数据结构40 【正确答案】 void BubbleSort2(int a，int n) 相邻两趟向相反方向起泡的冒泡排序算法int change=1：low=0；high=n 一 1； 冒泡的上下界while(lowai+1)aiai+1；change=1； 有交换，修改标志 changehigh-： 修改上界for(i=high；
43、ilow；i 一一) 从下向上起泡if(ai=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=i4； 调小堆 Ri=R0； else 插入元素大于双亲，调大堆 i=n ;j=i 4 ； while(j0&RjRikey) 插入元素大于双亲，先与双亲交换，然后调大堆 Rj=Ri ； j=i4； while(j0&Rj0&RjRi) Ri=Rj；i=j；j=i 4； Ri=R0 ； 【知识模块】 数据结构46
44、【正确答案】 typedef structint key；int next；SLRecType；SLRecType RN+1；typedef structint f，e；SLQueue；SLQueue B10；int Radixsort(SLRecType R，int n) 设各关键字已输入到 R 数组中for(i=1；i0) 栈非空，则取出一个子文件进行划分low=stacktoplow：high=stacktophigh；top 一一；出栈i=low；j=high；temp=Ri；d0while(itempkey)j- ；if(ij)Ri=Rj；i+；while(ij&Rikeytempkey)i+ ；if(ij)Rj=Ri；j- ；while(i=j)； 划分结束Ri=temp； 基元元素插入if(i+1high) 右子文件有两个以上记录，则首、尾位置入栈top+；stacktoplow=i+1；stacktophigh=high；if(lowi 一 1) 左子文件有两个以上记录，则首、尾位置入栈top+：stacktop10w=low；stacktophigh=i 一 1；
