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

試題一（15分，每空3分）
　　閱讀下列說(shuō)明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
　　【流程圖說(shuō)明]
　　下面的流程圖描述了對(duì)8位二進(jìn)制整數(shù)求補(bǔ)的算法。
　　該算法的計(jì)算過(guò)程如下：從二進(jìn)制數(shù)的低位（最右位）開(kāi)始，依次向高位逐位查看，直到首次遇到“1”時(shí)，停止查看。然后，對(duì)該“1”位左面的更高位（如果有的話），逐位求反，所得的結(jié)果就是對(duì)原二進(jìn)制數(shù)求補(bǔ)的結(jié)果。
　　例如：對(duì)二進(jìn)制整數(shù)10101000求補(bǔ)的結(jié)果時(shí)01011000。
　　設(shè)8位二進(jìn)制整數(shù)中的各位，從低位到高位，依次存放在整型數(shù)組BIT的BIT[1]～BIT[8]中。例如，二進(jìn)制整數(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分）
　　閱讀下列說(shuō)明和流程圖，將應(yīng)填入__(n)__的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
　　【函數(shù)說(shuō)明】
　　函數(shù)sort（int a[]，int n）的功能時(shí)對(duì)數(shù)組a中的a[0]～a[n-1]這n個(gè)元素進(jìn)行排序。排序過(guò)程如下：第一趟對(duì)所有的偶數(shù)下標(biāo)p，比較a和a[p+1],若a＞a[p+1],則將兩者交換；第二趟對(duì)所有的奇數(shù)下標(biāo)q，比較a[q]和a[q+1]，若a[q]＞a[q+1]，則將兩者交換；第三趟對(duì)偶數(shù)下標(biāo)，第四趟對(duì)奇數(shù)下標(biāo)，…，依次類推，直至整個(gè)數(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;
　　　}
　　}
　　對(duì)包含十個(gè)元素的數(shù)組a采用上述方法排序時(shí)，元素間的比較次數(shù)最少為_(kāi)_(4)__次，最多為_(kāi)_(5)__次。

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

　　鏈表結(jié)點(diǎn)的類型定義為：
　　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個(gè)元素并使指針p指向該結(jié)點(diǎn)*/
　　　　Prep=p; p=->next;k++
　　　}
　　　if (!p||k>i)return -1;
　　　if (__(2)__)　　　　　　　　/*第I個(gè)元素結(jié)點(diǎn)已經(jīng)是表尾結(jié)點(diǎn)，則無(wú)需移動(dòng)*/
　　　return 0;
　　　q=p;
　　　while(__(3)__)q=q-﹥next;　/*查找表尾并使q指向表尾結(jié)點(diǎn)*/
　　　__(4)__=p->next;
　　　p->next=NULL;
　　　__(5)__;
　　　return 0;
　　}

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

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

表2：輸出結(jié)果

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