题目描述

本链接包含多道客观题，目前在线评测系统可以支持判断题、单选题、多选题、填空题。

其中，判断题将以单选题的形式部署，填空题将只部署输入形式简单的题目（例如只输入一个整数）。

客观题内容

1. $\log^n n=\Theta (n^{\log n})$。（ {{ select(1) }} ）

• 正确
• 错误

source：826 考研初试 2020

2. 若我们规定向量的扩容/缩容策略为：在向量装填因子为 $100\%$ 之后的一次插入对容量加倍，在装填因子为 $50\%$ 之后的一次删除对容量减半，则可以保证容量调整的均摊复杂度为 $O(1)$。（ {{ select(2) }} ）

• 正确
• 错误

source：826 考研初试 2023

3. 有序向量的二路归并能在线性时间内完成，有序列表则不能。（ {{ select(3) }} ）

• 正确
• 错误

source：826 考研初试 2022

4. 请将以下中缀表达式转为逆波兰表达式：(0!+1)*2^(3!+4)-(5!/6+(7-(8-9))。 （{{ input(4) }}）

source：清华《数据结构》期末 2021

输入的时候，请将相邻两个字符之间用一个英文逗号分隔，最后一个字符后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。

例：3+(3+3) 写成逆波兰表达式为 3,3,3,+,+。

5. 有几种栈混洗方案，使得栈序列 <ABBBA] 得到栈混洗序列 [ABBBA> ？（{{ select(5) }}）

• 5
• 6
• 10
• 12

source：清华《数据结构》期中 2011

6. 给定一个 Huffman 树，交换其中一对深度差为 2 的叶子节点，则交换后依旧是最优 PFC 编码方案。（ {{ select(6) }} ）

• 正确
• 错误

source：水木清研 2023 原创

7. 考虑二叉搜索树的中序遍历，一个节点的后继节点在该节点的右子树当中。（ {{ select(7) }} ）

• 正确
• 错误

source：水木清研 2023 原创

8. 若 AVL 插入元素的过程中发生了旋转操作，则树高必然不变。（ {{ select(8) }} ）

• 正确
• 错误

source：清华《数据结构》期末 2016

9. 若伸展树的旋转调整只有单旋操作，则依旧能保证 $O(\log n)$ 的均摊复杂度。（ {{ select(9) }} ）

• 正确
• 错误

source：水木清研 2025 原创

10. 若一棵红黑树（不考虑外部节点）有 10 个黑节点，则最少和最多有（{{ input(10) }}）个红节点。

source：826 考研初试 2025，补充。

总计输入 2 个整数，分别是最少和最多的红节点个数。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。例如若答案分别是 3 和 10，则输入 3,10。

11. 给定一个采用双向平方试探策略的散列表，长度 $M=2021$，设关键码 $0$ 的试探链的正向/反向分别为 $\{a_0=0,a_1=1,a_2=4,a_3=9,\cdots\}$ 和 $\{b_0=0,b_1=2020,b_2=2017,b_3=2012,\cdots\}$，则 $\{a_i|i=0,1,2,\cdots\}\cap\{b_j|i=0,1,2,\cdots\}$ （即两个试探链的集合取交集）的集合规模为（{{ input(11) }}）

source：清华《数据结构》期末 2021

输入时请输入 1 个无前导零的十进制整数，开头/末尾/中间均不要出现空白或其他字符。

12. 给定以下无向图，其中边上数字代表该边长度，求点 A 到其他各点的最短路径长度。（{{ input(12) }}）

source：水木清研 2025 原创

总计输入 8 个整数，分别是 A 到 B,C,D,E,F,G,H,I 的距离。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。

13. 在一个 $n$ 个点 $m$ 条有向边的图中，若 $m\ge n$，则该图的强连通分量数小于 $n$。（ {{ select(13) }} ）

• 正确
• 错误

source：水木清研 2025 原创

14. 在一个 $n$ 个点 $m$ 条有向边的图中，若该图的强连通分量数小于 $n$，则 $m\ge n$。（ {{ select(14) }} ）

• 正确
• 错误

source：水木清研 2025 原创

15. 将序列 $\{12,29,20,24,70,80,150\}$ 视为完全二叉树的层次遍历，用 floyd 建大根堆后的排列结果为（{{ input(15) }}）

source：826 考研初试 2025

总计输入 7 个整数，分别是序列当中 7 个数的最终排列。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。

16. 给定字符串 CBCBACDCBFBEA，请求其改进 next 表（{{ input(16) }}）。

source：清华《数据结构》期末 2021

总计输入 13 个整数，分别是字符串各位置的改进 next 表（显然第一个数为 -1）。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。

17. 仅采用坏字符（bc）策略的 BM 算法，文本串长度为 2025，只包含字符 0 或者 1。模式串为 x20241222，则最好的情况下只需要比较（{{ input(17) }}）次。

source：826 考研初试 2025

输入一个所有数字均为无前导零的十进制整数，不要在字符串中增加任何空格。

18. 对于 Karp-Rabin 散列算法，若两个字符串的指纹 hash() 相等，则两个字符串必然相等。（ {{ select(18) }} ）

• 正确
• 错误

source：水木清研 2025 原创

19. 一个由 $\{1,2,\cdots,2025\}$ 组成的随机排列，利用快速排序的划分算法（quickSelect）寻找排列中排名为 196 的数（其中最小的数排名为 1，数越大则排名越大，对于本题而言目标查找的数即为 196），则 212 和 2000 进行比较的概率为（ {{ input(19) }} ）。

source：826 考研初试 2025，改编

可以得到概率一定是一个有理分数的形式，因此你的输入格式为 A/B，其中 A 和 B 均为无前导零的十进制整数，不要在字符串中增加任何空格。

请注意，你需要输出最简分数形式。如果你得到的概率为 375/750，则输入答案为 1/2。特殊地，若你得到的概率为 0 或者 1，则直接输入 0 或者 1 即可。

20. 记序列长度为 $N$，则采用以下哪种增量序列进行希尔排序时，做 $O(\log^2 N)$ 趟排序？（ {{ select(20) }} ）。

• $\{2^p~|~p\in \mathbb{N}\}$
• $\{2^{p+1}-1~|~p\in \mathbb{N}\}$
• $\{2^p\cdot 3^q~|~p,q\in \mathbb{N}\}$
• $\{9\times 4^p-9\times 2^p+1~|~p \in \mathbb{N}\}\cup\{4^p-3\times 2^p+1~|~p\in \mathbb{N}\}$

source：826 考研初试 2024

水木清研小程序 - 初试运营服务更新部分

基础推广部分请看客观题测试（826 精选混搭部分）

本次更新部分包含多种挑战练习模式，可以选择自由/套卷练习，可供同学们进行自测。

截止至 2025.8.31，水木清研的初试题库数量为：

• 统考题 580 道，其中 500 道有题解，161 道为公开题目
• 清华本科期中期末题 848 道，其中 464 道题有题解，76 道题为公开题目

目前 25 年统考的初试解析部分已基本完成，其他学科将会尽快更新。此外我们也将逐步更新期中期末题的解析，价格也会随着解析数量增多逐步上调，预购从速~尚未上传解析的题目，亦可由各位同学上传解析，若经过审核通过，会对应发放报酬。

具体折扣期详见水木清研小程序的产品中心介绍。