应用题
已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)?
问答题
15.关键字自小到大有序(key1＜kye2＜…＜keyn)；
【正确答案】本题主要考查直接插入法的算法思想及性能分析。
根据题目所给出的条件，最好情况下的比较次数即为最少比较次数。
在关键字自小到大有序的情况下，插入第i个(2≤i≤n)元素的比较次数为1，因此，总的比较次数为1+1+1+…+1=n—1。
【答案解析】
问答题
16.关键字自大到小逆序(key1＞key2＞…＞keyn)；
【正确答案】在关键字自大到小有序的情况下，插入第i个(2≤i≤n)元素的比较次数为i，因此，总的比较次数为2+3+4+…+n=[n(n+1)／2]一1=(n—1)(n+2)／2。
【答案解析】
问答题
17.奇数关键字顺序有序，偶数关键字顺序有序(key1＜key3＜…，key2＜key4＜…)；
【正确答案】在奇数关键字顺序有序和偶数关键字顺序有序的情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为n一1。
【答案解析】
问答题
18.前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序(key1＜key2＜…＜keym，keym+1＞keym+2＞…＞keyn，m为中间位置)。
【正确答案】在前半部分元素按关键字有序，后半部分按关键字逆序的情况下，后半部分元素的关键字均大于前半部分元素的关键字较次数最少，此时前半部分的比较次数为m一1，后半部分的比较次数为(n一m一1)(n—m+2)／2，因此，总的比较次数为m一1+(n一m一1)(n一m，m+2)／2=(n-1)(n+8)／8(假设n为偶数，m=n／2)。
【答案解析】