2016下半年下午題

1、2016年下半年程序員考試真題（下午題）試題一（共15分）閱讀以下說(shuō)明和流程圖，填補(bǔ)流程圖中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】設(shè)有整數(shù)數(shù)組 A1: N（ N>1）,其元素有正有負(fù)。下面的流程圖在該數(shù)組中尋找連續(xù)排列的 若干個(gè)元素，使其和達(dá)到最大值，并輸出其起始下標(biāo)K元素個(gè)數(shù)L以及最大的和值 M。例如，若數(shù)組元素依次為 3，-6，2，4,-2, 3,-1，則輸出K=3, L=4,M=7。該流程圖中考察了 A1: N中所有從下標(biāo)i到下標(biāo)j （j第i的各元素之和 S,并動(dòng)態(tài)地記錄其 最大值M?！玖鞒虉D】/ jtfi環(huán)開(kāi)姑、1*(1) rL Z J a輸出JG L, M注：循環(huán)開(kāi)始框內(nèi)

2、應(yīng)給出循環(huán)控制變量的初值和終值，默認(rèn)遞增值為 變量=初值，終值1,格式為：循環(huán)控制試題二(共 15 分) 閱讀以下代碼，回答問(wèn)題： 1 至問(wèn)題 3，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！敬a 1】#include <stdio.h> swap(int x,int y) int tmp=x;x=y;y=tmp;int main()int a=3,b=7; printf("a1=%d b1=%dn",a,b); swap(a,b);printf("a1=%d b1=%dn",a,b); return 0;【代碼 2】#include <stdio.

3、h> #define SPACE ' ' / 空格字符 int main() char str128=" Nothing is impossible! "int i,num=0,wordMark=0;for( i=0; stri; i+ ) if(stri=SPACE) wordMark=0;else if(wordMark=0) wordMark=1; num+; printf("%dn",num); return 0;【代碼 3】#include<stdio.h>#define SPACE ' '/

4、空格字符 int countStrs(char*);int main() char str128= " Nothing is impossible! " printf("%dn",countStrs(str);return 0;int countStrs(char*p)int num=0,wordMark=0; for(;p+)if(=SPACE)wordMark=0;else if(!wordMark) wordMark=1;+num; return ;問(wèn)題 1】（4 分） 寫(xiě)出代碼 1 運(yùn)行后的輸出結(jié)果。問(wèn)題 2】（3 分） 寫(xiě)出代碼 2 運(yùn)行后的輸

5、出結(jié)果。問(wèn)題 3】（8 分）代碼 3 的功能與代碼 2 完全相同，請(qǐng)補(bǔ)充 3 中的空缺，將解答寫(xiě)入答題紙的對(duì)應(yīng)欄內(nèi)。試題三(共 15 分) 閱讀以下說(shuō)明和代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】 下面的程序利用快速排序中劃分的思想在整數(shù)序列中找出第 k 小的元素(即將元素從小到大 排序后，取第 k 個(gè)元素)。對(duì)一個(gè)整數(shù)序列進(jìn)行快速排序的方法是： 在待排序的整數(shù)序列中取第一個(gè)數(shù)作為基準(zhǔn)值， 然 后根據(jù)基準(zhǔn)值進(jìn)行劃分， 從而將待排序的序列劃分為不大于基準(zhǔn)值者 (稱(chēng)為左子序列) 和大 于基準(zhǔn)值者(稱(chēng)為右子序列) ，然后再對(duì)左子序列和右子序列分別進(jìn)行快速排序，最終得到 非遞減的有序

6、序列。例如，整數(shù)序列 “19,12,30,11,7,53,78,25的第” 3 小元素為 12。整數(shù)序列 “19,12,7,30,11,11,7， 53.78,25,7 的”第 3 小元素為 7。函數(shù) partition (int a,int low,int high )以 alow的值為基準(zhǔn)，對(duì) alow、alow+l、ahigh 進(jìn)行劃分，最后將該基準(zhǔn)值放入 ai(low < i w hig并使得alow、alow+l、，.、ai-1都小于 或等于 ai，而 ai+l、ai+2、.、ahigh都大于 ai。函教 findkthElem(int a,int startldx,int e

7、ndldx,inr k)在 astartldx、astartldx+1、.、aendldx 中找出第 k 小的元素?！敬a】#include <stdio.h>#include <stdlib.h>int partition(int a,int low,int high)/對(duì)alowhigh進(jìn)行劃分，使得 alowi中的元素都不大于 ai+1high中/的元素int pivot=alow; /pivot 表示基準(zhǔn)元素int i=low,j=high;while()while(i<j&&aj>pivot) -j;ai=aj;while(i<

8、;j&&ai<=pivot) +i;aj=ai;/基準(zhǔn)元素定位 int findkthElem(int a,int startIdx,int endIdx,int k)/整數(shù)序列存儲(chǔ)在astartldxendldx中，查找并返回第K小的元素 if(startIdx<0|endIdx<0|startIdx>endIdx|k<1|k-1>endIdx|k-1<startIdx) return -1;/ 參數(shù)錯(cuò)誤if(startldx<endldx)int loc=partition(a,startldx,endldx);/ 進(jìn)行劃分，

9、確定基準(zhǔn)元素的位置 if(loc=k-1) / 找到第 k 小的元素return;if(k-1<loc) /繼續(xù)在基準(zhǔn)元素之前查找return findkthElem(a,k);else/繼續(xù)在基準(zhǔn)元素之后查找return findkthElem(a,k);return astartldx;int main()int i,k;int n;int a=19,12,7,30,11,11,7,53,78,25,7;n=sizeof(a)/sizeof(int); / 計(jì)算序列中的元素個(gè)數(shù) for (k=1;k<n+1;k+)for (i=0;i<n;i+)printf("

10、%d ",ai); printf("n");printf("elem%d=%dn",k,findkthElem(a,0,n-1,k); /輸出序列中第K小的元素試題四（共15分）閱讀以下說(shuō)明和代碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】圖是很多領(lǐng)域中的數(shù)據(jù)模型，遍歷是圖的一種基本運(yùn)算。從圖中某頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先 遍歷的過(guò)程是： 訪(fǎng)問(wèn)頂點(diǎn)V； 訪(fǎng)問(wèn)V的所有未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)W1,W2,.,Wk; 依次從這些鄰接頂點(diǎn) W1,W2,.,Wk出發(fā)，訪(fǎng)問(wèn)其所有未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)；依此類(lèi)推， 直到圖中所有訪(fǎng)問(wèn)過(guò)的頂點(diǎn)的鄰接頂點(diǎn)都得到訪(fǎng)問(wèn)

11、。顯然，上述過(guò)程可以訪(fǎng)問(wèn)到從頂點(diǎn)V出發(fā)且有路徑可達(dá)的所有頂點(diǎn)。對(duì)于從v出發(fā)不可達(dá)的頂點(diǎn)u,可從頂點(diǎn)u出發(fā)再次重復(fù)以上過(guò)程，直到圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到。例如，對(duì)于圖4-1所示的有向圖G，從a出發(fā)進(jìn)行廣度優(yōu)先遍歷，訪(fǎng)問(wèn)頂點(diǎn)的一種順序?yàn)閍、 b、c、e、f、d。abcdef0 110 10000011010100000001000100000000圖42設(shè)圖G采用數(shù)組表示法（即用鄰接矩陣arcs存儲(chǔ)），元素arcsij定義如下:1若G中存在邊（VpVj或弧<>0若6中不存在迦¥i，¥j）或弧< VVj >圖4-1的鄰接矩陣如圖4-2所示，頂點(diǎn)af對(duì)應(yīng)的編號(hào)

12、依次為 05.因此，訪(fǎng)問(wèn)頂點(diǎn) a的鄰接 頂點(diǎn)的順序?yàn)閎，c，e。函數(shù)BFSTraverse（Graph G利1用隊(duì)列實(shí)現(xiàn)圖 G的廣度優(yōu)先遍歷。相關(guān)的符號(hào)和類(lèi)型定義如下：#define MaxN : 50/*圖中最多頂點(diǎn)數(shù)*/typedef int AdjMatrixMaxNMaxN;typedef structin t vex num , edge num; / *圖中實(shí)際頂點(diǎn)數(shù)和邊（?。?shù) * /AdjMatrix arcs ; / * 鄰接矩陣 * /）Graph;typedef int QElemType ;enu mERROR=0;OK=l;代碼中用到的隊(duì)列運(yùn)算的函數(shù)原型如表4-1所述

13、，隊(duì)列類(lèi)型名為QUEUE。表4J 實(shí)現(xiàn)隊(duì)列運(yùn)算的函數(shù)原型及說(shuō)明* 41實(shí)現(xiàn)孰艸込尊的函越凱里良說(shuō)瞬諫明|*0)uEmptQUEUE Q)r銳瞬臥列是霖為空是劃丸1 swaoEnQuetietQUELE *Q, QElanTypc qc)赫元索単加人隊(duì)列1DcQueue( QUEUE *Q, QEl«n1ypc *tc)從隊(duì)列頭剋刪醸兄察.丼曲過(guò)參豐站帶回耳檢【代碼】int BFSTraverse(Graph G)/圖G進(jìn)行廣度優(yōu)先遍歷，圖采用鄰接矩陣存儲(chǔ)un sig ned char *visited;/visited用于存儲(chǔ)圖G中各頂點(diǎn)的訪(fǎng)問(wèn)標(biāo)志，0表示未訪(fǎng)問(wèn)int v,w,u;Q

14、UEUEQ Q;/申請(qǐng)存儲(chǔ)頂點(diǎn)訪(fǎng)問(wèn)標(biāo)志的空間，成功時(shí)將所申請(qǐng)空間初始化為0visited=(char*)calloc(G.vex nu m,sizeof(char);if()retum ERROR;/初始化Q為空隊(duì)列for(v=0;v<G.vex num ;v+)if(!visitedv) /從頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先遍歷printf("%d",v);訪(fǎng)問(wèn)頂點(diǎn)v并將其加入隊(duì)列visitedv=1;while(!isEmpty(Q) ;出隊(duì)列并用u表示出隊(duì)的元素 for(w=0;v<G.vex nu m;w+)if (G.arcsuw!=0&&/w是

15、u的鄰接頂點(diǎn)且未訪(fǎng)問(wèn)過(guò)printf("%d",w) ； / 訪(fǎng)問(wèn)頂點(diǎn) w visitedw=1 ；En Queue(&Q,w);free(visited);return OK;/BFSTraverse試題六(共15分)閱讀下列說(shuō)明和 C+弋碼，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】1UserCm-nanw : StmgCh&lRoomr 1+start孑詐祜0+ietHame()以下C+代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)單的聊天室系統(tǒng)(ChatRoomSystem),多個(gè)用戶(hù)(User)可以向聊天室(ChatRoom)發(fā)送消息，聊天室將消息展示給所有用戶(hù)。類(lèi)圖如

16、圖6-1所表示。團(tuán)類(lèi)團(tuán)C+代碼】#i nclude <iostream> #in clude <stri ng> using n amespace std; class Userprivate:stri ng n ame; public:User(stri ng n ame) =n ame;User()void setName(stri ng n ame)this->n ame=n ame;stri ng getName() return n ame;void sen dMessage(stri ng message); ;class ChatRoompublic

17、:static void showMessage(User* user,stri ng message) coutvv""vvuser->getName()vv":"vvmessagevve ndl;void User:sendMessage(string message) (this,message);class ChatRoomSystempublic:void starup()User* zhang=new User("John");User* li=new User("Leo"); zhang->

18、;sendMessage("Hi!Leo!"); li->sendMessage("Hi!John!");void join(User* user)("hello everyone!I am "+user->getName(); ;int main()ChatRoomSystem* crs=;crs->starup();crs->join("Wayne");delete crs;return 0;/*程序運(yùn)行結(jié)果：John：Hi!LeolLeo：Hi!John!Wayne】：Hello Ev

19、eryone!Iam Wayne /*試題五(共 15 分)閱讀以下說(shuō)明和Java程序，填補(bǔ)代碼中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)?！菊f(shuō)明】以下Java代碼實(shí)現(xiàn)一個(gè)簡(jiǎn)單的聊天室系統(tǒng)(ChatRoomSystem),多個(gè)用戶(hù)(User)可以向聊天室(ChatRoom)發(fā)送消息，聊天室將消息展示給所有用戶(hù)。類(lèi)圖如圖5-1所示?！綣ava 代碼】class ChatRoompublic static void showMessage(User user,Strmg message) System.out.println(""+user.getName()+":"+message); class