2021年（408）计算机学科专业基础综合试题 - 第41题回答
（1）首先检测顶点表中度为奇数的顶点个数是否为不大于2的偶数,若是则返回1,若不是，返回0
（2）
int IsExistEL(MGraph G){
int count;
int num=0;
for(int i=0;i<MaXV;i++)
count=0;
for(int j=i;j<MaXV;j++)
if(Edge[i][j]>0)
count++;//如果存在边相连，度加1
if(count%2==1)
num++;//计算度为奇数的点个数
if(num>2)
return 0;//度为奇数顶点大于2则不符题意
if(num%2==1)
return 0;//度为奇数顶点不为奇数则不符题意
return 1;
}
（3）时间复杂度为O(n^2)，空间复杂度为O(1)
评分及理由
（1）得分及理由（满分4分）
得分：2分
理由：学生的基本设计思想提到了检测度为奇数的顶点个数，但表述不够清晰完整。标准答案需要三个步骤：统计所有点的度、统计奇数度顶点个数、检查个数是否为0或2。学生只提到了最后一步的判断条件，缺少前两个步骤的具体描述，且对条件的描述不够准确（"不大于2的偶数"应为"0或2"）。
（2）得分及理由（满分9分）
得分：4分
理由：代码存在多处逻辑错误：
1. 宏定义常量写错：MAXV写成了MaXV（2处）
2. 循环结构错误：第一个for循环缺少大括号，导致内层循环和后续语句逻辑混乱
3. 邻接矩阵访问错误：应该使用G.Edge而不是Edge
4. 判断条件错误：题目要求奇数度顶点个数为不大于2的偶数（即0或2），但学生的判断逻辑有误，num%2==1的判断不符合题目要求
5. 变量初始化位置不当：count应该在每个顶点循环开始时初始化
优点：基本思路正确，使用了双重循环遍历邻接矩阵，尝试统计奇数度顶点个数。
（3）得分及理由（满分2分）
得分：1分
理由：时间复杂度分析正确（O(n²)），但空间复杂度分析不够准确。虽然学生使用了O(1)的额外空间，但由于代码中存在逻辑错误，实际的空间复杂度分析应该基于正确的算法实现。
题目总分：2+4+1=7分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发