文章

74

粉丝

0

获赞

0

访问

8.7k

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

(1)算法思想:对于唯一的拓扑序列,每一次进行扫描的时候,只有一个节点的入度是0,如果有多个节点的入度是0,那么就表明该拓扑序列不是唯一的。

(2)代码:

int uniquely(MGraph G){
    int n = G.numVertices;
    int countin=0;//用于记录已经消除的节点数量,每一轮都要提出一个节点
    for(int m=0;m<n;m++){//最多有n个节点,那么就表示要进行n次去边,因为拓扑序列唯一
        int count = 0;
         for(int i=0;i<n;i++){
        	int degreein=0;//用于记录入度
        	for(int j=0;j<n;j++){
            	degreein+=Edge[j][i];
       		}
            if(degreein == 0){
                count++;
                int start=i;//将i作为开始的节点提出并将边全部去除
            }
         }
        countin++;
        if(count-countin != 1) return 0;//存在节点的入度0的个数不为1,直接返回0
        for(int s=0;s<n;s++){
        	Edge[start][s]=0;//将边全部去掉然后开始新的一轮扫描
        }
    }
    return 1;
   
}

 


评分及理由

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

得分:4分

理由:学生的算法思想描述准确,明确指出拓扑序列唯一的条件是每一步只有一个入度为0的节点。这与标准答案的核心思想一致,表述清晰完整。

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

得分:3分

理由:代码存在多处逻辑错误:
1. 未正确维护入度数组,而是每次重新计算入度,效率低下且逻辑错误(扣3分)
2. 变量start的作用域问题,在if语句内定义但在外部使用(扣1分)
3. 边删除逻辑错误,只删除了一个...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发