问题 单项选择题

软件复杂性度量的参数包括______。

A.效率

B.规模

C.完整性

D.容错性

答案

参考答案:B

解析:[分析] 定量度量方法是程序复杂程度经常使用的方法,把程序的复杂程度乘以适当参数即可估算出软件中错误的数量以及软件开发需要用的工作量,定量度量的结果可以用来比较两个不同设计或两个不同算法的优劣,程序的定量的复杂程度可作为模块规模的精确限度,因而软件复杂性度量的参数包括规模。

选择题
问答题

阅读下列说明和C代码,回答问题。

[说明]

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

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

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

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

函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序,返回拓扑序列中的顶点编号序列,若不能完成拓扑排序,则返回空指针。其中,图G中的顶点从1开始依次编号,顶点序列为v1,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如图8.8所示,其邻接表如图8.9所示。

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

[C代码]

int *TODSort (LinkedDigraph G) ArcNode *p;

/*临时指针,指示表结点*/

Queue Q;/*临时队列,保存入度为0的顶点编号*/

int k=0;

/*临时变量,用作数组元素的下标*/

int j=0,w=0;

/*临时变量,用作顶点编号*/

int *topOrdert *inDegree;

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

inDegree=(int+)malloc( (G.n+l)+sizeof (int))j/*存储图G中各顶点的入度*/

if (!inDegree || !topOrder) return NULL;

(1) ;/*构造一个空队列*/

for(j=1;j<=G.n; j++) /*初始化*/

topOrder[j] =0;

inDegree[j] =0;for(j=1;j<=G.n;j++)

/*求图G中各顶点的入度*/

for(p=G.Vhead[j].firstarc; p;p=p->nextarc)

inDegree [p-> adjvex] +=1;

for(j=1;j<=G.n; j++) /*将图G中入度为0的顶点保存在队列中*/

if(0==inDegree[j] )EnQueue(&Q,j);

while(!IsEmpty (Q))

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

topOrder[k++]=w;

/*将顶点w的所有邻接顶点的入度减1(模拟删除顶点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*/

[问题1]

根据以上说明和C代码,填充C代码中的空(1)~(5)。

[问题2]

对于图8.8所示的有向图G,写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈,写出函数TopSort执行后得到的拓扑序列。

[问题3]

设某有向无环图的顶点个数为n、弧数为e,那么用邻接表存储该图时,实现上述拓扑排序算法的函数TopSort的时间复杂度是 (6)

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