填空题
阅读下列函数说明和C代码，将应填入{{U}} (n) {{/U}}处的字句写上。 [说明]
若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。
[图5-1]
无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。
现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U，TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。
函数中使用的预定义符号如下： #define MAX 32768
/*无穷大权，表示顶点间不连通*/ #define MAXVEX 30 /*图中顶点数目的最大值*/
typedef struct{ int startVex，stopVex;
/*边的起点和终点*/ float weight;
/*边的权*/ }Edge; typedef struct{
char vexs[MAXVEX]; /*顶点信息*/
float arcs[MAXVEX*(MAXVEX-1)/2];
/*邻接矩阵信息，压缩存储*/ int n;
/*图的顶点个数*/ }Graph; [函数]
void PrimMST(Graph*pGraph, Edge mst[]) {
int i,j,k,min,vx,vy;
float weight，minWeight;
Edge edge;
for(i=0; i＜pGraph-＞n-1；i++){
mst[i].StartVex=0;
mst[i].StopVex=i+1;
mst[i].weight=pGraph-＞arcs[i];
}
for(i=0；i＜{{U}}(1){{/U}}；i++){/*共n-1条边*/
minWeight=(float)MAX;
min=i;
/*从所有边(vx，vy)中选出最短的边*/
for(j=i; j＜pGraph-＞n-1; j++){
if(mst[j].weight＜minWeight){
minWeight={{U}}(2){{/U}};
min=j；
}
}
/*mst[minl是最短的边(vx，vy)，将mst[min]加入最小生成树*/
edge=mst[min]；
mst[min]=mst[i];
mst[i]=edge;
vx={{U}} (3) {{/U}};/*vx为刚加入最小生成树的顶点下标*/
/*调整mst[i+1]到mst[n-1]*/
for(j=i+1；j＜pGraph-＞n-1；j++){
vy=mst[j].StopVex;
if({{U}} (4) {{/U}}){/*计算(vx，vy)对应的边在压缩矩阵中的下标*/
k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；
}else{
k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;
}
weight={{U}} (5) {{/U}}；
if(weight＜mst[j].weight){
mst[j].weight=weight;
mst[j].StartVex=vx;
}
}
} }
填空题
阅读以下说明和C++代码，将应填入{{U}} (n) {{/U}}处的字句写上。 [说明]
现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显不display()。
需要新增图形Circle，又已知有类XXCircle实现了所需要实现的功能：显示displayIt()。为了继承自shape以提供统一接口，又不希望从头开发代码，希望使用XXCircle。这样将XXcircle作为Circle的一个属性，即Circle的对象包含一个XXCircle对象。当一个Circle对象被实例化时，它必须实例化一个相应的XXCircle对象：
Circle对象收到的做任何事的请求都将转发给这个XXCircle对象。通过这种称为Adapter模式，Circle对象就可以通过“让XXCircle做实际工作”来表现自己的行为了。图6-1显示了各个类间的关系。以下是C++语言实现，能够正确编译通过。
[图6-1] [C++代码]
class Shape{ public： {{U}}
(1) {{/U}}void display()=0; }; class Line：public
Shape{//省略具体实现 }; class Square：public
Shape{//省略具体实现 }; class XXCircle{
public： void displayIt(){
//省略具体实现 }
//省略其余方法和属性 }; class Circle：public
Shape{ private： XXCircle *pxc;
public： Circle();
void display(); };
Circle：：Circle(){ pxc={{U}} (2) {{/U}};
} void Circle：：display() {
pxc-＞{{U}} (3) {{/U}}; }
class Factory{ public： {{U}}
(4) {{/U}}getshapeInstance(int type){//生成特定类实例
switch(type){
case 1：return new Square;
case 2：return new Line;
case 3 ：return new Circle;
default：return NULL;
} } };
void main(int argc，char*argv[]){ if(argc
!=2){ cout＜＜"error
parameters!"＜＜endl; return;
} int
type=atoi(argv[1]); Factory factory；
Shape*s=factory.{{U}} (5) {{/U}};
if(s==NULL){ cout＜＜"Error get
the instance!"＜＜endl; return;
} s-＞display();
delete s； return；
}
填空题[说明]某游戏公司现欲开发一款面向儿童的模拟游戏，该游戏主要模拟现实世界中各种鸭子的发声特征、飞行特征和外观特征。游戏需要模拟的鸭子种类及其特征如表下表所示。为支持将来能够模拟更多种类鸭子的特征，采用策略设计模式(strategy)设计的类图如图5-1所示。其中，Duck为抽象类，描述了抽象的鸭子，而类RubberDuck、MallardDuck、CottonDuck和RedHeadDuck分别描述具体的鸭子种类，方法fly()、quack()和display()分别表示不同种类的鸭子都具有飞行特征、发声特征和外观特征；类FlyBehavior与QuackBehavior为抽象类，分别用于表示抽象的飞行行为与发声行为；类FlyNoWay与FlyWithWings分别描述不能飞行的行为和用翅膀飞行的行为；类Quack、Squeak与QuackNoWay分别描述发出“嘎嘎”声的行为、发出橡皮与空气摩擦声的行为与不发声的行为。请填补以下代码中的空缺。[C++代码]#include＜iostream＞usingnamespace(1);classFlyBehaviorpublic:(2)fly()=0；;classQuackBehaviorpublic:(3)quack()=0;ClassFlyWithWings:publicF1yBehaviorpublic:voidfly()cout＜＜"使用翅膀飞行!"＜＜endl;;classFlyNoWay:publicFlyBehaviorpublic:voidfly()cout＜＜"不能飞行!"＞＞endl;;classQuack:publicQuackBehaviorpublic:voidquack()cout＜＜"发出＼'嘎嘎'＼声!"＜＜endl;;classSqueak:publicQuackBehaviorpublic:voidquack()cout＜＜"发出空气与橡皮摩擦声!"＜＜endl;;classQuackNOWay:publicQuackBehaViorpublic:voidquack()cout＜＜"不能发声!"＜＜endl;;C1assDuckprotected:FlyBehavior*(4);QuackBehaVior*(5);public:VOidfly()(6);VOidquack()(7);;virtualvoiddisplay()=0;;classRubberDuck:publicDuckpublic:RubberDuck()flyBehavior=new(8);quackBehavior=new(9);～RubberDuck()if(!flyBehavior)deleteflyBehaVior;if(!quackBehavior)deletequackBehavior；Voiddisplay()/*此处省略显示橡皮鸭的代码*///其他代码省略