2. 计算机
  3. 对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码ki时，其前面的i－1个关键码已排好序，因此令ki与ki－1，ki－2，…，依次比较，最多到k1为止，找到插入位置并移动相关元素后将ki插入有序子序列的适当位置，完成本趟(即第

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码ki时，其前面的i－1个关键码已排好序，因此令ki与ki－1，ki－2，…，依次比较，最多到k1为止，找到插入位置并移动相关元素后将ki插入有序子序列的适当位置，完成本趟(即第

admin2021-01-13  37
问题 对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是：在插入第i个关键码ki时，其前面的i－1个关键码已排好序，因此令ki与ki－1，ki－2，…，依次比较，最多到k1为止，找到插入位置并移动相关元素后将ki插入有序子序列的适当位置，完成本趟(即第i—1趟)排序。以下关于直接插入排序的叙述中，正确的是_____________。
选项 A、若原关键码序列已经升序排序，则排序过程中关键码间的比较次数最少
B、若原关键码序列已经降序排序，则排序过程中关键码间的比较次数最少
C、第1趟完成后即可确定整个序列的最小关键码
D、第1趟完成后即可确定整个序列的最大关键码
答案A
解析 本题考查数据结构基础知识。
    以4个元素(10,20,30,40)为例说明直接插入排序的特点。
    若元素已经按照升序排列，即k1=10，k2=20，k3=30，k4=40，那么各趟排列结果如下：
    第一趟将20插入仅含元素10的子序列，20与10比较1次，得到10 20；
    第二趟将30插入含有元素10、20的子序列，30与20比较1次，得到10 20 30；
    第三趟将40插入10、20、30构成的子序列，40与30比较1次，得到10 20 30 40。
    在上述过程中，由于待插入的元素比有序子序列的最大元素都要大，所以总共进行3次比较，也不需要移动元素。推广到有n个元素的序列，则是进行n一1次比较。
    若元素已经按照降序排列，即k1=40，k2=30，k3=20，k4=10，那么各趟排列结果如下：
    第一趟将30插入仅含元素40的子序列，30与40比较1次，将40后移，再将30插入40之前，得到30 40；
    第二趟将20插入30、40构成的子序列，20与40比较1次，将40后移，再与30比较1次，将30后移，再将20插入30之前，得到20 30 40；
    第三趟将10插入20、30、40构成的子序列，10与40比较1次，将40后移，再与30比较1次，将30后移，再与20比较1次，将20后移，再将10插入20之前，得到10 20 30 40。
    在上述过程中，由于待插入的元素比有序子序列的所有元素都要小，所以总共进行1+2+3次比较，每次插入时有序子序列的所有元素都要移动。推广到有n个元素的序列，则总共进行1+2+…+n－2+n－1次比较。
    因此，题目选项中A选项正确。
若初始序列为30 20 10 40，则第一趟排序完成后得到的有序子序列为20 30，此时并没有得到整个序列的最小元素或最大元素，所以选项C和D的说法错误。
转载请注明原文地址:https://www.kaotiyun.com/show/UBNZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)