文章
161
粉丝
0
获赞
0
访问
20.3k
(3)时间复杂度O(n^2),空间复杂度:O(1)
评分及理由
(1)得分及理由(满分4分)
学生答案的基本设计思想是:通过遍历邻接矩阵计算每个顶点的出度和入度(对于无向图,出度和入度是相同的,实际就是度),然后统计度为奇数的顶点个数count,最后检查count是否为偶数且不超过2。思路正确,但存在冗余(无向图不需要分别计算入度和出度)。由于核心思想正确(统计奇度顶点个数并检查是否为0或2),且无逻辑错误,因此不扣分。得4分。
(2)得分及理由(满分9分)
学生代码实现了统计奇度顶点个数的功能,但存在以下问题:
1. 对于无向图,邻接矩阵是对称的,计算入度和出度是多余的(实际上入度等于出度,直接计算一行或一列的和即可)。但该冗余操作不影响正确性,且最终结果与标准一致。
2. 变量名拼写错误(如"indgree"应为"indegree","outdgree"应为"outdegree"),但这是识别问题或笔误,不影响逻辑,不扣分。
3. 条件判断"count % 2 == 0 && count <= 2"正确(因为题目要求奇度顶点个数为不大于2的偶数,即0或2)。
整体逻辑正确,但存在冗余计算(效率略低)。根据标准答案,功能正确即可得满分,因此得9分。
(3)得分及理由(满分2分)
学生正确分析了时间复杂度为O(n^2)(遍历邻接矩阵)和空间复杂度为O(1)(使用常数变量)。与标准答案一致,得2分。
题目总分:4+9+2=15分
登录后发布评论
暂无评论,来抢沙发