知识点练习

执行下列代码后，cnt 的值是（ ）。

用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。

把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ ）。

将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。

$3^{2026}mod 100$ 的值是（ ）。

有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。

树状数组维护长度 $n=16$ 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ ）。

有向无环图 $G$ 顶点集为 ${1, 2, 3, 4}$，边集为 ${(1, 2), (1, 3)}$，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。

某分治算法满足 $T(n)=T(n/3)+T(2n/3)+Θ(n)$，$T(1)=O(1)$，则 $T(n)$ 是（ ）。

无根树含 9 个结点（编号为 1—9），边集为 ${(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (6, 7), (7, 8), (5, 9)}$。该树的直径（以边数计）与重心分别是（ ）。

一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个，出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。

含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。

字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。

用归并排序统计逆序对，合并部分的核心代码为：

执行 power(2, 100, 1000) 调用下列函数，返回值是（ ）。

有 $5$ 个红色球和 $5$ 个蓝色球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

在 KMP 算法中，对于模式串 $P = \tt{abacaba}$，其 next 数组（next[i] 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？

对一个大小为 $16$（下标 $0\sim 15$）的数组上构建满线段树。查询区间 $[3, 11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

将字符串 $\tt cat$, $\tt car$, $\tt cart$, $\tt case$, $\tt dog$, $\tt do$ 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），其拓扑排序的结果有多少种可能？

在一个大小为 13 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 13$。依次插入关键字 $18, 26, 35, 9, 68, 74$。插入 $74$ 后，它最终被放置在哪个索引位置？

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权为 $|7 - 3| = 4$。该图的最小生成树总权重是多少？

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$，那么该树的前序遍历是什么？

一个 $0-1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$。装入背包的物品能获得的最大总价值是多少？

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（LCA）是结点 $4$。那么下列哪个结点的 LCA 组合是不可能出现的？