违法和不良信息举报 联系客服
免费注册 登录

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，最多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序 列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（ ）。

题目
对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，最多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序 列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（ ）。

A. 若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少
B.若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少
C.第1趟完成后即可确定整个序列的最小关键码
D.第1趟完成后即可确定整个序列的最大关键码
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为 ______。

A．1

B．i-1

C．i

D．i+1


正确答案：C

第2题：

每趟排序都从序列的未排好序的序列中挑选一个值最小(或最大)的元素，然后将其与未排好序的序列的第一个元素交换位置。此种排序法称为(54)。

A．插入排序法

B．选择排序法

C．希尔排序法

D．快速排序法


正确答案：B
解析：选择排序方法是每一趟排序从未排序的子序列中依次取出元素与已经排好序的序列中的元素进行比较，然后将其与未排好序的序列的第一个元素交换位置。因此选B。

第3题：

对一个由n个关键码组成的序列，借助排序过程选出其中最大的关键码，要求关键码比 较次数和移动次数最少，应当使用下列（ ）排序方法。A．归并排序B．直接插入排序C．直接选择排序D．快速排序


正确答案：C
第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[2]交换，....，

第4题：

对n个记录进行非递减排序，在第一趟排序之后，一定能把关键码序列中的最大或最小元素放在其最终排序位置上的排序算法是（ ）

A.冒泡排序 B.快速排序 C.直接插入排序 D.归并排序


正确答案：A

第5题：

若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为______。

A．1

B．11

C．i

D．i+l


正确答案：C

第6题：

采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数己经排好序，将第i个整数依次和第i-1, i-2, ...个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序，则需要进行（31）次整数之间的比较。对于该排序算法，输入数据具有（32）特点时,对整数进行从小到大排序，所需的比较次数最多。

A.9

B.10

C.12

D.13


正确答案：C
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：（1）从第一个元素开始，该元素可以认为已经被排序（2）取出下一个元素，在已经排序的元素序列中从后向前扫描（3）如果该元素（已排序）大于新元素，将该元素移到下一位置（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置（5）将新元素插入到下一位置中（6）重复步骤2~5对于本题：{5.2.4.6.1.3}第一趟：第一次比较，5大于2（新元素），元素5向后位移一位，而5之前无数据，即将2插入到1位，2，5第二趟：第一次比较，5大于4（新元素），元素5向后移一位，再进行第二次比较，2小于4（新元素），即将4插入2之后的一位，即2，4，5依次类推，，，所以比较的次数为1+2+1+4+4=12如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。

第7题：

对一个由n个关键码组成的序列，借助排序过程选出其中最大的关键码，要求关键码比较次数和移动次数最少，应当使用下列哪种排序方法?

A．归并排序

B．直接插入排序

C．直接选择排序

D．快速排序


正确答案：C
解析：直接选择排序第一趟扫描就可以把最大的关键码找出来(不必等到排序结束)其它几种排序方法都必须等到排序完成才能找到最大关键码。

第8题：

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码Ki时，其前面的i-1个关键码己排好序，因此令Ki与Ki-1、Ki-2、...，依次比较，多到K1为止，找到插入位置并移动相关元素后将Ki插入有序子序列的适当位置，完成本趟（即第i-1趟）排序。以下关于直接插入排序的叙述中，正确的是（）。

A.若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少

B.若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少

C.第1趟完成后即可确定整个序列的最小关键码

D.第1趟完成后即可确定整个序列的最大关键码


正确答案：A

第9题：

对一个由n关键码组成的序列，借助排序过程选出其中最大的关键码，要求关键码比较次数和移动次数最少，应当使用下列哪种排序方法?

A．归并排序

B．直接插入排序

C．直接选择排序．

D．快速排序


正确答案：C
解析：直接选择排序第一趟扫描就可以把最大的关键码找出来(不必等到排序结束)其他几种排序方法都必须等到排序完成才能找到最大关键码。

第10题：

采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i一1

个整数已经排好序，将第i个整数依次和第i．，i-2，…个整数进行比较，找到应该插入

的位置。现采用插入排序算法对6个整数{5 2，4，6，1，3}进行从小到大排序，则需要进行

(31)次整数之间的比较。对于该排序算法，输入数据具有(32)特点时，对整数进

行从小到大排序，所需的比较次数最多。

A.9

B.10

C.12

D.13

(32)A.从小到大

B.从大到小

C.所有元素相同

D.随机分布

请帮忙给出每个问题的正确答案和分析，谢谢！


问题 1 答案解析：C
采用插入排序算法对6个整数{5，2，4，61，3）进行从小到大排序的过程如表所示。

综上，元素间共比较12次。从上表中的第4步可看出，当待插入的元素比已排序部分的所有元素都要小时，需要比较和移动的元素最多，因此当输入数据序列正好从大到小排列，而需要将其从小到大排序时，元素间的比较次数最多。


问题 2 答案解析：B
同31题解析

更多相关问题
相关内容