阅读下列算法说明和算法流程，将应填入（n)处的字句写在对应栏内。 【算法说明】 程序实现了常见的猜

阅读以下说明和流程图，回答问题，并将解答填入对应栏内。

【说明】

求解约瑟夫环问题。算法分析：n个士兵围成一圈，给他们依次编号，班长指定从第w个士兵开始报数，报到第s个士兵出列，依次重复下去，直至所有士兵都出列。

【流程图】

【问题】

将流程图中的(1)～(5)处补充完整。

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

【算法说明】

本算法按照算符优先关系，实现对算术四则混合运算表达式(可含小括号)的求值。处理对象是以字符串形式给出的、语法正确且不含变量的整数表达式。

算符优先关系见表5.1(§1，§2为按顺序出现的两个运算符)

说明：“”是假设的表达式开始符和结束符，不可用。

为实现算法，使用了两个堆栈分别寄存运算符和运算数(中间结果值)。算法基本思路如下：首先置操作数栈S1为空，表达式起始符“”设为运算符栈S2的栈底元素；依次读入表达式的各符号，若是数字字符则连接在一起转换为int型操作数进S1栈；若是运算符§2，则和S2栈的栈顶运算符51比较优先级后作相应操作，直至整个表达式求值结束。算法流程图5.1如下：

【问题】请将流程图补充完整。

●试题一

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

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

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

1. 【说明】

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

【算法】

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

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

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

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

阅读下列函数说明和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);

}

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

●试题四

阅读下列函数说明和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) ；

}

阅读下列说明和流程图，将应填入(n)处。

[流程图说明]

流程图1-1描述了一个算法，该算法将给定的原字符串中的所有前导空白和尾部空白都删除，但保留非空字符之间的空白。例如，原字符串“ File Name ”，处理后变成“File Name”。流程图1-2、流程图1-3、流程图1-4分别详细描述了流程图1-1中的框A，B，C。

假设原字符串中的各个字符依次存放在字符数组ch的各元素ch(1)，ch(2)，…，ch(n)中，字符常量KB表示空白字符。

流程图1-1的处理过程是：先从头开始找出该字符串中的第一个非空白字符ch(i)，再从串尾开始向前找出位于最末位的非空白字符ch(j)，然后将ch(i)，…，ch(j)依次送入 ch(1)，ch(2)，…中。如果原字符串中没有字符或全是空白字符，则输出相应的说明。在流程图中，strlen是取字符串长度函数。

[问题]在流程图1-1中，判断框P中的条件可表示为：

i＞(5)

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

【说明】

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

【流程图】