2002年程序员试卷（下）

试题二
      阅读下列函数说明和C代码，将应填入—匹l处的字句写在答题纸的对应栏内。
  [函数2．1说明]
      函数strcat(char *si，char *s2)是将字符串s2连接在字符串si之后，构成一个首指
  针为s1的字符串。
  [函数2.1]   
  void strcat(char *sl，char *s2)
  {  while(*s1!='\0')    ；
      (1)    ：
    for( ；  (2)  ；s1++，s2++)；
  }
[函数2．2说明]    ．
      本函数输入n(<1000)个整数到指定数组，求该数组中最大元素的值和此元素的下标，最大元素值以函数值返回，此元素的下标通过指针形参带回调用处。
  [函数2．2]
  #include<stdio．h>
  #define MAXLINE  1000
  int maxindex(int a[]，int *index)
  {  int i，n；
    do  {
        printf("Please input n＼n")；
        scanf("％d"，&n)；
    }while(  (3)  )；/*保证输入的n在限定范围内*/
    for(i=0 ; i<n ; i++)
        scanf("%d"，&a[i])；
    *index=0；
    for(i=1 ; i<n ; i++)
        if(  (4)  )  *index=i；
    return  (5)  ；
  }

试题三
    阅读下列函数说明和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<count ; i++)
{  /*控制a[i],……, a[count-1]的比较和插入*/
  t=a[i];
  j=  (1)  ;
  while (j>=0 && t<a[j])
  {  /*在有序部分中寻找元素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 <stdio.h>
#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)  ;
    }

试题五
    阅读下列函数说明和C代码，将应填入  (n)  处的字句写在答题纸的对应栏内。
设二叉树的结点数据类型为：
    typedef struct node{
      char data；
      struct node *left；
      struct node *right：
    }BTREE；
[函数5.1说明]
    函数void SortTreelnsert(BTREE **tree，BTREE*s)采用递归方法，将结点s插入以*tree为根结点指针的二叉排序树(二叉查找树)中。
[函数5.1)
    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)；
}
[函数5．2说明]
    函数void TraversalTree(BTREE *tree)用非递归方法，对以tree为根结点指针的二叉树进行后序遍历。
[函数5，2]
    void TraversalTree(BTREE *tree)
    {  BTREE *stack[1000]，*p；
      int tag[1000]，top=0；
      p=tree；
      do  {
          while(p!=NULL){
            stack[++top]=p；
                (3)    ；
            tag[hop]=0；  ／*标志栈顶结点的左子树已进行过后序遍历*／  ：
          }
          while(top>0 &&  (4)  ){  /* 栈顶结点的右子树是否被后序遍历过*／
              p=stack[top--];
              putchar(p->data)；
          }
          if (top>0) {    /*对栈顶结点的右子树进行后序遍历*／
                (5)    ；
            tag[top]=1；
          }
        }while(top>0)；
    }