文章

166

粉丝

0

获赞

0

访问

10.1k

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年7月12日 22:35
阅读数 5

(1)因为是有向图的邻接矩阵存储方式,点所对应列即是该顶点的入度,点所对应行即是该顶点的出度,进行vumVertices轮遍历,每次去判断是否有且仅有一个入度为0的顶点

(2)

int uniquely(MGraph G){
	int indegrees[g.numVertices];//统计每个顶点的入度 
	for(int i = 0 ; i < numVertices ;i++){
		for(int j = 0 ; j < numVertices ; j++){
			indegrees[i] += g.Edge[j][i];
		}
	}
	//遍历 所以顶点,每次判断是否只有一个顶点入度0 
	for(int i = 0 ; i < numVertices ; i++){
		int count = 0;
		int tail = 0;
		for(int j = 0 ; j <numVertices ; j++0){
			if(indegrees[j] == 0){
				tail = i; //记录这一轮的弧尾结点 
				count ++;
			}
		}
		if(count != 1){
			return 0;//不存在只有一个入度0的结点则返回0 
		}
		for(int k = 0 ; k <numVertices ; k++){
			indegrees[k] -= g.Edge[tail][k]; //更新入度 
		}
	} 
	return 1;//如果遍历完所有结点则表示存在唯一拓扑序列 
}

 


评分及理由

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

得分:3分

理由:学生的基本设计思想与标准答案基本一致,正确理解了拓扑排序的唯一性判断方法。但未明确提到“移除入度为0的顶点”这一关键步骤,表述不够完整。

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

得分:6分

理由:代码整体思路正确,但存在以下问题:
1. 变量名拼写错误(如`g.numVertices`应为`G.numVertices`)
2. 循环条件错误(`j++0`应为`j++`)
3. 入度数组未初始化(`indegrees`应初始化为0)...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发