打印分户账清单（表3-8)时，必须以“（4)”作为关键字进行排序才能满足系统需求。A．储蓄所 B．账号 C．开

阅读下列函数说明和C代码，

[说明]

所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。

应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。

函数中使用的预定义符号如下：

define M 100

typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/

float x；

int p1，p2；

}tdr；

typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/

int n，p1，p2；

}tr；

typedef struct{/*给出两点坐标*/

float x，y；

}tpd；

typedef int tl[M]；

int n=10；

[函数]

float distance(tpd a，tpd b)；/*计算端点a、b之间的距离*/

void sortArr(tdr a[M]，int m)；

/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/

int isCircuit(tr r[M]，int i，int j)；

/*判断边(i，j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/

void selected(tr r[M]，int i，int j)；/*边(i，j)选入端点关系表r*/

void course(tr r [M]，tl l[M])；/*从端点关系表r中得出回路轨迹表*/

void exchange(tdr a[M]，int m，int b)；

/*调整表排序表，b表示是否可调，即是否有长度相同的边存在*/

void travling(tpd pd [M]，int n，float dist，tl locus[M])

/*dist记录总路程*/

{

tdr dr[M]；/*距离关系表*/

tr r[M]；/*端点关系表*/

int i，j，k，h，m；/*h表示选入端点关系表中的边数*/

int b；/*标识是否有长度相等的边*/

k=0；

/*计算距离关系表中各边的长度*/

for(i=1；i＜n； i++){

for(j=i+1；J＜=n；j++){

k++;

dr[k]．x=(1);

dr[k]．pl=i;

dr[k]．p2=j;

}

}

m=k；

sortArr(dr，m)；/*按距离大小从小到大排序形成排序表*/

do{

b=1;

dist=0；

k=h=0：

do{

k++；

i=dr[k]．p1；

j=dr[k]．p2；

if((r(i]．n＜=1)&&(r[j]．n＜=1)){/*度数不能大于2*/

if (2) {

/*若边(i，j)加入r后形成回路，则不能加入*/

(3);

h++；

dist+=dr[k]．x；

}else if (4) {

/*最后一边选入r成回路，则该边必须加入且得到解*/

selected(r，i，j)；

h++：

dist+=dr[k]．x;

}

}

}while((k !=n) && (h !=n))；

if(h==n){/*最后一边选入构成回路，完成输出结果*/

course(r，locus)；

}else(/*找不到解，调整dr，交换表中边长相同的边在表中的顺序，并将b置0*/

(5);

}

}while(!b);

}

(1)

它写成一个表示取值范围的表达式或者一个具体的值。例如图3-1中的类客人和住宿，客人端的“1”表示：一个住宿类的实例只能与一个1个客人类的实例相关联；住宿类端的“0..*’表示：一个住宿类的实例可以与0个或多个客人类的实例相关。请指出图3-1中(1)到(4)处的重复度分别为多少？

、(7)和(8)(用0符号表示)。

rt的时间复杂度是(6)。

若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

【说明】

对有向图进行拓扑排序的方法是：

(1)初始时拓扑序列为空；

(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；

(3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。

函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为vl，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：

define MAXVNUM 50 ／*最大顶点数*／

typedef struct ArcNode｜ ／*表结点类型*／

int adjvex； ／*邻接顶点编号*／

struct ArcNode*nextarc； ／*指示下一个邻接顶点*／

{ArcNode；

typedef struct AdjList{ ／*头结点类型*／

char vdata； ／*顶点的数据信息*／

ArcNode*firstarc； ／*指向邻接表的第一个表结点*／

}AdjList；

typedef struct LinkedDigraph ／*图的类型*／

int n： ／*图中顶点个数*／

AdjList Vhead[MAXVNUM]； ／*所有顶点的头结点数组*／

}LinkedDigraph；

例如，某有向图G如图4-1所示，其邻接表如图4-2所示。

函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：

【C代码】

int*TopSort(LinkedDigraph G){

ArcNode*P； ／*临时指针，指示表结点*／

Queue Q； ／*临时队列，保存入度为0的顸点编号*／

int k=0； ／*临时变量，用作数组元素的下标*／

int j=0，w=0； ／*临时变量，用作顶点编号*／

int*topOrder，*inDegree；

topOrder=(int*)malloc((G．n+1)*sizeof(int))；／*存储拓扑序列中的顶点编号*／

inDegree=(int*)malloc((G．n+1)*sizeof(int))；／*存储图G中各顶点的入度*／

if(!inDegree｜｜!topOrder) return NULL；

(1)； ／*构造一个空队列*／

for(j=1；j<=Gn；j++){ ／*初始化*／

topOrder[j]=0；inDegree[j]=0；

}

for(j=1；j<=Gn；j++) ／*求图G中各顶点的入度*／

for(p=G．Vhead[j]．firstarc；p；p=p->nextarc)

inDegree[P->adjvex]+=1；

for(j=i；j<=G．n；J++) ／*将图G中入度为0的顶点保存在队列中*／

if(0==inDegree[j]) EnQueue(&Q，j)；

while(! IsEmpty(Q)){

(2); ／*队头顶点出队列并用w保存该顶点的编号*／

topOrder[k++]=w； ／*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*／

for(p=G．Vhead[w]．firstarc；p；p=p->nextarc){

(3)-=1；

if(0== (4) ) EnQueue(&Q，P->adjvex)；

}／*for*／

｝/ * while*/

free(inDegree)；

if( (5) )

return NULL；

return topOrder；

｝/*TopSort*/

根据以上说明和C代码，填充C代码中的空(1)

阅读下列函数说明和C++代码，将应填入(n)处的字句写在对应栏内。

[说明]

在一些大型系统中，大多数的功能在初始化时要花费很多时间，如果在启动的时候，所有功能(包括不用的功能)都要全面初始化的话，会导致应用软件要花很多时间才能启动。因此常将程序设计成到了实际要使用某种功能的阶段才初始化该功能。

以下示例展示了Proxy(代理)模式，PrinterProxy类执行一些比较“轻”的方法，需要真正执行“重”的方法时才初始化Print类。图5-1显示了各个类间的关系。

[图5-1]

[C++代码]

class Printable{

public：

virtual void setPrinterName(string name)=0；

virtual string getprinterName()=0；

virtual void print(string name)=0；

}；

class Printer：public Printable{

private：

string name；

public：

Printer(string name){

cout＜＜"正在产生Printer的对象实例"＜＜endl；

this－＞name=name；

}

void setPrinterName(string name){

this-＞name=name；

}

string getPrinterName(){

return name；

}

void print(string msg){

cout＜＜"======="＜＜name＜＜"==========="＜＜endl；

cout＜＜msg＜＜endl；

}

}；

class printerproxy ：public (1) {

private：

String name；

Printer *real；

public：

PrinterProxy(string name){

(2)=NULL；

this-＞name=name；

}

void setPrinterName(string name){

if((3))real-＞setPrinterName(name)；

this-＞name=name；

}

string getPrinterName(){

return name；

}

void print(string msg){

(4)；

real-＞print(msg)；

}

void realize(){

if(real==NULL)real=(5)；

}

}；

(1)

阅读以下说明，回答问题1至问题3，将解答填人答题纸的对应栏内。

【说明】

某公司拟开发一套小区物业收费管理系统。初步的需求分析结果如下：

(1)业主信息主要包括：业主编号，姓名，房号，房屋面积，工作单位，联系电话等。房号可唯一标识一条业主信息，且一个房号仅对应一套房屋；一个业主可以有一套或多套的房屋。

(2)部门信息主要包括：部门号，部门名称，部门负责人，部门电话等；一个员工只能属于一个部门，一个部门只有一位负责人。

(3)员工信息主要包括：员工号，姓名，出生年月，性别，住址，联系电话，所在部门号，职务和密码等。根据职务不同员工可以有不同的权限，职务为“经理”的员工具有更改(添加、删除和修改)员工表中本部门员工信息的操作权限；职务为“收费”的员工只具有收费的操作权限。

(4)收费信息包括：房号，业主编号，收费日期，收费类型，数量，收费金额，员工号等。收费类型包括物业费、卫生费、水费和电费，并按月收取，收费标准如表2-1所示。其中：物业费=房屋面积(平方米)×每平米单价，卫生费=套房数量(套)×每套房单价，水费=用水数量(吨)×每吨水单价，电费=用电数量(度)×每度电单价。

(5)收费完毕应为业主生成收费单，收费单示例如表2—2所示

【概念模型设计】

根据需求阶段收集的信息，设计的实体联系图(不完整)如图2—1所示。图2—1中收费员和经理是员工的子实体。

【逻辑结构设计】

根据概念模型设计阶段完成的实体联系图，得出如下关系模式(不完整)：

业主((1)，姓名，房屋面积，工作单位，联系电话)

员工((2)，姓名，出生年月，性别，住址，联系电话，职务，密码)

部门((3)，部门名称，部门电话)

权限(职务，操作权限)

收费标准((4))

收费信息((5)，收费类型，收费金额，员工号)

根据图2-1，将逻辑结构设计阶段生成的关系模式中的空(1)～(5)补充完整，然后给出各关系模式的主键和外键。

阅读以下应用程序说明和C程序，将C程序段中(1)～(7)空缺处的语句填写完整。

[说明]

以下[C程序]完成从指定数据文件中读入职工的工号和他完成产品个数的数据信息，对同一职工多次完成的产品个数进行累计，最后按表5-22所示的格式输出职工完成产品数量的名次(ORDER)。该名次是按每位职工完成的产品数量(QUANTITY)排序，之后同一名次的职工人数(COUNT)和他们的职工号(NUMBER，同一名次的职工号以从小到大的顺序输出)。

以下[C程序]采用链表结构存储有关信息，链表中的每个表元对应一位职工。在数据输入同时，形成一个有序链表(按完成的产品数量和工号排序)。当一个职工有新的数据输入，在累计他的完成数量时会改变原来链表的有序性，为此应对链表进行删除、查找和插入等处理。

[C程序]