初级程序员下午试题-75
(总分90, 做题时间90分钟)
试题一
1. 
阅读以下说明和流程图，回答问题将解答填入对应栏。
   [说明]
   下面的流程图，用来完成计算一组数组中的中值，其方法是：将数组中的一个值与其他值比较，并计算大于等于被比较数的数值的个数，以及小于等于被比较数的数值的个数，如果两数都大于n/2，则已经到了中值，否则继续之前的步骤。
   注：流程中循环开始的说明按照“循环变量：循环初值，循环终值，增量”格式描述；
   
   [问题]
   将流程图的(1)～(5)处补充完整。
    分值: 15
答案:j=-1；    (2) x[j]!=x[i]；    (3) count_lower++；
(4) count_lower＜(n/2.0)||count higher(n/2.0)；    (5) x[j];
[解析]
   本题目考查流程图。
   算法描述在题目中已经详细给出，通过阅读题目可知j用来定位数组中一个被比较的数，i用来循环遍历数组中所有的数。j应该从第0个数开始，又由于要执行一步j=j+1，所以(1)中应填入“j=-1”，counUligher++说明遍历的数比被比较的数大，即(2)中应填入“x[j]!=x[i]”相应的，(3)
中就应填入“count_lower++”，题目说明中已经指出，当count_lower和count_higher都大于n/2时，就说明到了中值，所以(4)应当填入“count_lower＜(n/2.0)][count_higher(n/2.0)”，最后，如果循环结束，则x[i]就应该是中值，(5)中应填入“x[j]”。
试题二
1. 
阅读以下函数说明和C语言函数，将应填入  (n)  处的字句写在对应栏内。
   [说明1]
   L为一个带头结点的循环链表。函数LinkList deletenode(LinkList L,int c)的功能是删除L中数据域data的值大于C的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。
   [C函数1]
   LinkList deletenode(LinkList L,int c)
   {LinkList Lc,P,pre;
   pre=L;
   p=  (1)  ;
   Lc=(LinkList)malloc(sizeof(Listnode));
   Lc-＞next=Lc;
   while(P!=L)
   if(p-＞data＞C){
     (2)  ;
     (3)  ;
   Lc-＞next=p;
   p=pre-＞next;
   }
   else{
   pre=p;
   p=pre-＞next;
   }
   return Lc;
   }
   [说明2]
   递归函数dec_to_k_2(int n,int k)的功能是将十进制正整数n转换成进制数，并打印。
   [C函数2]
   dec to k 2(int n,int k)
   {  if(n!=O){
   dec to k 2(  (4)  ,k);
   printf("%d",  (5)  );
   }
   }
    分值: 15
答案:pre-＞next或L-＞next  (2) pre-＞neXt=p-＞next  (3)　p-＞next=Lc-＞next
(4) n/k  (5) n%k
[解析]
   函数1是考察链表的删除和插入的操作。(1)空所在语句是对指针P赋初值，应填“pre-＞next”或“L-＞next”，通过下面的程序可以判断指针pre所指的结点是指针p所指结点前驱结点。(2)、(3)空所在的语句块是处理当指针p所指的结点是一个大于C的结点，则将该结点从链表L中删除，再将它插入到链表Lc中。分别填“pre-＞next=p-＞next”和“p-＞next=-Lc-＞next”  。
   函数2是一个递归函数，采用除k取余法。最开始得到余数作为k进制数的最低位，最后得到的余数作为k进制数的最高位。用递归法求解时，先将n/k转换成k进制，再输出n%k。因此(4)填“n/k”，(5)填“n%k”。
试题三
1. 
阅读以下函数说明和C语言函数，将应填入  (n)  处的字句写在对应栏内。
   [说明]
   函数int psort(int a[],int n)实现将含n个整数的数组a[]的不同元素按从小到大顺序存于数组a[]中。实现方法是从未确定的元素列中到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。
   [C函数]
   int psort(int a[],int n)
   {int i,J,k,P;
   for(i=0,k=0;i＜  (1)  ;i++){
   for(j=i+1,  (2)  ;j＜n; j++)
   if(a[p]＞a[j])
   p=j;
   if(p!=i){
   t=a[p]; while语句流程图的例题
   a[p]=a[i];
   a[i]=t;
   }
   if(  (3)  )  k++;
   else if(  (4)  ＜a[i])
     (5)  =a[i];
   }
   return  k;
   }
   int a[]={5,7,5,6,4,3,4,6,7};
   main()
   {int k,n;
   for(k=0;k＜(Sizeof a)/Sizeof(int);k++)
   printf("%5d",a[k]);
   printf ("\n\n");
   n=psort(a,(sizeof(a))/sizeof(int));
   for(k=0;k＜n;k++)
   printf("%5d",a[k]);
   printf("\n\n");
   }
    分值: 15
答案:n-1    (2) P=i    (3) k==0    (4) a[k-1]    (5) a[k++]
[解析]
   本程序排序方法是从未确定的元素列中到最小元素并将a[]的第i最小元素交换至a[i]位置。如该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。这是采用选择法对数组元素进行排序，因此空(1)填“n-1”，空(2)填“p=i”。若该最小元素比已确定的最后一个最小元素大，则将它接在已确定的元素序列的后面；否则，忽视该元素。因此，空(3)填“k==0”；而当a[k-1]＜a[i]时”，则a[k++]=a[i]；否则忽略元素a[i]。所以空(4)填“a[k-1]”空(5)填“a[k++]”。
试题四
1. 
阅读以下函数说明和C语言函数，将应填入  (n)  处的字句写在对应栏内。
   [说明]
   这是一个求解Josephus问题的函数。用整数序列1，2，3…，n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。Josephus问题描述，设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，…如此反复直到所有的人全部出局为止。
   [C函数]
   void Josephus(int A[],int n,s,m)
   (int i,j,k,temp;
   if(m==O){
   printf("m=0是无效的参数!\n");
   return;
   }
   for(i=0;i＜n;i++)    A[i]=i+1;  /*初始化，执行n次*/
   i=  (1)    /*报名起始位置*/
   for(k=n;k＞1;k-){
   if(  (2)  )  i=0;
   i=  (3)  /*寻出局位置*/
   if(i!=k-1){
   tmp=A[i];
   for(j=i;J＜k-1;j++)  (4)  ;
   (5)  ;
   }
   }
   for(k=0;k＜n/2;k++){
   tmp=A[k];A[k]=A[n-k+1];A[n-k+1]=tmp;
   }
   }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。