文章

100

粉丝

0

获赞

0

访问

10.6k

头像
2019年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年8月23日 21:10
阅读数 48

(1) 入队操作和出队操作的时间复杂度始终保持为 O(1) ,则因选择顺序存储结构。

(2) 队空:Q.front == Q.rear==0, 队满:(Q.rear+1)%MaxSize == Q.front,其中f为指向队列第一个元素的指针,r为指向队列尾元素后一位置的指针,MaxSize为队列的最大长度。

(3)

(4)入队时,让元素放在rear指向的位置,然后Q.rear==(Q.rear+1)%MaxSize。

出队时,让front指向的元素出队,然后Q.front == (Q.front+1)%MaxSize.


评分及理由

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

学生答案选择顺序存储结构,但标准答案要求链式存储结构(循环链表)。因为题目要求出队后空间只增不减且可重复使用,顺序存储结构无法满足空间只增不减(需要固定大小数组),而链式存储可以动态增加节点。因此逻辑错误,扣2分。

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

学生答案使用顺序存储结构,但标准答案要求链式存储结构(循环链表)。学生给出的队空条件(Q.front == Q.rear == 0)和队满条件((Q.rear+1)%MaxSize == Q.front)是针对顺序循环队列的,且依赖固定MaxSize,但题目要求空间只增不减(无最大长度限制),因此逻辑错误。但学生正确画出了初始状态(front和rear均为0),得1分;队空条件正确(顺序结构下),但队满条件不适用本题,扣3分。本部分得1分。

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

学生答案显示顺序存储结构(数组)中第一个元素入队后rear指向1,front指向0,但标准答案要求链式结构(循环链表)状态。逻辑错误,但状态本身在顺序结构下正确,得1分。

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

学生答案描述顺序循环队列的入队和出队操作(通过模运算维护指针),但标准答案要求链式结构操作(动态增加节点)。操作逻辑错误(不满足空间只增不减),但操作在顺序结构下时间复杂度为O(1),得1分。

题目总分:0+1+1+1=3分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发