题目描述

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

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

需要注意的是，其中一部分题目通过本地编写代码程序可能会大幅降低计算与思考量。为了保证达到类似初试的全真模拟练习，请大家自觉规避在本地编写代码解题。

客观题内容

1. 若 $f(n)=O(g(n))$，则未必有 $2^{f(n)}=O(2^{g(n)})$。（ {{ select(1) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2014，判断题

2. 将有序列表 L 分为长 $\Theta(h)$ 的 $k$ 段各段分别置乱，则对 L 进行插入排序，时间复杂度上界为（ {{ select(2) }} ）。

• $\Theta(h\cdot k)$
• $\Theta(h^2\cdot k)$
• $\Theta(h\cdot k^2)$
• $\Theta(h^2\cdot k^2)$

source：清本《数据结构》期中 2014，单选题

3. 由 2019 个无差别节点构成的真二叉树，与由 1009 对括号构成的合法表达式一样多。（ {{ select(3) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2019，判断题

4. 使用容量为 1009 的辅助队列，足以对任一由 2019 个节点构成的二叉树做层次遍历。（ {{ select(4) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2019，判断题

5. 插入排序算法的（ {{ multiselect(5) }} ）特点，是选择排序算法所不具备的。

• 输入敏感性
• 支持在线计算
• 就地性
• 最好情况下复杂度更低

source：清本《数据结构》期中 2019，多选题

6. 对于二叉树中的节点 x，如果以其为根的子树规模不超过以其父节点为根的子树规模的一半（向下取整），则称 x 为“轻节点”。在包含 2019 个节点的二叉树中，一个节点至多可能有（ {{ select(6) }} ）个满足“轻节点”性质的真祖先。

• 8
• 9
• 10
• 11

source：清本《数据结构》期中 2019，单选题

7. 给定逆波兰表达式 0,!,1,2,+,3,4,+,?,+,5,!,6,7,+,8,-,9,*,+,-，若表达式的值为 2023，则 ? 处的运算符为（ {{ select(7) }} ）。

• + 加法
• - 减法
• * 乘法
• / 除法
• ^ 乘方
• ! 阶乘

source：826 考研初试 2023，单选题

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

• 正确
• 错误

source：826 考研初试 2022，判断题

9. 对于一个所有函数参数表仅两个参数的递归调用函数，每次调用函数都是先调用左侧参数的函数，再调用右侧参数的函数，其函数调用栈按照出栈序列排列，恰好与二叉树的（ {{ select(9) }} ）遍历序列相同。

• 先序
• 中序
• 后序
• 层次

source：清本《数据结构》期中 2019，单选题

10. AVL 删除操作可能会导致父亲失衡，而插入操作不可能导致父亲失衡。（ {{ select(10) }} ）

• 正确
• 错误

source：曙梦考研 2023 原创，判断题

11. 存在由（ {{ select(11) }} ）个节点组成的 AVL 树，所有内部节点的平衡因子均不为 0。

• 32
• 33
• 34
• 35

source：826 考研初试 2025，单选题

12. 给定以下函数，传入合法的 $p,q$ 之后，由于函数可能无法终止，所以不能被称之为一个明确的算法。（ {{ select(12) }} ）

• 正确
• 错误

void FailStone(int p, int q) // 0 < p < q
{
    assert(0 < p && p < q);
    while (p != q)
    {
        if (p > q) { int r = q; q = p, p -= r; }
        else { (q & 1) ? (p <<= 1) : (q >>= 1); }
    }
}

source：清本《数据结构》期中 2019，判断题。

13. 在求序列的总和最大区段时，如果存在两个最大子段，他们的子段和都是 2025，则这两个子段一定不重叠。（ {{ select(13) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2025，判断题。

14. 在求直方图最大矩形时，有一种基于单调栈的 One-Pass Scan 算法（可翻阅清华邓俊辉《数据结构》讲义第 04 章对应小节，对应算法代码我们也在下方给出）。若传入直方图的元素是单调的，则栈的最大规模为 $O(\log n)$。（ {{ select(14) }} ）

• 正确
• 错误

i64 one_pass()
{
    std::stack<int> SR;
    i64 maxRect = 0;
    for (int t = 0; t <= n; ++t)
    {
        while (!SR.empty() && (t == n || H[SR.top()] >= H[t]))
        {
            int r = SR.top(); SR.pop();
            int s = SR.empty() ? 0 : (SR.top() + 1);
            maxRect = std::max(maxRect, 1ll * H[r] * (t - s));
        }
        if (t < n) SR.push(t);
    }
    return maxRect;
}

source：清本《数据结构》期中 2025，判断题。

15. $\log\prod\limits_{k=1}^n k^2 = \Theta(n\log ^2 n)$。（ {{ select(15) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2025，判断题。

16. 对一个序列进行冒泡排序，所有元素的移动方向必然全部朝向自己最终所在的位置移动。（ {{ select(16) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2025，判断题。

17. 在插入排序的过程中，序列的循环节可能减少，也可能增加。（ {{ select(17) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2025，判断题。

18. 调用栈中多帧可能对应同一函数的调用，且不一定紧密相邻。（ {{ select(18) }} ）

• 正确
• 错误

source：清本《数据结构》期中 2019，判断题。

19. 给定表达式 $T(n)=\sum\limits_{k=1}^{2025} 64^k\cdot T(n/2^k)+\sqrt[2025]{\prod\limits_{k=6}^{15} n^{k^3}}$，若 $T(n)=\Theta(n^a\cdot\log^b n\cdot(\log\log n)^c)$，则 $a,b,c$ 分别为（ {{ input(19) }} ）。

总计输入 3 个非负整数，分别是 $a,b,c$ 的值。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。假设你得到的答案是 $O(n^3\log\log n)$，那么请输入 3,0,1。

source：清本《数据结构》期中 2025，填空题。

20. 长度为 $100$ 的某序列（序列下标为 $0,1,\cdots,99$）若共包含 $4560$ 个逆序对，则其中至少有（ {{ input(20) }} ）个逆序对完全落在区段 $[10,80)$ 内。

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

source：清本《数据结构》期中 2025，填空题。

21. 若字符频数为 $\{ \text{A}:2025, \text{B}:1013, \text{C}:507, \text{D}:254, \text{E}:x \}$。请你按照升序排列写出所有正整数 $x$，使得构造的 Huffman 树存在权重相等的节点（叶子节点的权重为对应字符频数，非叶子节点的权重为左右两个儿子权重的加和，由于 Huffman 树为真二叉树，因此非叶子节点的左右子节点显然都存在）。（ {{ input(21) }} ）

总计输入若干个正整数，分别是满足要求的值。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格，所有数字需要升序排列。英文逗号为 ,。假设你得到的答案是 114、514、1919、810，那么请输入 114,514,810,1919。

source：清本《数据结构》期中 2025，填空题。

接下来 22~25 题使用同一段代码。

给定一个函数（其中有两段代码的后方加入了 /**/ 类型的注释，注明了其操作内容）：

template <typename T> void puded(T* A, int &n) {
    for (int k = 0, i; k < n;) {
        for (i = 0; A[i] != A[k]/* CMP 操作 */; i++);
        if (i != k) {
            while (++i < n)
                A[i - 1] = A[i]; /* MOV 操作 */
            n--;
        } else
            k++;
    } // for
} // puded

22. puded 算法的功能是（ {{ select(22) }} ）

• 有序向量去重，相同关键码保留第一次出现位置
• 有序向量去重，相同关键码保留其中任意一次出现位置（随机保留）
• 无序向量去重，相同关键码保留最后一次出现位置
• 无序向量去重，相同关键码保留其中任意一次出现位置（随机保留）

23. 若 $\text{A}=\{2,0,2,5,1,1,0,9\}$，那么在 puded<int>(A, 8) 的过程当中，CMP 和 MOV 操作分别执行了多少次？（ {{ input(23) }} ）

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

24. 若 $\text{A}=\{3,0,2,4,0,1,8,4\}$，那么在 puded<int>(A, 8) 的过程当中，CMP 和 MOV 操作分别执行了多少次？（ {{ input(24) }} ）

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

25. 实际上，两类操作的总次数仅取决于数组的长度 $n$，而与其内容无关。设其公式为 $\dfrac{a}{b}n^3+\dfrac{c}{d}n^2+\dfrac{e}{f}n+\dfrac{g}{h}$，则 $a,b,c,d,e,f,g,h$ 分别为（ {{ input(25) }} ）。原题还需要进行阐述证明，由于客观题布置限制，此处省略，请各位用户自觉进行推导。

总计输入 8 个整数，分别是 $a,b,c,d,e,f,g,h$ 的值。输入的时候，所有数字均为无前导零的十进制整数，请将相邻两个数字之间用一个英文逗号分隔，最后一个数字后不要加逗号，不要在字符串中增加任何空格。英文逗号为 ,。若输入数字为负数，请使用英文符号 -。

请注意，你需要输出最简分数形式。如果你得到的其中一组分数为 375/750，则对应的输入片段应为 1,2。若你得到的分数为 0 或者 1，则输入片段为 0,1 或者 1,1 即可。其他非负整数 $x$ 同理输入 x,1。若分数为负数，则分子输入负数，分母输入正数即可。

假设你得到的答案是 $\dfrac{2}{3}n^3+n-6$，那么请输入 2,3,0,1,1,1,-6,1。

source：清本《数据结构》期中 2025，简答题。

曙梦教育科技 - 清华 826 初试运营相关内容

前述更新部分可见小题精选 202506和小题精选 202508。

曙梦 OJ 题解系列与曙梦考研解析系列均详细部署在曙梦教育科技 web 平台，需要绑定微信公开平台进行注册/登录。之前介绍过的相关小程序使用体验请搭配 web 端平台进行查看（目前 web 端只完成了基础功能开发，支持题库和知识点指南的查看，后续我们在同步小程序全部功能的同时，也会持续向用户征集新需求，持续进行迭代开发）。

相关产品介绍可详见该推文，6 月的促销活动已在筹备当中，请等待我们后续的更新通知。

此外，原本使用的小程序平台二维码见下方，之后的主体功能更新将集中在 web 平台，小程序只用作内容同步以及便携刷题，并定期集成刷题功能。