2014年上半年程序員考試下午真題：　

>>>點(diǎn)擊進(jìn)入軟考初級程序員歷年真題下載

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

【說明】

指定網(wǎng)頁中，某個關(guān)鍵詞出現(xiàn)的次數(shù)除以該網(wǎng)頁長度稱為該關(guān)鍵詞在此網(wǎng)頁中的詞頻。對新聞類網(wǎng)頁，存在一組公共的關(guān)鍵詞。因此，每個新聞網(wǎng)頁都存在一組詞頻，稱為該新聞網(wǎng)頁的特征向量。

設(shè)兩個新聞網(wǎng)頁的特征向量分別為：甲(a1,a2,…,ak)、乙(b1,b2,…,bk)，則計(jì)算這兩個網(wǎng)頁的相似度時需要先計(jì)算它們的內(nèi)積S=a1b1+a2b2+…+akbk。一般情況下，新聞網(wǎng)頁特征向量的維數(shù)是巨大的，但每個特征向量中非零元素卻并不多。為了節(jié)省存儲空間和計(jì)算時間，我們依次用特征向量中非零元素的序號及相應(yīng)的詞頻值來簡化特征向量。為此，我們用(NA(i),A(i)|i=1,2,…,m)和(NB(j),B(j)|j=1,2,…,n)來簡化兩個網(wǎng)頁的特征向量。其中：NA(i)從前到后描述了特征向量甲中非零元素A(i)的序號(NB(1)<na(2)<…)，nb(j)從前到后描述了特征向量乙中非零元素b(j)的序號(nb(1)<nb(2)<…)。< p="">

下面的流程圖描述了計(jì)算這兩個將征向量內(nèi)積S的過程。

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

【說明1】

函數(shù)isPrime(int n)的功能是判斷n是否為素?cái)?shù)。若是，則返回1，否則返回0。素?cái)?shù)是只能被1和自己整除的正整數(shù)。例如，最小的5個素?cái)?shù)是2，3，5，7，11。

【C函數(shù)】

int isPrime (int n)

{

int k, t;

if (n==2) return 1;

if(n<2|| (1) ) return 0; /* 小于2的數(shù)或大于2的偶數(shù)不是素?cái)?shù) */

t=(int)sqrt(n)+1;

for (k=3; k

if ( (2) ) return 0;

return 1;

}

【說明2】

函數(shù)int minOne(int arr[], int k)的功能是用遞歸方法求指定數(shù)組中前k個元素中的最小者，并作為函數(shù)值返回。

【C函數(shù)】

int minOne (int arr[], int k)

{

int t;

assert (k>0) ;

if(k==1)

return (3) ;

t=minOne(arr+1, (4) ;

if (arr[0]<t)< p="">

return arr[0];

return (5) ;

}

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

【說明】函數(shù)areAnagrams(char *fstword, char *sndword)的功能是判斷fstword和sndword中的單詞(不區(qū)分大小寫)是否互為變位詞，若是則返回1，否則返回0。所謂變位詞是指兩個單詞是由相同字母的不同排列得到的。例如，“triangle”與“integral”互為變位詞，而“dumbest”與“stumble”不是。

函數(shù)areAnagrams的處理思路是檢測兩個單詞是否包含相同的字母且每個字母出現(xiàn)的次數(shù)也相同。過程是先計(jì)算第一個單詞(即fstword中的單詞)中各字母的出現(xiàn)次數(shù)并記錄在數(shù)組counter中，然后掃描第二個單詞(即sndword中的單詞)的各字母，若在第二個單詞中遇到與第一個單詞相同的字母，就將相應(yīng)的計(jì)數(shù)變量值減1，若在第二個單詞中發(fā)現(xiàn)第一個單詞中不存在的字母，則可斷定這兩個單詞不構(gòu)成變位詞。最后掃描用于計(jì)數(shù)的數(shù)組counter各元素，若兩個單詞互為變位詞，則counter的所有元素值都為0。

函數(shù)areAnagrams中用到的部分標(biāo)準(zhǔn)庫函數(shù)如下表所述。

【C函數(shù)】

int areAnagrams (char *fstword, char *sndword

{

int index;

int counter [26]={0}; /* counter[i]為英文字母表第i個字母出現(xiàn)的次數(shù)，'A'或'a'為第0個，'B'或'b'為第1個，依此類推 */

if ( (1) ) /* 兩個單詞相同時不互為變位詞 */

return 0;

while(*fstword) { /* 計(jì)算第一個單詞中各字母出現(xiàn)的次數(shù) */

if (isalpha (*fstword)) {

if (isupper (*fstword))

counter [*fstword -'A']++;

else

counter [*fstword -'a']++;

(2) ; /* 下一個字符 */

}

}

while (*sndword) {

if (isalpha (*sndword)) {

index= isupper (*sndword) ? *sndword -'A': *sndword -'a';

if (counter [index] )

counter [index] --;

else

(3) ;

}

(4) ; /* 下一個字符 */

}

for (index = 0; index<26; index++)

if ( (5) )

return 0;

return 1;

}

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

【說明】

函數(shù)ReverseList(LinkList headptr)的功能是將含有頭結(jié)點(diǎn)的單鏈表就地逆置。處理思路是將鏈表中的指針逆轉(zhuǎn)，即將原鏈表看成由兩部分組成：已經(jīng)完成逆置的部分和未完成逆置的部分，令s指向未逆置部分的第一個結(jié)點(diǎn)，并將該結(jié)點(diǎn)插入已完成部分的表頭(頭結(jié)點(diǎn)之后)，直到全部結(jié)點(diǎn)的指針域都修改完成為止。

例如，某單鏈表如圖4-1所示，逆置過程中指針s的變化情況如圖4-2所示。

鏈表結(jié)點(diǎn)類型定義如下：

typedef struct Node {

int data;

struct Node *next,

} Node, *LinkList;

【C函數(shù)】

void ReverseList (LinkList headptr)

{ //含頭結(jié)點(diǎn)的單鏈表就地逆置，headptr為頭指針

LinkList p, s;

if ( (1) ) return; //空鏈表(僅有頭結(jié)點(diǎn))時無需處理

p= (2) ; //令p指向第一個元素結(jié)點(diǎn)

if (!p->next) return; //鏈表中僅有一個元素結(jié)點(diǎn)時無需處理

s = p->next; //s指向第二個元素結(jié)點(diǎn)

(3) = NULL; //設(shè)置第一個元素結(jié)點(diǎn)的指針域?yàn)榭?/p>

while (s) {

p= s; //令p指向未處理鏈表的第一個結(jié)點(diǎn)

s= (4) ;

p -> next - headptr -> next; //將p所指結(jié)點(diǎn)插入已完成部分的表頭

headptr -> next = (5) ;

}

}

●

閱讀下列說明、C++代碼和運(yùn)行結(jié)果，填補(bǔ)代碼中的空缺(1)～(5)，將解答填入答題紙的對應(yīng)欄內(nèi)。

【說明】

對部分樂器進(jìn)行建模，其類圖如圖5-1所示，包括：樂器(Instrument)、管樂器(Wind)、打擊樂器(Percussion)、弦樂器(Stringed)、木管樂器(Woodwind)、銅管樂器(Brass)。

下面是實(shí)現(xiàn)上述設(shè)計(jì)的C++代碼，其中音樂類(Music)使用各類樂器(Instrument)進(jìn)行演奏和調(diào)音等操作。

【C++代碼】

#include

using namespace std;

enum Note { /* 枚舉各種音調(diào) */

MIDDLE_C, C_SHARP, B_FLAT

};

class Instrument{ /* 抽象基類，樂器 */

public:

(1) ; //play函數(shù)接口

virtual void adjust()=0; //adjust函數(shù)接口

};

class Wind (2) {

public:

void play(Note n) { cout<<"Wind.play()"<<n<<end1; p="" }<="">

void adjust() { cout<<"Wind.adjust()"<<end1; p="" }<="">

};

/* 類Percussion和Stringed實(shí)現(xiàn)代碼略 */

class Brass (3) {

public:

void play(Note n) { cout<<"Brass.play()"<<n<<end1; p="" }<="">

void adjust() { cout<<"Brass.adjust ()"<<end1; p="" }<="">

};

class Woodwind : public Wind {

public:

void play(Note n) { cout<<"Woodwind.play()"<<n<<end1; p="" }<="">

};

class Music {

public:

void tune(Instrument* i) { i->play(MIDDLE_C); }

void adjust(Instrument* i) { i->adjust(); }

void tuneAll( (4) e[], int numIns) { /* 為每個樂器定調(diào) */

for( int i=O; i<numlns; p="" {<="">

this->tune(e[i]);

this->adjust(e[i]);

}

}

};

/* 使用模板定義一個函數(shù)size，該函數(shù)將返回?cái)?shù)組array的元素個數(shù)，實(shí)現(xiàn)代碼略 */

int main() {

Music* music= (5) Music();

Instrument* orchestra[]={ new Wind(), new Woodwind() };

music->tuneAll(orchestra, size(orchestra)); /* size數(shù)組orchestra的元素個數(shù) */

for (int i=0; i<size p="" i++)<="">

delete orchestra[i];

delete music;

}

本程序運(yùn)行后的輸出結(jié)果為：

Wind.play() 0

Wind.adjust()

Woodwind.play() 0

Wind.adjust()

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

【說明】

對部分樂器進(jìn)行建模，其類圖如圖6-1所示，包括：樂器(Instrument)、管樂器(Wind)、打擊樂器( Percussion)、弦樂器(Stringed)、木管樂器(Woodwind)、銅管樂器(Brass)。

下面是實(shí)現(xiàn)上述設(shè)計(jì)的Java代碼，其中音樂類(Music)使用各類樂器(Instrument)進(jìn)行演奏和調(diào)音等操作。

【Java代碼】

enum Note{ /* 枚舉各種音調(diào) */

MIDD[LE_C, C_SHARP, B_FLAT; //其他略

}

interface Instrument { /* 接口，樂器 */

(1) ; //play方法接口

void adjust() ; //adjust方法接口

}

class Wind (2) {

public void play(Note n) { System.out.println("Wind.play()"+n); }

public void adjust() { System.out.println("Wind.adjust()"); }

}

/* 類Percussion和Stringet實(shí)現(xiàn)代碼略 */

class Brass (3) {

public void play(Note n) { System.out.println("Brass.play()"+n); }

public void adjust () { System.out.println("Brass.adjust()"); }

}

class Woodwind extends Wind {

public void play (Note n) { System.out.println("Woodwind.play()"+n); }

}

public

void tune(Instrument i) { i.play(Note.MIDDLE_C); }

void adjust(Instrument i) { i.adjust(); }

void tuneAll (4) e ) {

class Music {

for(lnstrument i : e) {

adjust(i);

tune(i);

}

}

public static void main(String[] args) {

Music music= (5) Music();

Instrument[] orchestra={ new Wind(), new Woodwind() };

music.tuneAll(orchestra);

}

奉程序運(yùn)行后的輸出結(jié)果為：

Wind.adjust()

Wind.play() MIDDLE_C

Wind.adjust()

Woodwind.play() MIDDLE_C