文章

26

粉丝

93

获赞

1

访问

1.5k

头像
2018年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月7日 16:46
阅读数 34


评分及理由

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

学生作答的基本设计思想是使用一个长度为n+1的辅助数组,初始化为0,然后遍历原数组,将值在[1, n]范围内的正整数标记到辅助数组的对应位置(置1),最后遍历辅助数组找到第一个未被标记(值为0)的位置,即为未出现的最小正整数。该思路正确且高效,与标准答案(使用原数组进行标记)不同但同样满足要求,因此不扣分。得3分。

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

学生提供了C-like代码(实际为Java/C#风格,但题目要求C/C++),关键逻辑正确:
- 创建辅助数组并初始化(但代码中重复声明了`tem`数组,存在语法错误,扣1分)。
- 遍历原数组,将有效正整数(1到n)映射到辅助数组(置1),逻辑正确(但条件`num[i] < len + 1`应包含等于n,此处写法正确,因为n+1是开区间,实际判断是[1, n])。
- 遍历辅助数组从下标1开始(正确),找到第一个0返回下标,否则返回n+1。
代码中存在错误:
- 第4行`int[] tem = new int[len + 1];`与第5行`int tem[len + 1];`重复声明,且后者语法错误(C++中不支持变长数组声明为局部变量,除非使用动态分配)。扣1分(逻辑错误,但核心算法正确)。
- 函数名`Serch`拼写错误(应为`Search`),但属于次要问题,不扣分。
- 代码风格(如使用Java的数组声明)与题目要求的C/C++不符,但核心逻辑清晰,注释合理,因此仅扣重复声明错误分(1分)。得7分(8-1=7)。

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

学生正确分析了时间复杂度和空间复杂度均为O(n),与标准答案一致。得2分。

题目总分:3+7+2=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发