2003年程序员下午试题及答案

试题一（15分，每空3分）
　　阅读下列说明和流程图，将应填入__(n)__的字句写在答题纸的对应栏内。
　　【流程图说明]
　　下面的流程图描述了对8位二进制整数求补的算法。
　　该算法的计算过程如下：从二进制数的低位（最右位）开始，依次向高位逐位查看，直到首次遇到“1”时，停止查看。然后，对该“1”位左面的更高位（如果有的话），逐位求反，所得的结果就是对原二进制数求补的结果。
　　例如：对二进制整数10101000求补的结果时01011000。
　　设8位二进制整数中的各位，从低位到高位，依次存放在整型数组BIT的BIT[1]～BIT[8]中。例如，二进制整数10101000存放在数组BIT后，就有BIT[1]＝0，BIT[2]=0,…,BIT[7]=0,BIT[8]=1。若流程图中存在空操作，则用NOP表示。

　　流程图中__(1)__处按“循环变量名：循环初值，增量，循环终值”格式描述。

试题二（15分，每空3分）
　　阅读下列说明和流程图，将应填入__(n)__的字句写在答题纸的对应栏内。
　　【函数说明】
　　函数sort（int a[]，int n）的功能时对数组a中的a[0]～a[n-1]这n个元素进行排序。排序过程如下：第一趟对所有的偶数下标p，比较a和a[p+1],若a＞a[p+1],则将两者交换；第二趟对所有的奇数下标q，比较a[q]和a[q+1]，若a[q]＞a[q+1]，则将两者交换；第三趟对偶数下标，第四趟对奇数下标，…，依次类推，直至整个数组元素有序排列为止。
　　【函数]
　　void sort (int a[],int n)
　　{
　 　　int I ,j,t,tag=1;
　　　for(j=0;j＜n;j++＝      {
　　　　for (I=__(1)__;i＜n-1;__(2)__＝     {
      　　　if (a＞a[I+1])     {t=a;a=a[I+1];a[I+1]=t;tag=0;}
　　　　}
　　　　tag++
　　　　if (__(3)__) break;
　　　}
　　}
　　对包含十个元素的数组a采用上述方法排序时，元素间的比较次数最少为__(4)__次，最多为__(5)__次。

试题三（15分，每空3分）
　　阅读下列说明和流程图，将应填入__(n)__的字句写在答题纸的对应栏内。
　　【函数说明]
　　函数movetoend（LinkedList La int i）的功能时：将线性表示A的第I个元素移到表尾。若移动成功，则返回0，否则返回-1。线性表A采用带头结点的单链表表示，La为表A的头指针，如下图所示。

　　链表结点的类型定义为：
　　typedef struct node {    
　　　int key;
　　　struct node *next;
　　}*LinkedList
　　【函数]
　　int movetoend(LinkedList La,int i)
　　{
　　　LinkedList p ,q,prep;
　　　Int k=1;
　　　P=La->next;prep=La;
　　　While(__(1)__){　　　　　　/*查找第I个元素并使指针p指向该结点*/
　　　　Prep=p; p=->next;k++
　　　}
　　　if (!p||k>i)return -1;
　　　if (__(2)__)　　　　　　　　/*第I个元素结点已经是表尾结点，则无需移动*/
　　　return 0;
　　　q=p;
　　　while(__(3)__)q=q-﹥next;　/*查找表尾并使q指向表尾结点*/
　　　__(4)__=p->next;
　　　p->next=NULL;
　　　__(5)__;
　　　return 0;
　　}

试题四（15分，每空3分）
　　阅读下列说明和流程图，将应填入__(n)__的字句写在答题纸的对应栏内。
　　【说明]
　　某单位举办了一场知识竞赛，参加竞赛的选手为300名，依次从1～300进行编号。竞赛时间为9：00～11：00。8道竞赛题目依次从‘A’～‘H’编号，选手可按任意次序答题，每完成一道题目，可立即提交答案。若答题正确（Y），则选择其他题目进行解答，否则，可继续做该题目或选择其他题目进行解答，直至竞赛结束。
　　选手提交答案的情况及判定结果由专人即时录入，录入的数据如下表1所示，对竞赛情况进行统计和排名的结果如表2所示。

表1：输入数据

表2：输出结果

　　统计和排名的规则如下：
　　1. 若选手X在竞赛时提交的题目P解答正确，2. 则解答该题目所用时间如下计算：
　　解答题目P的用时＝提交题目P正确的时间－竞赛的开始时间＋罚时
　　罚时＝提交题目P错误解答的次数×20
　　例如：表1中14号选手在10:27提交了题目A的正确解答，因此该选手正确解答该题目所用时间为87分钟，由于之前的两次提交错误解答，罚时为2×20＝40分钟，所以14号选手解答题目A的用时＝87＋40＝127（分钟）。
　　2．已经提交正确答案的题目再次提交时不再计算。 
　　3．竞赛结束时，选手的总用时为所有解答正确的题目用时累加所得，解答不正确的题目不计时。 
　　4．排名时，完成题目数量多者排名靠前；若完成的题目数相同，则用时少者排名靠前；若完成的题目数和所用时间均相等，则名次相同；完成题目数为0的选手不参加排名。 
　　函数void Statistic()的功能是：读取输入数据，进行统计、排名并输出结果。
　　＃define MAXN 300
　　typedef struct {
　　　int no;          /*选手编号*/
　　　int num;        /*完成的题目数量*/
　　　int time;        /*完成题目的总用时*/
　　　int d[8];        /*d用于记录提交第I个题目错误答案的次数*/
　　　int a[8];        /*a用于记录第I个题目是否已经提交正确答案*/
　　}Info;
　【函数】
　　void Statistic () {
　　　char ch,pass;
　　　int I,j,k,h,m,t,time,MaxIndex;
　　　Info R[MAXN+1];
　　　For(I=1;I<=MAXN;I++){         /*数组R的元素置初值0*/
　　　　R no=0; R num=0; R time=0;
　　　　For(j=0;j<8;j++){R.d[j]=0;R.a[j]=0;}
　　　}/*for*/
　　　MaxIndex=0;
　　　While(1) {
　　　　/*录入一名选手提交答案的信息（小时：分钟，选手编号，题目号，是否正确）*/
　　　　scanf(”%d:%d,%d,%c”,&h,&m,&k,&ch,&pass);
　　　　if (h= =0) break;
　　　　R[k] no=k;
　　　　Time=__(1)__;
　　　　If (isupper(ch))     ch=’a’+ch-‘A’;
　　　　If (pass !=’Y’&& pass !=’Y’) { R[k] d[ch-‘a’]++;continue;}
　　　　If (R[k] a[ch-‘a’]= =1) continue;
　　　　R[k] a[ch-‘a’]=1;
　　　　R[k] num++;
　　　　R[k] time+=__(2)__;
　　　　if (k>MaxIndex)  MaxIndex=k;
　　　}　　　　　/*while*/
　　　for (I=1;I<MaxIndex;I++) {　　/*选择排序*/
　　　　for(t=I,j=I+1;j<=MaxIndex;j++)
　　　　if (R[t] num<R[j] num || __(3)__ t=j;)
　　　　if(__(4)__) { R[0]=R[t];R[t]=R;R=R[0];}
　　　}　　/*for*/
　　　k=1;R[0]=R[1];
　　　for(I=1;I<=MaxIndex;I++)                 /*输出排名情况*/
　　　if(R[i]．num>0){ 
　　　　if (R num!=R[0] num || R time!=R[0] time) k++;
　　　　R[0]=__(5)__;
　　　　Printf(“%d: %3d %4d %5d ”,k,R no,R num R time);
　　　}　/*if*/
　　}　/*Statistic*/