当前位置:   article > 正文

数据结构作业——第十六周--排序_对整数序列(8,9,10,4,5,6,20,1,2)进行递增排序,采用每趟冒出一个最小元素的冒泡排

对整数序列(8,9,10,4,5,6,20,1,2)进行递增排序,采用每趟冒出一个最小元素的冒泡排

1 . 单选题 简单 5分

对整数序列(8,9,10,4,5,6,20,1,2)进行递增排序,采用每趟冒出一个最小元素的冒泡排序算法,需要进行的趟数是______。

A.3

B.4

C.6

D.8

 回答正确

解析

2 . 单选题 简单 5分

以下排序方法中,不稳定的排序方法是______。

A.冒泡排序

B.直接插入排序

C.希尔排序

D.二路归并排序

 回答正确

解析

稳定排序有:直接输入、冒泡排序、二路归并排序;

不稳定排序有:快速排序、直接选择排序、堆排序;

3 . 单选题 简单 5分

对一组数据(2,12,16,88,5,10)进行排序,若前三趟的结果如下: 第一趟:2,12,16,5,10,88 第二趟:2,12,5,10,16,88 第三趟:2,5,10,12,16,88 则采用的排序方法可能是______。

A.冒泡排序

B.希尔排序

C.二路归并排序

D.基数排序

 回答正确

解析

排除法。

归并排序的第一趟结果是:(2,12,16,88,5,10)
基数排序第一趟结果(10,2,12,5,16,88)
希尔排序显然是不符合的,所以只有冒泡排序符合条件;

4 . 单选题 简单 5分

对8个元素的顺序表进行快速排序,在最好情况下,元素之间的比较次数为______ 次。

A.7

B.8

C.12

D.13

 回答正确

解析

对8个元素排序的最好情况是:

第一次找到的元素将原表分成长度为3和4的表,用到7次比较;
第二层,对于长度为3的表,最少需要2次;对于长度为4的表,继续分成长度为1 和长度为2的表,最少需要3次;
第三层,需要对长度为2 的表进行排序,最少需要1次比较,所以总共需要:7+2+3+1=13次

5 . 单选题 简单 5分

对关键字序列(28,16,32,12,60,2,5,72)进行快速排序,第一趟从小到大一次划分结果为______。

A.(2,5,12,16) 26 (60 32 72)

B.(5,16,2,12) 28 (60,32,72)

C.(2,16,12,5) 28 (60,32,72)

D.(5,16,2,12) 28 (32,60,72)

 回答正确

解析

排序前:28,16,32,12,60,2,5,72

           **  5,16,2,12,28,60,32,72(第一趟)

                2,5,16,12

                           12,16    

                                                 32,60,72

排序后:2,5,12,16,28,60,32,72

6 . 单选题 简单 5分

以下关于快速排序的叙述中正确的是______。

A.快速排序在所有排序方法中为最快,而且所需辅助空间也最少

B.在快速排序中,不可以用队列替代栈

C.快速排序的空间复杂度为O(n)

D.快速排序在待排序的数据随机分布时效率最高

 回答正确

解析

7 . 单选题 简单 5分

设有n(n为大于10000的整数)个无序元素,希望用最快速度从中选择前k(1≤k≤n)个关键字最小的元素,在以下排序方法中应选择______。

A.快速排序

B.希尔排序

C.二路归并排序

D.直接插入排序

 回答正确

解析

8 . 单选题 简单 5分

2n个不同的元素选择其中最小元素所需关键字比较次数最少是______次。

A.n

B.2n

C.2n-1

D.n-1

 回答正确

解析

9 . 单选题 简单 5分

以下序列不是堆的是______。

A.(100,85,98,77,80,60,82,40,20,10,66)

B.(100,98,85,82,80,77,66,60,40,20,10)

C.(10,20,40,60,66,77,80,82,85,98,100)

D.(100,85,40,77,80,60,66,98,82,10,20)

 回答正确

解析

查看堆的定义:

 意为父结点均不大于其孩子结点,或均不小于孩子结点;
由此定义即可判断出,D中的100大于85和40,而40小于60和66,所以D不是堆;

10 . 单选题 简单 5分

有一个整数序列为(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为______。

A.(-1,4,8,9,20,7,15,7)

B.(-1,7,15,7,4,8,20,9)

C.(-1,4,7,8,20,15,7,9)

D.以上都不对

 回答正确

解析

11 . 单选题 简单 5分

在二路归并排序中归并的趟数是______。

A.n

B.log2n

C.log2n+1

D.n2

 回答正确

解析

归并排序将序列一分为二,将问题范围缩小到原来的一半以递归方法加以解决

12 . 单选题 简单 5分

以下排序方法中,______ 不需要进行关键字的比较。

A.快速排序

B.二路归并排序

C.基数排序

D.堆排序

 回答正确

解析

基数排序是采用分配和手机实现的,不需要进行关键字的比较;
而其他集中排序方法都是关键字的比较实现的

13 . 单选题 简单 5分

以下4个线性表中,最适合采用基数排序的是______。

A.10000个实数

B.1000个由字母、数字和其他字符组成的字符串

C.1000个int类型的整数

D.10000个100以内的正整数

 回答正确

解析

14 . 单选题 简单 5分

对给定的关键字序列(110,119,007,911,114,120,122)进行基数排序,则第2趟分配 收集后得到的关键字序列是______。

A.007,110,119,114,911,120,122

B.007,110,119,114,911,122,120

C.007,110,911,114,119,120,122

D.110,120,911,122,114,007,119

 回答正确

解析

基数排序的第一趟排序是按照个位数字来排序的,第二趟排序是按照十位数字的大小进行排序的。

15 . 单选题 简单 5分

以下排序方法中,______ ,在初始序列已基本有序的情况下,排序效率最高。

A.冒泡排序

B.直接插入排序

C.快速排序

D.堆排序

 回答正确

解析

直接插入排序在初始序列越接近正序时,排序效率越高

16 . 单选题 简单 5分

数据序列(8,9,10,4,5,6,20,1,2)只能是______ 算法的两趟排序后的结果。

A.简单选择排序

B.冒泡排序

C.直接插入排序

D.堆排序

 回答正确

解析

17 . 单选题 简单 5分

以下排序算法中,______ 在最后一趟排序结束之前可能所有元素都没有放到其最终位置上。

A.简单选择排序

B.希尔排序

C.堆排序

D.冒泡排序

 回答正确

解析

排序过程中,一个元素放到其最终位置上称为归位,这几种排序方法中只有希尔排序每趟并不一定能归位一个元素,其他排序方法都可以;

18 . 单选题 简单 5分

下列排序方法中,______ 在一趟结束后不一定能选出一个元素放在其最终位置上。

A.简单选择排序

B.冒泡排序

C.二路归并排序

D.堆排序

 回答正确

解析

因为归并排序每趟并不一定产生全局有序区

19 . 单选题 简单 5分

整数序列(3,2,4,1,5,6,8,7)是第一趟递增排序后的结果,则采用的排序方法可能是______。

A.快速排序

B.冒泡排序

C.堆排序

D.简单选择排序

 回答正确

解析

该序列前,后都找不到全局有序区,所以不可能是冒泡排序,堆排序和简单选择排序。
该序列中可以找到一个基准5(或6),其前的所有元素小于它,其后的所有元素大于它,
所以可能是快速排序

20 . 单选题 简单 5分

整数序列(5,4,15,10,3,2,9,6,1)是某排序方法第一趟后的结果,该排序算法可能是______。

A.冒泡排序

B.二路归并排序

C.堆排序

D.简单选择排序

 回答正确

解析

冒泡排序、堆排序和简单选择排序,都产生全局有序区;

该数据序列前、后都没有全局有序区,所以可能是归并排序第一趟后的结果,是递减排序,最后一个元素没有参与归并,所以可能是二路归并算法;

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/喵喵爱编程/article/detail/784705
推荐阅读
相关标签
  

闽ICP备14008679号