[不定项选择题]
我觉得选AC
逐选项解析： 选项A 错误。 模拟队列（先进先出）仅需**2个栈即可实现: 用“入队栈”存储新元素，“出队栈”负责弹出元素（若出队栈为空，将入队栈的所有元素转移到出队栈，实现顺序反转）。 无需第3个栈，因此“至少需要3个栈”的说法错误。
选项B 正确。 这是平衡二叉搜索树（AVL树）的核心定义：任一节点的左右子树高度差（平衡因子）的绝对值不超过1，平衡因子只能是`-1、0、1`。
选项C 错误。 优先队列通常基于二叉堆实现，插入元素时需要通过“上浮”操作调整堆的结构，时间复杂度由堆的高度决定（完全二叉树的高度为$\log_2n$），因此插入操作的时间复杂度是O(log n)，而非O(1)。
选项D 正确。 `HashMap`基于哈希表实现，平均情况下插入、查找的时间复杂度为O(1)； `SortedMap`（如Java的`TreeMap`）基于红黑树实现，插入、查找的时间复杂度为O(log n)。 因此常规场景下`HashMap`的插入/查找速度更快（`SortedMap`的优势是“有序性”）。
发表于 2026-02-10 19:34:11
回复(0)
选AC
A. 至少需要 3 个栈才能模拟一个队列的操作 → 错误
模拟队列的核心是实现先进先出，仅需 2 个栈即可完成：
- 栈 1（入队栈）：专门接收入队元素，正常压栈；
- 栈 2（出队栈）：当需要出队 / 取队首时，若栈 2 为空，将栈 1 的所有元素依次弹出并压入栈 2（此时栈 2 的栈顶就是原队列的队首），再从栈 2 弹栈实现出队。 无需第 3 个栈，因此 “至少 3 个” 的说法错误。
B. 平衡二叉搜索树（AVL）要求任一节点的左右子树高度差的绝对值不超过 1（即平衡因子 ∈ {−1, 0, 1}）→ 正确
AVL 树的核心平衡定义：节点的平衡因子 = 左子树高度 - 右子树高度，要求所有节点的平衡因子只能是 - 1、0、1，若插入 / 删除后违反该规则，会通过旋转（左旋、右旋、左右旋、右左旋） 重新平衡。
C. 优先队列的插入操作复杂度是 O（1）→ 错误
优先队列的底层通常基于二叉堆（大顶堆 / 小顶堆） 实现，插入元素的过程为：
- 先将元素插入堆的末尾（O (1)）；
- 再通过上浮（percolate up） 调整堆的结构，使其满足堆的性质，该过程的时间复杂度为O(log n)（堆的高度为 log₂n，最多上浮 log n 层）。 因此插入操作的时间复杂度是O(log n)，而非 O (1)。
D. HashMap 比 SortedMap 在插入和查找操作上速度更快 → 正确
- HashMap：底层是数组 + 链表 / 红黑树，基于哈希表实现，平均时间复杂度为 O (1)（哈希无冲突时直接通过哈希值定位数组下标）；
- SortedMap（如 Java 中的 TreeMap）：底层是红黑树，属于有序的平衡二叉搜索树，插入和查找需通过树的遍历实现，时间复杂度为O(log n)。
- 因此在平均场景下，HashMap 的插入 / 查找速度远快于 SortedMap（SortedMap 的优势是有序性，而非查询 / 插入效率）。
发表于 2026-02-10 16:05:26
回复(0)
问题信息
难度：
3条回答
19收藏
236浏览
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
