初級(jí)程序員下午試題

1、初級(jí)程序員下午試題-96（總分：105.00，做題時(shí)間：90分鐘）、試題一（總題數(shù)：1,分?jǐn)?shù)：15.00）閱讀以下說(shuō)明和算法，完善算法并回答問(wèn)題，將解答寫(xiě)在對(duì)應(yīng)欄內(nèi)。說(shuō)明假設(shè)以二維數(shù)組G1.m,1.n表示一幅圖像各像素的顏色，則Gi,j表示區(qū)域中點(diǎn)（i,j處的顏色，顏色值為0到k的整數(shù)。下面的算法將指定點(diǎn)（i0,j0）所在的同色鄰接區(qū)域的顏色置換為給定的顏色值。約定所有與點(diǎn)（i0,j0）同色的上、下、左、右可連通的點(diǎn)組成同色鄰接區(qū)域。例如，一幅8X9像素的圖像如圖1-1所示。設(shè)用戶指定點(diǎn)（3,5），其顏色值為0,此時(shí)其上方（2,5）、下方（4,5）、右方（3,6）鄰接點(diǎn)的顏色值都為0,因此這些

2、點(diǎn)屬于點(diǎn)（3,5）所在的同色鄰接區(qū)域，再?gòu)纳?、下、左、右四個(gè)方向進(jìn)行擴(kuò)展，可得出該同色鄰接區(qū)域的其他點(diǎn)（見(jiàn)圖1-1中的陰影部分）。將上述同色區(qū)域的顏色替換為顏色值7所得的新圖像如圖1-2所示。若點(diǎn)（i0,j0）的顏色值與新顏色值newcolor點(diǎn)（i0,j0）的顏色值roldcolor；創(chuàng)建棧S,若，則轉(zhuǎn)第七步；棧頂元素出棧r（x,y），并（3）;newcolor之后的矩陣G）:相同，則（!；并將點(diǎn)坐標(biāo)（i0,j0）入棧;1)2)3)4)若點(diǎn)（x,y-1）若點(diǎn)（x,y+1）若點(diǎn)（x-1,y）若點(diǎn)（x+1,y）在圖像中且在圖像中且在圖像中且在圖像中且Gx,y-1Gx,y+1Gx-1,yGx+1,

3、y)等于等于等于等于oldcolor,oldcolor,oldcolor,oldcolor,則(x,y-1)則(x,y+1)則(x-1,y)則(x+1,y)入棧入棧入棧入棧S;S;S；S:第六步：轉(zhuǎn)第七步：算函束。問(wèn)題是否可以將算法中的棧換成隊(duì)列?回答：（5）（分?jǐn)?shù)：15.00）填空項(xiàng)1:填空項(xiàng)1:填空項(xiàng)1:填空項(xiàng)1:填空項(xiàng)1:（正確答案：轉(zhuǎn)第七步）（正確答案：棧為空）（正確答案:newcolor7Gx,y）（正確答案：轉(zhuǎn)第三步）（正確答案：可以）算法輸入：矩陣G,點(diǎn)的坐標(biāo)（i0,j0），新顏色值newcolor。輸出：點(diǎn)（i0,j0）所在同色鄰接區(qū)域的顏色置換為算法步驟（為規(guī)范算法，規(guī)定該算

4、法只在第七步后結(jié)束第一步第二步第三步第四步第五步、試題二（總題數(shù)：1,分?jǐn)?shù)：15.00）閱讀以下說(shuō)明和C程序，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明下面的程序按照以下規(guī)則輸出給定名詞的復(fù)數(shù)形式： a.若名詞以“y”結(jié)尾，則刪除y并添加“ies”； b.若名詞以"s"、"ch”或"sh”結(jié)尾，則添加"es”； c.其他所有情況，直接添加“s”。C語(yǔ)言程序include<stdio.h>include<string.h>char*plural(char*word)intn;char*pstr;n=strlen(wo

5、rd);/*求給定單詞的長(zhǎng)度*/pstr=(char*)malloc(n+3);/*申請(qǐng)給定單詞的復(fù)數(shù)形式存儲(chǔ)空間*/if(!pstr|n<2)returnNULL;strcpy(pstr,word);/*復(fù)制給定單詞*/if(1)pstrn-1='i-'pstrn='e'pstrn+1='s'(2);elseif(pstrn-1='s'|pstrn-1='h'&&(3)pstrn='e'pstrn+1='s'pstrn+2='0'elsepst

6、rn='s'pstrn+1='0'；main()inti;char*ps;charwc910="chair","dairy","boss","circus","fly","dog","church","clue","dish");for(i=0;iv9;i+)ps=(5);printf("%s:%sn",wci,ps);/*輸出單詞及其復(fù)數(shù)形式*/free(ps);

7、/*釋放空間*/system("pause");(分?jǐn)?shù)：15.00)填空項(xiàng)1:(正確答案：pstrn-1='y')解析：填空項(xiàng)1:(正確答案：pstrn+2='/0')解析:填空項(xiàng)1:(正確答案:pstrn-2='c'|pstrn-2='s')填空項(xiàng)1:(正確答案:returnpstr)解析：填空項(xiàng)1:(正確答案:plufal(wci)解析：三、試題三(總題數(shù)：1,分?jǐn)?shù)：15.00)閱讀以下說(shuō)明和C函數(shù)，將應(yīng)填入(n)處的字句寫(xiě)在對(duì)應(yīng)欄內(nèi)。說(shuō)明若一個(gè)矩陣中的非零元素?cái)?shù)目很少且分布沒(méi)有規(guī)律，則稱之為稀疏矩陣。對(duì)m

8、行n列的稀疏矩陣M進(jìn)行轉(zhuǎn)置運(yùn)算后得到n行m列的矩陣MT,如圖3-1所示為了壓縮稀疏矩陣的存儲(chǔ)空間，用三元組(即元素所在的行號(hào)、列號(hào)和元素值、表示稀疏矩陣中的一個(gè)非零元素，再用一維數(shù)組逐行存儲(chǔ)稀疏矩陣中的所有非零元素也稱為三元組順序表)。例如，圖3-1所示的矩陣M相應(yīng)的三元組順序表如表3-1所示。其轉(zhuǎn)置矩陣MT的三元組順序表如表3-2所示。函數(shù)TransposeMatrix(MatrixM)的功能是對(duì)用三元組順序表表示的稀疏矩陣M進(jìn)行轉(zhuǎn)置運(yùn)算。對(duì)M實(shí)施轉(zhuǎn)置運(yùn)算時(shí)，為了將M中的每個(gè)非零元素直接存入其轉(zhuǎn)置矩陣MT三元組順序表的相應(yīng)位置，需先計(jì)算M中每一列非零元素的數(shù)目(即MT中每一行非零元素的數(shù)目)

9、，并記錄在向量num中；然后根據(jù)以下關(guān)系，計(jì)算出矩陣M中每列的第一個(gè)非零元素在轉(zhuǎn)置矩陣MT三元組順序表中的位置：cpot0=0cpotj=cpotj-1+numj-1)/*j為列號(hào)*/類(lèi)型ElemType,Triple和Matrix定義如下:typedefintElemType;typedefstruct/*三元組類(lèi)型*/intr,c;/*矩陣元素的行號(hào)、列號(hào)*/ElemTypee;/*矩陣元素的值*/Triple;typedefstruct/*矩陣的元組三元組順序表存儲(chǔ)結(jié)構(gòu)*/introws,cols,elements;/*矩陣的行數(shù)、列數(shù)和非零元素?cái)?shù)目*/TripledataMAXSIZE

10、;Matrix;C語(yǔ)言函數(shù)intTransposeMatrix(MatrixM)intj,q,t;int*num,*cpot;MatrixMT;/*MT是M的轉(zhuǎn)置矩陣*/num=(int*)malloc(M.cols*sizeof(int);cpot=(int*)malloc(M.cols*sizeof(int);if(!num|cpot)returnERROR;MT.rows=(1);/*設(shè)置轉(zhuǎn)置矩陣MT行數(shù)、列數(shù)和非零元素?cái)?shù)目*/MT.cols=(2);MT.elements=M.elements;if(M.elements>0)for(q=0;q<M.cols;q+)numq

11、=0;for(t=0;t<M.elements;+t)/*計(jì)算矩陣M中每一列非零元素?cái)?shù)目*/numM.datat.c+;/*計(jì)算矩陣M中每列第一個(gè)非零元素在其轉(zhuǎn)置矩陣三元組順序表中的位置*/(3);for(j=1;j<M.cols;j+)cpotj=(4/*以下代碼完成轉(zhuǎn)置矩陣MT三元組順序表元素的設(shè)置*/for(t=0;t<M.elements;t+)j=(5);/*取矩陣M的一個(gè)非零元素的列號(hào)存入j*/*q為該非零元素在轉(zhuǎn)置矩陣MT三元組順序表中的位置(下標(biāo))*/q=cpotj;MT.dataq.r=M.datat.c;MT.dataq.c=M.datat.r;MT.da

12、taq.e=M.datat.e;+cpotj;/*計(jì)算M中第j列的下一個(gè)非零元素的目的位置*/*for*/*if*/free(num);free(cpot);/*此處輸出矩陣元素，代碼省略*/returnOK;/*TransposeMatrix*/(分?jǐn)?shù)：15.00)填空項(xiàng)1:(正確答案：M.cols)填空項(xiàng)1:(正確答案：M.rows)填空項(xiàng)1:(正確答案：cpot0=0)填空項(xiàng)1:(正確答案：cpotj-1+numj-1)填空項(xiàng)1:(正確答案：M.datat.c)四、試題四(總題數(shù)：1,分?jǐn)?shù)：15.00)閱讀以下說(shuō)明和C語(yǔ)言函數(shù)，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明aNN模擬劇

13、找出劇場(chǎng)中則函數(shù)返回1,假設(shè)一個(gè)劇場(chǎng)有N*N個(gè)座位，顧客買(mǎi)票時(shí)可以提出任意有效的座號(hào)請(qǐng)求。下面用二維數(shù)組的功能是：在部分票已售出的情況下,若找到滿足要求的一個(gè)座位排列，0。場(chǎng)中的座位，aij等于0表示第i排第j列(0<i,j<N-1)的票尚未售出函數(shù)intFind(intaN,intR,int*row,int*col)的R*R個(gè)空座位，要求這些座位的排列形成一個(gè)正方形。(a) 并算出該正方形左上角的行、列號(hào)；若未找到，則返回例如，一個(gè)7X7個(gè)座位的劇場(chǎng)如下圖所示，已售出部分座位的劇場(chǎng)如下圖所示，圖中陰影部分表示已售出的座位，從圖(b)中找出的3X3正方形空座位如圖（c）中斜線區(qū)所示

14、。C語(yǔ)言函數(shù)intFind(intaN,intR,int*row,int*col)inti,j,k,c,t;intFOUND=0;for(i=0;!FOUND&&i<N-R+1;i+)/*從第0排開(kāi)始查找*/(1);while(jvN-R+1&&!FOUND)for(k=0;&&aij+k=0;k+);/*查找第i排連續(xù)的R個(gè)座位*/if(k>=R)/*找到第i排連續(xù)的R個(gè)空座位*/for(c=0;c<R;c+)/*查找其余的R*(R-1)個(gè)座位*/for(t=1;tvR;t+)if(a(3)j+c!=0)break;if(tv

15、R)break;/*for*/if(4)FOUND=1;/*if*/(5);/*while*/*fori*/if(FOUND)*row=i-1;*col=j-1;/*計(jì)算正方形區(qū)域的左上角坐標(biāo)*/return1;return0;（分?jǐn)?shù)：15.00）填空項(xiàng)1:（正確答案：j=0）填空項(xiàng)1:（正確答案：kvR）填空項(xiàng)1:（正確答案：i+t）填空項(xiàng)1:（正確答案：c>=R）解析：填空項(xiàng)1:（正確答案：j+或j+=1）解析：五、試題五（總題數(shù)：1,分?jǐn)?shù)：15.00）閱讀以下說(shuō)明和C函數(shù)，將應(yīng)填入（n）處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明某班級(jí)有N名學(xué)生，他們可根據(jù)自己的情況選修名稱和數(shù)量不盡相同的

16、課程。設(shè)選課程及成績(jī)用鏈表結(jié)構(gòu)存儲(chǔ)，如圖5-1所示。N等于6,學(xué)生信息、所程序中相應(yīng)的類(lèi)型定義如下:#defineN6structnodecharcname5;/*課程名*/intgrade;/*成績(jī)*/structnode*next;/*指針，指示某學(xué)生選修的下一門(mén)課程及成績(jī)*/;structstudentcharxh5;/*學(xué)號(hào)*/charname20;/*姓名*/structnode*link;/*指針，指示出選修的課程及成績(jī)鏈表*/stud_infon;Stud_info為一個(gè)全局?jǐn)?shù)組。函數(shù)func(charkc,int*num)的功能是統(tǒng)計(jì)選修了課程名為kc的學(xué)生的人數(shù)，并返回該課程

17、的平均成績(jī)(若無(wú)人選修該課程，則平均成績(jī)?yōu)?)，參數(shù)num帶回選修課程kc的學(xué)生人數(shù)。C語(yǔ)言函數(shù)doublefunc(charkc,int*num)inti,count=0,sum=0;/*count用于記錄選修課程名為kc的學(xué)生的人數(shù)*/doubleavg=0.0;structnode*p;for(i=0;ivN;i+)p=(1);/*取第土個(gè)學(xué)生所修課程鏈表的頭指針*/while(p)if(2)sum=(3);count+;break;/*if*/p=p->next;/*while*/(4);if(5)avg=(double)sum/count;/*計(jì)算平均成績(jī)*/returnavg

18、;/*func*/從下列的2道試題(試題六至試題七)中任選1道解答。如果解答的試題數(shù)超過(guò)1道，則題號(hào)小的1道解答有效。(分?jǐn)?shù)：15.00)填空項(xiàng)1:(正確答案:stud_infoi.link)填空項(xiàng)1:(正確答案:!strcmp(p->cname,kc)填空項(xiàng)1:(正確答案:sum+p->grade)填空項(xiàng)1:(正確答案:*num=count)填空項(xiàng)1:(正確答案:count!=0)解析：六、試題六(總題數(shù)：1,分?jǐn)?shù)：15.00)閱讀以下說(shuō)明和C+程序代碼，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明在下面的C+對(duì)弋碼中，類(lèi)SalesTicket能夠完成打印票據(jù)正文的功能，類(lèi)H

19、eadDecorator與FootDecorator分別完成打印票據(jù)的抬頭和腳注的功能。已知該程序運(yùn)行后的輸出結(jié)果如下所示，請(qǐng)?zhí)钛a(bǔ)該程序代碼中的空缺。這是票據(jù)的抬頭！這是票據(jù)正文！這是票據(jù)的腳注！這是票據(jù)的抬頭！這是票據(jù)的腳注！C+程序代碼#include<iostream>usingnamespacestd;classSalesTicketpublic;(1)printTicket()coutvv"這是票據(jù)正文！"<<endl;；classDecorator:publicSalesTicketSalesTicket*ticket;public:De

20、corator(SalesTicke*t)ticket=t;voidprintTicket()if(ticket！=NULL)ticket->printTicket();classHeadDecorator:publicDecoratorpublic:HeadDecorator(SalesTicket*t):(2)voidprintTicket()cout<<"這是票據(jù)的抬頭！"<<endl;Decorator:printTicket();classFootDecorator:publicDecoratorpublic:FootDecorato

21、r(SalesTicket*t):(3)voidprintTicket()Decorator:printTicket();cout<<"這是票據(jù)的腳注！"<<endl;voidmain(void)SalesTickett;FootDecoratorf(&t);HeadDecoratorh(4);h.printTicket();cout<<"FootDecoratora(NULL);HeadDecoratorb(5);b.printTicket();-"vvendl;(分?jǐn)?shù)：15.00)填空項(xiàng)1:(正確答案：vi

22、rtualvoid)解析：填空項(xiàng)1:(正確答案：Decorator(t)解析：填空項(xiàng)1:(正確答案：Decorator(t)解析：填空項(xiàng)1:（正確答案：&f）填空項(xiàng)1:（正確答案：&a）七、試題七（總題數(shù):1,分?jǐn)?shù)：15.00)閱讀以下說(shuō)明和Java程序代碼，將應(yīng)填入（n）處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。說(shuō)明在下面的Java程序代碼中，類(lèi)SalesTicket能夠完成打印票據(jù)正文的功能，類(lèi)HeadDecorator與FootDecorator分別完成打印票據(jù)的抬頭和腳注的功能。己知該程序運(yùn)行后的輸出結(jié)果如下所示，請(qǐng)?zhí)钛a(bǔ)該程序代碼中的空缺。這是票據(jù)的抬頭！這是票據(jù)正文！這是票據(jù)的腳注！這是票據(jù)的抬頭！這是票據(jù)的腳注！Java程序代碼publicclassSalesTicketpublicvoidprintTicket()System.out.println("這是票據(jù)正文!”);publicclassDecoratorextendsSal