2017年上半年程序員考試程序員應(yīng)用技術(shù)下午真題一、案例分析題1.試題一

閱讀下列說明和流程圖，填補流程圖中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。

【說明】

設(shè)有二維整數(shù)數(shù)組（矩陣）A[1:m,1:n],其每行元素從左到右是遞增的，每列元素從上到下是遞增的。以下流程圖旨在該矩陣中需找與給定整數(shù)X相等的數(shù)。如果找不到則輸出“false”;只要找到一個（可能有多個）就輸出“True”以及該元素的下標(biāo)i和j（注意數(shù)組元素的下標(biāo)從1開始）。

例如，在如下矩陣中查找整數(shù)8，則輸出偉：True,4,1

2469

45910

671012

891113

流程圖中采用的算法如下：從矩陣的右上角元素開始，按照一定的路線逐個取元素與給定整數(shù)X進行比較（必要時向左走一步或向下走一步取下一個元素），直到找到相等的數(shù)或超出矩陣范圍（找不到）。

【流程圖】

該算法的時間復(fù)雜數(shù)是（

）

供選擇答案：A.O（1）B.O（m+n）C.O（m*n）D,O（m2+n2）__________________________________________________________________________________________

正確答案：（（1）n

（2）j-1→j

（3）i+1→I

（4）j

（5）C）讀題，可以看出元素查找的過程為從右上角開始，往右或者往下進行查找。因此，初始值i=1，j=n。

如果查找值小于右上角值，則往右移動一位再進行比較。所以，第二空填j-1→j。

接下來是判斷什么時候跳出循環(huán)。此時，終止循環(huán)的條件是：j=0，也就是其從最右端移到了最左端。

再看X<A[i,j]不成立時，執(zhí)行流程的右枝。此時，也就是說第一行的最大值都小于查找值，因此需往下移動一行。所以第三空填i+1→I。2.試題二

閱讀下列說明和C函數(shù)，填補函數(shù)中的空缺，將解答填入答案紙的對應(yīng)欄目內(nèi)。

【說明】

函數(shù)isLegal（char*ipaddr）的功能是判斷以點分十進制數(shù)表示的IPV4地址是否合法。參數(shù)ipadddr給出表示IPV4地址的字符串的首地址，串中僅含數(shù)字字符和“.”。若IPV4地址合法則返回1，否則返回0。判定為合法的條件是：每個十進制數(shù)的值位于整數(shù)區(qū)間[0,255]，兩個相鄰的樹之間用“.”分隔，共4個數(shù)、3個“.”。例如，192.168.0.15、1.0.0.1是合法的，192.168.1.256、1.1..1是不合法的。

【函數(shù)】

intisLegal（char*ipaddr）

{

intflag;

intcurVal;//curVal表示分析出的一個十進制數(shù)

intdecNum=0,dotNum=0；//decNum用于記錄十進制數(shù)的個數(shù)

//dotNum用戶記錄點的個數(shù)

char*p=（1）;

for（;*p;p++）{

curVal=0;flag=0;

while（isdigit（*p））{//判斷是否為數(shù)字字符

curVal=（2）+*p-’0’;

（3）

flag=1;

}

if（curVal>255）{

return0;

}

if（flag）{

（4）

}

if（*p=’.’）{

dotNum++;

}

}

if（（5））{

return1;

}

return0;

}__________________________________________________________________________________________

正確答案：（（1）ipaddr

（2）curval*10

（3）p++

（4）decNum++

（5）decNum==4&&dotNum==3）此題判斷IPV4地址是否合法，主要是判斷其每個十進制數(shù)的大小和總個數(shù)以及“.”個數(shù)來進行判別。

首先用isdigital函數(shù)判斷是否為十進制數(shù)，是則保留值。指針移到地址的下一個字符。

每找到一個十進制數(shù)都需要和前一次找到的值進行組合，即前一次的結(jié)果要乘以10。

每找完一個完整數(shù)字和“.”都需要記錄，所以要有decNum++和dotNum++。

最后，如果IP地址正確，則返回1。即：decNum=4和dotNum=3時成立。3.試題三

閱讀下列說明和C函數(shù)，填補C函數(shù)中的空缺，將解答填入答案紙的對應(yīng)欄目內(nèi)。

【說明】

字符串是程序中常見的一種處理對象，在字符串中進行子串的定位、插入和刪除是常見的運算。

設(shè)存儲字符串時不設(shè)置結(jié)束標(biāo)志，而是另行說明串的長度，因此串類型定義如下：

Typedefstruct

{

Char*str／／字符串存儲空間的起始地址

intlehgth／／字符串長

intcapacity／／存儲空間的容量

}SString;

【函數(shù)1說明】

函數(shù)indexStr（S,T,pos）的功能是：在S所表示的字符串中，從下標(biāo)pos開始查找T所表示字符串首次出現(xiàn)的位置。方法是：第一趟從S中下標(biāo)為pos、T中下標(biāo)偉0的字符開始，從左往右逐個對于來比較S和T的字符，直到遇到不同的字符或者到達T的末尾。若到達T的末尾，則本趟匹配的起始下標(biāo)pos為T出現(xiàn)的位置，結(jié)束查找；若遇到了不同的字符，則本趟匹配失效。下一趟從S中下標(biāo)pos+1處的字符開始，重復(fù)以上過程。

若在S中找到T，則返回其首次出現(xiàn)的位置，否則返回-1。

例如，若S中的字符串偉″studentsents″,T中的字符串偉″ent″，pos=0，則T在S中首次出現(xiàn)的位置為4。

【C函數(shù)1】

intindexStr（SStringS,SStringT,intpos）

{

inti,j:

i（S.length<1||S.length

return-1;

for（i=pos,j=0;i

if（S.str[i]==T.str[j]）

{

i++;j++;

}

else{

i=（

）;j=0

}

}

if（

）returni-T.length;

return-1;

}

【函數(shù)2說明】

函數(shù)eraseS位（S，T}的功能是刪除字符串S中所有與T相同的子串，其處理過程為:首先從字符串S的第一個字符（下標(biāo)為0）開始查找子串T，若找到（得到子串在S中的起始位置），則將串S中子串T之后的所有字符向前移動，將子串T覆蓋，從而將其刪除，然后重新開始查找下一個子串T，若找到就用后面的宇符序列進行覆蓋，重復(fù)上述過程，直到將S中所有的子串T刪除。

例如，若字符串S為“12ab345abab678”、T為“ab”。第一次找到"ab"時（位置為（2），將"345abab678"前移，S中的串改為"12345abab678"，第二次找到"ab"時（位置為5）;將ab678前移，S中的串改為"12345ab678"，第三次找到"ab"時（位置為5）;

將“678‘前移，S中的串改為"12345678"。

【C函數(shù)2】

VoideraseStr（SString*S,SStringT）

{

inti;

intpos;

if（S->length<||T.length<1||S->length

return;

Pos=0

for（;;）

{

／／調(diào)用indexStr在S所表示串的pos開始查找T的位置

Pos=indexStr（

）;

if（pos＝-1）／／S所表示串中不存在子串T

return;

for（i=pos+T.length;ilength;i++）／／通過覆蓋來刪除自串T

S->str[（

）]=S->str[i];

S->length=（

）;／／更新S所表示串的長度

}

}__________________________________________________________________________________________

正確答案：（（1）i+1

（2）j==T.length

（3）S,T,pos

（4）i-T.length

（5）S-＞length-T.length）函數(shù)1為字符串匹配，算法為：先判斷字符串S和T的長度，如果為空則不用循環(huán)，另外，如果字符串S的長度<字符串T的長度，那字符串S中也不能含有字符串T，也無需進行匹配。

那當(dāng)上述情況都不存在時，即需要進行循環(huán)。即從S的第一個字符開始，與T的第一個字符進行比較，如果相等，則S的第二個字符和T的第二字符進行比較，再相等就再往后移動一位進行比較，依次直到字符串T的結(jié)尾，也就是說j=T,.length。

當(dāng)某一個字符與T的字符不相等時，那么字符串S就往下移一位，再次進行與T的第一個字符進行比較，此時j恢復(fù)初始值，j=0。

函數(shù)2為字符串的刪除運算。首先，要調(diào)用函數(shù)indexStr，需要三個參數(shù)，字符串S、字符串T和pos。然后刪除的字符串的位置為刪除初始點的位置到其位置點+字符串T的長度，并將后面的字符串前移。而刪除T字符串后，字符串S的總長度變化，需減去字符串T的長度。4.試題四

閱讀以下說明和C函數(shù)，填補函數(shù)中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。

【說明】

簡單隊列是符合先進先出規(guī)則的數(shù)據(jù)結(jié)構(gòu)，下面用不含有頭結(jié)點的單向循環(huán)鏈表表示簡單隊列。

函數(shù)enqueue（queue*q，KeyTypenew_elem）的功能是將元素new_elem加入隊尾。

函數(shù)Dnqueue（queue*q，KeyType*elem）的功能使將非空隊列的隊頭元素出隊（從列隊中刪除），并通過參數(shù)帶回剛出隊的元素。

用單向循環(huán)鏈表表示的隊列如圖4-1所示

圖4-1單向循環(huán)鏈表表示的隊列示意圖

隊列及鏈表結(jié)點等相關(guān)類型定義如下：

enum{errOr，OK}；

typedef

int

KeyType；

typedef

struct

qNode{

KeyTypedata；

Struct

qNode*next；

}qNode，*Linkqueue；Typedef

struct

{

int

size；

Link；queuerear；

}queue；【C函數(shù)】

intenqueue（queue*q,KeyTypenew_elem）

{

／／元素new_elem入隊列

qNode*p;

P=（qNode*）malloc（sizeof（qNode））;

if（!p）

returnerrOr;

P->data=new_elem;

if（q->rear）

{

P->next=q->rear->next;

（

）;

}

else

P->next=p;

（

）;

q->size++;

returnOK;

}

intDequeue（queue*q,KeyType*elem）

{／／出隊列

qNode*p;

if（0＝＝q->size）／／是空隊列

returnerrOr；

P=（）（

）;／／令p指向隊頭元素結(jié)點

*elem=p->data;

q->rear->next=（

）;／／將隊列元素結(jié)點從鏈表中去除

if（（

））／／被刪除的隊頭結(jié)點是隊列中唯一結(jié)點

q->rear=NULL／／變成空隊列

free（p）;

q->size--;

returnOK;

}__________________________________________________________________________________________

正確答案：（（1）Q→rear→next=p

（2）Q→rear=p

（3）Q→rear→next

（4）p→next

（5）Q→rear==p或Q→rear→next==p→next或Q→size==1）本題考察C語言指針與鏈表的知識，為入隊列和刪除隊列問題。

對于入隊列，那么當(dāng)隊列Q不為空時，P的隊尾t要指向原Q的隊尾指向的元素，即：P->next=Q->rear->next，Q的隊尾要指向p，即：Q→rear→next=p。當(dāng)隊列Q為空時，插入p元素，則p的隊尾指向p自身，即：p→next=p，且整個隊列Q的隊尾也是p，即：Q→rear=p。

對于隊列刪除元素p，先判斷Q是否為空，為空隊列則返回ERROR;

If（0＝＝q->size）//是空隊列ReturnERROR；

另p指向隊頭元素結(jié)點，隊頭元素結(jié)點可用Q→rear→next表示。此時，p轉(zhuǎn)化為頭結(jié)點，p出列，則需要Q的隊尾指向p的下一個元素，因此第4空填：p→next。

最后，判斷被刪除的隊頭結(jié)點是否是隊列中的唯一結(jié)點，可采用：Q→rear==p或Q→rear→next==p→next或Q→size==1等表示方法。5.試題五

閱讀以下說明和Java程序，填補代碼中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。

【說明】

以下Jave代碼實現(xiàn)一個簡單客戶關(guān)系管理系統(tǒng)（CrM）中通過工廠（Customerrfactory）對象來創(chuàng)建客戶（Customer）對象的功能?？蛻舴譃閯?chuàng)建成功的客戶（realCustomer）和空客戶（NullCustomer）。空客戶對象是當(dāng)不滿足特定條件時創(chuàng)建或獲取的對象。類間關(guān)系如圖5-1所示。

圖5-1

【Java代碼】

AbstractclassCustomer{

ProtectedStringname;

（）booleanisNil（）

（）StringgetName（）;

}

ClassrealCustomer（）Customer{

PublicrealCustomer（Stringname）{

returnfalse;

}

}

ClassNullCustomer（）Customer{

PublicStringgetName（）﹛{return″NotAvailableinCustomerDatabase″;

}

PublicbooleanisNil（）{

returntrue;

}

}

classCustomerfactory{

publicString[]names={"rob"，"Joe"，"Julie"};

publicCustomergetCustomer（Stringname）{

for（inti=0;i<names.length;i++）{

if（names[i].（））

{

returnnewrealCusωmer（name）;

}

}

return（）

}

}

PublicclassCrM﹛

PublicviodgetCustomer（）﹛

Customerfactory（）

Customercustomer1-cf.getCustomer（″rob″）;

Customercustomer2=cf.getCustomer（″rob″）;

Customercustomer3=cf.getCustomer（″Julie″）;

Customercustomer4=cf.getCustomer（″Laura″）;

System.out.println（″customer1.getName（））;

System.out.println（″customer2getName（））;

System.out.println（″customer3.getName（））;

System.out.println（″customer4.getName（））;

}

Publicstaticviodmain（String[]arge）﹛

CrMcrm=newCrM（）;

Crm,getCustomer（）;

}

}

／*程序輸出為：

Customer

rob

NotAvailableinCustomerDatabase

Julie

NotAvailableinCustomerDatable

*／

intmain（）

{

CrM*crs=newCrM（）;

Crs->getCustomer（）;

Crs->getCustomer（）;

Deletecrs;

return（）;

}

／*程序輸出為：

Customer

rob

NotAvailableiniCustomerDatabase

Julie

NotAvailableinCustomerDatabase__________________________________________________________________________________________

正確答案：（1）publicabstract

2）publicabstract

3）extends

4）extends

5）equals（name）

6）newNullCustomer（）

7）cf=NewCustomerFactory（）;）本題考察Java程序設(shè)計客戶關(guān)系管理系統(tǒng)。

1）publicabstract定義可訪問方法

2）publicabstract

3）extends繼承Customer類

4）extends

5）equals（name）判斷名字是否在數(shù)組集合內(nèi)

6）newNullCustomer（）當(dāng)不滿足條件時創(chuàng)建一個空對象

7）cf=NewCustomerFactory（）;實例化對象cf6.試題六

閱讀下列說明和C++代碼，填補代碼中的空缺，將解答填入答題紙的對應(yīng)欄內(nèi)。

【說明】

以下C++代碼實現(xiàn)一個簡單客戶關(guān)系管理系統(tǒng)（CrM）中通過工廠（Customerfactory）對象來創(chuàng)建客戶（Customer）對象的功能。客戶分為創(chuàng)建成功的客戶（realCustomer）和空客戶（NullCustomer）?？湛蛻魧ο笫钱?dāng)不滿足特定條件時創(chuàng)建或獲取的對象。類間關(guān)系如圖6-1所示。

圖6-1

【C++代碼】

#include

#include

usingnamespacestd；

classCustomer｛

protected:

stringname；

public:

（1）bollisNil（）=0；

（2）stringgetName（）=0；

}；

classrealCustomer（3）｛

public:

realCustomer（stringname）｛this->name=name；

}

boolisNil（）｛returnfalse；

}

stringgetName（）｛returnname；

}

}

；

classNullCustomer（4）｛

public:

boolisNil（）｛returntrue；

}

stringgetName（）｛return〝NotAvailableinCustomerDatabase〞；

}

}

；

classCustomerfactory｛

public:

stringnames［3］=｛〝rob〞,〝Joe〞,〝Julie〞

}

；

public:

Customer*getCustomer（stringname）｛

for（inti=0；i<3；i++）｛

if（names［i］.（5））｛

returnnewrealCustomer（name）；

}

}

return（6）；

}

}

；

classCrM｛

public:

voidgetCustomer（）｛

Customerfactory*（7）；

Custome