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

>>>點擊進入軟考初級程序員歷年真題下載

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

【說明】

指定網頁中，某個關鍵詞出現的次數除以該網頁長度稱為該關鍵詞在此網頁中的詞頻。對新聞類網頁，存在一組公共的關鍵詞。因此，每個新聞網頁都存在一組詞頻，稱為該新聞網頁的特征向量。

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

下面的流程圖描述了計算這兩個將征向量內積S的過程。

● 閱讀以下說明和C函數，填補代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明1】

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

【C函數】

int isPrime (int n)

{

int k, t;

if (n==2) return 1;

if(n<2|| (1) ) return 0; /* 小于2的數或大于2的偶數不是素數 */

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

for (k=3; k

if ( (2) ) return 0;

return 1;

}

【說明2】

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

【C函數】

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程序，填補代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

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

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

函數areAnagrams中用到的部分標準庫函數如下表所述。

【C函數】

int areAnagrams (char *fstword, char *sndword

{

int index;

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

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

return 0;

while(*fstword) { /* 計算第一個單詞中各字母出現的次數 */

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函數，填補代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明】

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

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

鏈表結點類型定義如下：

typedef struct Node {

int data;

struct Node *next,

} Node, *LinkList;

【C函數】

void ReverseList (LinkList headptr)

{ //含頭結點的單鏈表就地逆置，headptr為頭指針

LinkList p, s;

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

p= (2) ; //令p指向第一個元素結點

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

s = p->next; //s指向第二個元素結點

(3) = NULL; //設置第一個元素結點的指針域為空

while (s) {

p= s; //令p指向未處理鏈表的第一個結點

s= (4) ;

p -> next - headptr -> next; //將p所指結點插入已完成部分的表頭

headptr -> next = (5) ;

}

}

●

閱讀下列說明、C++代碼和運行結果，填補代碼中的空缺(1)～(5)，將解答填入答題紙的對應欄內。

【說明】

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

下面是實現上述設計的C++代碼，其中音樂類(Music)使用各類樂器(Instrument)進行演奏和調音等操作。

【C++代碼】

#include

using namespace std;

enum Note { /* 枚舉各種音調 */

MIDDLE_C, C_SHARP, B_FLAT

};

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

public:

(1) ; //play函數接口

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

};

class Wind (2) {

public:

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

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

};

/* 類Percussion和Stringed實現代碼略 */

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) { /* 為每個樂器定調 */

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

this->tune(e[i]);

this->adjust(e[i]);

}

}

};

/* 使用模板定義一個函數size，該函數將返回數組array的元素個數，實現代碼略 */

int main() {

Music* music= (5) Music();

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

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

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

delete orchestra[i];

delete music;

}

本程序運行后的輸出結果為：

Wind.play() 0

Wind.adjust()

Woodwind.play() 0

Wind.adjust()

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

【說明】

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

下面是實現上述設計的Java代碼，其中音樂類(Music)使用各類樂器(Instrument)進行演奏和調音等操作。

【Java代碼】

enum Note{ /* 枚舉各種音調 */

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實現代碼略 */

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);

}

奉程序運行后的輸出結果為：

Wind.adjust()

Wind.play() MIDDLE_C

Wind.adjust()

Woodwind.play() MIDDLE_C