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