●试题一阅读下列算法说明和算法,将应填入(n)处的语句写在答题纸的对应栏内。【说明】为了减少

6 查阅

●试题一

阅读下列算法说明和算法，将应填入(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)空处应填

软考初级