正在载入在线练习界面，本页内容可直接阅读…

AK CSP › 知识点练习 › 算法概念与复杂度分析

算法概念与复杂度分析真题练习（共 66 题）

第4章 算法 · 入门+提高级考点 · 覆盖 CSP-J / CSP-S / NOIP 普及与提高组历年真题 · 免费在线练习

「算法概念与复杂度分析」是信息学奥赛初赛的核心考点之一。本页汇集该考点下全部 66 道历年真题，每题提供答案与深度题解，可按年份逐卷练习，也可以在页面载入后直接在线作答。

NOIP 提高 2018 第一轮（1 题）

  1. 第 5 题 设某算法的时间复杂度函数的递推方程是T(n)=T(n-1)+n(n 为正 · 单项选择

NOIP 提高 2017 第一轮（2 题）

  1. 第 6 题 则该算法的时间复杂度为（ ） · 单项选择
  2. 第 11 题 设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并 · 单项选择

NOIP 提高 2016 第一轮（2 题）

  1. 第 5 题 以比较作为基本运算，在N个数中找最小数的最少运算次数为（ · 单项选择
  2. 第 14 题 假设某算法的计算时间表示为递推关系式 · 单项选择

NOIP 提高 2015 第一轮（2 题）

  1. 第 10 题 设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + · 单项选择
  2. 第 11 题 具有n个顶点，é条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍 · 单项选择

NOIP 提高 2014 第一轮（2 题）

  1. 第 12 题 同时查找 2n 个数中的最大值和最小值，最少比较次数为（ ）. · 单项选择
  2. 第 15 题 以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出 · 单项选择

NOIP 提高 2013 第一轮（4 题）

  1. 第 7 题 斐波那契数列的定义如下：F_1 = 1, F_2 = 1, F_n = · 单项选择
  2. 第 14 题 与原数符号相反 · 单项选择
  3. 第 15 题 T(n) 表示某个算法输入规模为 n 时的运算次数。如果 T(1) 为常 · 单项选择
  4. 第 19 题 CCFNOIP2013初赛提高组C++语言试题 · 不定项选择

NOIP 提高 2012 第一轮（2 题）

  1. 第 11 题 如果对于所有规模为 n 的输入，一个算法均恰好进行（ ）次运算，我们可以 · 不定项选择
  2. 第 20 题 以下关于计算复杂度的说法中，正确的有（ · 不定项选择

NOIP 提高 2011 第一轮（2 题）

  1. 第 6 题 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ · 单项选择
  2. 第 7 题 应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最 · 单项选择

NOIP 普及 2018 第一轮（1 题）

  1. 第 9 题 同时找数组最大值和最小值的比较下界 · 单项选择

NOIP 普及 2017 第一轮（1 题）

  1. 第 17 题 合并两个有序数组的最坏比较次数 · 单项选择

NOIP 普及 2015 第一轮（1 题）

  1. 第 19 题 由递推式判断算法时间复杂度 · 单项选择

NOIP 普及 2011 第一轮（2 题）

  1. 第 12 题 空间复杂度中“空间”的含义 · 单项选择
  2. 第 13 题 双向链表查找的最快时间复杂度 · 单项选择

NOIP 普及 2010 第一轮（1 题）

  1. 第 12 题 基于比较排序的时间复杂度下界 · 单项选择

CSP-S 2025 第一轮（4 题）

  1. 第11题 递归关系式 T(n) = 2T(n/2) + O(n^2) 描述了某个分 · 单项选择
  2. 第26题 程序阅读第 2 题 · 第 5 小题 · 阅读程序·单选
  3. 第27题 程序阅读第 2 题 · 第 6 小题 · 阅读程序·单选
  4. 第32题 程序阅读第 3 题 · 第 5 小题 · 阅读程序·单选

CSP-S 2024 第一轮（5 题）

  1. 第2题 假设一个长度为n的整数数组中每个元素值互不相同，且这个数组是无序的。要找 · 单项选择
  2. 第18题 假设数组c长度无限制，该程序所实现的算法的时间复杂度是0(b)的。（） · 阅读程序·判断
  3. 第21题 假设数组 dp长度无限制，函数solve（)所实现的算法的时间复杂度是0 · 阅读程序·判断
  4. 第27题 假设程序运行前能自动将 maxn 改为 n+1，所实现的算法的时间复杂度 · 阅读程序·判断
  5. 第28题 时间开销的瓶颈是init()函数。（ · 阅读程序·判断

CSP-S 2023 第一轮（5 题）

  1. 第3题 假设n是图的顶点的个数，m是图的边的个数，为求解某一问题有下面四种不同时 · 单项选择
  2. 第15题 现在用如下代码来计算x"，其时间复杂度为（） · 单项选择
  3. 第25题 solve1（n）的时间复杂度为（ · 阅读程序·单选
  4. 第26题 solve2(n）的时间复杂度为（ · 阅读程序·单选
  5. 第31题 设a数组中最大值减最小值加1为A，则f函数的时间复杂度为（） · 阅读程序·单选

CSP-S 2022 第一轮（7 题）

  1. 第13题 对于给定的n，分析以下代码段对应的时间复杂度，其中最为准确的时间复杂度为 · 单项选择
  2. 第14题 以比较为基本运算，在n个数的数组中找最大的数，在最坏情况下至少要做（）次 · 单项选择
  3. 第19题 该算法最坏情况下的时间复杂度为（）。 · 阅读程序·单选
  4. 第23题 该算法的空间复杂度仅与n有关。（ · 阅读程序·判断
  5. 第24题 该算法的时间复杂度为 0(m(n+k))。 （) · 阅读程序·判断
  6. 第26题 若val[i]的最大值为100，k取（）时算法运算次数最少。 · 阅读程序·单选
  7. 第28题 该算法的时间复杂度为 0(logk n)。（) · 阅读程序·判断

CSP-S 2021 第一轮（5 题）

  1. 第5题 以比较为基本运算，对于2n个数，同时找到最大值和最小值，最坏情况下需要的 · 单项选择
  2. 第12题 斐波那契数列的定义为：F1=1，F2=1，Fn=Fn-1+Fn-2（n · 单项选择
  3. 第25题 solve1（1，n）的时间复杂度为（） · 阅读程序·单选
  4. 第26题 solve2（1，n）的时间复杂度为（ · 阅读程序·单选
  5. 第31题 设输入字符串长度为 n，encode函数的时间复杂度为（）。 · 阅读程序·单选

CSP-S 2020 第一轮（6 题）

  1. 第14题 对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短 · 单项选择
  2. 第24题 阅读程序：当输入的 d[i] 是严格单调递增序列时，第 17 行的 sw · 阅读程序·单选
  3. 第25题 阅读程序：当输入的 d[i] 是严格单调递减序列时，第 17 行的 sw · 阅读程序·单选
  4. 第26题 阅读程序：若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情 · 阅读程序·单选
  5. 第27题 阅读程序：若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( · 阅读程序·单选
  6. 第30题 若两个字符串的长度均为n，则最坏情况下，此程序的时间复杂度为 · 阅读程序·判断

CSP-S 2019 第一轮（3 题）

  1. 第20题 （3分）若输入的a数组是一个严格单调递增的数列，此程序的时间复 · 阅读程序·单选
  2. 第21题 最坏情况下，此程序的时间复杂度是（ · 阅读程序·单选
  3. 第27题 此程序的时间复杂度是（）。 · 阅读程序·单选

CSP-J 2024 第一轮（1 题）

  1. 第 29 题 程序（三）：b越大运行时间是否越长 · 阅读程序

CSP-J 2022 第一轮（2 题）

  1. 第 25 题 程序（二）：g(n,m)的时间复杂度 · 阅读程序
  2. 第 28 题 程序（三，牛顿迭代求平方根）：时间复杂度是否为O(log n+k) · 阅读程序

CSP-J 2021 第一轮（3 题）

  1. 第 4 题 找最大数最坏情况最少比较次数 · 单项选择
  2. 第 25 题 程序（二）：decode函数时间复杂度 · 阅读程序
  3. 第 31 题 程序（三）：init函数的时间复杂度 · 阅读程序

CSP-J 2019 第一轮（2 题）

  1. 第 30 题 程序（三）：n=100最坏情况比较次数 · 阅读程序
  2. 第 31 题 程序（三）：n=100最好情况比较次数 · 阅读程序

真题版权归 CCF 所有，本站仅用于非商业教学用途。 京ICP备2026056990号-1 京公网安备11010502062986号