2017年下半年程序員考試程序員應(yīng)用技術(shù)下午真題

2017年下半年程序員考試程序員應(yīng)用技術(shù)下午真題(總分：90.00，做題時(shí)間：150分鐘)一、案例分析題(總題數(shù)：6，分?jǐn)?shù)：90.00)1.試題一

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

【說明】

對(duì)于大于1的正整數(shù)n，(x+1)n可展開為

【流程圖】

注：循環(huán)開始框內(nèi)應(yīng)給出循環(huán)控制變量的初值和終值，默認(rèn)遞增值為1。格式為：循環(huán)控制變量=初值，終值，遞增值。（分?jǐn)?shù)：15.00）__________________________________________________________________________________________

正確答案：(（1）2，n，1

（2）A[k]

（3）k-1，1，-1

（4）A[i]+A[i-1]

（5）A[i])解析：（1）（3）空為填寫循環(huán)初值終值和遞增值，題目中給出的格式為循環(huán)控制變量=初值，終值，遞增值。按照題意，實(shí)質(zhì)為求楊輝三角。如下圖：

計(jì)算方式為從第2行計(jì)算迭代到計(jì)算第3行，再根據(jù)第3行值求取第4行，直到計(jì)算到第n行。所以第一空填2，n，1。

而對(duì)于每行的求取，第1項(xiàng)結(jié)果一直為1，最大項(xiàng)一直是1，可以直接賦值，所以第二空填A(yù)[k]。

然后從倒數(shù)第二項(xiàng)開始計(jì)算，依次往前計(jì)算。

所以第三空的填k-1，1，-1。因?yàn)椋?/p>

，故有A[i]=A[i]+A[i-1]。（注意A[i]+A[i-1]保留的k-1行的結(jié)果）。2.試題二

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

【說明】

對(duì)n個(gè)元素進(jìn)行簡(jiǎn)單選擇排序的基本方法是：第一趟從第1個(gè)元素開始，在n個(gè)元素中選出最小者，將其交換至第一個(gè)位置，第二趟從第2個(gè)元素開始，在剩下的n-1個(gè)元素中選出最小者，將其交換至第二個(gè)位置，依此類推，第i趟從n-i+1個(gè)元素中選出最小元素，將其交換至第i個(gè)位置，通過n-1趟選擇最終得到非遞減排序的有序序列?！敬a】

#include<stdio.h>

voidselectSort(intdata[],intn)

//對(duì)data[0]~data[n-1]中的n個(gè)整數(shù)按非遞減有序的方式進(jìn)行排列

{

inti,j,k;

inttemp;

for(i=0;i<n-1;i++){

for(k=i,j=i+1;（1）;（2）)//k表示data[i]~data[n-1]中最小元素的下標(biāo)

if(data[j]<data[k])（3）

if(k!=i){

//將本趟找出的最小元素與data[i]交換

temp=data[i];（4）;data[k]=temp;

}

}

}

intmain()

{

intarr[]={79,85,93,65,44,70,100,57};

inti,m;

m=sizeof(arr)/sizeof(int);//計(jì)算數(shù)組元素的個(gè)數(shù)，用m表示

（5）;//調(diào)用selectSort對(duì)數(shù)組arr進(jìn)行非遞減排序

for(（6）;i<m;i++)//按非遞減順序輸出所有的數(shù)組元素

printf(“%d\t”,arr[i]);

printf(“\n”);

return0;

}（分?jǐn)?shù)：15.00）__________________________________________________________________________________________

正確答案：(（1）j<n或者j<=n-1

（2）j++

（3）k=j

（4）data[i]=data[k]

（5）selectSort(arr,m)此處m也可以填8或者sizeof(arr)/sizeof(int),arr可以改成&arr[0]

（6）i=0)解析：本題考查C程序設(shè)計(jì)基本技能及應(yīng)用。簡(jiǎn)單選擇排序方法是設(shè)所排序序列的記錄個(gè)數(shù)為n。i取1,2,…,n-1,從所有n-i+1個(gè)記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個(gè)記錄交換。執(zhí)行n-1趟后就完成了記錄序列的排序。

第1空應(yīng)填j循環(huán)結(jié)束條件，j應(yīng)該運(yùn)行至序列末尾。填j<n或者j<=n-1；

第2空填j循環(huán)控制語句，j每次遞增1，往后移動(dòng)一個(gè)元素與a[i]進(jìn)行比較。

第3空為自動(dòng)保存最大元素的下標(biāo)，k=j。

第4空為交換兩個(gè)元素，temp為臨時(shí)變量，保存data[i]的值，使用data[i]=data[k]使data[i]為后面n-i+1個(gè)記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，再將temp賦給data[k]。

第5空為調(diào)用selectSort對(duì)數(shù)組arr進(jìn)行非遞減排序，selectSort有兩個(gè)參數(shù)，數(shù)組和排序元素個(gè)數(shù)，為selectSort(arr,m)。

第6空進(jìn)行元素遍歷輸出所有的數(shù)組元素，從下標(biāo)為0開始，所以填i=0。試題三

閱讀以下代碼和問題，回答問題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【代碼1】

typedefenum{A，B，C，D}EnumType;

EnumTypef(intyr)

{

if(0==yr%400){

returnA;

}

elseif(!(yr%4)){

if(0!=yr%100)

returnB;

else

returnC;

}

returnD;

}

【代碼2】

#include

intmain()

{intscore;

scanf("%d"，&score);

switch(score)

{

case5:printf("Excellent!\n");

case4:printf("Good!\n");break;

case3:printf("Average!\n");

case2:

case1:

case0:printf("Poor!\n");

default:printf("Oops,Error\n");

}

return0;

}

【代碼3】

#include

intmain()

{inti,j,k;

for(i=0;i<2;i++)

for(j=0;j<3;j++)

for(k=0;k<2;k++){

if(i!=j&&j!=k)

printf("%d%d%d\n",i,j,k);

}

ruturn0;

}（分?jǐn)?shù)：15）(1).對(duì)于代碼1，寫出下面的函數(shù)調(diào)用后x1、x2、x3和x4的值。

x1=f(1997);

x2=f(2000);

x3=f(2100);

x4=f(2020);（分?jǐn)?shù)：4）__________________________________________________________________________________________

正確答案：(x1=3；x2=0；x3=2；x4=1)解析：第一個(gè)條件0==yr%400，2000滿足，返回為A；其余都不滿足，繼續(xù)進(jìn)行判斷；

第二個(gè)條件！yr%4，1997不滿足，返回為D；其余滿足，繼續(xù)進(jìn)行判斷；

第三個(gè)條件0！=yr%100，2020滿足，返回為B；2100不滿足，返回為C。

枚舉類型中列出的每一個(gè)枚舉符都對(duì)應(yīng)著一個(gè)整數(shù)值，枚舉類型實(shí)際上是一個(gè)整型符號(hào)常量的集合。當(dāng)定義枚舉類型時(shí)，枚舉符都已經(jīng)被系統(tǒng)隱含地賦予了一個(gè)整型值，默認(rèn)情況下，第一個(gè)元素為0，第二個(gè)元素為1，依此類推。所以相應(yīng)的A=0，B=1，C=2，D=3，故返回為：x1=3;x2=0;x3=2;x4=1。(2).（1）寫出代碼2進(jìn)行時(shí)輸入為3的輸出結(jié)果；

（2）寫出代碼2進(jìn)行時(shí)輸入為5的輸出結(jié)果。（分?jǐn)?shù)：5）__________________________________________________________________________________________

正確答案：(（1）Average！

poor！

Oops，Error

（2）Excellent！

Good！)解析：控制傳遞給與開關(guān)的值匹配的case語句。switch語句可以包括任意數(shù)目的case實(shí)例，但是任何兩個(gè)case語句都不能具有相同的值。語句體從選定的語句開始執(zhí)行，直到break將控制傳遞到case體以外。case后面的常量表達(dá)式實(shí)際上只起語句標(biāo)號(hào)作用,而不起條件判斷作用,即"只是開始執(zhí)行處的入口標(biāo)號(hào)".因此,一旦與switch后面圓括號(hào)中表達(dá)式的值匹配,就從此標(biāo)號(hào)處開始執(zhí)行,而且執(zhí)行完一個(gè)case后面的語句后,若沒遇到break語句,就自動(dòng)進(jìn)入下一個(gè)case繼續(xù)執(zhí)行,而不在判斷是否與之匹配,直到遇到break語句才停止執(zhí)行,退出break語句。因此,若想執(zhí)行一個(gè)case分之后立即跳出switch語句,就必須在此分支的最后添加一個(gè)break語句。(3).寫出代碼3運(yùn)行后的輸出結(jié)果。（分?jǐn)?shù)：6）__________________________________________________________________________________________

正確答案：(010

020

021

101

120

121)解析：此題考察多重for循環(huán)再加上一個(gè)判定條件，i的取值為（0，1），j的取值為（0，1，2），k的取值為（0，1），只要按順序找到i！=j且j！=k的組合即可。試題四

閱讀以下說明、C函數(shù)和問題，回答問題，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。

【說明】

當(dāng)數(shù)組中的元素已經(jīng)排列有序時(shí)，可以采用折半查找（二分查找）法查找一個(gè)元素。下面的函數(shù)biSearch(intr[]，intlow，inthigh，intkey)用非遞歸方式在數(shù)組r中進(jìn)行二分查找，函數(shù)biSearch_rec(intr[]，intlow，inthigh，intkey)采用遞歸方式在數(shù)組r中進(jìn)行二分查找，函數(shù)的返回值都為所找到元素的下標(biāo)；若找不到，則返回-1。

【C函數(shù)1】

intbiSearch(intr[]，intlow，inthigh，intkey)

//r[low..high]中的元素按非遞減順序排列

//用二分查找法在數(shù)組r中查找與key相同的元素

//若找到則返回該元素在數(shù)組r的下標(biāo)，否則返回-1

{

intmid;

while(（1）){

mid=(low+high)/2;

if(key==r[mid])

returnmid;

elseif(key（2）;

else

（3）;

}/*while*/

return-1;

}/*biSearch*/

【C函數(shù)2】

intbiSearch_rec(intr[]，intlow，inthigh，intkey)

//r[low..high]中的元素按非遞減順序排列

//用二分查找法在數(shù)組r中查找與key相同的元素

//若找到則返回該元素在數(shù)組r的下標(biāo)，否則返回-1

{

intmid;

if(（4）){

mid=(low+high)/2;

if(key==r[mid])

returnmid;

elseif(keyreturnbiSearch_rec(（5）,key);

else

returnbiSearch_rec(（6）,key);

}/*if*/

return-1;

}/*biSearch_rec*/（分?jǐn)?shù)：15）(1).請(qǐng)?zhí)畛銫函數(shù)1和C函數(shù)2中的空缺，將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。（分?jǐn)?shù)：12）__________________________________________________________________________________________

正確答案：(（1）low<=high

（2）high=mid-1

（3）low=mid+1

（4）low<=high

（5）low,mid-1

（6）mid+1,high)解析：本題考察折半查找。二分查找又稱折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好，占用系統(tǒng)內(nèi)存較少；其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。

二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果xx>a[n/2],則只要在數(shù)組a的右半部搜索x。總共有n個(gè)元素，漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩余個(gè)數(shù)），其中k就是循環(huán)的次數(shù)。(2).若有序數(shù)組中有n個(gè)元素，采用二分查找法查找一個(gè)元素時(shí)，最多與（）個(gè)數(shù)組元素進(jìn)行比較，即可確定查找結(jié)果。

（7）備選答案：

A.[log2(n+1)]B.[n/2]C.n-1D.n（分?jǐn)?shù)：3）__________________________________________________________________________________________

正確答案：(（7）A)解析：3.試題五

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

【說明】

以下Java代碼實(shí)現(xiàn)一個(gè)超市簡(jiǎn)單銷售系統(tǒng)中的部分功能，顧客選擇圖書等物件(Item)加入購(gòu)物車(ShoppingCart)，到收銀臺(tái)(Cashier)對(duì)每個(gè)購(gòu)物車中的物品統(tǒng)計(jì)其價(jià)格進(jìn)行結(jié)賬。設(shè)計(jì)如圖5-1所示類圖。

【Java代碼】

interfaceItem{

publicvoidaccept(Visitorvisitor);

publicdoublegetPrice();

}

classBook（1）{

privatedoubleprice;

publicBook(doubleprice){（2）;}

publicvoidaccept(Visitorvisitor){//訪問本元素

（3）;

}

publicdoublegetPrice(){

returnprice;

}

}

//其它物品類略

interfaceVisitor{

publicvoidvisit(Bookbook);

//其它物品的visit方法

}

classCashier（4）{

privatedoubletotalForCart;

//訪問Book類型對(duì)象的價(jià)格并累加

（5）{

//假設(shè)Book類型的物品價(jià)格超過10元打8折

if(book.getPrice()<10.0）{

totalForCart+=book.getPrice();

}else

totalForCart+=book.getPrice()*0.8;

}

//其它visit方法和折扣策略類似，此處略

publicdoublegetTotal(){

returntotalForCart;

}

}

classShoppingCart{

//normalshoppingcartstuff

privatejava.util.ArrayListitems=newjava.util.ArrayList<>();

publicdoublecalculatePrice(){

Cashiervisitor=newCashier();

for(Itemitem:items){

（6）;

}

doubletotal=visitor.getTotal();

returntotal;

}

publicvoidadd(Iteme){

this.items.add(e);

}

}（分?jǐn)?shù)：15.00）__________________________________________________________________________________________

正確答案：(（1）implementsItem

（2）this.price=price

（3）visitor.visit(this)

（4）implementsVisitor

（5）publicvoidvisit(Bookbook)

（6）item.accept(visitor))解析：這里考察的是訪問者模式。其定義如下：封裝某些作用于某種數(shù)據(jù)結(jié)構(gòu)中各元素的操作，它可以在不改變數(shù)據(jù)結(jié)構(gòu)的前提下定義作用于這些元素的新的操作。

第一、四空為接口與實(shí)現(xiàn)，接口使用Interface，實(shí)現(xiàn)使用implements。第二空this表示類實(shí)例本身。第三空為訪問本元素。第五空實(shí)現(xiàn)接口里面的方法。第六空調(diào)用accept方法。4.試題六

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

【說明】

以下C++代碼實(shí)現(xiàn)一個(gè)超市簡(jiǎn)單銷售系統(tǒng)中的部分功能，顧客選擇圖書等物品（Item）加入購(gòu)物車（ShoppingCart），到收銀臺(tái)（Cashier）對(duì)每個(gè)購(gòu)物車中的物品統(tǒng)計(jì)其價(jià)格進(jìn)行結(jié)賬，設(shè)計(jì)如圖6-1所示類圖。

【C++代碼】

usingnamespacestd;

classBook;

classVisitor{

public:

virtualvoidvisit(Book*book)=0;

//其它物品的visit方法

};

classItem{

public:virtualvoidaccept(Visitor*visitor)=0;

virtualdoublegetPrice()=0;

};

classBook（1）{

private:doubleprice;

public:

Book(doubleprice){//訪問本元素

（2）;

}

voidaccept(Visitor*v