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

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

admin2014-12-08  107
问题 已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?
  (1)关键字自小到大有序(key1＜key2＜…＜keyn)。
  (2)关键字自大到小逆序(key1＞key2＞…＞keyn)。
  (3)奇数关键字顺序有序，偶数关键字顺序有序(key1＜key3…，key2＜key4＜…)。
  (4)前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1＜key2＜…＜keym，keym+1＞keym+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)在这种情况下，比较次数最少的情况是所有纪录关键字均按升序排列，这时，总的比较次数为n-1。 (4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数=m-1，后半部分的比较次数=(n-m-1)*(n-m+2)／2，因此，总的比较次数为m-1+(n-m-1)×(n-m+2)／2=(n-2)(n+8)／8(假设n偶数，m=n／2)。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/Ydxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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