2003年程序員下午試題及答案

試題一（15分，每空3分）
　　閱讀下列說明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對應(yīng)欄內(nèi)。
　　【流程圖說明]
　　下面的流程圖描述了對8位二進制整數(shù)求補的算法。
　　該算法的計算過程如下：從二進制數(shù)的低位（最右位）開始，依次向高位逐位查看，直到首次遇到“1”時，停止查看。然后，對該“1”位左面的更高位（如果有的話），逐位求反，所得的結(jié)果就是對原二進制數(shù)求補的結(jié)果。
　　例如：對二進制整數(shù)10101000求補的結(jié)果時01011000。
　　設(shè)8位二進制整數(shù)中的各位，從低位到高位，依次存放在整型數(shù)組BIT的BIT[1]～BIT[8]中。例如，二進制整數(shù)10101000存放在數(shù)組BIT后，就有BIT[1]＝0，BIT[2]=0,…,BIT[7]=0,BIT[8]=1。若流程圖中存在空操作，則用NOP表示。

　　流程圖中__(1)__處按“循環(huán)變量名：循環(huán)初值，增量，循環(huán)終值”格式描述。

試題二（15分，每空3分）
　　閱讀下列說明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對應(yīng)欄內(nèi)。
　　【函數(shù)說明】
　　函數(shù)sort（int a[]，int n）的功能時對數(shù)組a中的a[0]～a[n-1]這n個元素進行排序。排序過程如下：第一趟對所有的偶數(shù)下標p，比較a和a[p+1],若a＞a[p+1],則將兩者交換；第二趟對所有的奇數(shù)下標q，比較a[q]和a[q+1]，若a[q]＞a[q+1]，則將兩者交換；第三趟對偶數(shù)下標，第四趟對奇數(shù)下標，…，依次類推，直至整個數(shù)組元素有序排列為止。
　　【函數(shù)]
　　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;
　　　}
　　}
　　對包含十個元素的數(shù)組a采用上述方法排序時，元素間的比較次數(shù)最少為__(4)__次，最多為__(5)__次。

試題三（15分，每空3分）
　　閱讀下列說明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對應(yīng)欄內(nèi)。
　　【函數(shù)說明]
　　函數(shù)movetoend（LinkedList La int i）的功能時：將線性表示A的第I個元素移到表尾。若移動成功，則返回0，否則返回-1。線性表A采用帶頭結(jié)點的單鏈表表示，La為表A的頭指針，如下圖所示。

　　鏈表結(jié)點的類型定義為：
　　typedef struct node {    
　　　int key;
　　　struct node *next;
　　}*LinkedList
　　【函數(shù)]
　　int movetoend(LinkedList La,int i)
　　{
　　　LinkedList p ,q,prep;
　　　Int k=1;
　　　P=La->next;prep=La;
　　　While(__(1)__){　　　　　　/*查找第I個元素并使指針p指向該結(jié)點*/
　　　　Prep=p; p=->next;k++
　　　}
　　　if (!p||k>i)return -1;
　　　if (__(2)__)　　　　　　　　/*第I個元素結(jié)點已經(jīng)是表尾結(jié)點，則無需移動*/
　　　return 0;
　　　q=p;
　　　while(__(3)__)q=q-﹥next;　/*查找表尾并使q指向表尾結(jié)點*/
　　　__(4)__=p->next;
　　　p->next=NULL;
　　　__(5)__;
　　　return 0;
　　}

試題四（15分，每空3分）
　　閱讀下列說明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對應(yīng)欄內(nèi)。
　　【說明]
　　某單位舉辦了一場知識競賽，參加競賽的選手為300名，依次從1～300進行編號。競賽時間為9：00～11：00。8道競賽題目依次從‘A’～‘H’編號，選手可按任意次序答題，每完成一道題目，可立即提交答案。若答題正確（Y），則選擇其他題目進行解答，否則，可繼續(xù)做該題目或選擇其他題目進行解答，直至競賽結(jié)束。
　　選手提交答案的情況及判定結(jié)果由專人即時錄入，錄入的數(shù)據(jù)如下表1所示，對競賽情況進行統(tǒng)計和排名的結(jié)果如表2所示。

表1：輸入數(shù)據(jù)

表2：輸出結(jié)果

　　統(tǒng)計和排名的規(guī)則如下：
　　1. 若選手X在競賽時提交的題目P解答正確，2. 則解答該題目所用時間如下計算：
　　解答題目P的用時＝提交題目P正確的時間－競賽的開始時間＋罰時
　　罰時＝提交題目P錯誤解答的次數(shù)×20
　　例如：表1中14號選手在10:27提交了題目A的正確解答，因此該選手正確解答該題目所用時間為87分鐘，由于之前的兩次提交錯誤解答，罰時為2×20＝40分鐘，所以14號選手解答題目A的用時＝87＋40＝127（分鐘）。
　　2．已經(jīng)提交正確答案的題目再次提交時不再計算。 
　　3．競賽結(jié)束時，選手的總用時為所有解答正確的題目用時累加所得，解答不正確的題目不計時。 
　　4．排名時，完成題目數(shù)量多者排名靠前；若完成的題目數(shù)相同，則用時少者排名靠前；若完成的題目數(shù)和所用時間均相等，則名次相同；完成題目數(shù)為0的選手不參加排名。 
　　函數(shù)void Statistic()的功能是：讀取輸入數(shù)據(jù)，進行統(tǒng)計、排名并輸出結(jié)果。
　　＃define MAXN 300
　　typedef struct {
　　　int no;          /*選手編號*/
　　　int num;        /*完成的題目數(shù)量*/
　　　int time;        /*完成題目的總用時*/
　　　int d[8];        /*d用于記錄提交第I個題目錯誤答案的次數(shù)*/
　　　int a[8];        /*a用于記錄第I個題目是否已經(jīng)提交正確答案*/
　　}Info;
　【函數(shù)】
　　void Statistic () {
　　　char ch,pass;
　　　int I,j,k,h,m,t,time,MaxIndex;
　　　Info R[MAXN+1];
　　　For(I=1;I<=MAXN;I++){         /*數(shù)組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(chǎn)’]++;continue;}
　　　　If (R[k] a[ch-‘a(chǎn)’]= =1) continue;
　　　　R[k] a[ch-‘a(chǎn)’]=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*/