填空题在下面冒泡排序算法中填入适当内容，以使该算法在发现有序时能及时停止。 bubble（R） Rectype R[n]； {int i，j，exchang； Rectype temp； i=1； do {exchang=False； for（j=n；j>=¬¬i+1 ；j- -） if（R[j]

正确答案：B

参考答案：
　　[算法描述]：
　　typedef struct node
　　{ ElemType data;
　　struct node *prior,*next;
　　}node，*DLinkedList;
　　void TwoWayBubbleSort(DLinkedList la)
　　//对存储在带头结点的双向链表la中的元素进行双向起泡排序。
　　{int exchange=1; // 设标记
　　DLinkedList p,temp,tail;
　　head=la //双向链表头，算法过程中是向下起泡的开始结点
　　tail=null; //双向链表尾，算法过程中是向上起泡的开始结点
　　while (exchange)
　　{p=head->next; //p是工作指针，指向当前结点
　　exchange=0; //假定本趟无交换
　　while (p->next!=tail) // 向下(右)起泡，一趟有一最大元素沉底
　　if (p->data>p->next->data) //交换两结点指针，涉及6条链
　　{temp=p->next; exchange=1;//有交换
　　p->next=temp->next;temp->next->prior=p //先将结点从链表上摘下
　　temp->next=p; p->prior->next=temp; //将temp插到p结点前
　　temp->prior=p->prior; p->prior=temp;
　　}
　　else p=p->next; //无交换，指针后移
　　tail=p; //准备向上起泡
　　p=tail->prior;
　　while (exchange && p->prior!=head)
　　//向上(左)起泡，一趟有一最小元素冒出
　　if (p->dataprior->data) //交换两结点指针，涉及6条链
　　{temp=p->prior; exchange=1; //有交换
　　p->prior=temp->prior;temp->prior->next=p;
　　//先将temp结点从链表上摘下
　　temp->prior=p; p->next->prior=temp; //将temp插到p结点后(右)
　　temp->next=p->next; p->next=temp;
　　}
　　else p=p->prior; //无交换，指针前移
　　head=p; //准备向下起泡
　　}// while (exchange)
　　} //算法结束

正确答案：BCD

正确答案：C

正确答案：(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。

正确答案：D

参考答案：把待查记录看作枢轴，先由后向前依次比较，若小于枢轴，则从前向后，直到查找成功返回其位置或失败返回0为止。
　　[算法描述]
　　int index (RecType R[],int l,h,datatype key)
　　{int i=l,j=h;
　　while (i　　{ while (i<=j && R[j].key>key) j--;
　　if (R[j].key==key) return j;
　　while (i<=j && R[i].key　　if (R[i].key==key) return i;
　　}
　　cout<<“Not find”; return 0;
　　}//index

正确答案：A

正确答案：A
解析：直接插入排序、简单选择排序和冒泡排序最坏情况下计算时间可以达到O(n²)，而归并排序的时间最坏情况下可以达到O(nlogn)。而归并排序也是分治策略的一个典型应用。

正确答案：C