軟件水平考試（初級(jí)）程序員下午（應(yīng)用技術(shù)）模擬試卷1（共76題）

軟件水平考試（初級(jí)）程序員下午（應(yīng)用技術(shù)）模擬試卷1（共9套）（共76題）軟件水平考試（初級(jí)）程序員下午（應(yīng)用技術(shù)）模擬試卷第1套一、流程圖題(本題共2題，每題1.0分，共2分。)閱讀以下應(yīng)用程序說(shuō)明和C程序，將C程序段中(1)～(6)空缺處的語(yǔ)句填寫(xiě)完整?！菊f(shuō)明】某大學(xué)征詢(xún)學(xué)生意見(jiàn)，從各學(xué)院預(yù)選的n(n≤60)位優(yōu)秀大學(xué)生中，評(píng)選出“十佳大學(xué)生”。以下【C程序】對(duì)各位學(xué)生選票進(jìn)行相關(guān)的統(tǒng)計(jì)、排序等處理。(1)各學(xué)院預(yù)選的優(yōu)秀大學(xué)生按1，2，…順序連續(xù)編號(hào)，每個(gè)編號(hào)用兩個(gè)字符表示，即01，02，…。(2)所回收的選票按以下格式存于文件source中，每行字符串對(duì)應(yīng)一張選票。其中，姓名占10個(gè)字符，學(xué)院名稱(chēng)占30個(gè)字符，大學(xué)生編號(hào)占20個(gè)字符。(3)對(duì)應(yīng)名次的大學(xué)生編號(hào)可以有空缺，但必須用00表示。(4)若編號(hào)超出規(guī)定范圍，或編號(hào)重復(fù)出現(xiàn)，按照廢票處理。(5)按選票中所列“十佳大學(xué)生”順序給出各名大學(xué)生的得分。評(píng)分標(biāo)準(zhǔn)如下：一二三四五六七八九十151297654321(6)按各位大學(xué)生得分?jǐn)?shù)由高到低順序排隊(duì)，并按以下格式列出“十佳大學(xué)生”排行表。名次大學(xué)生編號(hào)合計(jì)得分合計(jì)得票數(shù)若得分相同，則得票數(shù)多的在前；若得分和得票數(shù)都相同，則編號(hào)小的在前。以下【C程序】中所應(yīng)用到的函數(shù)fopen、fclose和fgets都是I/O程序庫(kù)中的函數(shù)。【C程序】#include＜stdio.h＞#definen60longinttn[n],td[n],score[n+1][10],order[n];chars[80];intmark[]=(15,12,9,7,6,5,4,3,2,1);FILE*fp,*fopen();Main(){intc,g,k,I,j,b[10];longinte,d,t,tt,dd;char*p;for(i=0;i＜=n;i++)for(j=0;j＜10;j++)score[i][j]=0;fP=fopen("source","r");/*以讀方式打開(kāi)文件source*/p=fgets(s,80,fp);/*讀fp所指文件的下一行字符串于s*/while(*p){g=l;k=0;p+=40;while(k＜10){c=((*p++)-'0')*10+((*p++)-'0');b[k++]=c)if(c＜=n){if(c){i=0;While((1));If((2)){g=0;break;}}else{g=0;break;}}If(g)For(i=0;i＜k;i++)If(b[i])(3);p=fgets(s,80,fP);}Fclose(fp);/*關(guān)閉fp所指文件*/For(i=1;i＜n;i++){For(t=0,d=0,j=0;j＜10;j++){t+=(e=score[i][j]);d+=e*mark[j];}tn[i-1]=t;td[i-1]=d;order[i-1]=i;}For(i=0;i＜n-1;i++){k=i;for(j=i+1;j＜n;j++)if((t=td[order[j]-1])＞(d=td[order[k]-1]))k=j;elseif(t==d){tt=(4);dd=(5);for(c=0;c＜10;c++)if((e=(6))＞0){k=j;break;}elseif(e＜0)break;}If(k!=i){t=order[k];order[k]=order[i];order[i]=t;}}For(i=0;i＜10;i++)Printf("%2d%2d%d%d\n",i+1,order[i],td[order[i]-1],tn[order[i]-1]));}}1、請(qǐng)將以上C程序段中，(1)～(6)空缺處的語(yǔ)句填寫(xiě)完整。標(biāo)準(zhǔn)答案：(1)c!=b[i++]，或其他等價(jià)形式(2)i＜k，或其他等價(jià)形式(3)score[b[i]][i]++，或其他等價(jià)形式(4)order[j](5)ordcr[k](6)score[tt][c]-score[dd][c]知識(shí)點(diǎn)解析：仔細(xì)閱讀本試題的程序說(shuō)明和【C程序】后，可得出評(píng)選“十佳大學(xué)生”的數(shù)據(jù)格式和算法。該C程序先讀入一行字符，進(jìn)行合法性檢查后再進(jìn)行選票統(tǒng)計(jì)；讀入所有選票后，再計(jì)算每個(gè)大學(xué)生的得分和選票數(shù)，最后進(jìn)行排序輸出。通常，閱讀一個(gè)C程序時(shí)，應(yīng)先明白程序中所用變量的含義，這對(duì)解題是很有幫助的。程序中所用變量的含義，除了可在程序說(shuō)明中了解之外，還可以通過(guò)程序中的輸入/輸出語(yǔ)句來(lái)獲知。對(duì)照程序說(shuō)明中給出的輸出次序可以了解到，數(shù)組order是用來(lái)存放第i名大學(xué)生的編號(hào)，數(shù)組td用來(lái)存放大學(xué)生的總分，數(shù)組tn用來(lái)存放大學(xué)生得到的選票總數(shù)。程序中用while(*p){...}語(yǔ)句所包含的程序段進(jìn)行合法性檢查并進(jìn)行統(tǒng)計(jì)。合法性檢查即排除非法的選票。指針p用于表示每次讀入的一行80個(gè)字符的首地址，語(yǔ)句“p+=40”使p指向每張選票的第40個(gè)字符，把每張選票上的大學(xué)生編號(hào)轉(zhuǎn)換成十進(jìn)制數(shù)c，并存入數(shù)組b中。由于每張選票最多可選十名，因此需用k＜10來(lái)進(jìn)行循環(huán)控制。由于(1)、(2)空缺處位于while(*p){...}的內(nèi)循環(huán)中，且由語(yǔ)句“g=0;break;”(即變量g為0時(shí)跳出該循環(huán))和語(yǔ)句“if(g)”可知，譬為合法性標(biāo)記，因此(1)、(2)空缺處所填寫(xiě)的語(yǔ)句完成選票的合法性檢查。由于非法選票有“編號(hào)超出規(guī)定范圍”和“編號(hào)重復(fù)出現(xiàn)”兩種，因此應(yīng)當(dāng)把當(dāng)前編號(hào)c和已處理過(guò)的編號(hào)b[i](i=0...k-1)進(jìn)行比較，從而來(lái)判斷是否滿(mǎn)足“編號(hào)超出規(guī)定范圍”，即(1)空缺處應(yīng)填入“c!=b[i++]”。另外，當(dāng)前編號(hào)c已存放在第k個(gè)字符中，當(dāng)i小于k時(shí)，即表示有編號(hào)重復(fù)，因此(2)空缺處應(yīng)填入“i＜k”。(3)在空缺處的“for(i=0;i＜k;i++)”循環(huán)程序段中，數(shù)組b[i]表示編號(hào)為b[i]的大學(xué)生，在該張選票上被評(píng)為i+1名；數(shù)組score[b[i]][i]表示編號(hào)為b[i]的大學(xué)生，被評(píng)為i+1名的選票有score[b[i]][i]張。當(dāng)一張選票上的10個(gè)編號(hào)都合法時(shí)，則應(yīng)把該選票上的數(shù)據(jù)存入數(shù)組score中，即對(duì)編號(hào)為b[i]的大學(xué)生所得的第i+1名選票加1，因此(3)空缺處應(yīng)填入“score[b[i]][i]++”。“fclose(fp);”之后的語(yǔ)句是對(duì)大學(xué)生的得分進(jìn)行統(tǒng)計(jì)工作，其結(jié)果分別存放在大學(xué)生編號(hào)數(shù)組Order、選票總數(shù)變量tn和總分變量td中，然后進(jìn)行排序。由語(yǔ)句的結(jié)構(gòu)可知，用變量k標(biāo)記得分最高的位置，即編號(hào)為order[k]的大學(xué)生得分為本次排序中最高，然后在外層for循環(huán)中進(jìn)行條件交換，由此可知，該排序采用的是選擇排序算法。在排序過(guò)程中如果得分相同，即程序中條件“if(t==d)”成立，則必須根據(jù)兩名大學(xué)生的得票情況進(jìn)行排序，得分名次在前、票數(shù)多者排在前面。(6)空缺處所填寫(xiě)的語(yǔ)句是對(duì)得票數(shù)相同的情況進(jìn)行排序處理，e為控制變量，用來(lái)存放編號(hào)為Order[j]和Order[k]的相同名次的得票數(shù)的比較結(jié)果，并根據(jù)該比較結(jié)果確定是否進(jìn)行位置交換。因此(4)空缺處所填寫(xiě)的內(nèi)容是“order[j]”；(5)空缺處所填寫(xiě)的內(nèi)容是“order[k]”；(6)空缺處所填寫(xiě)的內(nèi)容是“score[tt][c]—score[dd][c]”，即編號(hào)為j的大學(xué)生與編號(hào)為k的大學(xué)生的得票數(shù)之差。2、以上C程序段中，采用了哪種算法對(duì)大學(xué)生得分進(jìn)行排序?標(biāo)準(zhǔn)答案：選擇排序算法知識(shí)點(diǎn)解析：由【問(wèn)題1】要點(diǎn)解析可知，該C程序段采用選擇排序算法對(duì)大學(xué)生得分進(jìn)行排序處理。二、C語(yǔ)言題(本題共3題，每題1.0分，共3分。)3、閱讀以下應(yīng)用程序說(shuō)明和C程序，將C程序段中(1)～(7)空缺處的語(yǔ)句填寫(xiě)完整。【說(shuō)明】以下【C程序】的功能是，逐一從指定課程成績(jī)文件中讀入學(xué)生的考號(hào)和成績(jī)，對(duì)同一學(xué)生匯總他(她)的總成績(jī)，并按如圖6-14所示格式輸出名次(按總成績(jī)由高到底的順序)、總成績(jī)、同一名次的學(xué)生人數(shù)、同一名次學(xué)生的學(xué)號(hào)(按學(xué)號(hào)由小到大的順序)。該應(yīng)用程序約定學(xué)生學(xué)習(xí)課程不超過(guò)30種，課程成績(jī)文件的第1個(gè)數(shù)字就是課程號(hào)。統(tǒng)計(jì)過(guò)程中，同一課程號(hào)的成績(jī)文件不能重復(fù)輸入。該應(yīng)用程序采用鏈表結(jié)構(gòu)存儲(chǔ)學(xué)生的相關(guān)信息，鏈表中的每個(gè)表元對(duì)應(yīng)一位學(xué)生。在數(shù)據(jù)輸入過(guò)程中，形成一個(gè)按學(xué)號(hào)從小到大順序鏈接的有序鏈表。當(dāng)數(shù)據(jù)輸入結(jié)束后，程序按總成績(jī)從高到低，學(xué)號(hào)從小到大的順序?qū)︽湵砼判?。最后程序按指定格式輸出鏈表中的信息?！綜程序】#include＜stdio.h＞#defineM30#defineNLEN10typedefstructnode{intcur_s;/*最近輸入成績(jī)的科目*/Charno[NLEN];intscore；structnode*next;}NODE；ints[M],sp,ss,i,mark,order,C;FILE*fp;NODE*h,*U,*V,*p;Charfname[80],no[NLEN],ans;main(){for(h=NULL,sp=0;;){printf("輸入科目成績(jī)文件名(輸入aaaa表示強(qiáng)行結(jié)束)。\n")；while(1){scanf("%s",fname);if(strcmp(fname,"aaaa")==0)break;if((fp=fopen(fname,"r"))==NULL)printf("不能打開(kāi)文件%s,請(qǐng)重新輸入科目文件名。\n",fname);elsebreak;}if(strcmp(fname,"aaaa")==0)break;fscanf(fp,"%d",&ss);/*輸入科目號(hào)*/s[sp]=s;for(i=0;s[i]!=ss;1++);if((1)){printf("該科目的成績(jī)已輸入，請(qǐng)輸入別的科目成績(jī)文件。\n");continue;}sp++;while(fscanf(fp,"%s%d",no,&mark)==2){/*在鏈表中尋找最近輸入的學(xué)號(hào)*/for(v=h;v!=NULL&&strcmp(v-＞no,no)＜0;u=v,v=v-＞next)；if(v!=NULL&&strcmp(v-＞no,nb)==0){/*該生已有成績(jī)*/if(V-＞cur_s!=ss){/*該生的當(dāng)前科目成績(jī)是第一次輸入*/v-＞score+=mark;/*累計(jì)總成績(jī)*/v-＞cur_s=ss;}/*同一科目成績(jī)重復(fù)輸入，后輸入成績(jī)被忽略*/}else{p=(NODE*)malloc(sizeof(NODE));/*一位新的學(xué)生*/strcpy(p-＞no,no);p-＞score=mark;p-＞cur_s=ss;p-＞next=v;if(v==h)(2);else(3);}}fclose(fp);printf("還有科目成績(jī)文件要輸入嗎?(Y/N)");scanf("%c",&ans);if(ans==’N’||ans==’n’)break;}/*以下按總成績(jī)和學(xué)號(hào)對(duì)鏈表排序*/v=(NODE*)malloc(sizeof(NODE));v-＞next=h;h=v;while(v-＞next!=NULL){/*在余下的部分鏈表中找總成績(jī)高學(xué)號(hào)小的表元*/for(p=v,u=v-＞next;u-＞next!=NULL;u=u-＞next)if(u-＞next-＞score＞p-＞next-＞score||u-＞next-＞score==p-＞next-＞score&&strcmp(u-＞next-＞no,p-＞next-＞no)＜0)p=u;if(p!=v){u=p-＞next;p-＞next=(4);(5)=v-＞next;v-＞next=u;}v=v-＞next;}v=h;h=h-＞next;free(v);printf("名次總成績(jī)?nèi)藬?shù)學(xué)號(hào)\n");/*以下按格式要求輸出*/v=h;order=1;while(v!=NULL){for(c=1,u=v-＞next;u!=NULL&&u-＞score==v-＞score;(6);printf("%4d%7d%8d",order,v-＞score,c);for(order+=c,i=1;(7);v=v-＞next,i++){if(i＞1&&i%5==1)printf("\n%23c",’’);printf("%s",v-＞no);}printf("\n");}}標(biāo)準(zhǔn)答案：(1)i＜sp或i!=sp或其他等價(jià)的形式(2)h=p(3)u-＞next=p(4)u-＞next(5)u-＞next(6)C++,u=u-＞next(7)i＜=c，或c-!=0，或u!=v，或c-＞0，或c-或其他等價(jià)的形式知識(shí)點(diǎn)解析：通讀題干說(shuō)明和C程序之后可知，該C程序首先從指定的文件中輸入某個(gè)科目的學(xué)生學(xué)號(hào)和成績(jī)，并進(jìn)行合法性檢查，全部輸入完成后，按總成績(jī)進(jìn)行排序。程序采用鏈表結(jié)構(gòu)進(jìn)行存儲(chǔ)，最后按指定的格式輸出。該應(yīng)用程序首先輸入數(shù)據(jù)，(1)空缺處所在的for循環(huán)語(yǔ)句是對(duì)輸入的數(shù)據(jù)進(jìn)行檢查，數(shù)組s的作用是記錄已經(jīng)輸入的科目。當(dāng)輸入一個(gè)科目之后，就在數(shù)組s中進(jìn)行檢查處理。如果已有該科目，就提示“該科目的成績(jī)已輸入，請(qǐng)輸入別的科目成績(jī)文件”信息，要求用戶(hù)重新輸入。其中，if語(yǔ)句用于判斷是否有該科目，因此(1)空缺處所填寫(xiě)的內(nèi)容是“i＜sp”或“i!=sp”。接著在鏈表中尋找最近輸入的學(xué)號(hào)，循環(huán)語(yǔ)句“for(v=h;v!=NULL&&strcmp(v-＞no,no)＜0;u=v,v=v-＞next);”結(jié)束之后，通過(guò)if...else語(yǔ)句對(duì)循環(huán)的出口進(jìn)行判斷，(2)、(3)空缺處是對(duì)應(yīng)沒(méi)有該學(xué)生的成績(jī)(即是一位新學(xué)生)的情況，此時(shí)需要申請(qǐng)存儲(chǔ)空間，然后進(jìn)行賦值并把它插入到鏈表中。由于鏈表是排序的，因此需要判斷插入點(diǎn)是否是第1個(gè)節(jié)點(diǎn)。如果是第1個(gè)節(jié)點(diǎn)，就需要修改表頭節(jié)點(diǎn)的指針，因此(2)空缺處所填寫(xiě)的內(nèi)容是“h=p”，(3)空缺處所填寫(xiě)的內(nèi)容為“u-＞next=p”。接下來(lái)程序通過(guò)while循環(huán)對(duì)鏈表按總成績(jī)的高低和學(xué)號(hào)從小到大的順序進(jìn)行排序。通讀C程序可知，指針p所指向的節(jié)點(diǎn)應(yīng)在指針u所指向的節(jié)點(diǎn)之前(或等于)，指針v所指向的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)。在內(nèi)循環(huán)結(jié)束之后，若p!=v，則表示找到一個(gè)滿(mǎn)足排序條件的節(jié)點(diǎn)，此時(shí)就需要移動(dòng)指針。因此(4)、(5)空缺處所填寫(xiě)的內(nèi)容均為“u-＞next”。應(yīng)用程序的最后一個(gè)while循環(huán)語(yǔ)句，其功能是對(duì)排序后的鏈表按指定的格式進(jìn)行輸出。變量c的功能是計(jì)數(shù)器，用來(lái)記錄總成績(jī)相等的人數(shù)，因此(6)空缺處所填寫(xiě)的內(nèi)容的作用是使指針u下移，計(jì)數(shù)器加1，即該空缺處應(yīng)填入“c++,u=u-＞next”。變量Order的作用是記錄名次，而(7)空缺處所在的for循環(huán)語(yǔ)句的功能是，輸出成績(jī)相同的學(xué)生的學(xué)號(hào)。由于計(jì)數(shù)器c的初值為1，因此該for循環(huán)的結(jié)束條件為c=O或i=c。由此進(jìn)一步推知，(7)空缺處所填寫(xiě)的內(nèi)容是“c--!=0”或“i＜=c”或其他等價(jià)的形式。4、請(qǐng)閱讀以下技術(shù)說(shuō)明和C代碼，將程序段中(1)～(5)空缺處的語(yǔ)句填寫(xiě)完整?！菊f(shuō)明】著名的四色定理指出任何平面區(qū)域圖均可用4種顏色著色，使相鄰區(qū)域著不同的顏色。以下C程序?qū)o定的區(qū)域圖找出所有可能的不超過(guò)4種顏色的著色方案。該程序中用1～4分別表示4種顏色。要著色的N個(gè)區(qū)域用0～-1編號(hào)，區(qū)域相鄰關(guān)系用adj[][]矩陣表示，矩陣的i行j列的元素為1，表示區(qū)域i與區(qū)域了相鄰；矩陣的i行j列的元素為0，表示區(qū)域i與區(qū)域j不相鄰。數(shù)組color[]用來(lái)存儲(chǔ)著色結(jié)果，color[i]的值為區(qū)域i，所著顏色?！綜程序】#include＜stdio.h＞#defineN10voidoutput(intcolor[]){/*輸出一種著色方案*/inti;for(i=0;i＜N;i++)printf("%4d",color[i]);printf("\n");}intback(int*ip,intcolor[]){/*回溯*/intc=4;while(c==4){if(*ip＜=0)return0;--(*ip);c=(1);color[*ip]=-1;}returnc;}/*檢查區(qū)域i，對(duì)c種顏色的可用性*/intcolorOk(inti,intc,int[][N],intcolor[]){intj;for(j=0;j＜i;j++)if((2))return0;return1;}/*為區(qū)域i選一種可著色的顏色*/intselect(inti,intc,intadj[][N],intcolor[]){intk;for(k=c;k＜=4;k++)if(colorOK((3)))returnk;return0;}intcoloring(intadj[][N]){/*尋找各種著色方案*/intcolor[N],i,c,cnt;for(i=0;i＜N;i++)color[i]=-1;i=c=0;cnt=0;while(1){if((c=(4))==0{c=back(&i,color);if(c==0)returncnt;}else{(5);i++;ifi==N){output(color);++cnt;c=back(&i,color);}elsec=0;}}}voidmain()(intadj[N][N]={{0,1,0,1,1,1,1,1,1,1},{1,0,1,1,0,1,1,1,1,0},{0,1,0,1,0,1,1,0,1,1},{1,1,1,0,1,1,0,0,1,1},{1,0,0,1,0,1,0,0,0,0},{1,1,1,1,1,0,1,0,0,1},{1,1,1,0,0,1,0,0,1,0},{1,1,0,0,0,0,0,0,1,1},{1,1,1,1,0,0,1,1,0,1},{1,0,1,1,0,1,0,1,1,0},};printf("共有%d組解.\n",coloring(adj));}標(biāo)準(zhǔn)答案：(1)color[*ip](2)adj[i][j]!=0&&color[j]==c(3)I,k,adj,color(4)select(I,c+1,adj,color)(5)color[i]=c知識(shí)點(diǎn)解析：這是一道要求考生用C語(yǔ)言解決著色問(wèn)題的編程題。本題的解答思路如下。認(rèn)真閱讀程序說(shuō)明部分和所給出的C程序段可知，該C程序由6個(gè)函數(shù)組成，即主函數(shù)main()、輸出一種著色方案函數(shù)voidoutput(intcolor[])、回溯操作函數(shù)intback(int*ip,intcolor[])、檢查區(qū)域i對(duì)c種顏色的可用性函數(shù)intcolorok(intI,intc,int[][N],intcolor[]、為區(qū)域i選一種可著的顏色函數(shù)intselect(intI,intc,intadj[][N],intcolor[])和尋找各種著色方案函數(shù)intcoloring(intadj[][N])。1)空缺處在回溯操作子函數(shù)back()中，其中形參用指針指向記錄當(dāng)前考查區(qū)域號(hào)的變量。整個(gè)回溯過(guò)程是一個(gè)循環(huán)過(guò)程，當(dāng)循環(huán)條件成立時(shí)，進(jìn)行回溯。如果當(dāng)前區(qū)域*ip已是0號(hào)區(qū)域，則不再回溯，函數(shù)返回0值，表示已窮盡了所有可能方案。否則，當(dāng)前區(qū)域*ip減1，取出*ip區(qū)域的著色方案color[*ip]存放在c中，并置*ip區(qū)域?yàn)槲粗Ｈ绻?ip區(qū)域的著色方案不是最后一種顏色，則回溯結(jié)束，函數(shù)返回該區(qū)域原來(lái)的著色方案。因此(1)空缺處所填寫(xiě)的內(nèi)容是“color[*ip]”。2)空缺處在檢查區(qū)域i對(duì)c種顏色的可用性子函數(shù)colorok()中，根據(jù)程序的意義可以看出，(2)空缺處應(yīng)填入的是判斷該顏色不可取的條件，根據(jù)題干說(shuō)明，相鄰區(qū)域不能著相同的顏色，即和區(qū)域i相鄰的區(qū)域不能著c種顏色。而當(dāng)adj[i][j]為1時(shí)，表示區(qū)域j和區(qū)域i相鄰。如果區(qū)域j著c種顏色，則顏色不可取。所以(2)空缺處所填寫(xiě)的內(nèi)容是“adj[i][j]!=0&&color[j]==c”。3)空缺處在為區(qū)域i選一種可著的顏色子函數(shù)select()中，依次選定一種顏色，調(diào)用colorok()函數(shù)，測(cè)試該顏色是否可以著在i區(qū)域上。(3)空缺處應(yīng)為該函數(shù)colorok()填上實(shí)參“I,k,adj,color”，即(3)空缺處所填寫(xiě)的內(nèi)容是“I,k,adj,color”。4)(5)空缺處在尋找各種著色方案子函數(shù)coloring()中，該程序中定義了用于存放一種著色方案的數(shù)組color[]，并對(duì)數(shù)組進(jìn)行了初始化。該函數(shù)執(zhí)行部分的程序結(jié)構(gòu)是由一個(gè)while循環(huán)完成，循環(huán)的主體是一個(gè)if...else語(yǔ)句。該if...else體的else部分又包含一個(gè)if...else語(yǔ)句。在嵌套的內(nèi)層if...else語(yǔ)句中，當(dāng)if(i==N)中條件成立時(shí)，表示為每一區(qū)域都找到了合適的顏色，則該方案是成功的，之后輸出一種著色方案，再進(jìn)行回溯。如果有一個(gè)區(qū)域找不到合適的顏色，則該方案就是失敗的，這時(shí)也需要進(jìn)行回溯操作。由以上分析可知，尋找全部著色方案在while循環(huán)中進(jìn)行，每次循環(huán)首先是為i號(hào)區(qū)域?qū)ふ乙环N方案。因?yàn)閟elect()函數(shù)的功能就是為i區(qū)域選一種可能的顏色，同時(shí)可選的初始顏色是c+1號(hào)顏色，鄰接矩陣是adj[][]，選定的顏色存于數(shù)組color[]中，所以(4)空缺處所填寫(xiě)的內(nèi)容是“select(I,c+1,adj,color)”。根據(jù)if(c=select(I,c+1,adj,color))==0)能夠證實(shí)對(duì)函數(shù)back()的第一次調(diào)用肯定是在一種方案失敗的情況下，而緊接著的else后面的語(yǔ)句則顯然表示為區(qū)域i找到了一種可用的顏色c，所以應(yīng)將顏色c存儲(chǔ)在數(shù)組color[]中，即(5)空缺處所填寫(xiě)的內(nèi)容是“color[i]=c”。5、閱讀以下函數(shù)說(shuō)明和C代碼，將C程序中(1)～(5)空缺處的內(nèi)容補(bǔ)充完整?！菊f(shuō)明】對(duì)給定的字符集合及相應(yīng)的權(quán)值，采用哈夫曼算法構(gòu)造最優(yōu)二叉樹(shù)，并用結(jié)構(gòu)數(shù)組存儲(chǔ)最優(yōu)二叉樹(shù)。例如，給定字符集合{a,b,c,d}及其權(quán)值2、7、4、5，可構(gòu)造如圖6-15所示的最優(yōu)二叉樹(shù)，以及相應(yīng)的結(jié)構(gòu)數(shù)組Ht(如表6-14所示，其中數(shù)組元素Ht[0]不用)。結(jié)構(gòu)數(shù)組Ht的類(lèi)型定義如下：#defineMAXLEAFNUM20structnode{charch;/*掃當(dāng)前節(jié)點(diǎn)表示的字符，對(duì)于非葉子節(jié)點(diǎn)，此域不用*/Intweight；/*當(dāng)前節(jié)點(diǎn)的權(quán)值*/intparent;/*當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的下標(biāo)，為0時(shí)表示無(wú)父節(jié)點(diǎn)*/intlchild,rchild;/*當(dāng)前節(jié)點(diǎn)的左、右孩子節(jié)點(diǎn)的下標(biāo)，為0時(shí)表示無(wú)對(duì)應(yīng)的孩子節(jié)點(diǎn)*/)Ht[2*MAXLEAFNUM];用“0”或“廣標(biāo)識(shí)最優(yōu)二叉樹(shù)中分支的規(guī)則是：從一個(gè)節(jié)點(diǎn)進(jìn)入其左(右)孩子節(jié)點(diǎn)，就用“0”(或“1”)標(biāo)識(shí)該分支，如圖6-15所示。若用上述規(guī)則標(biāo)識(shí)最優(yōu)二叉樹(shù)的每條分支后，從根節(jié)點(diǎn)開(kāi)始到葉子節(jié)點(diǎn)為止，按經(jīng)過(guò)分支的次序?qū)⑾鄳?yīng)標(biāo)識(shí)依次排列，可得到由“0”、“1”組成的一個(gè)序列，稱(chēng)此序列為該葉子節(jié)點(diǎn)的前綴編碼。例如，圖6-15所示的葉子節(jié)點(diǎn)a、b、c、d的前綴編碼分別是110、0、111、10。函數(shù)voidLeafCode(introot,intn)的功能是：采用非遞歸方法，遍歷最優(yōu)二叉樹(shù)的全部葉子節(jié)點(diǎn)，為所有的葉子節(jié)點(diǎn)構(gòu)造前綴編碼。其中，形參root為最優(yōu)二叉樹(shù)的根節(jié)點(diǎn)下標(biāo)；形參n為葉子節(jié)點(diǎn)個(gè)數(shù)。在函數(shù)voidLeafCode(introot,intn)構(gòu)造過(guò)程中，將Ht[p].weight域用做被遍歷節(jié)點(diǎn)的遍歷狀態(tài)標(biāo)志。函數(shù)voidDecode(char*buff,introot)的功能是：將前綴編碼序列翻譯成葉子節(jié)點(diǎn)的字符序列，并輸出。其中，形參root為最優(yōu)二叉樹(shù)的根節(jié)點(diǎn)下標(biāo)；形參buff指向前綴編碼序列?！竞瘮?shù)4.1】char**HC;voidLeafCode(introot,intn){/*為最優(yōu)二叉樹(shù)中的n個(gè)葉子節(jié)點(diǎn)構(gòu)造前綴編碼，root是樹(shù)的根節(jié)點(diǎn)下標(biāo)*/intI,p=root,cdlen=0;charcode[20];Hc=(char**)malloc((n+1)*sizeof(char*));/*申請(qǐng)字符指針數(shù)組*/For(i=1;i＜=p;++I)Ht[i].weight=0;/*遍歷最優(yōu)二叉樹(shù)時(shí)用做被遍歷節(jié)點(diǎn)的狀態(tài)標(biāo)志*/While(p){/*以非遞歸方法遍歷最優(yōu)二叉樹(shù)，求樹(shù)中每個(gè)葉子節(jié)點(diǎn)的編碼*/If(Ht[p].weight==0){/*向左*/Ht[p].weight=1;If(Ht[p].lchild!=0){p=Ht[p].lchild;code[cdlen++]=’0’;}elseif(Ht[p].rchild==0){/*若是葉子節(jié)點(diǎn),則保存其前綴編碼*/Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));(1);strcpy(Hc[p],code);}}elseif(Ht[p].weight==1){/*向右*/Ht[p].weight=2;If(Ht[p].rchild!=0){p=Ht[p].rchild;code[cdlen++]=’1’;}}else{/*Ht[p].weight==2,回退/Ht[p].weight=0;p=(2);(3);/*退回父節(jié)點(diǎn)*/}}/*while.結(jié)束*/}【函數(shù)4.2】voidDecode(char*buff,introot){intpre=root,p;while(*buff!=’\0’){p=root;while(p!=0){/*存在下標(biāo)為p的節(jié)點(diǎn)*/pre=p;if((4))p=Ht[p].lchild;/*進(jìn)入左子樹(shù)*/elsep=Ht[p].rchild;/*進(jìn)入右子樹(shù)*/elsebuff++;/*指向前綴編碼序列的下一個(gè)字符*/}(5);printf("%c",Hr[pre].ch);}}標(biāo)準(zhǔn)答案：(1)code[cdlen]=’\0’或code[cdlen]=0(2)Ht[p].parent(3)—cdlen或其等價(jià)形式(4)*buff=’0’或其等價(jià)形式(5)buff—或其等價(jià)形式知識(shí)點(diǎn)解析：這是一道要求讀者在用哈夫曼算法構(gòu)造的最優(yōu)二叉樹(shù)上進(jìn)行編碼和譯碼的程序設(shè)計(jì)題。本題的解答思路如下。哈夫曼算法構(gòu)造最優(yōu)二叉樹(shù)的過(guò)程如下。1)根據(jù)給定的n個(gè)權(quán)值{W1,W2,W3,...Wn)構(gòu)成n棵二叉樹(shù)的集合F=(T1,T2,T3,...Tn)，其中每棵二叉樹(shù)引中只有一個(gè)帶權(quán)為Wi的根節(jié)點(diǎn)，其左、右子樹(shù)均為空。2)在F中選取兩棵根節(jié)點(diǎn)權(quán)值最小的樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且設(shè)置新的二叉樹(shù)的根節(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根節(jié)點(diǎn)的權(quán)值之和。3)在F中刪除這兩棵二叉樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。4)重復(fù)步驟2)和3)，直到F只含一棵樹(shù)為止。這棵樹(shù)便是最優(yōu)二叉樹(shù)。綜上所述，最優(yōu)二叉樹(shù)是從葉子到根構(gòu)造起來(lái)的，每次都是先確定一棵二叉樹(shù)的左、右子樹(shù)，然后再構(gòu)造出樹(shù)根節(jié)點(diǎn)，因此最優(yōu)二叉樹(shù)中只有葉子節(jié)點(diǎn)和分支數(shù)為2的內(nèi)部節(jié)點(diǎn)。若已知葉子的數(shù)目為n，則內(nèi)部節(jié)點(diǎn)數(shù)比葉子少1，因此整棵樹(shù)所需的存儲(chǔ)空間規(guī)模是確定的，可以采用數(shù)組空間來(lái)存儲(chǔ)最優(yōu)二叉樹(shù)。例如，給定字符集合{a,b,c,d)及其權(quán)值2、7、4、5，構(gòu)造最優(yōu)二叉樹(shù)的過(guò)程如圖6-19所示。由于算法中對(duì)構(gòu)成左、右子樹(shù)的二叉樹(shù)不進(jìn)行限定，因此用哈夫曼算法構(gòu)造出的最優(yōu)二叉樹(shù)的形態(tài)不是唯一的。另外，題干中已給出了存放最優(yōu)二叉樹(shù)的結(jié)構(gòu)數(shù)組Ht的類(lèi)型定義，以及存儲(chǔ)圖6-19所構(gòu)造出的最優(yōu)二叉樹(shù)的結(jié)構(gòu)數(shù)組Ht(見(jiàn)表6-14)。由于二叉樹(shù)中的節(jié)點(diǎn)最多只有兩個(gè)分支，若用“0”和“1”分別標(biāo)識(shí)最優(yōu)二叉樹(shù)中的左子樹(shù)分支和右子樹(shù)分支，那么從根節(jié)點(diǎn)開(kāi)始到葉子節(jié)點(diǎn)為止，按經(jīng)過(guò)分支的次序?qū)⑾鄳?yīng)標(biāo)識(shí)依次排列，可得到由“0”和“1”組成的一個(gè)序列，稱(chēng)此序列為該葉子節(jié)點(diǎn)的前綴編碼。例如，如圖6-15所示的最優(yōu)二叉樹(shù)葉子節(jié)點(diǎn)a、b、c、d的前綴編碼分別是110、0、111、10。當(dāng)最優(yōu)二叉樹(shù)的構(gòu)造完成后，每個(gè)節(jié)點(diǎn)的weight域就可挪做他用，在構(gòu)造哈夫曼編碼的過(guò)程中，weight域用做被遍歷節(jié)點(diǎn)的遍歷狀態(tài)標(biāo)志。從樹(shù)根出發(fā)，以非遞歸方式遍歷最優(yōu)二叉樹(shù)的方法是：先沿著樹(shù)根的左分支向葉子方向搜索，并用code[]記下所經(jīng)過(guò)的分支的標(biāo)識(shí)，同時(shí)用cdlen記錄節(jié)點(diǎn)的路徑長(zhǎng)度，一直到葉子節(jié)點(diǎn)為止，即可得到當(dāng)前正在訪問(wèn)的葉子的編碼。然后，從該葉子節(jié)點(diǎn)回退到其父節(jié)點(diǎn)F。若剛才是從F的左子樹(shù)回到F，則下一次應(yīng)進(jìn)入F的右子樹(shù)進(jìn)行遍歷；若是從F的右子樹(shù)回到F節(jié)點(diǎn)，則下一步應(yīng)繼續(xù)向F的父節(jié)點(diǎn)回退。由以上分析可知，對(duì)于節(jié)點(diǎn)F，遍歷過(guò)程中最多可能以3種不同的情況經(jīng)過(guò)該節(jié)點(diǎn)，因此要為F節(jié)點(diǎn)的weight域賦予不同的值進(jìn)行標(biāo)識(shí)。初始時(shí)weight=0，當(dāng)沿遍歷路徑到達(dá)該節(jié)點(diǎn)時(shí)其weight域值等于0，則進(jìn)入其左子樹(shù)分支進(jìn)行遍歷，并將weight置為1：若沿遍歷路徑到達(dá)該節(jié)點(diǎn)時(shí)其weight域值等于1，則說(shuō)明剛從其左子樹(shù)返回，下面應(yīng)進(jìn)入其右子樹(shù)進(jìn)行遍歷并將weight置為2；若沿遍歷路徑到達(dá)該節(jié)點(diǎn)時(shí)其weight域值等于2，則說(shuō)明剛從其右子樹(shù)返回，下面應(yīng)繼續(xù)向該節(jié)點(diǎn)的父節(jié)點(diǎn)回退，并將weight置為0。遍歷路線(xiàn)如圖6-20中箭頭方向所示。函數(shù)voidLeafCode(introot,intn)的功能是：采用非遞歸方法，遍歷最優(yōu)二叉樹(shù)的全部葉子節(jié)點(diǎn)，為所有的葉子節(jié)點(diǎn)構(gòu)造前綴編碼。由于在該函數(shù)(1)空缺處之后的語(yǔ)句“strcpy(Hc[p1,code);”，是進(jìn)行字符串的復(fù)制運(yùn)算，則需要對(duì)源串中的串結(jié)束標(biāo)志進(jìn)行設(shè)置，因此(1)空缺處所填寫(xiě)的語(yǔ)句是“code[cdlen]=’\0’”或“code[cdlen]=0”。(2)空缺處是從右子樹(shù)向父節(jié)點(diǎn)回退的處理，因此該空缺處所填入的內(nèi)容是“Ht[p].parent”。由于每向上層回退一次，節(jié)點(diǎn)的路徑長(zhǎng)度就會(huì)減1，因此(3)空缺處所填寫(xiě)的語(yǔ)句是“—cdlen”或其等價(jià)形式。函數(shù)voidDecode(char*buff,introot)的功能是：將前綴編碼序列翻譯成葉子節(jié)點(diǎn)的字符序列，并輸出。譯碼的過(guò)程是：從根出發(fā)，若編碼序列的當(dāng)前字符是“0”，則進(jìn)入左子樹(shù)分支，否則進(jìn)入右子樹(shù)分支，直到到達(dá)一個(gè)葉子節(jié)點(diǎn)時(shí)為止，此時(shí)葉子所表示的字符就是翻譯出的字符。若編碼序列還沒(méi)有結(jié)束，則重新從樹(shù)根出發(fā)，重復(fù)上述過(guò)程，直到將編碼序列結(jié)束。所以(4)空缺處所填寫(xiě)的語(yǔ)句是“*buff==’0’”或其等價(jià)形式。由于到達(dá)一個(gè)葉子節(jié)點(diǎn)時(shí)，超前讀入了一個(gè)編碼序列中的字符，因此(5)空缺處所填寫(xiě)的語(yǔ)句是“buff—”或其等價(jià)形式。三、VB題(本題共2題，每題1.0分，共2分。)6、以下是與VisualBasic開(kāi)發(fā)應(yīng)用有關(guān)的5個(gè)問(wèn)題。對(duì)每一個(gè)問(wèn)題，請(qǐng)將解答填入對(duì)應(yīng)欄內(nèi)。1.在VisualBasic中，工程文件、窗體文件和標(biāo)準(zhǔn)模塊文件的擴(kuò)展名是什么?請(qǐng)從下列選項(xiàng)中選擇：prg、prj、exe、vbp、form、frm、win、fra、std、bas、vbs、vbm2．設(shè)某窗體上有一個(gè)命令按鈕，其名稱(chēng)為CmdSave，運(yùn)行時(shí)該按鈕上顯示有“保存(S(下劃線(xiàn)))”字樣的信息。為使熱鍵Alt+S與該命令按鈕相關(guān)聯(lián)，應(yīng)該對(duì)按鈕CmdSave的Caption屬性設(shè)置什么樣的屬性值?3．設(shè)某窗口內(nèi)有一個(gè)圖像框Imagel，以及兩個(gè)命令按鈕“放大”和“縮小”。單擊“放大”按鈕就會(huì)使該圖像框的長(zhǎng)和寬都放大10%；單擊“縮小”按鈕就會(huì)使該圖像框的長(zhǎng)和寬都縮小10%(該圖像框的左上角不動(dòng))。請(qǐng)分別寫(xiě)出這兩個(gè)命令按鈕的單擊事件過(guò)程中的程序代碼。4．為使某個(gè)單選按鈕初始時(shí)默認(rèn)被選中，在開(kāi)發(fā)時(shí)應(yīng)怎樣做?5．若有語(yǔ)句Tmpval=MsgBox(“非法操作!”，vbOKCancel+vbCritical，“提示”)，請(qǐng)簡(jiǎn)要描述程序運(yùn)行時(shí)彈出的消息框的主要特征。標(biāo)準(zhǔn)答案：(1)工程文件的擴(kuò)展名是vbp，窗體文件的擴(kuò)展名是frm，標(biāo)準(zhǔn)模塊文件的擴(kuò)展名是bas。(2)按鈕的Caption屬性設(shè)置為“保存(&S)”。(3)“放大”按鈕單擊事件過(guò)程中的程序代碼：Imagel.Width=Imagel.Width*1.1Imagel.Height=Imagel.Height*1.1“縮小”按鈕單擊事件過(guò)程中的程序代碼：Imagel.Width=Imagel.Width*0.9Imagel.Height=Imagel.Height*0.9(4)將該單選按鈕的Value屬性值設(shè)置成True(5)消息框的標(biāo)題欄顯示“提示”；消息框中有一個(gè)出錯(cuò)標(biāo)記以及兩個(gè)命令按鈕，分別顯示“確定”和“取消”；消息框中顯示的信息為“非法操作!”。知識(shí)點(diǎn)解析：暫無(wú)解析7、閱讀以下應(yīng)用說(shuō)明及VisualBasic部分程序代碼，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】本應(yīng)用程序是一個(gè)小寫(xiě)數(shù)字轉(zhuǎn)換成大寫(xiě)格式的轉(zhuǎn)換器，其運(yùn)行窗口如圖5所示。窗口中有兩個(gè)標(biāo)簽(lblNumber和lblChinese)、兩個(gè)文本框(txtNnmber和txtChinese)和一個(gè)命令按鈕(cmdChange)。當(dāng)單擊按鈕cmdChange時(shí)，將文本框txtNumber中數(shù)字轉(zhuǎn)換成中文大寫(xiě)，并顯示在文本框txtChinese中。例如，在文本框txtNumber輸入0076845，單擊cmdChange按鈕，將在文本框txtChinese中顯示“柒萬(wàn)陸仟捌佰肆拾伍”。程序中調(diào)用的函數(shù)CChinse(StrdigitAsString)的功能是先刪除字符串的所有前導(dǎo)0，再調(diào)用函數(shù)Change(StrdigitAsString)，將數(shù)字字符串Strdigit轉(zhuǎn)換成中文大寫(xiě)格式。為了防止用戶(hù)在文本框txtNumber輸入非數(shù)字形式的字符，程序?qū)⒁钥兆址嫠斎氲姆菙?shù)字有形字符。【程序】PrivateFunctionTransfer(StrdigitAsString)AsString′完成小寫(xiě)向大寫(xiě)的轉(zhuǎn)換，這段代碼省略EndFunctionPrivateFunctionCChinese(StrdigitAsString)AsStringDimintLen,intCounterAsIntegerintLen=Len(Strdigit)IfintLen＞0Thenintcounter=0Do’過(guò)濾數(shù)字串Strdigit的前導(dǎo)0intcounter=intcounter+1LoopUntilMid(Strdigit,(1))intLen=(2)Strdigit=(3)(Strdigit,intLen)CChinese=Transfer(Strdigit)EndIfEndFunctionPrivateSubcmdChange_Click()txtChinese.Text=CChinese((4))’調(diào)用Cchinese函數(shù)EndSubPrivateSubtxtNumber_KeyPress(KeyAsciiAsInteger)SelectCaseKeyAscii’根據(jù)輸入字符的ASCII碼的值進(jìn)行判斷CaseKeyAscii＜32’保留輸入的控制字符Case48To57’保留輸入的數(shù)字字符CaseElse’其他情況以空字符代替(5)=0EndSelectEndSub標(biāo)準(zhǔn)答案：(1)intcounter,1(2)intLen-intCounter+1或Len(Strdigit)-intCounter+1(3)Right或Right$(4)txtNumber.Text(5)KeyAscii知識(shí)點(diǎn)解析：(1)～(3)空所在語(yǔ)句塊的功能是刪除過(guò)濾數(shù)字串Strdigit的前導(dǎo)0。(1)空所在Do……Loop循環(huán)是找到第一個(gè)非0的位置，循環(huán)變量為intcounter，即要判斷第intcounter個(gè)字符是不是0，因此(1)空處應(yīng)填寫(xiě)“intcounter,1”。從(3)空所在語(yǔ)句可以判斷(2)空所在語(yǔ)句是求出過(guò)濾數(shù)字串Strdigit的前導(dǎo)0后的數(shù)字長(zhǎng)度，因此(2)空處應(yīng)當(dāng)填寫(xiě)“intLen-intCounter+1”或“Len(Strdigit)-intCounter+1”。(3)空所在語(yǔ)句是取出過(guò)濾數(shù)字串Strdigit的前導(dǎo)。后的數(shù)字，需要填寫(xiě)這一操作的函數(shù)，因此(3)空處應(yīng)當(dāng)填寫(xiě)“Right”或“Right$”。(4)空處需要填寫(xiě)調(diào)用Cchinese函數(shù)的參數(shù)，程序要對(duì)小寫(xiě)數(shù)字進(jìn)行轉(zhuǎn)換，其內(nèi)容存放在文本框txtNumber中，因此(4)空處應(yīng)當(dāng)填寫(xiě)“txtNumber.Text”。(5)空所在語(yǔ)句是處理當(dāng)前輸入若不是數(shù)字或控制字符時(shí)，則將具ASCII碼值設(shè)置為0。因此(5)空處應(yīng)當(dāng)填寫(xiě)“KeyAscII”。四、C++題(本題共1題，每題1.0分，共1分。)8、閱讀以下說(shuō)明和C++程序，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。【說(shuō)明】以下程序的功能是計(jì)算正方體、球體和圓柱體的表面積和體積并輸出。程序由4個(gè)類(lèi)組成：類(lèi)cube、sphere和cylinder分別表示正方體、球體和圓柱體；抽象類(lèi)container為抽象類(lèi)，提供了兩個(gè)純虛擬函數(shù)surface_area()和volum()，作為通用接口?！綜++程序】#include＜iostream.h＞#definepi3.1416classcontainer｛protected:doubleradius;public:container(doubleradius){container::radius=radius;}virtualdoublesurface_area()=0;virtualdoublevelum()=0;};classcube:(1){//定義正方體類(lèi)public:cube(doubleradius):container(radius){};doublesurface_area(){return6*radius*radius;}doublevolum(){returnradius*radius*radius;}};classsphere:(2){//定義球體類(lèi)public:sphere(doubleradius):container(radius){};doublesurface_area(){return(3);}doublevolum(){returnpi*radius*radius*radius*4/3;}};classcylinder:(4){//定義圓柱體類(lèi)doubleheight;public:cylinder(doubleradius,doubleheight):container(radius){container::height=height;}doublesurface_area(){return2*pi*radius*(height+radius);}doublevolum(){return(5);}};voidmain(){container*p;cubeobj1(5);sphereobj2(5);cylinderobj3(5,5);p=&obj1;cout＜＜“正方體表面積”(＜＜p-＞surface_area()＜＜end1;cont＜＜“正方體體積”＜＜p-＞volume()＜＜end1;p=&obj2;cout＜＜“球體表面積”＜＜p-＞surface_area()＜＜end1;cout＜＜“球體體積”＜＜p-＞volume()＜＜end1;p=&obj3;cout＜＜“球體表面積”＜＜p-＞surface_area()＜＜end1;cout＜＜“球體體積”＜＜p-＞volume()＜＜end1;}標(biāo)準(zhǔn)答案：(1)publiccontainer(2)publiccontainer(3)4*pi*radius*radius(4)publiccontainer(5)pi*radius*radius*height知識(shí)點(diǎn)解析：類(lèi)cube、sphere和cylinder分別表示正方體、球體和圓柱體，它們都需要求各自的表面積和體積，而抽象類(lèi)container提供純虛擬函數(shù)surface_area()和velum()，所以類(lèi)cube、sphere和cylinder都以類(lèi)contain為基類(lèi)，公有繼承，所以(1)、(2)和(4)空應(yīng)填入“publiccontainer”。(3)空處為類(lèi)sphere中求表面積函數(shù)的返回值，所以根據(jù)球體表面積公式應(yīng)填入“4*pi*radius*radius”。(5)空處為類(lèi)cylinder中求圓柱體體積函數(shù)的返回值，所以根據(jù)圓柱體體積公式應(yīng)填入“pi*radius*radius*height”。五、JAVA題(本題共1題，每題1.0分，共1分。)9、閱讀以下說(shuō)明和Java代碼，將解答寫(xiě)入對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】下面程序的功能是找出所有三位數(shù)中，個(gè)、十、百位數(shù)字的立方和等于該數(shù)本身的三位數(shù)并顯示。在程序的每條橫線(xiàn)處填寫(xiě)一個(gè)適當(dāng)?shù)脑~或語(yǔ)句，使程序的功能完整。public(1)classcube_Root{publicstaticvoid(2)main(Stringargs[]){System.out.println("個(gè)、十、百位數(shù)字的立方和等于該數(shù)本身的三位數(shù)有：");for(intn=100;n＜1000;n++){inta,b,c;(3)b=n/10%10;(4)if((5))System.out.println(n);}}}標(biāo)準(zhǔn)答案：(1)class(2)main(3)a=n%l0(4)c=n/l00%10(5)a*a*a+b*b*b+c*c*c==n知識(shí)點(diǎn)解析：此處應(yīng)填類(lèi)聲明的關(guān)鍵字class。此處應(yīng)填Java程序的函數(shù)人口名main。取得整數(shù)n的個(gè)位數(shù)字。取得整數(shù)n的百位數(shù)字。當(dāng)個(gè)、十、百位數(shù)字的立方和等于該數(shù)本身時(shí)輸出。軟件水平考試（初級(jí)）程序員下午（應(yīng)用技術(shù)）模擬試卷第2套一、流程圖題(本題共1題，每題1.0分，共1分。)1、下面的流程圖，用來(lái)完成求字符串t在s中最右邊出現(xiàn)的位置。其思路是：做一個(gè)循環(huán)，以s的每一位作為字符串的開(kāi)頭和t比較，如果兩字符串的首字母是相同的，則繼續(xù)比下去，如果一直到t的最后一個(gè)字符也相同，則說(shuō)明在s中找到了一個(gè)字符串t；如果還沒(méi)比較到t的最后一個(gè)字符，就已經(jīng)出現(xiàn)字符串不等的情況，則放棄此次比較，開(kāi)始新一輪的比較。當(dāng)在s中找到一個(gè)字符串t時(shí)，不應(yīng)停止尋找(因?yàn)橐蟮氖乔髏在s中最右邊出現(xiàn)位置)，應(yīng)先記錄這個(gè)位置pos，然后開(kāi)始新一輪的尋找，若還存在相同的字符串，則更新位置的記錄，直到循環(huán)結(jié)束，輸出最近一次保存的位置。如果s為空或不包含t，則返回-1。注：返回值用pos表示。[問(wèn)題]將流程圖的(1)～(5)處補(bǔ)充完整。標(biāo)準(zhǔn)答案：(1)pos=-1(2)s[i]!=’\0’(3)s[j]=t[k](4)k＞0(5)pos=i；知識(shí)點(diǎn)解析：暫無(wú)解析二、C語(yǔ)言題(本題共3題，每題1.0分，共3分。)2、[說(shuō)明1]函數(shù)voidconvelt(chal*a,intn)是用遞歸方法將一個(gè)正整數(shù)n按逆序存放到一個(gè)字符數(shù)組a中，例如，n=123，在a中的存放為’3’、’2’、’1’。[C函數(shù)1]voidconvert(char*a，intn){inti;if((i=n/10)!=0;convert((1)，i)；*a=(2);}[說(shuō)明2]函數(shù)intindex(char*s，char*t)檢查字符串s中是否包含字符串t，若包含，則返回t在s中的開(kāi)始位置(下標(biāo)值)，否則返回-1。[C函數(shù)2]intindex(char*s，char*t){inti，j=0；k=0；for(i=0；s[i]!：’\0’；i++)(for((3)；(t[k]!=’\0’)&&(s[j]!=’\0’)&&((4))；j++，k++);if((5))return(i)；}return(-1)；}標(biāo)準(zhǔn)答案：(1)A+1(2)n%10+’\0’(3)j=i，k=0(4)t[k]==s[j](5)t[k]==’\0’或!t[k]知識(shí)點(diǎn)解析：函數(shù)1采用遞歸方法將一個(gè)正整數(shù)n按逆序存放到一個(gè)字符數(shù)組a中，遞歸調(diào)用為convert(a+1,i)，所以(1)“a+1”。按逆序輸出字符保存在數(shù)組a中為*a=n%10+’\0’，即(2)填“n%10+’\0’”。函數(shù)2檢查字符串s中是否含有字符串t是在for循環(huán)中實(shí)現(xiàn)的?？?3)應(yīng)填“j=i，k=0”。如果兩個(gè)字符串中含有相同的字符，則字符串s和字符串t都指向下一個(gè)字符，循環(huán)繼續(xù)，直到字符串t結(jié)束。所以空(4)應(yīng)填“t[k]=s[j]”，空(5)應(yīng)填“t[k]=’\0’”或“!t[k]”。3、函數(shù)Node*difference(A,B)用于求兩個(gè)集合之差C=A-B，即當(dāng)且僅當(dāng)e是A中的一個(gè)元素，但不是B中的元素時(shí)，e是C中的元素。集合用有序鏈表實(shí)現(xiàn)，用一個(gè)空鏈表表示一個(gè)空集合，表示非空集合的鏈表根據(jù)元素之間按遞增排列。執(zhí)行C=A-B之后，表示集合A和B的鏈表不變，若結(jié)果集合C非空，則表示其鏈表根據(jù)元素之值按遞增排列。函數(shù)append()用于在鏈表中添加節(jié)點(diǎn)。[C函數(shù)]typedefstructnode{intelement;structnode*link；}Node；Node*A，*B，*C；Node*append(last，e)Node*last；inte；{last-＞link=(Node*)malloc(sizeof(Node))；last-＞link-＞element=e；return(last-＞link)；}Node*difference(A,B)Node*A，*B；{Node*c，*last；C=last=(Node*)malloc(sizeof(Node))；while((1))if(A-＞element＜B-＞element){last=append(last，A-＞element);A=A-＞link：}elseif((2)){A：A-＞link；B：B-＞link;}elSe(3)；while((4)){last=append(last，A-＞element)；A=A-＞link：}(5);last=c；c=c-＞link;free(last)；return(c);}標(biāo)準(zhǔn)答案：(1)B-＞link(2)A-＞element==B-＞element(3)B=B-＞link(4)A＞link!=NULL(5)last-＞link=NULL知識(shí)點(diǎn)解析：本題用鏈表表示集合，通過(guò)比較鏈表的元素值判斷集合的元素之間的關(guān)系。第一個(gè)while循環(huán)的條件是鏈表B指針不指向空，即空(1)應(yīng)填“B-＞link”。由于A，B兩集合都是按遞增排列的，則如果A中的元素小于B中的元素，A中元素直接放入集合C中，集合A指向其下一個(gè)元素；如果A中的元素等于B中的元素，集合A，B分別指向下一個(gè)元素，即空(21填“A-＞element==B-＞element”；如果A中的元素大于B中的元素，集合B指向其下一個(gè)元素，即空(3)填“B=B-＞link”。第二個(gè)循環(huán)的條件是鏈表A指針不指向空時(shí)，將A中元素直接加入到C中，即空(4)填“A-＞link!=NULL”。將鏈表C最后節(jié)點(diǎn)指針指向空，即空(51填“l(fā)ast-＞link=NULL”。4、為參加網(wǎng)球比賽的選手安排比賽日程。設(shè)有n(n=2k)位選手參加網(wǎng)球循環(huán)賽，循環(huán)賽共進(jìn)行n-1天，每位選手要與其他n-1位選手賽一場(chǎng)，且每位選手每天賽一場(chǎng)，不輪空。試按此要求為比賽安排日程。設(shè)n位選手被順序編號(hào)為1,2,…,n。比賽的日程表是一個(gè)n行n-1列的表，i行j列的內(nèi)容是第i號(hào)選手第j天的比賽對(duì)手。用分治法設(shè)計(jì)日程表，就是從其中一半選手(2m-1位)的比賽曰程，導(dǎo)出全體(2m位)選手的比賽日程。從只有2位選手的比賽日程出發(fā)，反復(fù)這個(gè)過(guò)程，直到為n位選手安排好比賽日程為止。[C函數(shù)]#include＜stdio.h＞#defineMAXN64inta[MAxN+1][MAXN]；voidmain(){inttwoml，twom，il,j,m,k；printf("指定n(n=2的k次冪)位選手，清輸入k。\n")；scanf("%d"，&k);a[1][1]=2;/*預(yù)設(shè)2位選手的比賽日程*/a[2][1]=1；m=1;twoml=1;while(m＜k){(1)；twoml+=twoml;/*為2m位選手安排比賽日程*/(2)；/*填日程表的左下角*/for(il=twoml+l；il＜=twom；i1++)for(j=1；j＜=twoml-1;j++)a[i1][J]=a[i1-twoml][j]+twoml；(3)；for(i1=2;i1＜=twom；i1++)a[i1][twoml]=a[i1-1][twom1]+l;for(j=twoml+1；j＜twom；j++){for(i1=1；i1＜twoml;i1++)a[i1][j]=a[i1+1][j-1]；(4);}/*填日程表的右下角*/for(j=twoml；j＜twom;j++)for(ii=i；i1＜=twoml;i1++)(5)；for(i1=1;i1＜=twom;i1++){for(j=1；J＜twom;j++)printf("%4d"，a[i1][J]);printf("\n");}printf("\n");}}標(biāo)準(zhǔn)答案：(1)m++(2)twom+=2*twom1(3)A[1][twoml]=twom1+1(4)A[twom1][j]=a[1][j-1](5)A[a[i1][j][j]=i1知識(shí)點(diǎn)解析：分別有2位、4位、8位選手參加比賽時(shí)的日程表。若1～4號(hào)選手之間的比賽日程填在日程表的左上角(4行3列)，5～8號(hào)選手之間的比賽日程可填在日程表的左下角(4行3列)，而左下角的內(nèi)容可由左上角對(duì)應(yīng)項(xiàng)加上數(shù)4得到。至此剩下的右上角(4行4列)是為編號(hào)小的1～4號(hào)選手與編號(hào)大的5～8號(hào)選手之間的比賽安排日程。程序的思路是：由2位選手的比賽日程得到4位選手的比賽日程；依次得到8位選手的比賽日程。三、C++題(本題共1題，每題1.0分，共1分。)5、下而程序?qū)崿F(xiàn)十進(jìn)制向其他進(jìn)制的轉(zhuǎn)換。[C++程序]#include"ioStream．h"#include"math．h"#include＜conio．h＞typedefstructnode{intdata；node*next；}Node；classTransform{public：voidTrans(intd，inti)；//d為數(shù)字；i為進(jìn)制voidprint();private：Node*top；}；voidTransform::Trans(intd,inti){intm，n=0；Node*P；while(d＞0){(1);d=d/i；p=newNode；if(!n){P-＞data=m；(2)j(3);n++;}else{p-＞data=m；(4)；(5)；}}}voidTransform::print(){Node*P;while(top!=NULL){p=top；if(P-＞data＞9)cout＜＜data+55：elsecout＜＜data；top=p-＞next；deleteP;}}標(biāo)準(zhǔn)答案：(1)m=d%i(2)top=p(3)top-＞next=NULL(4)p-＞next=top(5)top=p知識(shí)點(diǎn)解析：本題考查C++編程，主要考查了鏈表的使用。所有的問(wèn)題只出在函數(shù)Trans中，它的功能是完成將十進(jìn)制數(shù)d轉(zhuǎn)換為任意進(jìn)制i的數(shù)，并存在數(shù)組中。函數(shù)中首先定義了一個(gè)指向鏈表節(jié)點(diǎn)的指針，然后開(kāi)始進(jìn)行轉(zhuǎn)換，進(jìn)制轉(zhuǎn)換應(yīng)該是一個(gè)很常見(jiàn)的問(wèn)題，就是不斷地求模運(yùn)算，所以(1)處應(yīng)填入“m=d%i”。然后，我們要把求模的結(jié)果保存到鏈表節(jié)點(diǎn)中，并使鏈表首指針指向該節(jié)點(diǎn)，節(jié)點(diǎn)中指向下一個(gè)節(jié)點(diǎn)的指針設(shè)為空，所以(2)處應(yīng)填入top=p，(3)處應(yīng)填入top-＞next=NULL。由于求模運(yùn)算是從低位到高位逐位求出的，所以在進(jìn)行完第二次求模運(yùn)算后，應(yīng)該將第二次運(yùn)算的結(jié)果放到鏈表首位，所以(4)處應(yīng)填入p-＞next=top，(5)處應(yīng)填入top=p。四、JAVA題(本題共1題，每題1.0分，共1分。)6、下面程序?qū)崿F(xiàn)十進(jìn)制向其他進(jìn)制的轉(zhuǎn)換。[Java程序]C1assNode{intdata；Nodenext；}classTransform{privateNodetop；publiCvoidprint(){NodeP；while(top!=null){P=top；if(P.data＞9)System.out.print((char)(p.data+55))；elseSystem.out.print(p.data);top=P.next;}}publicvoidTrans(intd,inti)(//d為數(shù)字;i為進(jìn)制intm；(1)n=false;NodeP;while(d＞0){(2);d=d/i;P=flewNode()；if((3)){P.data=m；(4);top=P；n=true；}else{p.data=m；(5)；toP=P；}}}}標(biāo)準(zhǔn)答案：(1)boolean(2)m=d%i(3)ln(4)top-＞next=null(5)p-＞next=top知識(shí)點(diǎn)解析：本題考查Java編程，主要考查了鏈表的使用。所有的問(wèn)題只出在函數(shù)Trans中，它的功能是完成將十進(jìn)制數(shù)d轉(zhuǎn)換為任意進(jìn)制i的數(shù)，并存在數(shù)組中。變量n被賦值為false，說(shuō)明n是布爾型變量，Java中布爾型變量關(guān)鍵字為boolean。故(1)應(yīng)填“boolean”。函數(shù)中首先定義了一個(gè)指向鏈表節(jié)點(diǎn)的指針(實(shí)為鏈棧)，然后開(kāi)始進(jìn)行轉(zhuǎn)換，進(jìn)制轉(zhuǎn)換應(yīng)該是一個(gè)很常見(jiàn)的問(wèn)題，就是不斷地求模運(yùn)算，所以(2)處應(yīng)填入“m=d%i”。然后，我們要把求模的結(jié)果保存到鏈棧中。對(duì)于鏈棧，第一個(gè)節(jié)點(diǎn)比較特殊，需要特殊處理，從if塊中的語(yǔ)句“n=tme”可知，此處正是處理第一個(gè)節(jié)點(diǎn)的特殊情況，故(3)應(yīng)填“!n”，(4)處應(yīng)填入“top-＞next=null”。這里采用的鏈棧，所以(5)處應(yīng)填入“p-＞next=top”。軟件水平考試（初級(jí)）程序員下午（應(yīng)用技術(shù)）模擬試卷第3套一、流程圖題(本題共1題，每題1.0分，共1分。)1、閱讀以下說(shuō)明和流程圖，回答問(wèn)題。[說(shuō)明]從鍵盤(pán)輸入一個(gè)高精度正整數(shù)n，去掉其中s個(gè)數(shù)字后按原左右次序再組成一個(gè)新的正整數(shù)。對(duì)給定的n，要尋找一種方案，使得余下的數(shù)字組成的新數(shù)最小。算法分析：每次刪除一個(gè)數(shù)字，選擇一個(gè)使余下的數(shù)最小的數(shù)字作為刪除對(duì)象。當(dāng)s=1時(shí)，在n中刪除哪一個(gè)數(shù)字能達(dá)到最小的目的?從左到右每相鄰的兩個(gè)數(shù)字比較：若出現(xiàn)減，郎左邊大于右邊，則刪除左邊的大數(shù)字；若不出現(xiàn)減，即所有數(shù)字全部升序，則刪除最右邊的大數(shù)字。當(dāng)s＞l(當(dāng)然小于n的位數(shù))，按上述操作一個(gè)一個(gè)刪除，刪除一個(gè)達(dá)到最小后，再?gòu)念^即從串首開(kāi)始，刪除第2個(gè)，依此分解為s次完成。若刪除不到s個(gè)后已無(wú)左邊大于右邊的減序，則停止刪除操作，打印余下串的左邊L-s個(gè)數(shù)字即可。(x為統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù)，m=1表示脫離循環(huán)，L為n的長(zhǎng)度)。[流程圖][問(wèn)題]將流程圖中的(1)～(5)處補(bǔ)充完整。標(biāo)準(zhǔn)答案：(1)s＞x&&m=0(2)1-x-L(3)a(i)=a(k+1)(4)m=1(5)for(i=li＜1-s；i++)知識(shí)點(diǎn)解析：暫無(wú)解析二、C語(yǔ)言題(本題共3題，每題1.0分，共3分。)2、閱讀下列程序說(shuō)明和C代碼，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。[說(shuō)明]函數(shù)Printprime(intUpBound)的功能是輸出1到UpBound以?xún)?nèi)的全體素?cái)?shù)。[函數(shù)2.1]voidPrintPrime(intUpBound)printf("2,");for(i=3;i＜UpBound;i+=2){intk=sqrt(i);for(j=3;j＜=k;(1))/*檢查i是否有3到k以入的奇因數(shù)*/if((2))break;fi((3))printf("%d",i);[函數(shù)2.2說(shuō)明]遞歸函數(shù)invert(inta[],intk)，intk)的功能是將數(shù)組a中的前k個(gè)元素逆置。[函數(shù)2.2]voidinvert(inta[],intk){intt;if((4)){invert((5));t=a[0];a[0]=a[k-1];a[k-l]=t;}}標(biāo)準(zhǔn)答案：(1)j+=2(2)i%j==0(3)j＞k(4)k＞1(5)a+1，k-2知識(shí)點(diǎn)解析：(1)～(3)由于(1)處循環(huán)只檢查i是否能被3到k以?xún)?nèi)的奇數(shù)所整除，因此循環(huán)增量應(yīng)該是2。并且一旦i被某個(gè)3到k以?xún)?nèi)的奇數(shù)整除，那么內(nèi)層for應(yīng)當(dāng)立即終止，此時(shí)j<=k。相反的，若內(nèi)層for循環(huán)結(jié)束后j>k，則表明i沒(méi)有3到k以?xún)?nèi)的奇因數(shù)，即i是一素?cái)?shù)，應(yīng)該輸出；(4)由于函數(shù)遞歸的終止條件是k不大于1，于是僅在k>1時(shí)需要繼續(xù)進(jìn)行遞歸；(5)為了將數(shù)組a的前k個(gè)元素a[0]、……、a[k-1]置逆，只需先將a[1]、……、a[k-2]這k-2個(gè)元素置逆，即調(diào)用invert(a+1，k-2)，再交換a[0]和a[k-1]的值即可。3、閱讀下列程序說(shuō)明和C程序，已知其輸出為“12345678910”。將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。[說(shuō)明]本程序包含的函數(shù)及其功能說(shuō)明如下：(1)函數(shù)first_insert()的功能是在已知鏈表的首表元之前插入一個(gè)指定值的表元；(2)函數(shù)reverse_copy()的功能是按已知鏈表復(fù)制出一個(gè)新鏈表，但新鏈表的表元鏈接順序與已知鏈表的表元鏈接順序相反；(3)函數(shù)Print_link()用來(lái)輸出鏈表中各表元的值；(4)函數(shù)free_link()用來(lái)釋放鏈表全部表元空間。[程序]#include＜stdio.h＞#include＜malloe.h＞typodefstructnode{intval;structnode*next;}NODE;voidfirst_insert(NODE**p,intv){NODE*q=(NODE*)malloe(sizeof(NODE));q->val=v;q-＞next=*p;/*為新表元賦值*/*p=(1);}NODE*reverse_copy(NODE*p){NODE*u;for(u=NULL;p!=NULL;p=p-＞next)first_insert((2));returnu;}voidprintlink(NODE*p){for(;(3))prinff("%d\t",p->val);printf("\n");}voidfree_link(NODE*p){NODE*u;while(p!=NULL){u=p->next;free(p);(4);}voidmain(){NODE*link1,*link2;inti;link1=NULL;for(i=1;i＜=10;i++)first_insert(&linkl,i);link2=reverse_copy(link1);(5);free_link(linkl);free_link(link2);}標(biāo)準(zhǔn)答案：(1)q(2)&u，p->val(3)p!=NULL；P=p->next(4)P=u(5)print_link(link2)知識(shí)點(diǎn)解析：(1)定義新表元并且給予賦值后需要更新鏈?zhǔn)字羔?，使其指向新表元?2)為了由空鏈表生成原來(lái)鏈表的逆序鏈，可以自鏈?zhǔn)妆碓狿起遍歷其每一個(gè)表元，調(diào)用first_insert函數(shù)將這個(gè)表元的值插入到新鏈表u中；(3)此處的循環(huán)是自鏈?zhǔn)妆碓猵起循環(huán)遣歷鏈表，循環(huán)結(jié)束條件是p!=NULL，每循環(huán)一次，將p指向下一個(gè)表元，即P=P->next；(4)釋放鏈表全部表元空間是自鏈?zhǔn)妆碓?，循環(huán)釋放每一個(gè)表元空間；(5)此處定義了程序的輸出。由于main函數(shù)中鏈表link1、link2分別為：“10987654321”及“12345678910”，因而此處應(yīng)該是調(diào)用print_link函數(shù)輸出link2。4、閱讀下列程序說(shuō)明和C代碼，回答問(wèn)題1～2。[說(shuō)明]本程序用古典的Eratosthenes的篩法求從2起到指定范圍內(nèi)的素?cái)?shù)。如果要找出2至10中的素?cái)?shù)，開(kāi)始時(shí)篩中有2到10的數(shù)，然后取走篩中的最小的數(shù)2，宜布它是素?cái)?shù)，并把該素?cái)?shù)的倍數(shù)都取走。這樣，第一步以后，篩子中還留下奇數(shù)3、5、7、9：重復(fù)上述步驟，再取走最小數(shù)3，宣布它為素?cái)?shù)，井取走3的倍數(shù)，于是留下5、7。反復(fù)重復(fù)上述步驟，直至篩中為空時(shí)，工作結(jié)束，求得2至10中的全部素?cái)?shù)。程序中用數(shù)組sieve表示篩子，數(shù)組元素sieve[i]的值為1時(shí)，表示數(shù)i在篩子中，值為-1時(shí)表示數(shù)i已被取走。[