文章

161

粉丝

0

获赞

0

访问

20.3k

头像
2021年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月13日 18:02
阅读数 58

(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分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发