发帖
雷达卡
已知带头结点的非空单链表L，其头指针为 h，指针 p 指向链表中间的一个结点（既不是首结点也不是尾结点）。执行以下操作：
q = p->next; p->next = q->next; q->next = h->next; h->next = q;
该段代码的作用是将 q 所指向的结点移动至头结点之后的第一个位置。因此，其功能是将 q 指向的结点插入到 h 的后面。
正确选项为：D、把q指向的结点插入到h的后面
[此处为图片1]
对于表达式 x + y * (z - u) / v，将其转换为等价的后缀表达式（逆波兰表示）时，需遵循运算符优先级和结合性规则：
- 括号内先计算：z - u → zu-
- 乘除优先于加法：y * (zu-) / v → yzu-*v/
- 最后执行加法：x + (yzu-*v/) → x yzu-*v/+
因此，正确的后缀表达式为：xyzu-*v/+
正确选项为：A.xyzu-*v/+
[此处为图片2]
设 p、q、v 是二叉树 T 中的三个结点，且中序遍历结果为 …, p, v, q, …，其中 v 有两个孩子结点。根据中序遍历“左-根-右”的特性：
- p 出现在 v 之前，说明 p 在 v 的左子树中最右侧路径上的某个末端；由于 v 有左孩子，那么 p 必然没有右孩子（否则中序会继续向右延伸），即 p 无右孩子。
- q 出现在 v 之后，说明 q 在 v 的右子树中最左侧路径上；由于 v 有右孩子，q 是其右子树中第一个被访问的结点，故 q 不可能是某个结点的右子树末端，而应是左子树起点，因此 q 没有左孩子。
综上所述，p 没有右孩子，q 没有左孩子。
正确选项为：A.p 没右孩子，q 没左孩子
[此处为图片3]
给定一个无向图的邻接多重表结构，要求求出顶点 b 和 d 的度。
在邻接多重表中，每条无向边仅存储一次，但通过指针关联两个顶点。每个边结点若与某顶点相关联，则该顶点的度为其关联的边结点数量。
假设从结构分析得：
- 顶点 b 参与了 4 条边 → 度为 4
- 顶点 d 参与了 2 条边 → 度为 2
因此，b 和 d 的度分别为 4 和 2。
正确选项为：B.4, 2
[此处为图片4]
下列数据结构中，不适合直接使用折半查找的是：
- 有序链表：无法实现随机访问，折半查找失效 → 不适合
- 无序数组：未排序，不满足折半查找前提 → 不适合
- 有序静态链表：虽逻辑有序，但物理上非连续且不能随机访问 → 不适合
- 无序静态链表：既无序又无法高效访问 → 不适合
所有四项均不满足折半查找的基本条件（有序 + 支持随机访问）。
正确选项为：D.I、II、III、IV
[此处为图片5]
KMP算法中，采用修正后的 next 数组进行模式匹配。给定模式串 S = "aabaab"，求当失配发生时，模式串最多可向右滑动的距离。
首先构造 next 数组（或称 fail 数组）：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 字符 | a | a | b | a | a | b |
| next | -1 | 0 | 1 | 0 | 1 | 2 |
最大真前后缀匹配长度为 2，因此最远滑动距离为当前匹配长度减去 next 值，最大可滑动 4 位（例如在末尾失配时）。
但题目问的是“向右滑动的最长距离”，即模式串可跳跃的最大位数，实际由最长公共前后缀决定，滑动距离为 len - next[len]，即 6 - 2 = 4。
正确选项为：B.4
[此处为图片6]
使用快速排序对含有 N（N ≥ 3）个元素的数组 M 排序，第一趟排序以某一枢轴划分其余 N-1 个元素为 P 和 Q 两部分。
快速排序的核心思想是分治：选择一个基准元素，使得比它小的放左边（P），大的放右边（Q），但块内并不有序，仅完成一次划分。
- A. P 和 Q 块间有序 —— 正确，P 整体小于 Q
- B. 块内有序 —— 错误，仅第一趟不可能有序
- C. 元素个数大致相等 —— 不一定，取决于枢轴选择
- D. 不存在相等元素 —— 无关，可能存在重复值
唯一正确的描述是 A：P 和 Q 块间有序。
正确选项为：A. P 和 Q 块间有序
[此处为图片7]
已知关键字序列 28, 22, 20, 19, 8, 12, 15, 5 构成一个大根堆（最大堆）。
删除操作流程如下：
- 第一次删除 28（堆顶），将最后一个元素 5 移至根部，向下调整：比较左右孩子（22 和 20），取较大者 22 上浮；再比较 5 与 19、12 等，最终形成新堆：22, 19, 20, 5, 8, 12, 15
- 第二次删除 22，用 15 替换根，重新调整：比较 19 和 20，选 20 上浮；然后比较 15 与 19 和 12，最终得到：20, 19, 15, 12, 8, 5
两次删除后，堆的层序遍历为：20, 19, 15, 12, 8, 5
正确选项为：A. 20, 19, 15, 12, 8, 5
[此处为图片8]
初始有三个升序序列：(3, 5)、(7, 9)、(6)，按从左至右顺序进行二路归并排序。
归并过程如下：
- 先合并前两个序列 (3,5) 和 (7,9)：
- 3 与 7 比较 → 输出 3
- 5 与 7 比较 → 输出 5
- 剩余 7,9 直接输出
- 共 2 次比较
- 将结果 (3,5,7,9) 与第三个序列 (6) 合并：
- 3 与 6 比较 → 输出 3
- 5 与 6 比较 → 输出 5
- 6 与 7 比较 → 输出 6
- 剩余 7,9 输出
- 共 3 次比较
总比较次数 = 2 + 3 = 5
正确选项为：C. 5
[此处为图片9]
在外排序中，利用败者树对多个初始为升序的归并段进行多路归并。
败者树是一种用于选择最小（或最大）元素的完全二叉树结构。在最小值归并中，每次选出最小关键字所在段。
其中，“冠军”节点保存的是胜出者的信息，即拥有当前最小关键字的归并段编号。
因此，记录“冠军”的结点保存的是：最小关键字所在的归并段号
正确选项为：D、最小关键字所在的归并段号
[此处为图片10]
分析如下 C 语言代码：
int i = 32777; short si = i; int j = si;
变量 i 为 int 类型，赋值 32777，在 16 位 short 范围外（通常为 -32768 ~ 32767），因此强制截断存储时会发生溢出。
将 32777 强制转为 short：
- 32777 的二进制（补码）低 16 位为：1000 0000 0000 1001
- 最高位为 1，解释为负数，其值为 -(2^15 - 777) = ? 实际计算：该二进制等于 -32759（因为 32777 - 65536 = -32759）
所以 si = -32759，再赋值给 j（int 类型），符号扩展仍为 -32759。
最终 j 的值为 -32759。
正确选项为：B. -32759
[此处为图片11]
京公网安备 11010802022788号
