第7章_排序_考点2_插入排序_2016年考研核心考点命题思路解密_数据结构.pdfVIP

2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 考点2 插入排序 一．选择题部分 1. 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放 入已排序序列的正确位置上的方法，称为 （ ）。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 2. n 个关键码排序，如果选用直接插入排序方法，则元素的移动次数在最坏情况下可以达 到 （ ）。 1 2 B. n(n-1)/2 A. 2 C. n/2 D. (n-1)/2 3. 当初始序列已经按键值有序，用直接插入法对其进行排序，需要比较的次数为（ ）。 2 A. n B. n-1 C. log n D. nlog n 2 2 4. 设一组初始记录关键字的长度为8，则最多经过 （ ）趟插入排序可以得到有序序 列。 A. 6 B. 7 C. 8 D. 9 5. 如表r 有100000 个元素，前99999 个元素递增有序，则采用 （ ）方法比较次数 较少。 A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序 6. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是 （ ）。 A. 94,32,40,90,80,46,21,69 B. 32,40,21,46,69,94,90,80 C. 21,32,46,40,80,69,90,94 D. 90,69,80,46,21,32,94,40 7. 插入排序在（ ）情况下效率最高。 A. 被排序的数据中有多个相同的数据元素 B. 被排序的数据已基本有序 C. 被排序的数据完全无序 D. 被排序的数据中最大值和最小值相差悬殊 二．综合应用部分 1. 以下为直接插入排序的算法。请分析算法，并在横线上填充适当的语句。 void straightsort(seqlist r,int n) { 2016 年考研核心考点命题思路解密——数据结构 梦享团队主编 for(i= ;i=n;i++) { r[0]=r[i]; j=i -1; while(r[0].keyr[j].key) { r[j+1]= ; j --; } r[j+1]= ; } } 2. 对记录38、49 、65、97、76、13、27 进行直接插入排序，并写出插入排序的过程。 3. 用直接插入排序方法对序列(94,32,40,90,80,46,21,69)进行排序（由小到大），试写出排 序的过程。 参 考 答 案