2016上半年软件设计师考试真题及答案-下午卷

}

/*构造最大不相交连接集合，net[i]表示最大不相交子集中第i条连线的上端接线柱的序号*/

void constructSet（int pi[],int size[N+1][N+1],int n,int net[n]）{ int i,j=n; m=0；

for(i=n；i>1;i--){/*从后往前*/

if(size[i][j]!=size[i-l][j]){/*(i,pi[i])是最大不相交子集的一条连线*/ （3）;/*将i记录到数组net中，连接线数自增1*/ j=pi[i]-1;/*更新扩展连线柱区间*/ } }

if(j>=pi[l])net[m++]=l;/*当i=1时*/ }

【问题1】（6分）

根据以上说明和C代码，填充C代码中的空（1）~（3）。 【问题2】（6分）

根据题干说明和以上C代码，算法采用了（4）算法设计策略。

函数maxNum和constructSet的时间复杂度分别为（5）和（6）（用O表示）。 【问题3】（3分）

若连接排列为{8,7,4,2,5,1,9,3,10,6}，即如图4-1所示，则最大不相交连接数为（7），包含的连线为（8）（用(i,π(i))的形式给出）。 解析 【问题1】

(1)size[1][j]=1

(2)size [i][j]=size[i-1][j] (3) net[m++]=i; 【问题2】

(4)动态规划算法 (5)O(n2)

11

(6)0(n) 【问题3】 (7)4

(8) (9，π(9)，(7，π (7))，(5，π(5))，(3，π(3))

试题五（共15分）

阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】

某软件系统中，已设计并实现了用于显示地址信息的类Address（如图5-1所示），现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口，决定采用适配器（Adapter）模式实现该要求，得到如图5-1所示的类图。

【C++代码】

#include using namespace std; class Address{ public:

void stree(){/*实现代码省略*/} void zip(){/*实现代码省略*/} void city(){/*实现代码省略*/}

12

∥其他成员省略 };

class DutchAddress{ public:

virtual void straat()=0; virtual void postcode()=0; virtual void plaats()=0; //其他成员省略 };

class DutchAddressAdapter:public DutchAddress{ private: （1）; public:

DutchAddressAdapter(Address*addr){ address=addr; }

void straat(){ （2）; }

void postcode(){ （3）; }

void plaat(){ （4）; }

//其他成员省略 };

void testDutch(DutchAddress *addr){ addr->straat(); addr->postcode();

13

addr->plaats(); }

int main(){

Address *addr=new Address(); （5）;

Cout<<\The DutchAddress\\n\ testDutch(addrAdapter); return 0; } 解析：

(1)Address* address; (2)address->street(); (3)address->zip(); (4) address->city();

(5)DutchAddress *addr=new DutchAddressAdaptor(addr); 试题六

阅读下列说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。 【说明】

某软件系统中，已设计并实现了用于显示地址信息的类Address（如图6-1所示），现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口，决定采用适配器（Adapter）模式实现该要求，得到如图6-1所示的类图。

14

问题：6.1 【Java代码】 import java.util.*; Class Address{

public void street() { //实现代码省略 } public void zip() { //实现代码省略 } public void city() { //实现代码省略 } ∥其他成员省略 }

class DutchAddress{

public void straat() { //实现代码省略 } public void postcode() { //实现代码省略 } public void plaats() { //实现代码省略 } //其他成员省略 }

class DutchAddressAdapter extends DutchAddress { private （1） ;

public DutchAddressAdapter (Address addr){ address= addr;

15