1、计算机学科专业基础综合数据结构-排序(一)及答案解析(总分：44.00，做题时间：90 分钟)一、B单项选择题/B(总题数：19，分数：32.00)1.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li中的排序码按升序排列，则_是初始步长为 4的希尔排序一趟扫描的结果。 A.an，bai，deng，fang，li，shi，tang，wan B.an，tang，deng，wan，shi，bai，fang，li C.li，deng，an，shi，bai，fang，tan
2、g，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D.2.以下关于希尔排序的说法中，正确的是_。 A.当待排序元素序列的初始排列基本有序时，希尔排序比直接插入排序快 B.当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快 C.当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快 D.当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢（分数：2.00）A.B.C.D.3.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，
3、wan，shi，bai，fang，li)中的排序码按升序排列，则_是以第一个元素为分界元素的快速排序一趟扫描的结果。 A.deng，an，tang，shi，bai，fang，li，wan B.deng，tang，an，wan，bai，shi，fang，li C.li，deng，an，shi，bai，fang，tang，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D.4.对下列 4个序列做快速排序，各以序列第一个元素为轴点进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为_。 A.10，30，50，70，90 B.50，7
4、0，90，10，30 C.50，30，10，70，90 D.90，70，50，30，10（分数：2.00）A.B.C.D.5.在快速排序中，要使最坏情况下的空间复杂度为 O(log2n)，要对快速排序做_修改。 A.先排小子区间 B.先排大子区间 C.划分轴点为三者取中 D.采用链表排序（分数：2.00）A.B.C.D.6.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li)中的排序码按升序排列，则_是大根堆排序初始建堆的结果。 A.deng，tang，an，wan
5、，bai，shi，fang，li B.wan，tang，fang，li，shi，bai，an，deng C.an，bai，deng，fang，li，shi，tang，wan D.an，tang，deng，wan，shi，bai，fang，li（分数：2.00）A.B.C.D.7.向具有 n个结点的堆中插入一个新元素的时间复杂度为_。 A.O(1) B.O(n) C.O(log2n) D.O(nlog2n)（分数：2.00）A.B.C.D.8.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，sh
6、i，bai，fang，li中的排序码按升序排列，则_是二路归并排序一趟扫描的结果。 A.wan，deng，tang，an，bai，fang，li，shi B.an，deng，bai，li，shi，tang，fang，wan C.deng，an，tang，shi，bai，fang，li，wan D.deng，tang，an，wan，bai，shi，fang，li（分数：2.00）A.B.C.D.9.对由 n个元素所组成的序列按排序码排序时，二路归并排序算法的排序码平均比较次数为_，所需要的辅助存储是 O(n)。 A.O(1) B.O(nlog2n) C.O(n) D.O(n2)（分数：1.00）
7、A.B.C.D.10.按排序策略分类，起泡排序属于_。对 n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需进行 n-1次元素值的比较，0 次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行 n(n-1)/2次元素值的比较，n(n-1)/2 次元素的交换。 A.插入排序 B.选择排序 C.交换排序 D.分配排序（分数：1.50）A.B.C.D.11.若对 27个元素只进行 3趟多路归并排序，则选取的归并路数为_。 A.2 B.3 C.4 D.5（分数：1.50）A.B.C.D.12.如果将所有中国人按照生日(不考虑年份，只考虑月、日
8、)来排序，那么使用下列排序算法中的_算法最快。 A.归并排序 B.希尔排序 C.快速排序 D.基数排序（分数：1.50）A.B.C.D.13.在下列指定的排序算法中，_使用的附加空间与输入序列的长度及初始排列无关。 A.锦标赛排序 B.快速排序 C.基数排序 D.归并排序（分数：1.50）A.B.C.D.14.下列排序算法中，_算法是不稳定的。 A.起泡排序 B.直接插入排序 C.基数排序 D.快速排序（分数：1.50）A.B.C.D.15.如果输入序列是已经排好顺序的，则下列算法中_算法最快结束，快速排序算法最慢结束。 A.归并排序 B.直接插入排序 C.简单选择排序 D.快速排序（分数：1
9、.50）A.B.C.D.16.当所有 n个待排序记录的排序码都相等时，直接插入排序、堆排序、起泡排序、简单选择排序的排序码比较次数和元素移动次数分别为()、O(n)和 O(n)、n-1 和 0、n(n-1)/2 和 0。 A.n-1和 0 B.n(n-1)/2和 n C.n(n-1)/2和 0 D.O(n)和 O(n)（分数：1.50）A.B.C.D.17.以下有关排序的说法中，正确的是_。 A.使用链表可以实现简单选择排序，但很难实现堆排序 B.当待排序元素序列的初始排列完全有序时，快速排序的排序速度显著提高 C.简单选择排序是一个稳定的排序方法 D.在最坏情况下，快速排序的时间性能也好于堆
10、排序的时间性能（分数：1.50）A.B.C.D.18.以下不属于内排序方法的是_。 A.起泡排序 B.拓扑排序 C.基数排序 D.快速排序（分数：1.50）A.B.C.D.19.将两个各有 m个元素的有序序列归并成一个有序序列，排序码比较次数最少为_。 A.m-1 B.m C.2m-1 D.2m（分数：1.50）A.B.C.D.二、B综合应用题/B(总题数：1，分数：12.00)设有 11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为 25，40，16，38，77，64，53，88，9，48，98。试对它们做四路平衡归并，要求：（分数：12.00）(1).指出总的归并趟
11、数。（分数：4.00）_(2).构造最佳归并树。（分数：4.00）_(3).根据最佳归并树计算每一趟及总的读记录数。（分数：4.00）_计算机学科专业基础综合数据结构-排序(一)答案解析(总分：44.00，做题时间：90 分钟)一、B单项选择题/B(总题数：19，分数：32.00)1.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li中的排序码按升序排列，则_是初始步长为 4的希尔排序一趟扫描的结果。 A.an，bai，deng，fang，li，shi，tang，w
12、an B.an，tang，deng，wan，shi，bai，fang，li C.li，deng，an，shi，bai，fang，tang，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C.D. 解析：解析 希尔排序是按增量将关键字分组。首先取增量 d1n 把全部关键字分成 d1个组，所有距离为 d1的元素放在一组中，各组内用直接插入排序法排序；然后取 d2d 1，重复上述分组和排序工作，直至取 dt=1。选项 D是取 d1=4的一趟排序的结果。2.以下关于希尔排序的说法中，正确的是_。 A.当待排序元素序列的初始排列基本有序时，希尔排序比
13、直接插入排序快 B.当待排序元素序列的初始排列基本逆序时，希尔排序比直接插入排序快 C.当待排序元素序列的初始排列基本有序时，希尔排序比起泡排序快 D.当待排序元素序列的初始排列基本逆序时，希尔排序比起泡排序慢（分数：2.00）A.B. C.D.解析：解析 当待排序元素序列的初始排列基本有序时，希尔排序的排序码比较次数为 n*(log2n-1)+1，元素移动次数为 0。直接插入排序的排序码比较次数为 n-1，元素移动次数为 0，起泡排序的排序码比较次数为 n-1，元素移动次数为 0。因此希尔排序不比直接插入排序和起泡排序快，选项 A和选项 C不正确。当待排序元素序列的初始排列基本逆序时，希尔排
14、序的排序码比较次数和元素移动次数为 1.5n；直接插入排序的排序码比较次数为 n(n-1)/2，元素移动次数为(n+4)(n-1)/2；起泡排序的排序码比较次数为n(n-1)/2，元素移动次数为 3n(n-1)/2；这种场合，希尔排序比直接插入排序和起泡排序都要快，所以选项 B正确，选项 D不正确。3.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li)中的排序码按升序排列，则_是以第一个元素为分界元素的快速排序一趟扫描的结果。 A.deng，an，tang，shi
15、，bai，fang，li，wan B.deng，tang，an，wan，bai，shi，fang，li C.li，deng，an，shi，bai，fang，tang，wan D.shi，bai，an，li，tang，deng，fang，wan（分数：2.00）A.B.C. D.解析：解析 快速排序是一种分组的递归排序方法。它首先以第一个元素为轴点，对整个序列做一趟划分，将序列中所有元素分成两部分，排序码值比它小的在前半部分，排序码值比它大的在后半部分。再分别对这两个部分实施上述过程，一直重复到排序完成。选项 C是采用两个检测指针交替扫描的一趟划分方法排序的结果。4.对下列 4个序列做快速排序，
16、各以序列第一个元素为轴点进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为_。 A.10，30，50，70，90 B.50，70，90，10，30 C.50，30，10，70，90 D.90，70，50，30，10（分数：2.00）A.B. C.D.解析：解析 采用快速排序，以一个元素为“枢轴”，通过一趟快速排序，将序列分成两部分，枢轴的一边全是比它小的，另一边全是比它大的。可以知道，选项 A不交换，选项 B交换 4次，选项 C和选项 D交换 1次。5.在快速排序中，要使最坏情况下的空间复杂度为 O(log2n)，要对快速排序做_修改。 A.先排小子区间 B.先排大子区间 C.划分
17、轴点为三者取中 D.采用链表排序（分数：2.00）A.B.C. D.解析：解析 划分轴点改为三者取中，使得每次划分出来的两个子区间长度接近相等，递归树的深度可达 O(log2n)，可以降低递归工作栈深度。6.在内排序的过程中，通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li)中的排序码按升序排列，则_是大根堆排序初始建堆的结果。 A.deng，tang，an，wan，bai，shi，fang，li B.wan，tang，fang，li，shi，bai，an，deng C.an，ba
18、i，deng，fang，li，shi，tang，wan D.an，tang，deng，wan，shi，bai，fang，li（分数：2.00）A.B. C.D.解析：解析 堆排序初始建堆后根结点是其中排序码值最大的结点，选项 B是大根堆。7.向具有 n个结点的堆中插入一个新元素的时间复杂度为_。 A.O(1) B.O(n) C.O(log2n) D.O(nlog2n)（分数：2.00）A.B.C. D.解析：解析 在向有 n个元素的堆中插入一个新元素时，需要调用一个向上调整的算法，比较次数最多等于树的高度减 1，由于树的高度为*，所以堆的向上调整算法的比较次数最多等于*。8.在内排序的过程中，
19、通常需要对待排序元素序列的排序码做多趟扫描。采用不同的排序方法将产生不同的排序中间结果，设要将集合tang，deng，an，wan，shi，bai，fang，li中的排序码按升序排列，则_是二路归并排序一趟扫描的结果。 A.wan，deng，tang，an，bai，fang，li，shi B.an，deng，bai，li，shi，tang，fang，wan C.deng，an，tang，shi，bai，fang，li，wan D.deng，tang，an，wan，bai，shi，fang，li（分数：2.00）A.B.C.D. 解析：解析 二路归并排序是将两个已有序的序列合并成为一个有序序列。
20、选项 D是二路归并排序非递归算法第一趟排序的结果。9.对由 n个元素所组成的序列按排序码排序时，二路归并排序算法的排序码平均比较次数为_，所需要的辅助存储是 O(n)。 A.O(1) B.O(nlog2n) C.O(n) D.O(n2)（分数：1.00）A.B. C.D.解析：解析 二路归并排序是将初始序列看成 n个有序的子序列，每个子序列的长度为 1，然后两两合并，得到n/2个长度为 2的有序子序列，最后一个长度为 0或 1；再两两合并，如此重复，直至得到一个长度为 n的有序序列为止。其时间复杂度为 O(nlog2n)。二路归并排序需要有和待排序记录等数量的存储空间，因而为 O(n)。10.
21、按排序策略分类，起泡排序属于_。对 n个元素的序列进行排序时，如果待排序元素序列的初始排列已经全部有序，则起泡排序过程中需进行 n-1次元素值的比较，0 次元素值的交换。如果待排序元素序列的初始排列完全逆序，则起泡排序过程中需进行 n(n-1)/2次元素值的比较，n(n-1)/2 次元素的交换。 A.插入排序 B.选择排序 C.交换排序 D.分配排序（分数：1.50）A.B.C. D.解析：解析 起泡排序属于交换类排序，在排序过程中元素按排序码值两两比较，发现逆序则交换。这一类排序方法还有快速排序。当待排序元素的初始排列已经有序时，起泡排序的排序码比较次数为 n-1，元素交换次数为 0。当待排
22、序元素的初始排列完全逆序时，起泡排序的排序码比较次数为(n-1)+(n-2)+1+0=n(n-1)/2。在排序过程中，每次比较发现逆序即交换，所以在最坏情况下，比较 n(n-1)/2次需交换 n(n-1)/2次。11.若对 27个元素只进行 3趟多路归并排序，则选取的归并路数为_。 A.2 B.3 C.4 D.5（分数：1.50）A.B. C.D.解析：解析 设需要的路数为 m，则对于 11个元素做 m路归并排序所需趟数*。当 n=27，s=3 时，则*，m=27 1/3=3。12.如果将所有中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中的_算法最快。 A.归并排序
23、B.希尔排序 C.快速排序 D.基数排序（分数：1.50）A.B.C.D. 解析：解析 按照所有中国人的生日(月、日)排序，一方面是 n很大；另一方面 d不大(d=2，两个排序码)且一个排序码的基数为 12(月)，另一排序码的基数为 31(日)，都不大，可采用多排序码排序，即基数排序。其时间复杂度可达 O(n)。13.在下列指定的排序算法中，_使用的附加空间与输入序列的长度及初始排列无关。 A.锦标赛排序 B.快速排序 C.基数排序 D.归并排序（分数：1.50）A.B.C. D.解析：解析 基数排序是一种分配排序，或称为桶排序。它根据排序码每一位的取值范围(基数)，设置若干个桶，通过“分配”
24、和“收集”完成排序。它的附加存储与基数有关。如果不考虑可能需要的链接指针，它需要的附加存储与待排序的元素个数和初始排列无关。当待排序元素个数为 n时，锦标赛排序需要n-1个附加结点以构成胜者树；快速排序平均需要 log2n个递归工作栈结点空间；归并排序需要 n个元素空间。14.下列排序算法中，_算法是不稳定的。 A.起泡排序 B.直接插入排序 C.基数排序 D.快速排序（分数：1.50）A.B.C.D. 解析：解析 不稳定的排序算法有希尔排序、简单选择排序、快速排序和堆排序。15.如果输入序列是已经排好顺序的，则下列算法中_算法最快结束，快速排序算法最慢结束。 A.归并排序 B.直接插入排序
25、C.简单选择排序 D.快速排序（分数：1.50）A.B. C.D.解析：解析 当待排序元素的初始排序已经有序的情形下，直接插入排序只需 n-1次排序码比较和 0次数据移动，排序速度变得最快；而快速排序则变成慢速排序，它的排序码比较次数与简单选择排序一样，达到 n(n-1)/2，但因为是递归算法，还要利用一个栈，时间和空间开销较大。16.当所有 n个待排序记录的排序码都相等时，直接插入排序、堆排序、起泡排序、简单选择排序的排序码比较次数和元素移动次数分别为()、O(n)和 O(n)、n-1 和 0、n(n-1)/2 和 0。 A.n-1和 0 B.n(n-1)/2和 n C.n(n-1)/2和
26、0 D.O(n)和 O(n)（分数：1.50）A. B.C.D.解析：解析 所有待排序的数据记录的排序码都相等，可按照数据初始排列已经有序的情况来分析。按照本教材所给算法： 直接插入排序的排序码比较次数和元素移动次数受数据的初始排列影响，每趟只比较 1次，做 n-1趟，排序码比较次数总共为 n-l，元素移动次数为 0。 起泡排序的排序码比较次数和元素移动次数也受数据的初始排列影响，只比较一趟，排序码比较次数为 n-1，元素移动次数为 0。 简单选择排序的排序码比较次数不受数据的初始排列影响，比较 n-1趟，排序码比较次数为 n(n-1)/2；但元素移动次数受数据的初始排列影响，当待排序记录排序
27、码都相等时，元素移动次数为 0。 对于堆排序，在形成初始堆时，总共有*次排序码比较，*次数据移动；在堆排序时，做 n-1次对调和重新形成堆，每次对调做 3次数据移动，最多做(n-1)2 次排序码比较，(n-1)(3+2)次数据移动。综上所述，堆排序的排序码比较次数最多为*，元素移动次数最多是*。17.以下有关排序的说法中，正确的是_。 A.使用链表可以实现简单选择排序，但很难实现堆排序 B.当待排序元素序列的初始排列完全有序时，快速排序的排序速度显著提高 C.简单选择排序是一个稳定的排序方法 D.在最坏情况下，快速排序的时间性能也好于堆排序的时间性能（分数：1.50）A. B.C.D.解析：解
28、析 能够使用链表实现排序功能的大多是可以顺序比较的排序算法，如直接插入排序、简单选择排序、起泡排序、归并排序。堆排序以一定的间隔进行比较和交换，用链表不方便。18.以下不属于内排序方法的是_。 A.起泡排序 B.拓扑排序 C.基数排序 D.快速排序（分数：1.50）A.B. C.D.解析：解析 拓扑排序是把一个偏序无环有向图变成全序图，从而得到所有顶点的拓扑有序序列的方法。它不是依据每个顶点的数据值，而是依据各顶点之间的优先关系把图中顶点排入一个线性序列的方法，不属于内排序。因此，B 选项正确。 其他选项都不对。当元素的初始排列已经有序时快速排序就变成了慢速排序。本节关键问题点拨中有反例证实，
29、简单选择排序是不稳定的排序算法。19.将两个各有 m个元素的有序序列归并成一个有序序列，排序码比较次数最少为_。 A.m-1 B.m C.2m-1 D.2m（分数：1.50）A.B. C.D.解析：解析 当前一个有序序列的所有元素的排序码值都小于后一个有序序列时，只需要比较 m次即可。二、B综合应用题/B(总题数：1，分数：12.00)设有 11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为 25，40，16，38，77，64，53，88，9，48，98。试对它们做四路平衡归并，要求：（分数：12.00）(1).指出总的归并趟数。（分数：4.00）_正确答案：(四路平衡
30、归并总的归并趟数为*。)解析：(2).构造最佳归并树。（分数：4.00）_正确答案：(构造的最佳归并树如下图所示。*)解析：(3).根据最佳归并树计算每一趟及总的读记录数。（分数：4.00）_正确答案：(第一趟的读记录数：9+16=25； 第二趟的读记录数：25+25+38+40+48+53+64+77=370； 第三趟的读记录数：128+88+242+98=556； 总的读记录数：25+370+556=9510。)解析：说明 最佳归并树在建立时，首先判断是否增加虚段，然后再建立。关于虚段的增加规律：对 k路归并而言，若有 m个初始归并段，满足(m-1)MOD(k-1)=0，则不需要加虚段，否则在第一次归并时需要附加 k-(m-1)MOD(k-1)-1个虚段。
