希赛 整理了2017上半年软件设计师考试下午真题，以下是第二部分。
试题四
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】
假币问题：有n枚硬币，其中有一枚是假币，己知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。
【分析问题】
将n枚硬币分成相等的两部分:
(1)当n为偶数时，将前后两部分，即1…n/2和n/2+1…0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币:
(2)当n为奇数时，将前后两部分，即1..(n-1)/2和(n+1)/2+1…0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币:若两端重量相等，则中间的硬币，即第(n+1)/2枚硬币是假币。
【C代码】
下面是算法的C语言实现，其中:
coins[]:硬币数组
first，last:当前考虑的硬币数组中的第一个和最后一个下标
#include <stdio.h>
int getCounterfeitCoin(int coins[]， int first，iot last)
{
int firstSum = 0，lastSum = 0;
int ì;
If(first==last-1){ /*只剩两枚硬币*/
if(coins[first] < coins[last])
return first;
return last;
}
if((last – first + 1) % 2 =0){ /*偶数枚硬币*/
for(i = first;i <( 1 );i++){
firstSum+= coins[i];
}
for(i=first + (last-first) / 2 + 1;i < last +1;i++){
lastSum += coins[i];
}
if( 2 ){
Return getCounterfeitCoin(coins,first,first+(last-first)/2;)
}else{
Return getCounterfeitCoin(coins,first+(last-first)/2+1,last;)
}
}
else{ /*奇数枚硬币*/
For(i=first;i<first+(last-first)/2;i++){
firstSum+=coins[i];
}
For(i=first+(last-first)/2+1;i<last+1;i++){
lastSum+=coins[i];
}
If(firstSum<lastSum){
return getCounterfeitCoin(coins,first,first+(last-first)/2-1);
}else if(firstSum>lastSum){
return getCounterfeitCoin(coins,first+(last-first)/2-1,last);
}else{
Return( 3 )
}
}
}
【问题一】
根据题干说明，填充C代码中的空（1）-（3）
【问题二】
根据题干说明和C代码，算法采用了（）设计策略。函数getCounterfeitCoin的时间复杂度为（）（用O表示）。
【问题三】
若输入的硬币数为30，则最少的比较次数为（），最多的比较次数为（）。
试题五(共15分〉
阅读下列说明和C++代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某快餐厅主要制作井出售儿童套餐，一般包括主餐(各类比萨)、饮料和玩具，其餐品种类可能不同，但其制作过程相同。前台服务员(Waiter)调度厨师制作套餐。现采用生成器(Builder)模式实现制作过程，得到如图5-1所示的类图。
【C++代码】
#include<iostream>
#include <string>
using namespace std;
class Pizza {
private: string parts;
public:
void setParts(string parts) { this->parts=parts; }
string getParts() { return parts; }
};
class PizzaBuilder {
protected:Pizza* pizza;
public:
Pizza* getPizza() { retum pizza; }
void createNewPizza() {pizza = new Pizza();}
( 1 );
}
class HawaiianPizzaBuilder :public PizzaBuilder {
public:
void buildParts() { pizza->setParts(“cross +mild + ham&pineapple”); }
class SpicyPizzaBuider: public PizzaBuilder {
public:
void buildParts() { pizza->setParts(“pan baked +hot + ham&pineapple”); }
}
Class Waiter{
Private:
PizzaBuilder* pizzaBuilder;
public:
void setPizzaBuilder(PizzaBuilder* pizzaBuilder) { /*设置构建器*/
( 2 )
}
Pizza* getPizza() { return pizzaBuilder->getPizza(); }
void construct() { /*构建*/
pizzaBuilder->createNewPizza();
( 3 )
}
};
int main(){
Waiter*waiter=new Waiter();
PizzaBuilder*hawaiian pizzabuilder=new HawaiianPizzaBuilder()
( 4 );
( 5 );
cout<< “pizza: “<< waiter->getPizza()->getParts()<< endl;
}
程序的输出结果为:
pizza:cross+mild+ham&pineapple
试题六(共15分)
阅读下列说明和Java代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
某快餐厅主要制作并出售儿童套餐，一般包括主餐(各类比萨)、饮料和玩具，其餐品种类可能不同，但其制作过程相同。前台服务员(Waiter)调度厨师制作套餐。现采用生成器(Builder)模式实现制作过程，得到如图6-1所示的类图。
【Java代码】
class Pizza {
private String parts；
public void setParts(String parts) {this.parts = parts;}
public String toString() {return this.parts;}
}
abstract class PizzaBuilder {
protected Pizza pizza;
public Pizza getPizza() {return pizza;}
public void createNewPizza() { pizza = new Pizza();}
public (1) ;
}
class HawaiianPizzaBuilder extends PizzaBuilder {
public void buildParts() {pizza.setParts(“cross + mild + ham&pineapp1e”};
}
class SpicyPizzaBuilder extends PizzaBuilder {
public void buildParts() { pizza.setParts(“pan baked + hot + pepperoni&salami”);}
}
class Waiter {
private PizzaBuilder pizzaBuilder;
public void setPizzaBuilder(PizzaBuilder pizzaBuilder) { /*设置构建器*/
(2) ;
}
public Pizza getPizza(){ return pizzaBuilder.getPizza(); }
public void construct() {/*构建*/
pizzaBuilder.createNewPizza();
(3) ;
}
}
Class FastFoodOrdering {
public static viod mainSting[]args) {
Waiter waiter = new Waiter();
PizzaBuilder hawaiian_pizzabuilder = new HawaiianPizzaBuilder();
(4);
(5);
System.out.println(“pizza: ” + waiter.getPizza());
}
}
程序的输出结果为：
Pizza:cross+mild+ham&pineapple
原文标题：2017上半年软件设计师考试下午真题汇总
原文链接：http://www.educity.cn/rk/1787691.html
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！