文章

280

粉丝

1

获赞

8

访问

87.0k

头像
2012年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年9月12日 15:14
阅读数 226


评分及理由

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

学生给出的基本设计思想是使用哈希表存储str1链表的节点,然后遍历str2链表并在哈希表中查找相同节点。这种方法在理论上是可行的,但存在两个主要问题:一是哈希表的大小仅为26,这假设了所有节点数据都是小写字母,但题目中并未明确说明单词仅由小写字母组成(虽然示例是字母,但一般性情况下可能不是);二是哈希冲突问题,即不同节点可能有相同数据(字母),但学生的方法直接使用数据作为哈希键,可能导致错误匹配(例如,不同节点有相同数据但地址不同,但学生比较的是节点地址,这正确,但哈希键仅基于数据,所以多个相同数据的节点会覆盖哈希表条目)。因此,该方法在通用性上存在缺陷,但思路正确。得2分(扣2分,因为方法有局限性且未考虑通用情况)。

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

学生代码实现了哈希表方法,但有以下逻辑错误:
1. 哈希表大小固定为26,但节点数据可能不是小写字母(例如大写字母或其他字符),这会导致越界或错误。
2. 哈希表存储的是节点指针,但键仅基于数据(字母),因此多个相同数据的节点会覆盖同一哈希位置,导致信息丢失。例如,如果str1中有多个相同字母的节点,只有最后一个会被记录,这可能导致在str2中匹配时错误。
3. 代码中使用了`str1 = str1->next`和`str2 = str2->next`,这修改了原始链表头指针(参数是引用),但算法不应该修改输入链表。
4. 函数参数使用`ListNode &str1`(引用)可能意图修改传入指针,但标准答案通常不修改输入。
5. 内存分配`malloc(26 * sizeof(ListNode))`应为`malloc(26 * sizeof(ListNode*))`,因为Hash是指针数组(但代码中未明确定义Hash类型,假设是ListNode**)。
由于这些逻辑错误,代码不能正确工作。但核心思路(使用哈希)是另一种可行方法,因此给予部分分数。得3分(扣5分,因为多个逻辑错误导致算法不可靠)。

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

学生正确分析了时间复杂度为O(n1 + n2),这与标准答案一致。空间复杂度声称O(1)是错误的,因为哈希表大小固定为26,但这是常数空间,所以实际上O(1)正确(26是常数)。但学生说“使用常数级的辅助空间”正确。因此得1分。

题目总分:...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发