2. 计算机
  3. 阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后

阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。 【说明】 为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后

admin2010-01-15  24
问题 阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。
   【说明】
    为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)
   [算法]
   1．变量声明
    X: Data Type
   i,j,low, high,mid,r:0..n
   2．每循环一次插入一个R
   循环：i以1为步长，从2到n，反复执行。
   (1)准备
   X←R;(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].key＜k，则要插入的k必在mid的右子表R[mid+1，…，high]中，其中 low=mid+1。
   (4)在上面的过程中，low逐步增加，而high逐步减少，直到high＜low，则找到插入位置为low，然后循环移动位置low后面的元素，再插入数值。
   (5)重复上述过程，直到所有数都被插入。
   有了上面的分析，我们再来看程序伪代码，第(1)空处在准备阶段，准备阶段要完成的任务是给变量赋初值，high←i-1将数组中的最后一个位置赋给了插入指针high，因为插入的范围是数组的整个范围，那么第(1)空应该用来将数组的第一个位置赋给插入指针low，因此答案为low←1。
   第(2)空是找插入位置用的循环条件，根据我们上面的分析，要直到high＜low时，才能确定插入的位置；而在low＜=high时，循环一直执行，结合程序的内容，知道此空答案为low＜=high。
   第(3)空很明显是用来确定区间的中间位置，但mid有可能为小数，在程序中我们用取整的方法来去掉小数部分，因此，此空答案为mid＜-int((low+high)/2)。
   第(4)空是条件X.key＜R[mid].key不成立的情况下执行的语句，如果条件为假，则说明要插入的数大于中间位置的数，应该在其右区间里进行插入，根据分析知道，这时左指针low应该改变，这个空就是用来实现这个功能的，因此，答案为low←mid+1。
   第(5)空在后移的循环操作中，作为后移的循环判断条件，在找到插入位置后，进行插入前，我们需要一个空间来存放插入的值。从程序中不难看出，是将待插入位置后面的所有元素向后移动一位，而待插入位置存放在low中，因此，此空答案为i-1到 low。
转载请注明原文地址:https://kaotiyun.com/show/LBjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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