2. 考研
  3. 已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl

已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keyl

admin2013-09-16  86
问题 已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(keylkey2)…>keyn)。(3)奇数关键字顺序有序，偶数关键字顺序有序(key1keym+2>…>keyn，m为中间位置)。
选项
答案依题意，取各种情况下的比较次数即为最少比较次数。 (1)在这种情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n一1。 (2)在这种情况下插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=(n一1)(n+2)／2。 (3)在这种情况下，比较次数最少的情况是所有纪录关键字均按升序排列，这时，总的比较次数为11一1。(4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数m--1，
解析
转载请注明原文地址:https://kaotiyun.com/show/C0xi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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