阅读以下说明和C代码，填写程序中的空（1）~（5），将解答写入答题纸的对应栏内。【说明】直接插入排序是一种简单的排序方法，具体做法是：在插入第i个关键码时，k1，k2，…，ki-1已经排好序，这时将关键码ki依次与关键码ki-1，ki-2，…，进行比较，找到ki应该插入的位置时停下来，将插入位置及其后的关键码依次向后移动，然后插入ki。例如，对｛17，392，68，36｝按升序作直接插入排序时，过程如下：第1次：将392（i＝1）插入有序子序列{17}，得到{17，392}；第2次：将68（i＝2）插入有

题目

阅读以下说明和C代码，填写程序中的空（1）~（5），将解答写入答题纸的对应栏内。【说明】直接插入排序是一种简单的排序方法，具体做法是：在插入第i个关键码时，k1，k2，…，ki-1已经排好序，这时将关键码ki依次与关键码ki-1，ki-2，…，进行比较，找到ki应该插入的位置时停下来，将插入位置及其后的关键码依次向后移动，然后插入ki。例如，对｛17，392，68，36｝按升序作直接插入排序时，过程如下：第1次：将392（i＝1）插入有序子序列{17}，得到{17，392}；第2次：将68（i＝2）插入有序子序列{17，392}，得到{17，68，392}；第3次：将36（i＝3）插入有序子序列{17，68，392}，得到{17，36，68，392}，完成排序。下面函数 insertSort用直接插入排序对整数序列进行升序排列，在main函数中调用insertSort并输出排序结果。【C代码】void insert Sort(int data[],int n)/*用直接插入排序法将data[0]～ data[n-1]中的n个整数进行升序排列*/{ int i,j; int tmp; for(i=1; i=0 && data[j] > tmp;j----) //查找插入位置并将元素后移（2）; （3） =tmp; //插入正确位置 }/*if*/ }/*for*/}/*insertSort*/ int main(){ int *bp,*ep; int n,arr[]={17,392,68,36,291,776,843,255}; n = sizeof(arr) / sizeof(int); insertSort(arr,n); bp= （4） ; ep = arr+n; for( ;bp=0 && data[j] > tmp;j----) //查找插入位置并将元素后移（2）; （3） =tmp; //插入正确位置 }/*if*/ }/*for*/}/*insertSort*/ int main(){ int *bp,*ep; int n,arr[]={17,392,68,36,291,776,843,255}; n = sizeof(arr) / sizeof(int); insertSort(arr,n); bp= （4） ; ep = arr+n; for( ;bp

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

若待排序列已基本有序,要使它们完全有序,从关键码比较次数和移动次数考虑,应当使用的排序方法是( )。

A、归并排序

B、直接插入排序

C、直接选择排序

D、快速排序

正确答案: A

第2题：

下列排序方法中，哪一种方法总的关键码比较次数与记录的初始排列状态无关?( )

A) 直接选择排序

B) 直接插入排序

C) 起泡排序

D) 快速排序

A．

B．

C．

D．

正确答案：A

第3题：

（15）下列排序方法中，（）方法的总的关键码比较次数与记录的初始排列状态无关。

A）直接插入排序

B）直接选择排序

C）起泡排序

D）快速排序

正确答案：A

（15）【答案】A)
【解析】直接插入排序在已排好顺序的序列中查找插入位置时用顺序法查找，找到查入位置后将该位置及其后面的记录顺序后移一个位置，空出来插入记录。所以它与记录的初始排列状态无关。

第4题：

用直接插入排序方法对序列{15，11，9，10，13}进行排序，关键码比较次数是

A．10

B．8

C．4

D．9

正确答案：B
解析：直接插入排序的基本算法：当插入第I(I＞=1)个对象时，前面的 V(0)，V(1)…V(I-1)已经排好序，这时，用V(I)的关键码与V(I-1)，(I-2)，…的关键码顺序进行比较，找到插入位置即将V(I)插入，原来位置上的对象则向后移。本题中的I只能取1，第1趟(I：1)：11和15比较，插入：11，15，9，10，13；第2趟(I =2)：9和11比较，插入：9，11，15，10，13；第3趟(1=3)：10和9比较，不插入，再和11比较，插入：9，10，11，15，13；第4趟(I=4)：13和9比较，不插入，再和10比较，不插入，和11比较，不插入，和15比较，插入，排序完成。共比较8次。

第5题：

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

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

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

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

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

正确答案：A

第6题：

下列排序方法中，哪一种方法的总的关键码比较次数与记录的初始排列状态无关?______。

A．直接插入排序

B．起泡排序

C．快速排序

D．直接选择排序

正确答案：B

第7题：

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

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

第8题：

在排序方法中，关键码比较次数与记录的初始排列无关的是

A．Shell排序

B．归并排序

C．直接插入排序

D．选择排序

正确答案：C

第9题：

采用插入排序算法对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）。

第10题：

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

A．归并排序

B．直接插入排序

C．直接选择排序

D．快速排序

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

题目

相似问题和答案

更多相关问题

相关内容