201405程序员下午真题

第 1 题

  下面的流程图描述了计算这两个将征向量内积S的过程。

答案与解析

• 试题难度：较难
• 知识点：流程图>流程图
• 试题答案：
  （1）0
  （2）S+A(i)B(j)或等价表示
  （3）i>m或i=m+1或等价表示
  （4）j>n或j=n+1或等价表示
  （5）i>m or j>n或i=m+1 or j=n+1或等价表示
• 试题解析：
      本题是简化了的一个大数据算法应用之例。世界上每天都有大量的新闻网页，门户网站需要将其自动进行分类，并传送给搜索的用户。为了分类，需要建立网页相似度的衡量方法。流行的算法是，先按统一的关键词组计算各个关键词的词频，形成网页的特征向量，这样，两个网页特征向量的夹角余弦（内积/两个向量模的乘积），就可以衡量两个网页的相似度口因此，计算两个网页特征向量的内积就是分类计算中的关键。
      对于存在大量零元素的稀疏向量来说，用题中所说的简化表示方法是很有效的。这样，求两个向量的内积只需要在分别从左到右扫描两个简化向量时，计算对应序号相同(NA(i)=NB(j))时的A(i)*B(j)之和（其他情况两个向量对应元素之乘积都是0）。因此，流程图中（2）处应填S+A(i)*B(j)，而累计的初始值S应该为0，即（1）处应填0。
      流程图中，NA(i)<NB(j)时，下一步应再比较NA(i+1)<NB(j)，除非i+1已经越界。因此，应先执行i+1→i，再判断是否i>m或i=m+1（如果成立，则扫描结束）。因此（3）处应填i>m或i=m+1。
      流程图中，NA(i)>NB(j)时，下一步应再比较NA(i)<NB(j+1)，除非j+1已经越界。因此，应先执行j+1→j，再判断是否j>n或j=n+1（如果成立，则扫描结束）。因此（4）处应填j>n或j=n+1。
      （5）处应填扫描结束的条件，i>m or j>n或i=m+1 or j=n+1，即两个简化向量之一扫描结束时，整个扫描就结束了。

第 2 题

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）n%2==0，或!(n%2)，或其等价形式
  （2）n%k==0，或!(n%k)，或其等价形式
  （3）arr[0]，或*arr，或其等价形式
  （4）k-1，或其等价形式
  （5）t
• 试题解析：
      本题考查C程序的基本语法和运算逻辑。
      首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。
      函数isPrime(int n)的功能是判断n是否为素数。根据素数的定义，小于2的数和大于2的偶数都不是素数，n是偶数可表示为“n%2等于0”，因此空（1）处应填入“n%2==0”，或者“!(n%2)”。
      在n是大于2的奇数的情况下，下面的代码从3开始查找n的因子，直到n的平方根为止。
      for (k=3; k<t; k+=2 )
         if (  （2）  ) return 0;
      若k的值是n的因子，则说明n不是素数。因此，空（2）处应填入“n%k==0”，或者“!(n%k)”。
      函数int minOne(int arr[],int k)的功能是用递归方法求指定数组中前k个元素中的最小者，显然，k为1时，这一个元素就是最小者。因此，空（3）处应填入“arr[0]”或其等价形式。
      空（4）所在的语句是通过递归方式找出arr[1]～arr[k-1]中的最小者，第一个实参指出从arr[1]开始，第二个参数为元素个数，为k-1个，因此空（4）应填入“k-1”。
      接下来的处理就很明确了，当t表示arr[1]～arr[k-1]中的最小者，其与arr[0]比较后就可以得到arr[0]～arr[k-1]中的最小者，因此空（5）处应填入“t”。

第 3 题

    函数areAnagrams中用到的部分标准库函数如下表所述。
    

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）strcmp(fstword, sndword)==0，或其等价形式
  （2）fstword++，或其等价形式
  （3）return 0
  （4）sndword++，或其等价形式
  （5）counter[index]，或counter[index]!=0，或其等价形式
• 试题解析：
      本题考查C程序的基本语法和运算逻辑。
      首先应认真分析题目中的说明，然后确定代码结构和各变量的作用。
      空（1）所在语句是比较两个字符串，若它们完全相同，则可断定不是变位词。显然，根据说明中的描述，可以用标准库函数strcmp来完成该处理，当两个字符串相同时，strcmp的返回值为0。因此，空（1）处应填入“strcmp(fstword,sndword)==0”或“!strcmp(fstword, sndword)”或其等价方式。
      上面代码中的第一个while语句用于扫描第一个单词中各字母出现的次数，并直接存入对应的数组元素counter[]中，显然，空（2）处应填入“fstword++”或其等价方式，从而可以遍历单词中的每个字母。
      在接下来的while语句中，通过sndword逐个扫描第二个单词中的字母，当*sndword表示的字母在第一个单词中没有出现时（与该字母对应的数组元素counter[]的值为0），这两个单词显然不互为变位词，在这种情况下函数可返回，因此空（3）处应填入“return 0”。空（4）处的处理与空（2）类似，应填入“sndword++”或其等价形式。
      根据题目中的说明，若两个词互为变位词，则它们包含的字母及每个字母出现的次数相同，这样数组counter的每个元素都应力0，如若不然，则可断定不是变位词。因此，空（5）处应填入“counter[index]”或“counter[index]!=0”或其等价形式。

第 4 题

   
图4-1

图4-2
 

答案与解析

• 试题难度：较难
• 知识点：C程序设计>C程序设计
• 试题答案：
  （1）!headptr->next，或!headptr||!headptr->next，或其等价形式
  （2）headptr->next
  （3）headptr->next->next，或p->next，或其等价形式
  （4）s->next，或p->next，或其等价形式
  （5）p 
• 试题解析：
      本题考查C语言的指针应用和运算逻辑。
      本问题的图和代码中的注释可提供完成操作的主要信息，在充分理解链表概念的基础上填充空缺的代码。
      对于含有头结点的单链表，链表为空时，头结点的指针域为空，表示之后没有其他结点了。因此，空（1）处应填入“!headptr->next”。
      根据注释，空（2）处所在语句令p指向链表的第一个元素结点，因此空（2）处应填入“headptr->next”。
      空（3）处的语句执行后，可由图4-1所示的链表得到图4-2(a)的链表，空（3）处应填入“p->next”或者“headptr->next->next”。
      代码中的while循环完成链表中除第一个元素结点之外的其他结点的指针域的修改。根据题目中的说明，s指向未逆置部分的第一个结点。在while循环中，变量p的作用是辅助完成将s所指结点插入头结点之后的处理，处理步骤为：
      p=s;
      p->next=headptr->next;    //将p所指结点插入已完成部分的表头
      headptr->next=p;
      因此，空（4）处应填入“s->next”或“p->next”，从而避免链表断链。空（5）处应填入“p”。

第 5 题

  
图5-1  类图

答案与解析

• 试题难度：较难
• 知识点：C++程序设计>C++程序设计
• 试题答案：
  （1）virtual void play(Note n)=0
  （2）:public Instrument
  （3）:public Wind
  （4）Instrument*
  （5）new
• 试题解析：
      本题考查C++程序设计的基本能力，涉及类、对象、函数的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。
      先考察题目说明。本题目中涉及的部分乐器，音乐类利用各类乐器进行演奏和调音等操作。根据说明进行设计，题目给出了类图（图5-1类图所示）。
      图中父接口Instrument，代表乐器，C++中设计为抽象基类，包含表示进行演奏的接口函数play()和表示调音的接口函数adjust()，其中函数play()的参数Note实现为枚举类型（enum），以枚举各种音调。这两个函数由具体子类型完成实现，所以Instrument的play()和adjust()为纯虚函数，原型中=0表示纯虚函数，实现由子类完成：
      virtual void play(Note n)=0;
      virtual void run()=0;
      Wind、Percussion和Stringed都是继承自Instrument的三个子类型，所以他们都继承了Instrument的play()和adjust()函数，各自演奏和调音方式有所不同，所以都覆盖了Instrument的play()函数和adjust()函数，并加以实现：
      void play(Note n)  {  /* 代码略 */  }
      void adjust()  {  /* 代码略 */  }
      Wind的两个子类型Woodwind和Brass都继承自Wind，继承用：Public关键字，从而Woodwind和Brass也都继承了Instrument的play()函数和adjust()函数。图5-1中Woodwind类对应的Woodwind的实现中只有play()，没有adjust()，因此其父类Wind的adjust()会自动被调用。
      Music类对各类乐器进行演奏和调音操作。函数tune()为一个乐器的定调，其参数为乐器对象指针Instrument*；函数adjust()为一个乐器进行调音，其参数也为Instrument*；函数tuneAll()为每个乐器定调，其参数是所有乐器数组。Music中的tune()和adjust()的参数均为Instrument*类型的对象指针i，调用函数play()和adjust()，其真正执行的函数根据所传实际对象指针所指对象而定，即动态绑定。
      所有乐器用Instrument*对象指针数组orchestra表示：使用模板定义一个函数size，该函数的参数为数组array，函数返回数组array的元素个数，表示乐器的数量。
      主控逻辑代码在mam函数中实现。在main()函数中，先初始化Music类的对象指针music，即：
      Music* music=new Music();
      并初始化各类乐器对象指针数组orchestra，各类乐器用抽象父类Instrument类型，因为向上转型是安全的，可以自动向上转型成为Instrument类型，用父类表示其各个子类型，即：
      Instrument* orchestra[]={  new  Wind(), new Woodwind() };
      然后调用music的tuneAll()函数，实现为orchestra中的每个乐器定调。其参数为orchestra数组以及使用size计算的数组中的对象指针个数。Orchestra指针数组的类型为Instrument*，所以tuneAll的第一个参数也应该为Instrument*，而非其子类型。在tuneAll()函数体内部，为每个数组元素调用当前对象的tune()和adjust()。
      数组orchestra中第一个元素为Wind类对象，第二个元素为Woodwind类对象。tuneAll()中循环的第一次执行时tune()函数中语句i->play(MIDDLE_C)；调用Wind中的play()函数，因此输出Wind.play() 0；adjust()函数中语句i->adjust()；为调用Wind类的adjust()函数，输出为Wind.adjust()。tuneAll()中循环的第二次执行时tune()函数中语句i->play(MIDDLE_C)；调用Woodwind中的play()函数，因此输出Woodwind.play() 0；adjust()函数中语句i->adjust()；为调用Woodwind类的adjust()函数，输出为Woodwind.adjust()。
      在main()函数中使用完数组对象之后，需要用delete操作进行释放对象，对每个orchestra中的元素进行删除，即delete orchestra[i];，对Music对象进行删除，即delete music;。
      因此，空（1）需要定义纯虚函数play(Note n)，原型中=0表示纯虚函数，分号在题目代码中已经给出，所以空（1）为virtual void play(Note n)=0；空（2）需要继承Instrument，即:public Instrument；空（3）需要继承Wind，即:public Wind；空（4）需要定调的乐器指针，即Instrument*；空（5）处为创建Music类的对象的关键字new。

第 6 题

  
图6-1  类图

答案与解析

• 试题难度：较难
• 知识点：Java程序设计>Java程序设计案例
• 试题答案：
  （1）void play(Note n)
  （2）implements Instrument
  （3）extends Wind
  （4）Instrument[]
  （5）new
• 试题解析：
      本题考查Java语言程序设计的能力，涉及类、对象、方法的定义和相关操作。要求考生根据给出的案例和代码说明，认真阅读理清程序思路，然后完成题目。
      先考察题目说明。本题目中涉及的部分乐器，音乐类利用各类乐器进行演奏和调音等操作。根据说明进行设计，题目给出了类图（图6-1类图所示）。
      图中父接口Instrument代表乐器，Java中设计为接口。Java中定义接口也即定义了抽象数据类型，用interface关键字。Instrument包含表示进行演奏的接口方法play()和表示调音的接口方法adjust()，接口方法默认为public，且没有方法实现。其中play()的参数Note实现为枚举类型（enum），以枚举各种音调。这两个方法由具体实现类完成实现，所以Instrument的play()和adjust()为方法声明，没有实现体，实现由子类完成：
      void play(Note n);
      void run();
      Wind、Percussion和Stringed是实现接口Instmment的三个类，用关键字implements。Java中实现接口的类必须全部实现接口中的方法，才能成为具体类，否则未被实现的方法需要加上abstract关键字，并且相应类必须为抽象类。Wind、Percussion和Stringed均为具体类，都要实现Inistrument的play()方法和adjust()方法，只是各自演奏和调音方式有所不同，所以都包含了Instrument的play()方法接口和adjust()方法接口，并加以实现：
      public void play(Note n)  {  /* 代码略 */  }
      public void adjust()  {  /* 代码略 */  }
      Wind的两个子类型Woodwind和Brass都继承自Wind, Java中继承用extends关键字，从而Woodwind和Brass也都实现了Instrument的play()方法和adjust()方法。图6-1中Woodwind类对应的Woodwind的实现中只有play()方法，没有adjust()方法的实现，因此其父类Wind的adjust()方法自动复制并被调用。
      Music类对各类乐器进行演奏和调音操作。方法tune()为一个乐器的定调，其参数为乐器Instrument接口类型；方法adjust()为一个乐器进行调音，其参数也为Instrument接口类型；函数tuneAll()为每个乐器定调，其参数是所有乐器数组。Java中数组一旦创建，就可以通过成员length获取数组中成员个数。Java 5.0升始，对集合还支持foreach，对集合中每个元素循环进行处理：
      for(Instrument i : e)  {
        adjust(i);
        tune(i)，
      }
  Music中的tune()和adjust()的参数均为Instrument接口类型引用i，调用play()和adjust()方法，其真正执行的方法根据所传实际对象而定，即动态绑定。
      主控逻辑代码在Music类中程序主入口main()方法中实现。在main()方法中，先初始化Music类的对象，引用名称music，即：
      Music music=new Music();
  并初始化各类乐器对象数组orchestra，各类乐器用父接口Instrument类型，因为向上转型是安全的，可以自动向上转型成为Instrument类型，用父接口类型表示其各个子类型，即：
      Instrument[] orchestra=  {  new Wind(), new Woodwind()  };
  或
      Instrument orchestra[]=  {  new Wind(), new Woodwind()  };
  然后调用music的tuneAll()方法：music.tuneAll(orchestra)，实现为orchestra中的每个乐器定调，其参数为orchestra数组。数组orchestra中元素的类型为Instrument，所以tuneAll()的参数也应该为Instrument类型数组，而非其子类型。在tuneAll()方法体内部，为每个数组元素调用当前对象的tune()和adjust()。
      数组orchestra中第一个元素为Wind类型对象，第二个元素为Woodwind类型对象。tuneAll()中for循环的第一次执行时tune()方法中语句i.play(Note.MIDDLE_C);调用Wind中的play()方法，因此输出Wind.play() MIDDLE_C;adjust()方法中语句i.adjust();为调用Wind类的adjust()方法，输出为Wind.adjustootuneAll()中循环的第二次执行tune()方法中语句i.play(Note.MIDDLE_C);时，调用Woodwind中的play()方法，因此输出Woodwind.play() MIDDLE_C;adjust()方法中语句i.adjust();为调用Woodwind类的adjust()方法，Woodwind没有实现adjust()方法，即Wind的adjust()方法，因此输出为Wood.adjust()。
      因此，空（1）需要定义接口play(Note n)，题目代码中已经给出用分号结尾，所以空（1）为void play(Note n)；空（2）需要实现接口Instrument，即implements Instrument；空（3）需要继承Wind，即extends Wind；空（4）需要定调的乐器数组，即Instrument[]；空（5）处为创建Music类的对象的关键字new。