2006年10月全国自考《数据结构》试题

33．假设有向图采用邻接表表示法，其定义如下：

typedef struct {

VertexNode adjlist[MaxVertexNum];

int n,e; //图的当前顶点数和弧数

} ALGraph; //邻接表类型

其中顶点表结点VertexNode结构为：

边表结点EdgeNode结构为：

下列算法f33的功能是，对以邻接表表示的有向图进行拓扑排序。

（1）阅读算法f33，并在空缺处填入

合适的内容，使其成为一个完

整的算法；

（2）对于如图所示的邻接表，将执

行算法f33后的topo[ ]结果填入

给定的数组中。

void f33(ALGraph G, int topo [ ]){

int i,j,k,count=0;

int indegree[MaxVertexNum];

EdgeNode *p; //p为指向边表结点的指针

Queue Q; //Q为队列

FindIndegree(G, indegree); //求各顶点的入度，并置于入度向量indegree

InitQueue(&Q);

for(i=0;i

if(!indegree[i])EnQueue(&Q,i);

while(!QueueEmpty(&Q)){

j= ① ;

topo[j]=++count;

for(p=G.adjlist[j].firstedge;p;p=->next){

k=p->adjvex;

if(!(--indegree[k])) ② ;

}

}

if(count

}

（1）①

②

（2） topo

五、算法设计题（本大题10分）

34．假设以带头结点的单链表表示有序表，单链表的类型定义如下：

typedef struct node{

DataType data;

struct node *next

}LinkNode, *LinkList;

编写算法，从有序表A中删除所有和有序表B中元素相同的结点。