文章

164

粉丝

0

获赞

1

访问

43.8k

头像
2024年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月3日 11:18
阅读数 6

(1)拓扑序列每次挑选入度为0的节点进行弹出,所以若每次弹出时,都仅有一个点满足入度为0的条件,且能够完整弹出所有点,则说明拓扑序列唯一,为便于更新弹出节点后的入度变化,采用一个辅助数组od[numVertices],记录各个节点的入度,在每轮处理时,查询od数组进行弹出,若某次处理时发现od数组中有至少两个为0,则说明不存在唯一拓扑序列。

(2)

初始化图,设置其指针为G;

int od[G.numVertices];

void initod(int od[G.numVertices], MGraph G)

{

for(int i=0; i<G.numVertices;i++)

{

for(int j=0;j<G.numVertices;j++)

 od[i]+=G.Edge[j][i];

}

}

}

int uniquely(MGraph G)

{

initod(od,G);

int count=G.numVertices;

int num=0;//用于计数

int fz=0;//第一个入度为0的位置

While(num<count)

{

for(int i=0;i<G.numVertices;i++)

{

int count1=0;//检查入度为0的本轮节点数量

if(od[i]==0)  fz=i; count++;

if(count>1) return 0;//检查到本轮入度节点个数大于1

}

od[fz]=-1;//说明节点已经弹出完毕,设置为-1

for(int i=0;i<G.numVertices;i+=)

{ od[i]-=Edge[fz][i]//除去该节点与其他节点的出边}

count++;

}

return 1;//成功返回

}


评分及理由

(1)得分及理由(满分4分)

学生给出了基本正确的设计思想:通过每次挑选入度为0的节点,若每次仅有一个入度为0的节点且能处理完所有节点,则拓扑序列唯一。思路与标准答案一致,表述清晰。得4分。

(2)得分及理由(满分9分)...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发