2017年上半年软件设计师下午真题试卷 下载本文

【分析问题】

将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

int getCounterfeitCoin(int coins[], int first,int 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

firstSum+=coins[i]; }

for(i=first+(last-first)/2+1;i

lastSum+=coins[i]; }

if(firstSum

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,则最少的比较次数为(),最多的比较次数为()。

答案解析: 问题1

(1)first+(last-first)/2 或(first+last)/2 (2)firstSum

(6)2 (7)4

试题分析:若输入30个硬币,找假硬币的比较过程为: 第1次:15 比 15,此时能发现假币在15个的范围内。

第2次:7 比 7,此时,如果天平两端重量相同,则中间的硬币为假币,此时可找到假币,这是最理想的状态。

第3次:3 比 3,此时若平衡,则能找出假币,不平衡,则能确定假币为3个中的1个。

第4次:1 比 1,到这一步无论是否平衡都能找出假币,此时为最多比较次数。 第6题

阅读下列说明和 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(){