image

编辑人: 舍溪插画

calendar2025-06-07

message4

visits768

2014年5月 程序员 下午题参考答案

一、问答题

1、阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。
[说明]
指定网页中,某个关键词出现的次数除以该网页长度称为该关键词在此网页中的词频。对新闻类网页,存在一组公共的关键词。因此,每个新闻网页都存在一组词频,称为该新闻网页的特征向量。
设两个新闻网页的特征向量分别为:甲(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)的序号(NA(1)<NA(2)<...),NB(j)从前到后描述了特征向量乙中非零元素B(j)的序号(NB(1)<NB(2)<...)。
下面的流程图描述了计算这两个特征向量内积S的过程。

参考答案:

0
S+A(i)B(j) 或 等价表示
i>m或i=m+1或 等价表示
j>n或i=n+1 或 等价表示
i>m or j>n或i=m+1 or i=n+1 或等价表示


2、阅读以下说明和C函数,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明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 || ______)return 0;  /*小于2的数或大于2的偶数不是素数//

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

    for(k=3; k<t; k+=2)

    if(______)
 return 0;

    return 1;

    }
[说明2]
函数int minOne(int art[],int k)的功能是用递归方法求指定数组中前k个元素中的最小者,并作为函数值返回。
[C函数]
int minOne(int arr[],int k)
{
int t;
assert(k>0);
if(k==1)
return ______;
t=minOne(arr+1,______);
if(arr[0]<t)
return amr[0];
return ______;
}

参考答案:

n%2==0,或!(n%2),或其等价形式
n%k==0,或!(n%k),或其等价形式
arr[0],或*arr,或其等价形式
k-1,或其等价形式
t


3、阅读以下说明和C程序,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明]
函数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(______)  
 /*两个单词相同时不互为变位词*/ 

    return 0; 

    while (*fstword){
   /*计算第一个单词中各字母出现的次数*/ 

    if
(isalpha(*fstword)){ 

    if (isupper
(*fstword)) 

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

    else 

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

    ______;  
 /*下一个字符*/ 

    } 

    } 

    while (*Sndword){ 

    if (isalpha
(*sndword)) { 

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

    if(counter
[index]) 

    counter [index]--;


    elSe 

    ______; 

    } 

    ______;  
 /*下一个字符*/ 

    } 

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

    if(______) 

    return 0; 

    return 1; 

    }

参考答案:

strcmp(fstword,sndword)=0,或其等价形式
fstword++,或其等价形式
return 0
sndwotd++,或其等价形式
counter [index],或counter [index]!=0,或其等价形式


4、阅读以下说明和C函数,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明]
函数ReverseList(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成:已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。
例如,某单链表如图1所示,逆置过程中指针s的变化情况如图2所示。

链表结点类型定义如下:

typedef struct Node{

    int data;

    Struct Node *next;

    }Node,*LinkList;

    [C函数]

    void ReverseList
(LinkList headptr)

    {  //含头结点的单链表就地逆置,headptr为头指针

    LinkList p,s;

    if(______)
 return;    //空链表(仅有头结点)时无需处理

    P=______;  
 //令P指向第一个元素结点

    if(!P->next)  return;    //链表中仅有一个元素结点时无需处理

    s=p->next;    //s指向第二个元素结点

    ______ =NULL;
   //设置第一个元素结点的指针域为空

    while(s){

    p=s;  
 //令p指向未处理链表的第一个结点

    s= ______;

    p->next=headptr->next;    //将p所指结点插入已完成部分的表头

    headptr->next= ______;

    }

    }

参考答案:

!headptr->next,或!headptr||!headptr->next,或其等价形式
headptr->next
headptr->next->next,或p->next,或其等价形式
s->next,或p->next,  或其等价形式
p


5、阅读下列说明、C++代码和运行结果,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明]
对部分乐器进行建模,其类图如下图所示,包括:乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。
类图
下面是实现上述设计的C++代码,其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。

using namespace std;

    enum Note(/*枚举各种音调*/

  
 MIDDLE_C,C_SHARP,B_FLAT

    };

    class
Instrument{/*抽象基类,乐器*/

    public:

    ______;  
//play函数接口

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

    };

    class Wind ______
{

    public:

    void play(Note n)
 { cout<<"Wind.play()
 "<<n<<endl;    }

    void adjust()
{cout<<"Wind.adjust()"<<endl;    }

    );

    /*类Percussion和Stringed实现代码略*/

    class Brass ______{

    public:

    void play(Note n)
 {cout<<"Brass.play()
 "<<n<<endl;  }

    void adjUSt()
{cout<<"Brass.adjust()"<<endl;)

    };

    class
Woodwind:public Wind{

    public:

    void play(Note n)
 {  cout<<"Woodwind.play()"<<n<<endl;  }

    };

    class MusiC {

    public:

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

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

    void tuneAll(
______ e[],int numIns){    /*为每个乐器定调*/

    for(int i=0; i<numIns; i++){

    this->tune(e[i]);

    this->adjust(e[i]);

    }

    }

    };

    /*使用模板定义一个函数size,该函数将返回数组array的元素个数,实现代码略*/

    int main(){

    Music*music=
______ Music();

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

    music->tuneAll(orchestra,size(orchestra));/*size返回数组orchestra的元素个数*/

    for(int i=0;i<size(orchestra);i++)

    delete
orchestra[i];

    delete music;

    }

本程序运行后的输出结果为:

Wind.play()0

    Wind.adjust()

    Woodwind.play()0

    Wind.adjust()


参考答案:

virtual void play(Noten)=0
:public Instrument
:public Wind
Instrument*
new


6、阅读以下说明和Java程序,填补代码中的空缺,将解答填入答题纸的对应栏内。
[说明]
对部分乐器进行建模,其类图如下图所示,包括:乐器(Instrument)、管乐器(Wind)、打击乐器(Percussion)、弦乐器(Stringed)、木管乐器(Woodwind)、铜管乐器(Brass)。
类图
下面是实现上述设计的Java代码,其中音乐类(Music)使用各类乐器(Instrument)进行演奏和调音等操作。

[Java代码]

    enum Note{/*枚举各种音调*/

    MIDDLE_C,C_SHARP,B_FLAT;
   //其他略

    }

    interface
Instrument {/*接口,乐器*/

    ______;  
 //play方法接口

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

    }

    class Wind ______
{

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

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

    }

    /*类Percussion和Stringed实现代码略*/

    class Brass ______
{

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

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

    }

    Class Woodwind
extends Wind{

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

    }

    public class
Music{

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

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

    void
tuneAll(______ e){

    for(Instrument
i:e){

    adjust(i);

    tune(i);

    }

    }

    public Static void
main(String[] args){

    Music music=
______ Music();

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

  
 music.tuneAll(orchestra);

    }

    }
本程序运行后的输出结果为:
Wind.adjust()

    Wind.play()
MIDDLE_C

    Wind.adjust()

  
 Woodwind.play()MIDDLE_C

参考答案:

voidplay (Note n)
implements Instrument
extends Wind
Instrument[]
new


喵呜刷题:让学习像火箭一样快速,快来微信扫码,体验免费刷题服务,开启你的学习加速器!

创作类型:
原创

本文链接:2014年5月 程序员 下午题参考答案

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章
share