2016年下半年下午程序員試題及答案與解析-軟考考試真題-案例分析

1、2016年下半年下午程序員考試試題-案例分析-答案與解析試題一（共15分）閱讀以下說明和流程圖，埴補流程圖中的空缺，將解答埴入答題紙的對應欄內(nèi)?！菊f明】設有整數(shù)數(shù)組Al：N（N>1）,其元素有正有負。下面的流程圖在該數(shù)組中尋找連續(xù)排列的若干個元素，使其和達到最大值，并輸出其起始下標K、元素個數(shù)L以及最大的和值M。例如，若數(shù)組元素依次為3,-6,2,4,-2,3,-1,則輸出"3,L=4M=7。該流程圖中考察了Al：N中所有從下標i到下標j（j>i）的各元素之和S,并動態(tài)地記錄其最大值M。流程圖】O M;循環(huán)開始jttt環(huán)開始注：循環(huán)開始框內(nèi)應給出循環(huán)控制變量的初值和終值，

2、默認遞增值為1,格式為：循環(huán)控制變量二初值，終值【參考答案】1、LN2、S+Aj3、S4、H+15、S【答案解析】要想在數(shù)組中尋找連續(xù)排列的若干個元素，使其和達到最大值，并輸出其起始下標K、元素個數(shù)L以及最大的和值M。那么，會將數(shù)組從第一個元素出發(fā)，依次比較A川，A+A，A+A+A，,Al+A+AN,然后再比較A，A+A，A+A+A，,A+A+AN,然后再比較A+A，A+A+A5,A+A4+AN,直到最后一個元素AN.按照這種邏輯，要使用兩個循環(huán)，且要保存之前求和項。一個是i循環(huán)，從1到N遞增，另一個是j循環(huán)，j表示的是求和項的最大下標值，那么j從i開始，旦要小于N。S+AjX不斷保留Ai+A

3、i+1+Aj的值，直到j循環(huán)結(jié)束。并將S的值與之前保存的M的值進行比較，如果S>M,則將S的值賦給M,并求出L值，在這里，i是最小下標值，j是最大下標值，那么L=H+1。如果SM,則跳出循環(huán)。試題二（共15分）閱讀以下代碼，回答問題：1至問題3,將解答埴入答題紙的對應欄內(nèi)?！敬a1】#include<stdio.h>voidswap（intxzinty）（intImp=x;x=y;y=imp;intmaim()(into二3,b=7;printf("al=%dbl=%dn",azb);Swap(Q,b);Printf("a2=%db2=%dn”，

4、Q,b)；return0;)代碼2#include<stdio.h>#defineSPACE空格字符Intmoin()(charstr128="Nothingisimpossible!intiznum=0zwordMQrk=0;for(i=0;stri;i+)lf(stri=SPACE)WordMark=0;elself(wordMark=0)wordMark=l;Mun+;Printf(“d/n”mum)retun0;代碼3#include<stdio.h>#defineSPACE“空格字符intcountStrs(char*);intmain()(char

5、str128="Nothingisimpossible!Printf('%d/n,(1)(str)return0;intcountStrs(char*p)intnum=0,wordMark=0;for(;(2)；p+)china_nejcerIf(3)=SPACE)wordMork=0;elseif(IwordMark)wordMark=1;+num)Return(4)【問題】（4分）寫出代碼1運行后的輸出結(jié)果。【參考答案】al=3bl=702=3b2=7【問題2】（3分）寫出代碼2運行后的輸出結(jié)果。【參考答案】3【問題3（8分）代碼3的功能與代碼2完全相同，請補充3中的空缺

6、，將解答寫入答題紙的對應欄內(nèi)?！緟⒖即鸢浮?、CountStr2、*p3、*p4、num【答案解析】此題考查C語言程序設計能力，要求掌握形參與實參，值傳遞與引用傳遞的區(qū)別1、本題考查函數(shù)中值傳遞與引用傳遞，在實參與形參傳遞過程中可以是值傳遞，值傳遞時，形參的改變不會影響實參，引用傳遞是地址的傳遞，實參將地址傳遞給形參時，形參的改變會影響實參的改變。在本題中的第一次輸出ab變量的值時，結(jié)果是直接輸出，所以chino_nejcerQ=3,bl=7,而在調(diào)用swop函數(shù)時，實參Q,b傳遞的是值傳遞，在函數(shù)swop（intx,inty）中形參x,y也是值類型，在函數(shù)swop內(nèi)部是交換兩個變量的值，交換

7、完畢后x二y,y二x,但這個改變不會影響實參。,b,所以第二次輸出。2,b2時，Q,b的值不變還是3,7,所以輸出結(jié)果是：01=3bl=7a2=3b2=72、本題是計算出字符數(shù)組中有多少個單詞，單詞之間是以空格''為標識，即遇到空格時變量wordMork二。，程序中再判斷wordMork是否等于0,若等于0,則變量workMork置為1,同時變量num是用于統(tǒng)計單詞個數(shù)，此時num加1,最后輸出num的值就是統(tǒng)計的單詞個數(shù)。程序運行夕土里日Q幻禾THOo3、本題是將上面的功能通過調(diào)用函數(shù)來完成的。第1處就應該直接埴寫調(diào)用函數(shù)的函數(shù)名，即countStrs,調(diào)用者將數(shù)組名作為實參

8、，數(shù)組名代表的是數(shù)組的首地址，所以這里是引用傳遞，函數(shù)countStrs的形參p是一個指針變量，它接收實參s什數(shù)組的首地址，這樣實參與形參都是指針變量。在函數(shù)countStrs內(nèi)部，定義兩個局部變量num用于統(tǒng)計個數(shù)，WodM0rk用于標識空格，在f。循環(huán)中，第2處應該設置終止條件，即*p,表示指針指向的內(nèi)容不為空，第3處是判斷當前的指向元素是否等于SPACE,即當前的*p是否是空格''，如果是則將標識變量WordMok等于0,否則變量num自增，最后函數(shù)應該返回num的值，所以4處應該埴num。答案是：1）countStrs2）pi!=,0,或者是pi3）pi4）num試題三

9、（共15分）閱讀以下說明和代碼，埴補代碼中的空缺，將解答埴入答題紙的對應欄內(nèi)?！菊f明】下面的程序利用快速排序中劃分的思想在整數(shù)序列中找出第k小的元素（即將元素從小到大排序 后，取第k個元素）。對一個整數(shù)序列進行快速排序的方法是：在待排序的整數(shù)序列中取第一個數(shù)作為基準值，然后根 據(jù)基準值進行劃分，從而將待排序的序列劃分為不大于基準值者（稱為左子序列）和大于基準值者（稱為 右子序列），然后再對左子序列和右子序列分別進行快速排序，最終得到非遞減的有序序列。例如，整數(shù)序列“ 19, 12,30, 11,7,53,78,25”的第3小元素為12。整數(shù)序列“ 19,12,7,30, 11, 11,7 ,

10、53. 78, 25, 7” 的第 3 小元素為 7O函數(shù) partition （int az int lowjnt high）以 cilow的值為基準,對 olow、alow+l x、ahigh進行劃分，最后將該基準值放入ai （low <ihigh）,并使得qIow、 alow+l x , . .都小于或等于。i,而。i+l、oi+2、. .、ohigh都大于 ”i。函 教 findkthElem（int ajnt startldxjnt endldxjnr k）在 astartldx s astartldx+l x .、 oendldx中 找出第k小的元素。china_nejcer

11、【代碼】#include <stdio.h>#include <stdlib.h>Int partition (int q , int lowz int high/ 對 alow.high進行劃分，使得。Uow.i中的元素都不大于。i+L.high中的元素。int pivot=alow ； pivot 表示基準元素Int i=lowj=high;while( ( 1) )While(i<j&&ai>pivot)+i;（2）； 基準元素定位return i ；)Int findkth日em ( int a , int startldx,int

12、endldx, int k )/ 整數(shù)序列存儲在 astartldx.endldx中，查找并返回第k小的元素。if (startldx<0 | | endldx<0startldx>endldxk<l | | k-l>endldxI|k-l<startldx)全國計算機技術(shù)與軟件專業(yè)技術(shù)資格（水平）、考試庫Return-1;/參數(shù)錯誤if(startldx<endldx)intloc=partition(a,startldx,endldx)/進行劃分，確定基準元素的if(loc-k-1)II找到第k小的元素return(3)；if(k-l<loc

13、)繼續(xù)在基準元素之前查找etumfindkthEIm(q,(4),k)；else/繼續(xù)在基準元素之后查找eturnHndkthElem(a,(5),k);returnastartldx;intmain()inti,k;intn;into二19,12,7,30,11,11,7,53,78,25,7;n=sizeof(o)/sizeof(int)計算序歹lj中的元素個數(shù)for(k=l;k<n+1;k+)for(i=0;i<n;i+)printf("n”);輸出序列中第k小的元素printf("elem%d=%dnkfindkth日em(o,0,n-l*);retur

14、n0；【參考答案】1、 !i=i或者i<i2、 ai=pivot3、 oloc4、 startldxjoc-l5、 loc+bendldx【答案解析】此題考查排序算法的應用，快速排序的思想是：通過一趟排序?qū)⒋判虻挠涗泟澐譃楠毩⒌膬刹糠郑渲幸徊糠钟涗浀年P鍵字均比另一部分記錄的關鍵字小，然后利用遞歸再分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。一趟排序的具體做法是：設兩個變量low和high,初值分別指向序列的第一個和最后一個，通常將第一個記錄的關鍵字設為Pivotkey,首先從high所指位置向前搜索，找到第一個關鍵字小于Pivotkey的記錄并互相交換，然后從low位置向后搜

15、索，找到第一個大于pivotkey的記錄并互相交換，重復這兩步直到low二high為止。本題是要找出第K個元素，要求將元素從小到大排序，然后取第K個元素。如數(shù)組中的元素是19,12,7,30,11,11,7,53,78,25,7,則第1,2,3個元素都是7,第4,5個元素是11,第6個元素是12,第11個元素是78,本題就是要找出前K個元素中第K個元素，K是不斷變化的，K的取值范圍是從1到數(shù)組長度，第K個元素也是不斷變化的。P。什ition函數(shù)是找到基準元素的位置，根據(jù)快速排序算法，循環(huán)判斷的條件是最小值和最大值不相等，即處應該埴歸或者i<j,當開始位置和結(jié)束位置不相等時則從數(shù)組的兩端分

16、別向中間掃描。掃描的方法是：依次比較數(shù)組的high與基準pivot的大小，如果chinQ.nejceraj>=pivot,則卜-,直到遇到第一個pivoQj,則停止移動，將。川賦值給。川,同時依次比較數(shù)據(jù)的low與基準pivot的大小，如果Qiv=pivot,貝lji+,直到遇到第一個pivotv0i,則停止移動，將。用賦值給。川，直到i等于1,則完成一次快速排序，此時找到了基準元素的位置，將基準元素移到正確的位置，賦給。川，并返回i的值，作為函數(shù)portion的結(jié)果。FindthElem函數(shù)是查找并返回第k小的元素，它實際上是將原來應該在快速排序中遞歸完成的功能換成了FindthEle

17、m函數(shù)去完成,形參k用來接收partition函數(shù)中的i,第3處上面的if(loc=k-l)判斷成立的時候表明此時找到了第k個的元素，所以直接返回數(shù)組第I。位置的元素，所以3處埴。loc,第4處，第5處是當沒有確定基準元素位置時，重復調(diào)用自己，重復調(diào)用時要判斷k與loc的大小，小于I。時，表明要向前移動，大于loc時，要向后移動，所以處4處埴stQtldx,loc-l,第5處埴loc+l,endldxo答案是：1)i!二j或者ivj2)。0二pivot3)aloc4)stortldxjoc-l5)loc+l,endldx,整個程序運行結(jié)果是：elen8=25ilen11=78試題四閱讀以下說明

18、和代碼，埴補代碼中的空缺，將解答埴入答題紙的對應欄內(nèi)?！菊f明】圖是很多領域中的數(shù)據(jù)模型，遍歷是圖的一種基本運算。從圖中某頂點V出發(fā)進行廣度優(yōu)先遍歷的過程是：訪問頂點V；訪問V的所有未被訪問的鄰接頂點W1,W2,Wk；依次從這些鄰接頂點W1,W2.,Wk出發(fā)，訪問其所有未被訪問的鄰接頂點；依此類推，直到圖中所有訪問過的頂點的鄰接頂點都得到訪問。顯然，上述過程可以訪問到從頂點v出發(fā)且有路徑可達的所有頂點。對于從V出發(fā)不可達的頂點u,可從頂點u出發(fā)再次重復以上過程，直到圖中所有頂點都被訪問到。例如，對于圖4-1所示的有向圖G,從。出發(fā)進行廣度優(yōu)先遍歷，訪問頂點的一種順序為。、bsc、e、f、doa

19、b c d e f 101000001!0101000000 010001000000 00設圖G采用數(shù)組表示法（即用鄰接矩陣Qrcs存儲），元素。定義如下：4-2所示，頂點。f對應的編號依次為05.因此，訪問頂點函數(shù)BFSTcverse（GraphG）利用隊列實現(xiàn)圖G的廣度優(yōu)先遍歷。相關的符號和類型定義如下：#defineMoxN：50/*圖中最多頂點數(shù)*/typedefint圖4-1的鄰接矩陣如圖接AdjM0trixMoxNM0xN；°的鄰頂點的順序為b,c,eotypedefstructintvexnum,edgenum;/*圖中實際頂點數(shù)和邊（?。?shù)*/AdjMatrixar

20、cs；/*鄰接矩陣*/）Graph；typedefintQ日emType；enumERROR=0;OK=I;代碼中用到的隊列運算的函數(shù)原型如表4-1所述，隊列類型名為QUEU。E表4-1實現(xiàn)隊列運算的函數(shù)原型全國計算機技術(shù)與軟件專業(yè)技術(shù)資格(水平)、考試庫chino_nejcer【代碼】intBFSTraverse(GrophG)圖G進行廣度優(yōu)先遍歷，圖采用鄰接矩陣存儲unsignedchar*visited；/visited用于存儲圖G中各頂點的訪問標志，。表示未訪問intv,w；u；QUEUEQQ;II申請存儲頂點訪問標志的空間，成功時將所申請空間初始化為0visited二(chor*)C

21、Qlloc(G.vexnum,sizeof(char);returnERROR;(2)；/初始化Q為空隊列for(v=0;v<G.vexnum;v+)HMsitedM)從頂點v出發(fā)進行廣度優(yōu)先遍歷prinH(“d”，v)；訪問頂點v并將其加入隊列visitedv=l;(3)；while(!isEmpty(Q)(4)；/出隊列并用u表示出隊的元素for(v=0;v<G.vexnum;w+)if(G.arcsuw!=0&&(5)w是u的鄰接頂點且未訪問過printf("%dn,w);/訪問頂點wvisitedw=l；EnQueue(&Q,w);)fre

22、e(visited);china_nejcer )/BFSreturnOK;Traverse【參考答案】1、 visited二二NULL2、 lnitQueue(&Q)3、 EnQueue(&Q,v)4、 DeQueue(&Q,&u)5、 visitedw=0【答案解析】本題考查圖的遍歷問題，圖的存儲有鄰接矩陣和鄰接鏈表兩種，圖的遍歷有深度遍歷和廣度遍歷兩種，廣度遍歷是盡可能進行橫向搜索，即最先訪問的頂點的鄰接點也先被訪問，為此需要引入隊列來保存已訪問過的頂點序列，即每當一個頂點被訪問后，就將其放入隊中，當隊頭頂點出隊時，就訪問其未被訪問的鄰接點并令這些鄰接頂點

23、入隊。在廣度優(yōu)先遍歷中，每個頂點至多進行一次隊列。題目中已經(jīng)提供隊列的有關操作，如初始化隊列，入隊，出隊等。程序中第1處應該埴visit6d二二NULL,表示分配內(nèi)存函數(shù)colloc分配內(nèi)存空間是否成功，如果失敗，則程序返回。第2處埴lnitQueue(&Q),表示初始化隊列，函數(shù)InitQueue的形參是一個指針變量，接收一個指向QUEUE的變量，所以實參應該是一個地址，即&Q,第3處是頂點v入隊，入隊函數(shù)EnQueue有兩個形參，一個是指針變量*Q,個是元素qe,所以此處埴EnQueue(&Q,v),第4處是出隊，出隊函數(shù)也有兩個參數(shù)，一個是指向隊列的指針變量*Q,

24、另一個參數(shù)是int類型的指針變量*te,表示要通過參數(shù)為帶回出隊的元素，即知道是哪個元素出隊了，所以實參在傳遞時應該使用引用傳遞，因此第4處埴DeQueue(&Q,&u),第5處是判斷圖Gares中w頂點是否被訪問過，visited數(shù)組是用于存儲圖G中各頂點的訪問標志，0表示未訪問，1表示已訪問，此處是要判斷w頂點是否被訪問過，即visitedw是否等于0,所以第5處埴visitedw=0,如果沒有訪問過,則將w頂點置為1,并入隊。試題五閱讀以下說明和JQV。程序，埴補代碼中的空缺，將解答埴入答題紙的對應欄內(nèi)?！菊f明】以下Java代碼實現(xiàn)一個簡單的聊天室系統(tǒng)(ChotRoomS

25、ystem),多個用戶(User)可以向聊天室 (ChotRoom)發(fā)送消息，聊天室將消息展示給所有用戶。類圖如圖5-1所示。User-nAn)e: Strin j _ 一今 *User() jetName()sendMeasageOChatfloom SystemChatRoomstartup。 MOJqvq代碼】classChatRoompublicstaticvoidshowMessage(Useruser,Strmgmessage)System.out.println(,+user.getNQme()+':"+message);classUserprivateStri

26、ngname;publicStringgetName()returnname;publicvoidsetName(Stringname)=name;publicUserfStringname)(1)=name；publicvoidsendMessagefStringmessage)(2)(fhiszmessage);publicclassCh0t:RoomSystempublicvoidstartup!)Userzhang=newUser(,JohnH);Userli=newUserf'Leo")；chino.nejcerzhang.sendMessage(

27、NHi!Leo!");1i.sendMessagef'Hi!John!")；publicvoidjoin(Useruser)(3)("HelloEveryone!Iamu+user.getName();)publicstaticvoidmain(Stringargs)ChotRoomSystemcrs=(4);Crs.startup();Crs.join(5)("Wayne")；)/*程序運行結(jié)果：John：Hi!LeolLeo：Hi!John!Wayne:HelloEveryonellamWayne*/【參考答案】1、 this.na

28、me2、 ChatRoom.showMessage3、 user.sendMessage4、 newChatRoomSystem()5、 newUser【答案解析】本題考查jov。程序基本知識，涉及到類的定義，方法調(diào)用及封裝等。第1處埴,User類中定義了私有變量name,及兩個屬性getNome,setNome,個構(gòu)造方法Use(Stingname),因為構(gòu)造方法中的參數(shù)名與變量同名，所以要加this區(qū)別，因此第1處埴,第2處定義了一個方法sendMessage,此處要調(diào)用ChatRoom類中的showMessage方法，傳遞兩個參數(shù)，以實現(xiàn)某個人說了某句

29、話，所以第2處埴ChQtRoom.showMessQge,另外類ChotRoomSystem定義了方法join，傳入一個User類型的用戶變量user,此處必須調(diào)用Use類中的sendMessoge方法，第3處埴user.sendMessage,第4處是實例化ChotRoomSystem類，并賦給變量crs,所以第4處埴newChatRoomSystem（）,第5處是調(diào)用ChotRoomSystem類的join方法，要求傳入一個Use類型的變量，而Use類有個構(gòu)造方法，要求有初始值，所以第5處埴寫NewUser。試題六一閱讀下列說明和C+代碼，埴補代碼中的空缺，將解答埴入答題紙的對應欄說明】內(nèi)。以下C+代碼實現(xiàn)一個簡單的聊天室系統(tǒng)(ChotRoomSystem),多個用戶(User)可以向聊天室(ChotRoom)發(fā)送消息，聊天室將消息展示給所有用戶。類圖如圖6-1所表示?！綜+代石馬】#include<iostream>#include<string>usingnamespacestd；classUserprivate:stringname;public:User(stringname)(