阅读下列算法说明和算法，将应填入（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. 【说明】

实现连通图G的深度优先遍历(从顶点v出发)的非递归过程。

【算法】

第一步：首先访问连通图G的指定起始顶点v；

第二步：从V出发，访问一个与v(1)p，再从顶点P出发，访问与p(2)顶点q，然后从q出发，重复上述过程，直到找不到存在(3)的邻接顶点为止。

第三步：回退到尚有(4)顶点，从该顶点出发，重复第二、三步，直到所有被访问过的顶点的邻接点都已被访问为止。

因此，在这个算法中应设一个栈保存被(5)的顶点，以便回溯查找被访问过顶点的未被访问过的邻接点。

【说明】

本程序可以将字符串s1中出现的所有s2子串替换成s3，形成一个新串，但不破坏字符串s1。

【代码】

include＜stdio.h＞

include＜stdlib.h＞

include＜string.h＞

char*replace(char *s1, char *s2,char *s3)

{ char *p, *q, *r, *s; int |2，|3, i=0;

|2=strlen(s2);

|3=strlen(s3);

p=s1;

while((p=strstr(p,s2))!=NULL)

{ i++; /* 统计s2串出现的次数*/

(1);

}

i=(2);

s=r=(char*)malloc(i); /*分配动态内存存放新字符串*/

p=s1;

while(1)

{ q=strstr(p, s2); /* s2串是否在s1中出现，q是首次出现的位置*/

if(q!=NULL)

{ i=q-p;

(3);

r+=i;

(4);

r+=|3;

p=q+|2; /*将指向s1串的指针移到s2子串出现的位置后，

为下一次循环做好准备*/

}

else /*q为空，表示剩余的s1串中已经没有s2*/

{ (5);

break; /*终止循环*/

}

}

return(s); /*返回指向所形成的新串的指针*/

}

void main()

{ char *a="sabcababde", *b="ab", *c="efg", *d;

d=replace(a, b, c); printf("result=%s\n", d); free(d);

}

阅读下列算法说明和算法，将应填入(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．算法结束

【说明】

本程序用古典Eratosthenes；筛选法求从2起到指定范围内的素数。如果要找出2～10中的素数，开始时筛中有2～10的数，然后取走筛中最小的数2，宣布它是素数，并把该素数的倍数都取走。这样，第一步以后，筛子中还留下奇数3、5、7、9；重复上述步骤，再取走最小数3，宣布它为素数，并取走3的倍数，于是留下5、7。反复重复上述步骤，直到筛中为空时，工作结束，求得2～10中的全部素数。

【代码】

include ＜stdio.h＞

define MAX 22500

/*程序中用数组sieve表示筛子，数组元素sieve[i]的值为1时，表示数i在筛子中，值为-1时表示数i已被取走*/

main()

{ unsigned int i, range, factor, k;

int sieve[MAX];

printf("please input the range:");

scanf("%d", &range);/* range 指出在多大的范围内寻找素数*/

for(i=2; i＜=range; i++)

(1);

factor=2;

while (factor＜=range)

{ if((2)) /* 筛中最小数是素数 */

{ printf("%d\t", factor);

k=factor;

while (k＜=range) /*移走素数的倍数 */

{ (3);

k=(4);

}

}

(5);

}

}

【说明】

本程序利用非递归算法实现二叉树后序遍历。

【函数】

include＜stdio.h＞

include＜stdlib.h＞

typedef struct node{/*二叉树的结点数据结构类型*/

char data;

struct node *left;

struct node *right;

}BTREE;

void SortTreelnsert(BTREE **tree, BTREE *s)

{

if(*tree==NULL)*tree=s;

else

if(s-＞data＜(*tree)-＞data)

SortTreelnsert((1),s);

else if(s-＞data＞=(*tree)-＞data)

SortTreelnsert((2),s);

}

void TraversalTree(BTREE *tree)

{

BTREE *stack[1 000],*p;

int tag[1000],top=0;

p=tree;

do{

while(p !=NULL)

{

stack[++top]=p;

(3);

tag[top]=0; /*标记栈顶结点的左子树已进行过后序遍历*/

}

while(top＞0&&(4))/*栈顶结点的右子树是否被后序遍历过*/

{

p=stack[top--];

putchar(p-＞data);

}

if(top＞0)/*对栈顶结点的右子树进行后序遍历*/

{

(5);

tag[top]=1;

}

}while(top＞0);

}

void PrintSortTree(BTREE *tree)

{

if(tree !=NULL)

{

printSortTree(tree-＞left);

putchar(tree-＞data);

pdntSortTree(tree-＞right);

}

}

main()

{

BTREE *root=NULL, *node;

char ch;

ch=getchar();

while(ch !='')

{

node=(BTREE*)malloc(sizeof(BTREE));

node-＞data=ch;

node-＞left=node-＞right=NULL;

SortTreelnsert(&root, node);

ch=getchar();

}

PrintSortTree(root);

putchar('\n');

TraversalTree(root);

}

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

【流程图】

图1

下面的流程图描述了对16位二进制整数求补的算法。计算过程是：从二进制数的低位(最右位)开始，依次向高位逐位查看，直到首次遇到"1"时，停止查看。然后，对该"1"位左面的更高位(如果有的话)，逐位求反，所得的结果就是对原二进制数求补的结果。

例如：对二进制整数10111001 10101000求补的结果是01000110 01011000。

设16位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT［1］～BIT［16］中。例如，二进制整数10111001 10101000存放在数组BIT后，就有BIT1［1］=0，BIT［2］=0，……，BIT［15］=0，BIT［16］=1。

流程图(如图1所示)中 (1) 处按"循环变量名：循环初值，增量，循环终值"格式描述。若流程图中存在空操作，则用NOP表示。

阅读下列说明和C代码，将应填入（n）处的字句写在答题纸的对应栏内。说明：设某一机器由n个部件组成，每一个部件都可以从m个不同的供应商处购得。供应商j供应的部件i具有重量Wij和价格Cij。设计一个算法，求解总价格不超过上限cc的最小重量的机器组成。采用回溯法来求解该问题。首先定义解空间。解空间由长度为n的向量组成，其中每个分量取值来自集合{1，2，…，m}，将解空间用树形结构表示。接着从根节点开始，以深度优先的方式搜索整个解空间。从根节点开始，根节点成为活节点，同时也成为当前的扩展节点。向纵深方向考虑第一个部件从第一个供应商处购买，得到一个新节点。判断当前的机器价格（C11）是否超过上限（cc），重量（W11）是否比当前已知的解（最小重量）大，若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，根节点不再是扩展节点。继续向纵深方向考虑第二个部件从第一个供应商处购买，得到一个新节点。同样判断当前的机器价格（C11+C21）是否超过上限（cc），重量（W11+W21）是否比当前已知的解（最小重量）大。若是，应回溯至最近的一个活节点；若否，则该新节点成为活节点，同时也成为当前的扩展节点，原来的节点不再是扩展节点。以这种方式递归地在解空间中搜索，直到找到所要求的解或者解空间中已无活节点为止。C代码：下面是该算法的C语言实现。（1）变量说明n：机器的部件数。m：供应商数。cc：价格上限。w［］［］：二维数组，w［i］［j］表示第j个供应商供应的第i个部件的重量。c［］［］：二维数组，c［i］［j］表示第j个供应商供应的第i个部件的价格。bestW：满足价格上限约束条件的最小机器重量。bestC：最小重量机器的价格。bestX［］：最优解，一维数组，bestX［i］表示第i个部件来自哪个供应商。cw：搜索过程中机器的重量。cp：搜索过程中机器的价格。x［］：搜索过程中产生的解，x［i］表示第i个部件来自哪个供应商。i：当前考虑的部件，从0到n-1。j：循环变量（2）函数backtrack

A、蒙特卡洛算法

B、普里姆算法

C、舍伍德算法

D、拉斯维加斯算法

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。 INSERTION-SORT(A) 1. for i=2 to N 2. { key = A[i] ; 3. j =i-1; 4. While (j>0 and A[j]>key) do 5. { A[j+1]=A[j]; 6. j=j-1; } 7. A[j+1]=key; 8. } SELECTION-SORT(A) 1. for i=1 to N-1 2. { k=i; 3． for j=i+1 to N 4. { if A[j] <a[k] then k="j;" } 5. if> i then 6. { 7. temp =A[k]; 8. A[k]=A[i]; 9. A[i]=temp; 10. } 11. } BUBBLE-SORT(A) 1. for i=1 to N-1 2. { haschange=false; 3. for j=1 to N-i 4. { if A[j]>A[j+1] then 5. { temp =A[j]; 6. A[j]=A[j+1]; 7. A[j]=temp; 8. haschange=true; 9. } 10. } 11. if (haschange ==false) then break; 12. } 阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。

A、第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较

B、第4轮次，是将第1个元素至第20个元素之间的元素，相邻者进行比较

C、第8轮次，是将第20个元素至第12个元素之间的元素，相邻者进行比较

D、第11轮次，是将第20个元素至第1个元素之间的元素，相邻者进行比较