1、排序模拟试卷 3 及答案与解析一、单项选择题1 排序是将一批(组) 任意次序的记录重新排列成按( )有序的记录序列。（A）数据（B）记录（C）元素（D）关键字2 排序方法稳定是指若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(ij，i， j=1，2，n)，且在排序前 Ki 先于 K(jij)，排序后的记录序列( )。（A）K i 先于 Kj（B） Ki 后于 Kj（C）不能确定（D）在同一位置3 内部排序是指( ) 。（A）所有的记录都能存放在计算机内部进行排序（B）所有的记录都能存放在内存中进行排序（C）部分记录能存放在内存中进行排序（D）所有的记录都能存放在函数中进行排序4 外部
2、排序的说法中，不正确的是( )。（A）所有的记录不可能存放在内存中（B）所有的记录都存放在内存中（C）排序过程中必须在内、外存之间进行数据交换（D）排序的过程中，有一部分数据不在内存中5 内部排序的基本操作包括( )。（A）关键字位置的移动（B）记录大小的比较（C）关键字大小的比较和记录位置的移动（D）数据大小的比较和记录位置的移动6 在内部排序过程中，记录存储在一组连续地址的存储空间，下面( )说法是正确的。（A）记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现（B）记录的移动是必不可少的（C）记录的比较是必不可少的（D）以上说法全部正确7 在内部排序过程中，记录采用链式存储方式，排序
3、过程不需要( )。（A）移动元素位置（B）修改记录的指针（C）比较关键字的大小（D）以上都需要8 在内部排序过程中，记录存储在一组连续地址的存储空间，排序过程不需要( )。（A）移动元素位置（B）修改辅助表中的指针（C）比较关键字的大小（D）以上都需要9 关于直接插入排序的算法中，(1)处应该填入的内容是( )。（A）j=i+1（B） j=i-1（C） j=i（D）j=Q10 直接插入排序算法中的 RO开始时并不存放任何待排序的记录，主要作用是( )。（A）不需要增加辅助空间（B）保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起“ 哨兵监视”作用，避免在内循环中每
4、次都要判断 j 是否越界（C）保存当前待插入的记录 Ri（D）以上都是11 直接插入排序算法的空间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlogn)（D）O(1ogn)12 若待排序记录按关键字从小到大排列(正序)，直接插入排序的时间复杂度为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)13 若待排序记录按关键字从大到小排列(逆序)，直接插入排序的时间复杂度为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)14 直接插入排序的时间复杂度为( )。（A）O(n 2)（B） O(n)（C） O(nlo
5、gn)（D）O(1ogn)15 直接插入排序是一种( )的算法。（A）一直稳定（B）一直不稳定（C）随着情况变化（D）以上均不对16 折半查找的前提是( )。（A）将记录插入一个乱序的序列中（B）将记录插入一个基本有序的序列中（C）将记录插入一个已经排好序的序列中（D）将记录插入一个倒序排列好的序列中17 关于折半插入排序的算法中，(1)、(2) 处应该填人的内容是( )。（A）1ow=mid 一 1；high=mid+1（B） high=mid+1；low=mid 一 1（C） high=mid-1；low=mid+1（D）1ow=mid+1；high=mid 一 118 从时间上比较，折半
6、插入排序比直接插入排序减少了( )。（A）移动元素的次数（B）关键字的比较次数（C）关键字的交换次数（D）关键字的选择次数19 折半插入排序的时间复杂度是( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)20 折半插入排序是一种( )的算法。（A）一直稳定（B）一直不稳定（C）随着情况变化（D）以上均不对21 关于冒泡排序的算法，(1)处应该填人的内容是( )。（A）L 一Rk=L-Rk+1（B） L 一Rk+1=L 一Rk（C） L 一Rk=L 一 Rk 一 1（D）L-Rk 一 1=L 一Rk22 冒泡排序算法的空间复杂度为( )。（A）O(1) l（B
7、） O(n)（C） O(nlogn)（D）O(1ogn)23 当待排序列按关键字已经有序(正序)的情况下，冒泡排序算法的时间效率为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)24 当待排序列按关键字逆序的情况下，冒泡排序算法的时间效率为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)25 冒泡排序算法中，出现了相同的关键字 K1K n 顺序是 K1 在最前，K n 在最末尾，排序之后的顺序是( ) 。（A）K 1 在最尾，K 在最前（B） K1 在最前，K n 在最尾（C）二者在同一位置上（D）不能确定26 关于简
8、单选择排序的算法中，(1)处要填人的内容( )。（A）RiHRj（B） RiHRk（C） RiHRk+1（D）Ri+1Rk27 简单选择排序的空间复杂度是( )。（A）O(1)（B） O(n)（C） O(nlogn)（D）O(1ogn)28 简单选择排序的最好时间复杂度为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)29 简单选择排序的平均时间复杂度为( )。（A）O(n 2)（B） O(n)（C） O(nlogn)（D）O(1ogn)30 每次从排序记录中挑出最小(或最大)的关键字，加入待排序序列的末尾，则该排序算法是 ( ) 。（A）选择排序（B）快
9、速排序（C）冒泡排序（D）插入排序31 若对序列(t，a ，d，w ，s，b，f，1) 采用简单选择排序法按字典顺序进行排序，下面给出的四个序列中，第三趟的结果是( )。（A）a，b， d，w，t，f，s，l（B） a，b，d，w，s，t，f，l（C） a，b，d，w，f ，s ，t，l（D）a，b， d，w，s ，l，t，f32 对于一趟希尔排序的算法中，(1)处应该填人的内容( )。（A）k=k+d（B） k=k-d（C） k=k+1（D）k=k-133 希尔排序的空间复杂度为( )。（A）O(1)（B） O(n)（C） O(nlogn)（D）O(1ogn)34 希尔排序的说法正确的是(
10、)。（A）希尔排序的时间复杂度为 O(nlogn)（B）希尔排序的时间复杂度为 O(n2)（C）希尔排序是个稳定的排序算法（D）希尔排序是个不稳定的排序算法二、综合题35 简述单链表中设置头结点的作用。【电子科技大学 2008 三、1(6 分)】排序模拟试卷 3 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 排序是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列。【知识模块】 排序2 【正确答案】 A【试题解析】 若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj(ij，i，j=1，2， ，n)，且在排序前 K 先于 Ki(ij) ，排序后的记录序列仍然是 K 先于
11、 Kj，称排序方法是稳定的，否则是不稳定的。【知识模块】 排序3 【正确答案】 B【试题解析】 所有的记录都能存放在内存中进行排序，称为内部排序。【知识模块】 排序4 【正确答案】 B【试题解析】 所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。【知识模块】 排序5 【正确答案】 C【试题解析】 内部排序的基本操作包括比较两个关键字的大小和待比较记录的存储位置的移动：从一个位置移到另一个位置。【知识模块】 排序6 【正确答案】 D【试题解析】 记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必
12、不可少的。【知识模块】 排序7 【正确答案】 A【试题解析】 记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录。【知识模块】 排序8 【正确答案】 A【试题解析】 构造另一个辅助表来保存各个记录的存放地址(指针)：排序过程不需要移动记录，而仅需修改辅助表中的指针，排序后视具体情况决定是否调整记录的存储位置。【知识模块】 排序9 【正确答案】 B【试题解析】 给出哨兵所在位置。【知识模块】 排序10 【正确答案】 D【试题解析】 算法中的 RO开始时并不存放任何待排序的记录，引入的作用主要有两个：不需要增加辅助空间；保存当前待插入
13、的记录 Ri，Ri会因为记录的后移而被占用；保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起“哨兵监视”作用，避免在内循环中每次都要判断 j 是否越界。【知识模块】 排序11 【正确答案】 A【试题解析】 直接插入排序算法仅用了一个辅助单元，空间复杂度为 0(1)。【知识模块】 排序12 【正确答案】 B【试题解析】 若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数 1 次，记录移动次数 2 次(RiRO，RORj+1)。则整个排序的关键字比较次数和记录移动次数分别是：比较次数：，移动次数： ，总体的时间复杂度为 O(
14、n)。【知识模块】 排序13 【正确答案】 A【试题解析】 若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行 i 一 1，关键字比较次数 i 次，记录移动次数 i+1。则就整个排序而言：比较次数： ，移动次数：，总体的时间复杂度为 O(n2)。【知识模块】 排序14 【正确答案】 A【试题解析】 一般情况下，认为待排序的记录可能出现的各种排列的概率相同，则取最好和最坏两种情况的平均值作为排序的关键字比较次数和记录移动次数，约为 n24，则复杂度为 O(n2)。【知识模块】 排序15 【正确答案】 A【试题解析】 直接插入排序是一种稳定的排序方法。【知识模块】 排序1
15、6 【正确答案】 C【试题解析】 当将待排序的记录 Ri插入已排好序的记录子表 R1，i 一 1中时，由于 R1，R 2，R i 一 1 已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成折半插入排序。【知识模块】 排序17 【正确答案】 C【试题解析】 当比较的结果是比 mid 指针指向的位置小，则将 high 指针移到mid 指针的前面。当比较的结果是比 mid 指针指向的位置大，则将 low 指针移到mid 指针的后面。【知识模块】 排序18 【正确答案】 B【试题解析】 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数。【知识模块】 排序
16、19 【正确答案】 A【试题解析】 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为 O(n2)。【知识模块】 排序20 【正确答案】 A【试题解析】 折半插入排序是一种稳定的排序方法。【知识模块】 排序21 【正确答案】 A【试题解析】 交换顺序的语句。【知识模块】 排序22 【正确答案】 A【试题解析】 冒泡排序算法仅用了一个辅助空间，空间复杂度为 O(1)。【知识模块】 排序23 【正确答案】 B【试题解析】 正序的情况下，记录的比较次数为 n 一 1，移动次数为 0，因此时间复杂度为 O(n)。【知识模块】 排序24 【正确答案】 A【
17、试题解析】 逆序的情况下，比较的次数为： ；移动的次数为： ，故时间复杂为 T(n)=D(n2)。【知识模块】 排序25 【正确答案】 B【试题解析】 冒泡排序法是一种稳定的排序方法。排序前和排序后记录的位置不变。【知识模块】 排序26 【正确答案】 B【试题解析】 简单选择排序是选取比当前关键字小的进行交换，(1)处是实现交换的语句。【知识模块】 排序27 【正确答案】 A【试题解析】 简单选择排序的空间复杂度为 O(1)。【知识模块】 排序28 【正确答案】 A【试题解析】 对于简单选择排序来说，最好的时间复杂度为 O(n2)。【知识模块】 排序29 【正确答案】 A【试题解析】 对于简单
18、选择排序来说，平均的时间复杂度也为 O(n2)。【知识模块】 排序30 【正确答案】 A【试题解析】 题干中描述的是选择排序算法的基本过程。【知识模块】 排序31 【正确答案】 B【试题解析】 本题根据简单选择排序法的算法思想可得答案 B。【知识模块】 排序32 【正确答案】 B【试题解析】 这一步是进行下一次比较的位置调整，下一次要比较的是 k 一 d 位置上的数据和 k 位置上数据的大小。【知识模块】 排序33 【正确答案】 A【试题解析】 在希尔排序中，仅用了一个辅助单元(即源码中的监视哨)，空间复杂度为 O(1)。【知识模块】 排序34 【正确答案】 D【试题解析】 希尔排序时效分析很
19、难，关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以估算出关键码的比较次数和记录的移动次数。希尔排序方法是一个不稳定的排序方法。【知识模块】 排序二、综合题35 【正确答案】 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等)。有头结点后，链表指针(即头指针) 值是确定的，无论链表是否为空，头指针均不为空；对于链表操作，特别是插入或删除结点是第一元素结点的操作，就不用再作判断，与对其他结点的操作就统一了。
