2021年（408）计算机学科专业基础综合试题 - 第41题回答

评分及理由

（1）得分及理由（满分4分）

得分：3分

理由：学生的基本设计思想是正确的，即通过遍历邻接矩阵计算每个顶点的度，统计度为奇数的顶点个数，并判断该个数是否为0或2。但是，学生的描述中“邻接矩阵第i行与第i列中1的个数除2为该顶点的度”存在错误。对于无向图的邻接矩阵，顶点i的度就是第i行（或第i列）中非零元素（或1）的个数，不需要将行和列相加再除以2。因为邻接矩阵是对称的，行和列相加会导致重复计算。这是一个逻辑错误，因此扣1分。

（2）得分及理由（满分9分）

得分：6分

理由：学生的代码框架基本正确，但存在以下逻辑错误和细节问题：

1. 变量声明错误：int i=j=k=0; 在C/C++中不能这样连续赋值，应分别初始化。这是一个语法/逻辑错误。
2. 内层循环变量j未在每次外层循环开始时重置为0。在外层循环中，for(j; j < G.numVertices; j++) 的初始化部分为空，导致第一次内层循环后，j的值已等于G.numVertices，后续外层循环的内层循环将不再执行。这是一个严重的逻辑错误，会导致度计算错误。
3. 度计算逻辑错误：sum += G.Edge[i][j]; sum += G.Edge[j][i]; 如前所述，这会导致重复计算。对于无向图，只需计算行（或列）即可。

由于存在多处逻辑错误，严重影响了算法的正确性，因此扣3分。代码的其他部分（如统计奇数度顶点个数、最终判断）是正确的。

（3）得分及理由（满分2分）

得分：2分

理由：学生正确分析了算法的时间复杂度为O(n²)（n为顶点数），空间复杂度为O(1)。这与标准答案一致，且分析正确，因此得满分。

题目总分：3+6+2=11分

赞同