CSP-S 提高级 初赛题库

CSP-S 提高级 初赛题库共 51 道题（单项选择题 36 题、多项选择题 10 题、程序阅读题 3 题、程序完善题 2 题），逐题提供题干、选项、正确答案与详细解析，支持按题查看、在线练习与自动批改。

题目列表

• 二叉树第 k 层（根节点为第 1 层）最多有____个节点？二叉树
• 深度为 h 的满二叉树共有____个节点？二叉树
• 有 n 个节点的完全二叉树，其叶子节点个数约为？完全二叉树
• 二叉树的后序遍历（post-order）访问顺序是？遍历
• 大根堆（大顶堆）中，父节点与子节点的关系是？堆
• 若二叉树节点从 1 开始编号，节点 i 的左孩子是？二叉树存储
• n 个顶点的无向完全图 K_n 共有多少条边？图论
• n 个顶点的连通无向图，最少需要几条边？图论
• 用邻接表存储图时，DFS（深度优先搜索）的时间复杂度是？图遍历
• BFS（广度优先搜索）通常借助哪种数据结构实现？图遍历
• Dijkstra 算法主要用于求解？最短路
• 下列哪些算法可求最小生成树（MST）？最小生成树
• 拓扑排序适用于？拓扑排序
• Floyd 算法求解全源最短路的时间复杂度是？最短路
• 动态规划的核心思想包含？动态规划
• 求最长公共子序列(LCS)常用哪种方法？动态规划
• 0-1 背包问题（n 件物品、容量 W）的时间复杂度约为？背包
• 记忆化搜索本质上是？记忆化
• 并查集（Disjoint Set）常用于哪种算法？并查集
• 并查集经路径压缩后，单次操作均摊时间约为？并查集
• 对二叉搜索树(BST)做中序遍历，得到的结果是？二叉搜索树
• 线段树最常用于处理哪类问题？线段树
• 下列哪种不是哈希冲突的解决方法？哈希
• 红黑树、AVL 树属于？平衡树
• 求最大公约数 gcd(a,b) 常用？数论
• 两数的最小公倍数 lcm(a,b) 等于？数论
• 100 以内的质数大约有多少个？数论
• 组合数满足 C(n,k) = ？组合数学
• KMP 字符串匹配算法的核心是利用？字符串
• 字符串哈希（如 Rabin-Karp）常用于？字符串
• 朴素的字符串暴力匹配，最坏时间复杂度是？字符串
• 归并排序的时间复杂度是？排序
• 快速排序在最坏情况下（如已有序且选首元素为基准）的时间复杂度是？排序
• 堆排序的空间复杂度是？排序
• 下列哪种不属于 P 类问题的特征？计算理论
• 由主定理，递推 T(n)=2T(n/2)+O(n) 的解为？复杂度
• 下列哪些排序算法是稳定的？排序
• 关于完全二叉树，下列说法正确的是？完全二叉树
• 图的遍历（Traversal）主要包括？图遍历
• 动态规划适用的问题通常具备哪些特征？动态规划
• 下列哪些可用贪心算法正确求解？贪心
• 并查集的基本操作包括？并查集
• 关于哈希表，下列说法正确的是？哈希
• 下列哪些时间复杂度属于多项式时间（P 类）？复杂度
• 可用于求解单源最短路径的算法有？最短路
• 关于二叉搜索树(BST)，下列说法正确的是？二叉搜索树
• 阅读以下快速排序的 partition（挖坑法）实现，回答子问题：快速排序 partition
• 阅读以下并查集 find（含路径压缩）实现，回答子问题：并查集
• 阅读以下 0-1 背包一维 DP 核心代码，回答子问题：0-1 背包 DP
• 补全以下 Dijkstra 单源最短路的核心框架（填空处用 __ 表示）：Dijkstra 算法
• 补全以下 Kadane 算法（最大子段和）的核心代码：最大子段和