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

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

admin2009-02-15  21
问题 阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。
   【说明】
   为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1.n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R[]中的元素互不相同)。
  【算法】
   1．变量声明
   X：DataType
   i，j，low，high，mid，R[0..n])
   2．每循环一次插入一个R
   循环：i以1为步长，从2到n，反复执行
   ①准备
   X＜-R；(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的过程，这是一个典型的折半查找过程。初始时指针low指向第一个元素，即R [1]，指针hish指向第后一个元素，因此(1)空处应填写“low-1”。要查找R，先与中间元素进行比较，中间元素使用mid指向，因此，(3)空处应填入“mid＜-int((low+high)/2)”。当R＜R[mid]时，则在前半部分查找，将high＜-mid-1，如果R＞R[mid]时，则在后半部分查找，因此(4)空处应填“low＜-mid+1”。那什么时候结束呢?显然，一种情况是已经找该元素，由于题目中已经假设元素互不相同，这种情况不会发生，二是没有找到该元素，即指针low和指针high之间的没有元素了，所以(2)空处应填写“low≤high”。(5)空所在循环是进行数据移动，结合下面语句，可以判断循环是从i-1开始，到什么时候结束呢?通过分析，可以知道，最终要把R放在R[low]的位置，循环要到low时结束，因此(5)空处应填写“i-1到low”。
转载请注明原文地址:https://kaotiyun.com/show/UEjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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