Relax1000 数据结构 · 第8章 排序 · 题目¶
第8章 排序¶
本章 78 题；题目册印刷页 51–60。
Q1¶
对 n 个不同的元素进行直接插入排序，比较次数最多为（ ）次。
- A．n
- B．n-1
- C．n(n+1)/2
- D．n(n- 1)/2
Q2¶
下列关于插入排序的说法正确的是（ ）。
- A．直接插入排序的平均时间复杂度是〔公式/符号见原页版面片段〕2
- B．折半插入排序的平均时间复杂度是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- C．希尔排序是稳定的排序算法
- D．初始序列不同，折半插入排序的总比较次数一定是相同的
原页版面片段（用于核对图表、公式、矩阵或代码）
Q3¶
序列{20,26,40,8,6,66}只能是（ ）两趟排序后的结果。
- A．简单选择排序
- B．冒泡排序
- C．直接插入排序
- D．堆排序
原页版面片段（用于核对图表、公式、矩阵或代码）
Q4¶
用直接插入排序算法对下列 4 个表进行（从小到大）排序，比较次数最少的是（ ）。
- A．94,32,40,90,80,46,21,69
- B．21,32,46,40,80,69,90,94
- C．32,40,21,46,69,94,90,80
- D．90,69,80,46,21,32,94,40
Q5¶
设一组初始记录关键字序列为（50，40，95，20，15，70，60，45），则以增量 d=4 的一趟希尔排序结束后前 4 条记录关键字为（ ）。
- A．40，50，20，95
- B．15，40，60，20
- C．15，20，40，45
- D．45，40，15，20
原页版面片段（用于核对图表、公式、矩阵或代码）
Q6¶
对序列{15,9,7,8,20,-1,4}采用希尔排序，经一趟后序列变为{15,-1,4,8,20,9,7}，则该次采用的增量是（ ）。
- A．1
- B．4
- C．3
- D．2
原页版面片段（用于核对图表、公式、矩阵或代码）
Q7¶
下列能说明希尔排序（增量 d 每轮取值依次为 3、1）是不稳定的算法的初始数据序列是（ ）。
- A．[49, 38, 65, 49, 76, 13]
- B．[49, 38, 49, 65, 13, 76]
- C．[49, 49, 13, 65, 76, 38]
- D．[49, 13, 65, 38, 76, 49]
原页版面片段（用于核对图表、公式、矩阵或代码）
Q8¶
对 n 个不同的元素利用冒泡法从小到大排序，在（ ）情况下元素交换的次数最多。
- A．从大到小排列好的
- B．从小到大排列好的
- C．元素无序
- D．元素基本有序
Q9¶
用冒泡排序方法对序列（12，24，36，48，60，72）从大到小排序，需要的比较次数是（ ）。
- A．5
- B．10
- C．15
- D．25
原页版面片段（用于核对图表、公式、矩阵或代码）
Q10¶
对数据序列 {4，9，10，8，5，6，20，1，2} 进行升序冒泡排序，则下列说法正确的是（ ）。
- A．至少需要 6 趟
- B．元素的移动次数是 21 次
- C．从后往前进行冒泡排序，第三趟的结果是 {1，2，4，9，10，8，5，6，20}
- D．无论从前往后还是从后往前进行冒泡排序，元素的移动次数都是 22 次
原页版面片段（用于核对图表、公式、矩阵或代码）
Q11¶
双向起泡排序过程可以理解为双向进行的冒泡排序，其排序过程描述如下：每一趟按照冒泡排序的方法，找到序列最大值最小值，并将其放在序列最右端/最左端。第一趟从左往右，将最大值放在序列最右端；第二趟从右往左，将最小值放在序列最左端。下一趟缩小范围重复此过程。直到可以判断序列有序为止。对数组[4,7,8,3,5,6,10,9,1,2]进行双向起泡排序，排序趟数为（ ）。
- A．7
- B．6
- C．8
- D．9
原页版面片段（用于核对图表、公式、矩阵或代码）
Q12¶
下列关于快速排序的说法中，正确的是（ ）。
I．快速排序算法的最坏时间复杂度为 〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
II．快速排序的空间复杂度平均为 O(1)
III．快速排序算法的性能关键在于每次划分操作均分的程度
IV．快速排序是一个不稳定的排序算法V．快速排序每趟排序都将大数据区间分为左右小数据区间（如果有的话），小区间之间相对有序
- A．I, II, V
- B．III, IV, V
- C．II、III、IV
- D．I、IV、V
原页版面片段（用于核对图表、公式、矩阵或代码）
Q13¶
以区间第一个元素为枢轴元素，能说明快速排序（升序）不稳定的一组关键字序列是（ ）。
- A．(10，20，30，40，50)
- B．(50，40，30，20，10)
- C．(20，20，30，10，40)
- D．(20，40，30，30，10)
原页版面片段（用于核对图表、公式、矩阵或代码）
Q14¶
使 用 快 速 排 序 算 法 对 数 据 进 行 升 序 排 序 ， 若 经 过 一 次 划 分 后 得 到 的 数 据 序 列 是{68,11,70,23,80,77,48,81,93,88}，则该次划分的枢轴是（ ）。
- A．11
- B．70
- C．80
- D．81
Q15¶
对下列关键字序列利用快速排序进行排序时，速度最快（比较次数最少）的情形是（ ）。
- A．21,25,5,17,9,23,30
- B．25,23,30,17,21,5,9
- C．21,9,17,30,25,23,5
- D．5,9,17,21,23,25,30
原页版面片段（用于核对图表、公式、矩阵或代码）
Q16¶
对下列关键字序列利用快速排序进行从小到大排序时，递归深度最小的序列是（ ）。
- A．[4, 2, 6, 1, 5, 3, 8, 7]
- B．[5, 2, 6, 1, 4, 3, 8, 7]
- C．[7, 1, 2, 3, 4, 5, 6, 8]
- D．[1, 2, 3, 4, 5, 6, 7, 8]
原页版面片段（用于核对图表、公式、矩阵或代码）
Q17¶
对下列 4 个序列，以第一个关键字为基准用快速排序算法进行排序，在第一趟过程中移动元素次数最多的是（ ）。
- A．92,96,88,42,30,35,110,100
- B．92,96,100,110,42,35,30,88
- C．100,96,92,35,30,110,88,42
- D．42,30,35,92,100,96,88,110
原页版面片段（用于核对图表、公式、矩阵或代码）
Q18¶
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟。下列序列中，不可能是快速排序第二趟结果的是（ ）。
- A．5,2,16,12,28,60,32,72
- B．2,16,5,28,12,60,32,72
- C．2,12,16,5,28,32,72,60
- D．5,2,12,28,16,32,72,60
原页版面片段（用于核对图表、公式、矩阵或代码）
Q19¶
下列关于简单选择排序的说法，正确的是（ ）。
- A．移动的时间复杂度是〔公式/符号见原页版面片段〕2
- B．每趟会确定一个元素的最终位置
- C．比较次数最少是〔公式/符号见原页版面片段〕
- D．是稳定排序算法
原页版面片段（用于核对图表、公式、矩阵或代码）
Q20¶
下列初始数据序列中，不能说明简单选择排序不稳定的是（ ）。
- A．[4, 3, 5, 7, 6, 5, 2]
- B．[2, 5, 4, 6, 5, 3, 7]
- C．[1, 6, 3, 6, 2, 6, 7]
- D．[2, 1, 3, 4, 5, 5, 7]
原页版面片段（用于核对图表、公式、矩阵或代码）
Q21¶
有一组数据{12，15，1，18，2，35，30，11}，用简单选择排序由小到大排序，第 2 趟交换数据后数据的顺序是（ ）。
- A．11，1，2，12，35，18，30，15
- B．1，2，12，18，15，35，30，11
- C．1，2，11，12，15，18，30，35
- D．1，2，11，12，15，18，35，30
Q22¶
下列关键字序列为堆的是（ ）。
- A．100，60，70，50，32，65
- B．60，70，65，50，32，100
- C．65，100，70，32，50，60
- D．70，65，100，32，50，60
原页版面片段（用于核对图表、公式、矩阵或代码）
Q23¶
现有关键字序列{5,2,34,16,20,19,1}，要求对其进行降序排列，下列哪个选项是第二次调整堆之后的结果（ ） 。
- A．2,16,5,34,20,19,1
- B．19,16,5,34,20,2,1
- C．5,16,19,34,20,2,1
- D．16,19,5,34,20,2,1
原页版面片段（用于核对图表、公式、矩阵或代码）
Q24¶
使用堆排序方法排序(45，78，57，25，41，89)，初始堆为（ ）。
- A．78，45，57，25，41，89
- B．89，78，57，25，41，45
- C．89，78，25，45，41，57
- D．89，45，78，41，57，25
Q25¶
将关键字 7,5,1,4,6,8,9 依次插入初始为空的小根堆 H，得到的 H是（ ）。
- A．1,4,5,7,6,8,9
- B．1,4,7,5,6,8,9
- C．1,4,5,6,7,8,9
- D．1,5,4,6,8,9,7
Q26¶
对关键字序列{23, 17, 72, 60, 25, 8, 68, 71, 52}进行堆排序，输出两个最小关键字后的剩余堆是（ ） 。
- A．{23, 72, 60, 25, 68, 71, 52}
- B．{23, 25, 52, 60, 71, 72, 68}
- C．{71, 25, 23, 52, 60, 72, 68}
- D．{23, 25, 68, 52, 60, 72, 71}
原页版面片段（用于核对图表、公式、矩阵或代码）
Q27¶
堆排序分为两个阶段，其中第一阶段将给定的序列建成一个堆，第二阶段逐次输出堆顶元素。设给定序列{48, 62, 35, 77, 55, 14, 35, 98}，若在堆排序的第一阶段将该序列建成一个堆（大根堆），那么交换元素的次数为（ ） 。
- A．5
- B．6
- C．7
- D．8
原页版面片段（用于核对图表、公式、矩阵或代码）
Q28¶
对数据序列{32,40,21,46,69,94,90,80}构建成一个大根堆后，插入元素 66，则调整后，元素 66在第（ ）层（根节点为第一层）。
- A．1
- B．2
- C．3
- D．4
原页版面片段（用于核对图表、公式、矩阵或代码）
Q29¶
对数据序列{32,40,21,46,69,94,90,80}构建成一个小根堆后，删除元素 21，则调整后，堆顶元素的左右孩子为（ ）。
- A．40，32
- B．80，40
- C．40，80
- D．40，46
原页版面片段（用于核对图表、公式、矩阵或代码）
Q30¶
下列关于堆排序的说法，错误的是（ ）。
- A．可以将堆视为一棵完全二叉树
- B．可以将堆视为一棵二叉排序树
- C．若要升序排序，最好使用大根堆
- D．堆中根节点到任意一个叶子结点的序列都是有序的
原页版面片段（用于核对图表、公式、矩阵或代码）
Q31¶
数据表 A有 10000个元素，如果仅要求找出其中最大的 10个元素，则采用（ ）最节省时间。
- A．堆排序
- B．希尔排序
- C．快速排序
- D．基数排序
Q32¶
若只进行 3 趟排序就完成对 64 个元素的多路归并排序，则选取的归并路数最少是（ ）。
- A．2
- B．3
- C．4
- D．5
Q33¶
一组记录的关键字为{25，48，16，35，79，82，23，40，36，72}，其中分为 5 个长度为 2 的有序表，按归并排序的方法对该序列再进行一趟归并后的结果为（ ）
- 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，82
原页版面片段（用于核对图表、公式、矩阵或代码）
Q34¶
已知进行 2-路归并排序的待排序记录的关键字当前序列为{49, 38, 65, 97, 76, 13, 27}，下列说法错误的是（ ）
- A．该序列只可能是初始状态
- B．要进行 3 趟归并
- C．第一趟关键字比较的次数是 4 次
- D．第二趟归并后，13 的相邻元素是 97，27
原页版面片段（用于核对图表、公式、矩阵或代码）
Q35¶
对{05, 46, 13, 55, 94, 17, 42}进行基数排序，一趟排序的结果是（ ）。
- A．05, 46, 13, 55, 94, 17, 42
- B．05, 13, 17, 42, 46, 55, 94
- C．42, 13, 94, 05, 55, 46, 17
- D．05, 13, 46, 55, 17, 42, 94
Q36¶
对 n 个 r 进制的关键字，关键字最多有 m 位进行基数排序，时间复杂度为（ ）
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕 + 〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q37¶
有 n 个十进制整数进行基数排序，其中最大的整数为 5 位，则基数排序过程中临时建立的队列个数是（ ）。
- A．n
- B．2
- C．5
- D．10
Q38¶
在最后一趟排序开始之前，所有记录有可能都不在其最终位置上的是（ ）。
- A．直接插入排序
- B．冒泡排序
- C．堆排序
- D．快速排序
Q39¶
在快速排序、冒泡排序、堆排序、归并排序、插入排序这五种排序算法中，属于稳定排序的有几个（ ）。
- A．2
- B．3
- C．4
- D．5
Q40¶
下列说法错误的是（ ） 。
- A．在线性表的初始状态为反序的情况下，冒泡排序过程中元素的移动次数达到最大值
- B．在线性表的初始状态为反序的情况下，简单选择排序过程中元素的移动次数达到最大值
- C．在线性表的初始状态为反序的情况下，直接插入排序过程中元素的移动次数达到最大值
- D．对 n 个元素进行快速排序，在进行第一次划分时，关键字的比较次数总是 n-1 次
Q41¶
下列（ ）算法平均情况、最好情况和最坏情况下的时间复杂度都为〔公式/符号见原页版面片段〕2。
- A．直接选择排序
- B．直接插入排序
- C．冒泡排序
- D．归并排序
原页版面片段（用于核对图表、公式、矩阵或代码）
Q42¶
下列关于排序和查找，说法错误的有（ ）。
I．若借助二分查找确定每个元素的插入位置，序列的插入排序只需 O(nlogn)时间
II．对任意基于比较的排序算法，最坏情况下的时间复杂度不低于 O（nlogn）
III．相对有序的序列适合使用插入排序作为排序算法。
IV．对于同一有序序列，每次折半查找绝不会慢于顺序查找
- A．I、IV
- B．I、II、IV
- C．I、III、IV
- D．I、II、III、IV
原页版面片段（用于核对图表、公式、矩阵或代码）
Q43¶
下列排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是（ ）。
- A．直接插入排序
- B．冒泡排序
- C．快速排序
- D．堆排序
Q44¶
以下排序方式中平均空间复杂度是〔公式/符号见原页版面片段〕 的是（ ）。
- A．简单选择排序
- B．快速排序
- C．堆排序
- D．二路归并排序
原页版面片段（用于核对图表、公式、矩阵或代码）
Q45¶
以下（ ）算法的最坏时间复杂度可以达到〔公式/符号见原页版面片段〕 。
- A．归并排序
- B．快速排序
- C．冒泡排序
- D．插入排序
原页版面片段（用于核对图表、公式、矩阵或代码）
Q46¶
设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的元素在后；在 k1 值相同的情况下，再看 k2，k2 值小的元素在前，大的元素在后。满足这种要求的排序算法是（ ）。
- A．先按 k1 进行直接插入排序，再按 k2 进行简单选择排序
- B．先按 k2 进行直接插入排序，再按 k1 进行简单选择排序
- C．先按 k1 进行简单选择排序，再按 k2 进行直接插入排序
- D．先按 k2 进行简单选择排序，再按 k1 进行直接插入排序
Q47¶
选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是（ ）。
I．数据的规模
II．数据的存储方式
III．算法的稳定性
IV．数据的初始状态
- A．仅 III
- B．仅 I、Ⅱ
- C．仅 II、III、IV
- D．I、II、III、IV
Q48¶
下列排序方法中，时间性能与待排序记录的初始状态无关的是（ ）。
- A．插入排序和快速排序
- B．归并排序和快速排序
- C．选择排序和归并排序
- D．插入排序和归并排序
Q49¶
对各种内部排序方法来说（ ）。
- A．快速排序时间性能最佳
- B．基数排序和归并排序是稳定的排序方法
- C．快速排序是一种选择排序
- D．堆排序所用的辅助空间较大
Q50¶
一台计算机具有多核 CPU，可以同时执行相互独立的任务。归并排序的各个归并段可以并行执行，在下列排序算法中，不可以并行执行的有（ ）。
I．基数排序
II．冒泡排序
III．快速排序
IV．堆排序
- A．I、III
- B．I、II
- C．I、III、IV
- D．II、IV
Q51¶
对大部分元素已有序的数组进行排序时，选择冒泡排序而不选择简单选择排序，其原因是（ ）。
I．冒泡排序过程中元素之间的比较次数更少
II．冒泡排序过程中所需要的辅助空间更少
III．冒泡排序是稳定的
- A．I
- B．III
- C．I，II
- D．I，III
原页版面片段（用于核对图表、公式、矩阵或代码）
Q52¶
以下排序算法中，（ ）不需要进行关键字的比较。
- A．快速排序
- B．归并排序
- C．基数排序
- D．堆排序
Q53¶
在下列排序算法中，平均情况下空间复杂度为〔公式/符号见原页版面片段〕 的是（ ），最坏情况下空间复杂度为〔公式/符号见原页版面片段〕的是（ ）。
I．希尔排序
II．堆排序
III．冒泡排序
IV．归并排序 V．快速排序
VI．基数排序
- A．I、IV、VI
- B．II、V
- C．IV、V
- D．IV
原页版面片段（用于核对图表、公式、矩阵或代码）
Q54¶
以下关于外部排序的说法错误的是（ ）。
- A．影响外部排序的时间因素主要是内存与外存交换信息的总次数
- B．外部排序的两个基本操作过程是生成初始归并段和归并
- C．采用败者树进行 k 路平衡归并，其总的归并效率与 k 无关
- D．外部排序通过减少初始归并段个数和增加归并路数可以提高排序效率
Q55¶
在做 m 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置（①）个输入缓冲区和（②）个输出缓冲区。①
- A．2
- B．m
- C．2m-1
- D．2m ② A．2 B．m C．2m-1 D．2m
Q56¶
若外部存储上有 3110400 个记录，做 6 路平衡归并排序，计算机内存工作区能容纳 400 个记录，则排序好所有记录，需要作几趟归并排序（ ）。
- A．6
- B．3
- C．5
- D．4
Q57¶
假设文件有 2000 个记录，磁盘块每块可容纳 125 个记录，用于内部排序的内存工作区容量为250 个记录，采用二路平衡归并排序对文件进行排序。那么文件从初始无序的状态到最后有序的状态，总的 I/O 次数为（ ）。
- A．32
- B．96
- C．128
- D．64
Q58¶
m 个初始归并段采用 k 路平衡归并时，构建的败者树中共有（ ）个节点（不计冠军节点）。
- A．2m-1
- B．2m
- C．2k
- D．2k-1
Q59¶
在使用败者树进行外部排序时，败者树有以下（ ）特点。
- A．非叶子结点存储的是败者的标号
- B．叶子结点存储的是输入数据
- C．败者树只适用于内部排序
- D．败者树的根结点存储的是最小值
Q60¶
下列关于败者树的说法错误的有（ ）。
I．败者树的分支结点存储的内容是失败（较大）记录关键字的值
II．败者树每次维护，都必须从叶子结点一直比较到根节点（直到选出冠军节点）
III．使用败者树从 n 个归并段中选出最小值，空间上的开销是〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
IV．败者树为了防止某个归并段记录被选完影响其他缓冲区记录的进一步排序，可以在每个归并段的最后添加一个关键字为最大的记录，当冠军节点为“最大值”时，表示归并结束
- A．I、IV
- B．I、III
- C．II、IV
- D．II、III
原页版面片段（用于核对图表、公式、矩阵或代码）
Q61¶
现有五个归并段，每个归并段（0-4 编号）的所有记录关键字如下：{10，15，16}、{9，18，20}、{20，22，40}、{6，15，25}、{12，37，48}。若采用败者树实现 5 路归并，在进行第二轮比较后（得到第二个冠军节点），根节点的值为（ ）。
- A．1
- B．0
- C．9
- D．10
Q62¶
设由置换-选择排序法得到 9 个初始归并段，其长度（记录个数）依次为(9,30,12,18,3,17,2,6,24)。假设每条记录的大小是一个磁盘块，则由其构成的 3 路最佳归并树的 I/O 次数为（ ）。
- A．440
- B．442
- C．444
- D．446
Q63¶
对于输入数据流(15,19,04,83,12,27,11,25,16,34,26,07,10,90,06)，在使用置换-选择排序算法进行外部排序时，设工作区大小为 4，那么在置换-选择排序过程中，生成的初始归并段的数量是（ ）。
- A．2
- B．3
- C．4
- D．5
Q64¶
下面数据结构是选择置换排序内存工作区的存储结构定义：typedef struct { RedType rec; //记录KeyType key; //从记录中抽取的关键字int rnum; //所属归并段的段号RcdNode WorkArea[w];NorkArea wa; //内存工作区，容量为 w使用败者树来选出每一轮的 MINIMAX 记录。相比于普通的败者树，选择置换排序中的败者树在叶子节点，除了记录的关键字（索引）外，还引入了段号，规则为：①败者树的建立时，所有叶子节点初始关键字值为 0 段号为 0 ②依次从后往前将待排序序列记录的关键字输入到叶子结点，段号置为 1。至编号最小的叶子结点被填充完，第一个冠军节点（MINIMAX 记录的编号）被选出。③后续冠军节点所在叶子结点补充新的记录的关键字后，若小于上一轮的 MINIMAX，段号+1。否则仍为当前轮次的段号。比较的规则如下：a.先比较段号，段号小者直接获胜。b.段号相等，记录的关键字值小的获胜。根据上述规则，对{51，49，39，46，38，29，14，61，15，30，1，48}进行选择置换排序，工作区WA 的大小 w=6，得到第一个初始归并段后（即新的冠军结点内的编号所在叶子结点的段号是 2 的时候），败者树的根节点编号为（ ）。
- A．0
- B．1
- C．3
- D．4
原页版面片段（用于核对图表、公式、矩阵或代码）
Q65¶
使用置换-选择排序算法时，哪个选项描述了算法如何处理候选区和输入数据流的关系?（ ）。
- A．从候选区中选择最大记录，并在输入数据流中找到一个比其大的记录进行替换
- B．从候选区中选择最小记录，并在输入数据流中找到一个比其小的记录进行替换
- C．从输入数据流中选择最小记录，并与候选区中的最大记录进行交换
- D．将输入数据流中当前读取的记录插入到候选区中适当的位置，然后选择候选区中的最小记录输出
Q66¶
用败者树筛选 MINIMAX记录的选择置换排序算法中，若内存工作区 WA大小为 m个记录，共有 n 个记录，生成所有的初始归并段所需的时间复杂度为（ ）。
- A．〔公式/符号见原页版面片段〕
- B．〔公式/符号见原页版面片段〕
- C．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
- D．〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕
原页版面片段（用于核对图表、公式、矩阵或代码）
Q67¶
下列关于选择 - 置换排序的说法正确的是（ ）。
I. 创建初始段文件过程中，需要不断地在内存工作区中选择不小于旧的 MINMAX 的最小值，此过程需利用败者树实现
II. 利用败者树不断选择新的 MINMAX 记录时，为防止新加入的关键字值更小，每个叶结点都附加一个段号，当进行关键字比较时，先比较段号，段号大的为胜者；段号相同的关键字值小的为胜者
III. 置换选择排序算法得到的初始归并段的长度并不受内存容量的限制，且获得的归并段的平均长度为内存工作区大小的两倍
- A．I、III
- B．II、III
- C．I、II、III
- D．I、II
Q68¶
下列对于外部排序的说法正确的有（ ）个。
I. 外部归并排序需要有序的初始归并段，由内部排序算法在内存工作区进行内部排序得到
II. 置换-选择排序是通过减少初始归段数量来减少磁盘 I/O 次数的
III. 败者树在优化归并排序中，主要是减少选择各缓冲区首个元素中最小元素的比较次数
IV. 败者树在优化置换-选择排序中，主要是减少选出 MINIMAX 的比较次数V. 最佳归并树采用哈夫曼树的思想，在初始归并段长度不一致时，通过优化归并顺序，减少总归并代价，从而减少磁盘 I/O 次数
- A．2
- B．3
- C．4
- D．5
Q69¶
设外存上有 80个归并段，进行 8路平衡归并，为实现最佳归并，需要补充的虚段个数是（ ）。
- A．4
- B．5
- C．6
- D．不需要补充
Q70¶
在对大量数据进行外部排序时，以下策略不能有效降低磁盘 I/O 操作次数的是（ ）。
- A．选择置换排序
- B．败者树
- C．最佳归并树
- D．适当增大归并路数
Q71¶
对序列 49，38，65，97，76，13，27 进行折半插入排序，按升序排列。若用折半查找确定插入位置，且折半查找在确定 mid时，如果有偶数个结点，按照 mid左边关键字个数比右边关键字个数少1 的规则确定。统计关键字比较次数，则总比较次数为（ ）。
- A．11
- B．12
- C．13
- D．14
原页版面片段（用于核对图表、公式、矩阵或代码）
Q72¶
若希尔排序第一趟排序后的结果为 7，15，3，12，18，6，40，34，25。则该趟排序采用的增量（即间隔 d）可能是（ ）。
- A．2
- B．3
- C．4
- D．5
Q73¶
对序列 49，38，65，97，76，13，27 进行直接插入排序，按升序排列。若只统计元素后移次数，不统计临时变量赋值，则整个排序过程中元素后移次数是（ ）。
- A．10
- B．11
- C．12
- D．13
原页版面片段（用于核对图表、公式、矩阵或代码）
Q74¶
对序列 5，1，4，2，8，3 进行冒泡排序，按升序排列。整个排序过程中需要交换的次数为（ ）。
- A．6
- B．7
- C．8
- D．9
原页版面片段（用于核对图表、公式、矩阵或代码）
Q75¶
对如下序列进行最低位优先的基数排序：278，109，063，930，589，184，505。按十进制从低位到高位进行分配和收集。第二趟，即按十位排序后的结果为（ ）。
- A．930，063，184，505，278，109，589
- B．505，109，930，063，278，184，589
- C．063，109，184，278，505，589，930
- D．109，505，930，063，278，184，589
原页版面片段（用于核对图表、公式、矩阵或代码）
Q76¶
对序列 49，38，65，97，76，13，27 建立大根堆。建堆阶段关键字比较次数为（ ）。
- A．6
- B．7
- C．8
- D．9
原页版面片段（用于核对图表、公式、矩阵或代码）
Q77¶
下列排序算法中，较适合在链表结构上实现的是（ ）。
- A．希尔排序
- B．堆排序
- C．归并排序
- D．折半插入排序
Q78¶
在先进排序算法中（平均性能 〔公式/符号见原页版面片段〕(〔公式/符号见原页版面片段〕2〔公式/符号见原页版面片段〕)），当待排序的记录个数 n 很大且元素基本有序，且要求稳定性，那么应该选用的排序算法是（ ）。
- A．冒泡排序
- B．快速排序
- C．归并排序
- D．堆排序
原页版面片段（用于核对图表、公式、矩阵或代码）
