阅读下列算法说明和算法，将应填入(n)处的语句写在对应栏内。【说明】为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R[1..n]进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置。(假设R[]中的元素互不相同)[算法]1．变量声明X: Data Typei,j,low, high,mid,r:0..n2．每循环一次插入一个R[i]循环：i以1为步长，从2到n，反复执行。(1)准备X←R[i];(1); high←i-

题目

阅读下列算法说明和算法，将应填入(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.●试题四阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明】函数QuickSort是在一维数组A［n］上进行快速排序的递归算法。【函数】void QuickSort(int A［］，int s，int t){int i=s，j=t+1，temp；int x=A［s］；do{do i＋＋；while (1) ；do j--；while(A［j］>x)；if(i<j){temp=A［i］； (2) ； (3) ；}}while(i<j)；A［a］=A［j］；A［j］=x；if(s<i-1) (4) ；if(j+1<t) (5) ；}

2.阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。【说明】函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。【函数】void QuickSort( int A[ ],int s,int t){ int i=s,j=t+1,temp;int x=A[s];do{do i ++ ;while (1);do j -- ;while(A[j]＞x);if(i＜j){temp=A[i];(2);(3);}}while(i＜j);A[a] =A[j];A[j] =x;if(s＜i-1) (4);if(j+1＜t) (5);}

3.阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。[说明]完成以下中序线索化二叉树的算法。[函数]Typedef int datatype;Typedef struct node {Int ltag, rtag;Datatype data;*lchild,* rchild;}bithptr;bithptr pre;void inthread ( p );{if{inthread ( p-＞lchild );if ( p-＞lchild==unll ) (1);if ( P-＞RCHILD=NULL) p-＞rtag=1;if (2){if (3) pre-＞rchild=p;if ( p-＞1tag==1 )(4);}INTHREAD ( P-＞RCHILD );(5);}}

4.●试题一阅读下列算法说明和算法，将应填入(n)处的语句写在答题纸的对应栏内。【说明】为了减少直接插入排序关键字的比较次数，本算法使用了二分(折半)插入法对一个无序数组R［1..n］进行排序。排序思想是对一个待插入元素，先通过二分法(折半)找到插入位置，后移元素后将该元素插入到恰当位置(假设R［］中的元素互不相同)。【算法】1．变量声明X：DataTypei，j，low，high，mid，R0..n2．每循环一次插入一个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］<-X3．算法结束

参考答案和解析
正确答案：(1)low←1 (2)low=high (3)mid←int((low+high)/2) (4)low←mid+1 (5)i-1到low
(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。
更多“阅读下列算法说明和算法,将应填入(n)处的语句写在对应栏内。 【说明】为了减少直接插入排序关键字的 ”相关问题

  • 第1题：

    阅读下列说明和流程图，将应填入(n)处的语句写在对应栏内。

    【说明】

    下列流程图用泰勒(Taylor)展开式y=ex=1+x+x2/2!+x3/3!+…+xn/n!+…计算并打印ex的近似值，其中用ε(＞0)表示误差要求。

    【流程图】


    正确答案：(1)0 (2)0 (3)|t|:ε (4)s+1 (5)t*x/s
    (1)0 (2)0 (3)|t|:ε (4)s+1 (5)t*x/s 解析：本题考查程序流程图的内容。
    首先让我们来了解一下题目的真正含义，题目要求用泰勒展开式计算y=ex的近似值。并且给出了误差要求，只要当误差小于ε时，就可以输出计算结果了。泰勒展开式的式子是n项之和，每多加一项，其值就越接近真实值。因此，在程序设计时，每加一项之前，先进行此项与ε的比较，来判定计算结果是否已满足题目要求。
    从流程图中看到有S、y、t、x这几个变量。其中x、y是公式中的变量，而S、t则是中间变量。从y←y+t语句可以看出，t是每次要加的项，S则是帮助t改变的变量。在计算开始前，我们应该将y的值赋为零，因此，第(2)空答案就为0；而S在t没发生变化的初值也应该是0，即第(1)空答案为0。
    第(3)空处是个条件判断语句，应该是进行该加项与ε比较判断，因此第(3)空的答案是|t|:ε。
    第(4)空与第(5)空要一起考虑。由于S是帮助t改变的变量，而t的每次改变是分母乘以一个加1的数，而分子乘以x。这里假设S是帮助t改变分母的变量，第(4)空应填s+1，那么第(5)空应该为t*x/s。

  • 第2题：

    阅读下列说明和流程图，将应填入(n)处的语句写在对应栏内。

    【说明】

    设学生(学生数少于50人)某次考试的成绩按学号顺序逐行存放于某文件中，文件以单行句点“.”为结束符。下面的流程图用于读取该文件，并把全部成绩从高到低排序到数组B[50]中。

    【流程图】


    正确答案：(1)B[0]←a (2)i←0 (3)a="." (4)aB[j] (5)j--
    (1)B[0]←a (2)i←0 (3)a="." (4)aB[j] (5)j-- 解析：本题考查用程序流程图来描述排序。
    题目要求将文件中学生的成绩读出，并把全部成绩从高到低排序到数组B[50]中。这里面涉及两个问题，第一是从文件中读数，文件中的数据是以单行句点“.”为结束符的，在未读到此符号前，应该将继续取数据。第二是排序，每取到一个学生的成绩都要与数组的学生成绩比较，按照从高到低的顺序在数组中找到合适的位置存放。下面来具体分析流程图。
    第(1)空在条件判断为假的情况下执行流程中，如果条件为假说明从文件中取到的数据是学生成绩。从程序流程图中可以看到，从文件中读的数据存放在变量a中，而此空是第一次取数据，应该存放数组B的第一个位置，因此此空答案为B[0]←a。
    第(2)空是紧接着第(1)空来的，在上面已经把从文件中读到的第一个数存放到了数组中，接下来应该处理数组的下标问题，从后面的流程中可以推断出变量i是存放数组当前下标的，而且没有初值，那么此空的任务应该是用来给变量i赋一个初值，而对数组的操作应该从头开始，因此此空答案为i←0。
    第(3)空是循环的判断条件，如果条件成立则结束，在这之前又对文件进行了一次读数，根据我们上面的分析只有在读到了结束符时程序才结束，那么此空肯定是判断从文件中读到的数据是否为结束符，因此此空答案为a="."?。
    第(4)空也是一个循环的判断条件，如果条件成立，则将取到的数存放到数组的当前下标位置；如果不成立，则循环找到合适的位置再存放。从这里我们不难推断出，流程图中是将从文件取到的成绩与当前数组中的最小成绩进行比较的，而当前数组中的最小成绩存放在位置j中，因此此空答案为aB[i]?。
    第(5)空在循环体中，这个循环的作用是为当前从文件中读到的成绩在已经排好序的数组元素中找到合适的位置，找到了就要插入，数组中的元素是按从大到小排列的，在查找合适位置时是从后往前依次比较，因此此空的任务应该是将数组的下标往前移动，所以此空答案为“i--”。

  • 第3题：

    阅读下列说明和?C++代码，将应填入(n)处的字句写在答题纸的对应栏内。
    【说明】
    阅读下列说明和?Java代码，将应填入?(n)?处的字句写在答题纸的对应栏内。
    【说明】
    某快餐厅主要制作并出售儿童套餐，一般包括主餐(各类比萨)、饮料和玩具，其餐品种
    类可能不同，但其制作过程相同。前台服务员?(Waiter)?调度厨师制作套餐。现采用生成器?(Builder)?模式实现制作过程，得到如图?6-1?所示的类图。






    答案：
    解析：

  • 第4题：

    阅读下列程序说明和C++程序，把应填入其中(n)处的字句，写在对应栏内。

    【说明】

    阅读下面几段C++程序回答相应问题。

    比较下面两段程序的优缺点。

    ①for (i=0; i＜N; i++ )

    {

    if (condition)

    //DoSomething

    …

    else

    //DoOtherthing

    …

    }

    ②if (condition) {

    for (i =0; i＜N; i++ )

    //DoSomething

    }else {

    for (i=0; i ＜N; i++ )

    //DoOtherthing

    …

    }


    正确答案：程序1优点：程序简洁；缺点：多执行了N-1次逻辑判断并且程序无法循环“流水”作业使得编译器无法对循环进行优化处理降低了效率。 程序2优点：循环的效率高；缺点：程序不简洁。
    程序1优点：程序简洁；缺点：多执行了N-1次逻辑判断，并且程序无法循环“流水”作业，使得编译器无法对循环进行优化处理，降低了效率。 程序2优点：循环的效率高；缺点：程序不简洁。

  • 第5题：

    试题三（共 15 分）

    阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。


    正确答案：

相关内容