自考数据结构历年试题及答案

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

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

34．假设以带头结点的单链表表示有序表，单链表的类型定义如下： typedef struct node{ DataType data; struct node *next }LinkNode, *LinkList;

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