数据结构线性表真题

2021年

【2021年题1】 已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为

其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。

A. h->next = h->next->next; q = h->next; free(q);

B. q = h->next; h->next = h->next->next; free(q);

C. q = h->next; h->next = q->next; if(p != q)p = h; free(q);

D. q = h->next; h->next = q->next; if(p == q)p = h; free(q);

解析：

如图 1 所示，要删除带头结点的非空单循环链表中的第一个元素，就要先用临时指针 q 指向待删结点，q = h->next；然后再将 q 从链表中断开，h->next = q->next（这一步也可写成 h->next = h->next->next）；此时要考虑一种特殊情况，若待删结点是链表的尾结点，即循环单链表中只有一个元素（p 和 q 指向同一个结点），如图 2 所示，则在删除后要将尾指针指向头结点，即 if(p == q) p = h；最后释放 q 结点即可，答案选 D。

[链表删除示意图]

【2021年题2】 已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1, 2, 3, 4, 5，则不能得到的出队序列是（ ）。

A. 5, 4, 3, 1, 2   B. 5, 3, 1, 2, 4   C. 4, 2, 1, 3, 5   D. 4, 1, 3, 2, 5

解析：

假设队列左端允许入队和出队，右端只能入队。对于 A，依次从右端入队 1, 2，再从左端入队 3, 4, 5。对于 B，从右端入队 1, 2，然后从左端入队 3，再从右端入队 4，最后从左端入队 5。对于 C，从左端入队 1, 2，然后从右端入队 3，再从左端入队 4，最后从右端入队 5。无法验证 D 的出队序列，故选 D。

[队列操作示意图]

【另解】队列两端都可以入队，入队结束后，队列中的序列（或逆序）可视输出队序列。由于入队序列是从小到大的顺序，因此左端入队的子序列满足从大到小的顺序，右端入队的子序列满足从小到大的顺序。A、B 和 C 都满足这样特点，只有 D 不满足，故选 D。

【2021年题3】 已知二维数组 A 按行优先方式存储，每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100，A[3][3] 的存储地址是 220，则元素 A[5][5] 的存储地址是（ ）。

A. 295   B. 300   C. 301   D. 306

解析：

二维数组 A 按行优先存储，每个元素占用 1 个存储单元，由 A[0][0] 和 A[3][3] 的存储地址可知 A[3][3] 是二维数组 A 中的第 121 个元素，假设二维数组 A 的每行有 n 个元素，则 $n \times 3 + 4 = 121$，求得 ，故元素 A[5][5] 的存储地址为 ，故选 B。