🏷️ 知识点：删除
已知头指针 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);
[tag_link]
正确答案：D
删除 头结点后一个结点的基本流程为q = h->next; h->next = q->next; free(q);，即通过指针操作跳过下一个结点后删除该结点。 由于题目中提到了该链表非空，所以可以确定q = h->next一定不为空。 但是如果链表中只有一个结点的话，我们还需要在删除该结点后，将尾指针指向头结点的位置，即if (p == q) p = h;
下列关于非空 B 树的叙述中，正确的是（ ）
I. 插入操作可能增加树的高度
II. 删除操作一定会导致叶结点的变化
III. 查找某关键字一定是要查找到叶结点
IV. 插入的新关键字最终位于叶结点中
A. 仅 I B. 仅 I、II C. 仅 III、IV D. 仅 I、II、IV
[tag_link]
正确答案：B
在 B 树 中，插入 操作可能导致节点分裂。如果根节点已满，插入新键会触发根节点分裂，生成一个新的根节点，从而增加树的高度。因此，插入操作确实可能（但不一定）增加树的高度。选项 I 正确。删除 操作可能涉及以下情况：
- 删除的键在叶子结点：直接从叶子结点移除该键，导致叶子结点内容变化。
- 删除的键在非叶子结点：B 树会用前驱或后继键（通常位于叶子结点）替换该键，然后删除前驱或后继键。这仍然会导致叶子结点的变化。
- 删除后触发合并或借键：如果删除键后某个节点键数低于最小要求（通常 ⌈m / 2⌉ − 1），可能需要从兄弟节点借键或与兄弟节点合并。这些操作可能涉及叶子结点（例如，合并两个叶子结点或调整叶子结点的键）。在所有删除场景中，无论是直接删除键还是通过替换、合并、借键，操作最终都会影响叶子结点（键的移除或调整发生在叶子结点）。选项 II 正确。查找关键字并不一定需要查找到叶子结点。例如，如果目标键位于根节点或中间节点，查找会在这些非叶子结点停止。选项 III 错误。新关键字在 B 树中开始总是被插入到叶子结点中，但是可能随着分裂上溢到非叶子结点，选项 IV 错误。
已知一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点中的关键字是（）。
A. 60
B. 60, 62
C. 62, 65
D. 65
[tag_link]
正确答案：D本题考察 B 树的 删除 操作。对于上图所示的 3 阶 B 树，被删关键字 78 所在结点在删除前的关键字个数 = 1 = ⌈3/2⌉-1，且其左兄弟结点的关键字个数 = 2 ≥ ⌈3/2⌉，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
