工学
单选题若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。Aj-iBi-j-1Ci-jDi-j+1
题目
j-i
i-j-1
i-j
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．算法结束
(1)low←1 (2)low=high (3)mid←int((low+high)/2) (4)low←mid+1 (5)i-1到low 解析： 本题考查使用二分插入法对无序数组排序的伪码实现。
在做题前，我们需要先大概明白二分插入法的基本思想和步骤，其基本思想是(设 R[low，…，high]是当前的插入区间)：
(1)将要插入的数取出放在X中；
(2)确定区间的中点位置：mid=[(low+high)/2]；
(3)确定插入位置，将待插入的k值与R[mid].key比较，具体方法如下：
·若R[mid].key＞k，则由排序后表的有序性可知R[mid,…，n].key均大于k，因此，插入区间是左子表R[low,…，high]，其中high=mid-1。
·若R[mid].keyk，则要插入的k必在mid的右子表R[mid+1，…，high]中，其中 low=mid+1。
(4)在上面的过程中，low逐步增加，而high逐步减少，直到highlow，则找到插入位置为low，然后循环移动位置low后面的元素，再插入数值。
(5)重复上述过程，直到所有数都被插入。
有了上面的分析，我们再来看程序伪代码，第(1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值，high←i-1将数组中的最后一个位置赋给了插入指针high，因为插入的范围是数组的整个范围，那么第(1)空应该用来将数组的第一个位置赋给插入指针low，因此答案为low←1。
第(2)空是找插入位置用的循环条件，根据我们上面的分析，要直到highlow时，才能确定插入的位置；而在low=high时，循环一直执行，结合程序的内容，知道此空答案为low=high。
第(3)空很明显是用来确定区间的中间位置，但mid有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为mid-int((low+high)/2)。
第(4)空是条件X.keyR[mid].key不成立的情况下执行的语句，如果条件为假，则说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针low应该改变，这个空就是用来实现这个功能的，因此，答案为low←mid+1。
第(5)空在后移的循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在low中，因此，此空答案为i-1到 low。
第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
解析： 在采用顺序结构存储的线性表的第i个位置插入新元素，则要将第i个元素以后的元素向后移动(包括第i个元素) ，所以共有n-i+1个元素后移。