【问题1】（6分）
根据说明中的描述，给出图3-1中U1～U6所对应的用例名。 【问题2】（4分）
图3-1中用例U1～U6分别与哪个（哪些）用例之间有关系，是何种关系？ 【问题3】（5分）
根据说明中的描述，给出图3-2中C1～C5所对应的类名。 试题四（共15分）
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】
在一块电路板的上下两端分别有n个接线柱。根据电路设计，用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连，称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤i
在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定连线集Nets={(i,π(i))，1≤i≤n}的最大不相交子集。 【分析问题】
记N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。N(i,j)的最大不相交子集为MNS(i,j)，size(i,j)=|MNS(i,j)|。
经分析，该问题具有最优子结构性质。对规模为n的电路布线问题，可以构造如下递归式：
【C代码】
下面是算法的C语言实现。 （1）变量说明
size[i][j]：上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数 pi[i]：π(i)，下标从1开始
（2）C程序 #include\ #include
Int m=0；/*牢记录最大连接集合中的接线柱*/
Void maxNum(intpi[],intsize[N+1][N+1],intn){/*求最大不相交连接数*/ int i,j;
for(j=0;j for(j=0;j for(j=pi[i];j<=n；j++){/*当j>=c[i]时,考虑两种情况*/ size[i][j]=size[i-l][j]>=size[i-l][pi[i]-l]+1?size[i-l][j]:size[i-l][pi[i]-l]+l; } } /*最大连接数*/ size[n][n]=size[n-l][n]>=size[n-l][pi[n]-l]+1?size[n-l][n]:size[n-l][pi[n]-l]+l; } /*构造最大不相交连接集合，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))的形式给出）。 试题五（共15分） 阅读下列说明和C++代码，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】 某软件系统中，已设计并实现了用于显示地址信息的类Address（如图5-1所示），现要求提供基于Dutch语言的地址信息显示接口。为了实现该要求并考虑到以后可能还会出现新的语言的接口，决定采用适配器（Adapter）模式实现该要求，得到如图5-1所示的类图。 【C++代码】 #include void stree(){/*实现代码省略*/} void zip(){/*实现代码省略*/} void city(){/*实现代码省略*/} ∥其他成员省略 }; 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(); addr->plaats(); } int main(){ Address *addr=new Address(); （5）; Cout<<\ testDutch(addrAdapter); return 0; }