试题三

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

[函数3.1说明]

函数insert_sort(int a[]，int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。

直接插入排序法的基本思想是：将整个数组(count个元素)看成是由有序的(a[0]，…，a[i-1])和无序的(a[i]，…，a[Count-1))两个部分组成;初始时i等于1，每趟排序时将无序部分中的第一个元素a[i]插入到有序部分中的恰当位置，共需进行count-1趟，最终使整个数组有序。

[函数3.1]

void insert_sort(int a[] , int count)

{ int i, j, t;

for(i=1 ; i

{ /*控制a[i],……, a[count-1]的比较和插入*/

t=a[i];

j= (1) ;

while (j>=0 && t

{ /*在有序部分中寻找元素a[i]的插入位置*/

(2) ;

j--;

}

(3) ;

}

}

[函数3.2说明]

递归函数invert(int a[]，int k)将指定数组中的前k个元素逆置。

[函数3.2]

void invert(int a[] , int k);

{ int t;

if ( (4) ) {

invert( (5) );

t=a[0];

a[0]=a[k-1];

a[k-1]=t;

}

}

试题四

阅读下列程序说明和C代码，将应填入 (n) 处的字句写在答题纸的对应栏内。

[程序4说明]

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

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

[程序4]

#include

#define MAX 22500

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) ;

}

答案解析