文章

65

粉丝

19

获赞

367

访问

38.8k

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年6月30日 20:13
阅读数 10

1.不停遍历寻找入度为0的点,将其存入队列,队列里如果出现了两个点及以上说明不唯一,因为可以选择任意一个先出队,有多个拓扑序列,返回0即可

2.

int uniquely(MGraph G){
	char[MAXV] ver = G.verticesList;
	int graph[MAXV][MAXV] = G.Edge;
	int nv = G.numsVertices;
	int ne = G.numEdges;
	queue<int> q;
	vector<int> in; // 入度个数
	for(int i=0;i<nv;i++){
		for(int j=0;j<nv;j++){
			if(graph[i][j]==1){
				in[j]++;
			}
		}
	}
	//找到入度为0的点
	for(int i=0;i<nv;i++){
		if(in[i]==0){
			q.push(i);
		}
	}
	if(q.empty()){
		return 0;//没有拓扑排序
	}
	while(!q.empty()){
		if(q.size()>=2){
			return 0;
		}
		int temp = q.front();
		q.pop();
		for(int i=0;i<nv;i++){
			if(graph[temp][i]==1){
				in[i]--;
			}
			if(in[i]==0){
				q.push(i);
			}
		}
	}
	return 1;
}
 
 
 

评分及理由

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

得分:4分

理由:学生的设计思想与标准答案一致,正确地描述了通过队列寻找入度为0的顶点,并判断是否存在多个入度为0的顶点来确定拓扑序列的唯一性。思路清晰且正确。

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

得分:7分

理由:代码整体逻辑正确,但存在以下问题:

  • 1. 变量名拼写错误:G.numsVertices应为G.numVertices,扣1分。
  • 2. 入度数组in未...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发