文章

156

粉丝

0

获赞

0

访问

16.4k

头像
2019年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年12月2日 19:30
阅读数 3


评分及理由

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

学生第一次识别结果提到“循环式存储结构”,第二次识别结果为“链式存储结构”。题目要求空间只增不减且O(1)操作,链式存储结构(特别是循环链表)是合适的。虽然第一次识别表述不精确(“循环式”可能指顺序循环队列,但顺序结构难以满足空间只增不减),但第二次识别明确为“链式存储结构”,且结合上下文(提到了指针操作)可判断学生意图是链式存储。因此不扣分。
得分:2分

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

学生给出了队头指针q和队尾指针r,并给出了队空条件 q==r,这与标准答案一致,正确。
队满条件,学生写为“设队满时链表长度为n,(r+1)%n = q”。这个表述存在逻辑错误:
1. 在链式存储中,通常不预设固定长度n,且队列空间只增不减,理论上不存在传统意义上的“队满”(除非内存耗尽)。标准答案中“队满”是指循环链表中所有结点(包括空结点)都已存放数据,此时需要新增空结点,其判断条件是 Q.front == Q.rear->next。
2. 学生使用了模运算“%”,这更符合顺序循环队列的队满判断方式,与链式存储的设计不符,属于逻辑错误。
因此,队空判断正确得2分,队满判断错误扣2分。
得分:2分

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

学生描述了第一个元素入队后的操作:“P→next = q; r→next = P; q = P;”。这个描述非常混乱:
1. 初始状态q和r应指向同一个空结点。入队第一个元素P时,应使P成为数据结点,并调整指针形成循环。学生的操作序列逻辑不清,例如“P→next = q”在q指向空结点时可能正确,但紧接着“r→next = P”和“q = P”的次序和结果未体现队列的初始状态和最终状态,且未说明r指针的最终指向(应指向空结点)。
2. 未能清晰画出或描述队列的初始状态和入队后状态(如front和rear分别指向哪个结点)。
因此,未能正确描述第一个元素入队后的队列状态,扣2分。
得分:0分

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

学生给出了入队和出队操作的基本过程,但描述混乱且存在逻辑错误:
1. 入队操作部分出现了“q→pre = P”、“P→pre = r”等双向链表的操作,而题目未要求双向链表,且标准答案为单向循环链表。操作序列次序混乱,未体现判断队满和新增结点的逻辑。
2. 出队操作部分描述不完整且错误,例如“假设出队元素为...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发