j-i
i-1
i-j-1
i-j+1
第1题：
●试题一
阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。
【算法】
1．变量声明
X：DataType
i，j，low，high，mid，R0..n
2．每循环一次插入一个R［i］
循环：i以1为步长，从2到n，反复执行
①准备
X<-R［i］； (1) ；high<-i-1；
②找插入位置
循环：当 (2) 时，反复执行
(3)
若X．key<R［mid］．key
则high<-mid-1
否则 (4)
③后移
循环：j以-1为步长，从 (5) ，反复执行
R［j+1］<-R［j］
④插入
R［low］<-X
3．算法结束
●试题一
【答案】(1)low<-1(2)low≤high(3)mid<-int((low+high)/2)(4)low<-mid+1
(5)i-1到low
【解析】这是一个通过自然语言描述二分插入排序的过程。整个过程由一个大循环来完成，在大循环中又包含两个循环，第一个循环是一个二分查找过程，第二循环是后移过程。
查找过程是在有序序列R［1］．R［i-1］中查找R［i］的过程，这是一个典型的折半查找过程。初始时指针low指向第一个元素，即R［1］，指针high指向第后一个元素，因此(1)空处应填写"low-1"。要查找R［i］，先与中间元素进行比较，中间元素使用mid指向，因此，(3)空处应填入"mid<-int((low+high)/2)"。当R［i］<R［mid］时，则在前半部分查找，将high<-mid-1，如果R［i］>R［mid］时，则在后半部分查找，因此(4)空处应填"low<-mid+1"。那什么时候结束呢?显然，一种情况是已经找该元素，由于题目中已经假设元素互不相同，这种情况不会发生，二是没有找到该元素，即指针low和指针high之间的没有元素了，所以(2)空处应填写"low≤high"。(5)空所在循环是进行数据移动，结合下面语句，可以判断循环是从i-1开始，到什么时候结束呢?通过分析，可以知道，最终要把R［i］放在R［low］的位置，循环要到low时结束，因此(5)空处应填写"i-1到low"。
第2题：
A、n-i+1
B、n-i-1
C、i
D、n-i
第3题：
第4题：
在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为______。
A． n-i+1
B．n-i
C．i
D．i-1
第5题：
A.n-i+1
B.n-i-1
C.n-i
D.i
第6题：
（） 下面是一趟插入排序的程序, 把R[i+1]插入到R[1..i]的适当位置 R[0] = R[i + 1]; j = i; while ( R[j] >R[0] ) { R[j + 1] = R[j]; j = j - 1; } R[j + 1] = R[0];问题：（15分） 请用路径覆盖方法为它设计足够的测试用例(while循环次数为0次、1次、2次)。
第7题：
阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
【说明】
为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)
[算法]
1．变量声明
X: Data Type
i,j,low, high,mid,r:0..n
2．每循环一次插入一个R[i]
循环：i以1为步长，从2到n，反复执行。
(1)准备
X←R[i];(1); high←i-1;
(2)找插入位置
循环：当(2)时，反复执行。
(3)
若X.key＜R[mid].key
则high←mid-1;
否则 (4)
(3)后移
循环：j以-1为步长，从(5)，反复执行。
R[j+1]←R[j]
(4)插入
R[low]←X
3．算法结束
第8题：
在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n＋1），元素的移动次数为：()。
A.n–i＋1
B.n–i
C.i
D.i–1
第9题：
若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为 ______。
A．1
B．i-1
C．i
D．i+1
第10题：
若长度为n的线性表采用顺序存储结构，那么在第i个位置插入一个元素，需要依次向后移动 ______个元素。
A．n-i
B． n-i+1
C． n-i-1
D． i