Type: Objective

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

客观题内容

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

正确
错误

source：826 考研初试 2020

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

正确
错误

source：826 考研初试 2023

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

正确
错误

source：826 考研初试 2022

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

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

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

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

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

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

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

正确
错误

source：水木清研 2023 原创

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

正确
错误

source：水木清研 2023 原创

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

正确
错误

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

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

正确
错误

source：水木清研 2025 原创

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

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

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

给定一个采用双向平方试探策略的散列表，长度 $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 个无前导零的十进制整数，开头/末尾/中间均不要出现空白或其他字符。

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

source：水木清研 2025 原创

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

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

正确
错误

source：水木清研 2025 原创

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

正确
错误

source：水木清研 2025 原创

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

source：826 考研初试 2025

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

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

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

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

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

source：826 考研初试 2025

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

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

正确
错误

source：水木清研 2025 原创

一个由 $\{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 即可。

记序列长度为 $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}\}$