考研 408 · 数据结构算法题与复杂度
这张图讲什么
「考研 408 · 数据结构算法题与复杂度」是 SeekFlaw 编辑团队整理的思维导图,分 6 个一级分支:循环和递归的时间复杂度怎么数;408 算法设计题怎么答才不丢分;顺序表与数组类算法题的常用套路;单链表类算法题的常用套路;二叉树类算法题的常用套路;图、排序与查找思想在算法题里的用法,共 55 个节点、54 张记忆卡。
这张图面向考研 408 的数据结构大题,不重讲概念,只讲怎么做题。共六块:循环和递归的时间复杂度怎么数;算法设计题的答题框架;顺序表与数组套路(原地删除、三次逆置、两端夹逼、投票、标记数组);单链表套路(快慢指针、先后指针、公共结点、重排);二叉树套路(递归三问、层序、判定类);图、排序与查找思想的借用。建议先看前两块,再按题型各练一遍小例子, 手走一遍比背代码有用。
5 个要点
- 循环和递归的时间复杂度怎么数:复杂度题先找基本操作 (最内层执行次数最多的语句),设它执行 t 次,列出 t 与 n 的关系,再取最高阶。
- 408 算法设计题怎么答才不丢分:算法题一般要交三样:基本设计思想、用 C 或 C++ 描述的算法(关键处加注释)、时间和空间复杂度。
- 顺序表与数组类算法题的常用套路:数组题的核心是把下标当指针用:保留型双指针原地删除、三次逆置做循环移位、两端夹逼、归并式计数、投票找主元素、用标记数组换时间。
- 单链表类算法题的常用套路:链表题大多是指针的相对位置问题:快慢指针找中点和判环,先后指针找倒数第 k 个,对齐长度找公共结点,再由找中点、逆置、合并拼出综合题。
- 二叉树类算法题的常用套路:树的题大多用递归:先假设左右子树的结果已经求出,再想根这一层怎么合并。
适用:考研备考。用法:点开任一节点先自己答,再翻面核对。
发布于
一句话:这张图把「考研 408 · 数据结构算法题与复杂度」整理成 55 个节点、54 张记忆卡;点开节点翻面就能看答案。
从考研大题角度讲时间复杂度怎么数、算法设计题怎么答,以及顺序表、链表、二叉树、图四类题的常用套路,每个套路配自编小例。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。
SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。
55 个节点 · 54 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-18。
先看这 3 条
- 分析循环时间复杂度的通用步骤是什么:找出最内层的基本操作,设循环执行 t 次,写出第 t 次后循环变量的值,令它刚好不满足循环条件,解出 t 与 n 的关系,最后 只留最高阶、去掉系数 。
- 怎样原地删除顺序表中所有值为 x 的元素:用下标 k 记录 已保留的元素个数 :从头扫描,不等于 x 的元素搬到 A[k] 并让 k 加 1,扫完把表长改为 k。
- 怎样用广度优先搜索求无权图的单源最短路径:从源点做广度优先搜索,某顶点 第一次被访问时 的层数就是它到源点的最短路径长度,因为广度优先是按距离由近到远扩展的。
循环和递归的时间复杂度怎么数
- 分析循环时间复杂度的通用步骤是什么:找出最内层的基本操作,设循环执行 t 次,写出第 t 次后循环变量的值,令它刚好不满足循环条件,解出 t 与 n 的关系,最后 只留最高阶、去掉系数 。 步骤 ①找基本操作;②写出循环变量随次数 t 的变化规律;③代入终止条件解出 t;④…
- 循环条件是 i 的平方不超过 n 时复杂度是多少:是 $O(\sqrt n)$。 i=1; while(i*i<=n) i++; 中 i 每次加 1,循环体执行的条件是 $i^2\le n$,所以共执行 $\lfloor\sqrt n\rfloor$ 次。 例 n 取 30:i 为 1 …
- 内层循环次数依赖外层变量时怎么算:把内层的执行次数 按外层变量逐项求和 ,不能直接「外层次数乘内层最大次数」后就下结论(阶数常常一样,但填空题要的精确次数会错)。 例 for(i=1;i<=n;i++) for(j=1;j<=i;j++) x++; 执行 $1+2+\cd…
- 外层变量成倍增长、内层跑到外层变量时复杂度是多少:是 $O(n)$, 不是 $O(n\log n)$。 for(i=1;i<=n;i=i*2) for(j=1;j<=i;j++) x++; 内层总次数是等比数列求和:$1+2+4+\cdots+2^k$($2^k\le n$),等于 $2…
- 递归算法的时间复杂度怎么求:先写出递推式 $T(n)$,再 逐层展开到递归出口 求和。常见结论: $T(n)=T(n-1)+O(1)$:$O(n)$,如递归求阶乘 $T(n)=T(n-1)+O(n)$:$O(n^2)$,如快速排序最坏情况 $T(n)=T(n/2)+…
- 主定理的简化版怎么用:对 $T(n)=aT(n/b)+\Theta(n^d)$($a\ge 1$,$b\gt 1$,$d\ge 0$), 比较 a 和 $b^d$: $a\lt b^d$:$T(n)=\Theta(n^d)$ $a=b^d$:$T(n)=\Th…
- 递归算法的空间复杂度怎么算:等于 递归栈的最大深度 乘每层占用的空间,再加上额外申请的辅助空间。 例 递归求 n 的阶乘:深度 n,空间 $O(n)$。递归折半查找:深度约 $\log_2 n$,空间 $O(\log n)$。快速排序:栈深平均 $O(\log n)…
- 最好、最坏、平均时间复杂度怎么区分:三者是同一个算法在 同一规模 n 下,面对不同输入时的执行情况:最有利的输入、最不利的输入、各种输入按概率加权。不特别说明时,时间复杂度一般指最坏情况。 例 在长度为 n 的表里顺序查找:最好 1 次,$O(1)$;最坏 n 次,$O(n…
- 常见时间复杂度的大小顺序是什么:$$O(1)\lt O(\log n)\lt O(\sqrt n)\lt O(n)\lt O(n\log n)\lt O(n^2)\lt O(n^3)\lt O(2^n)\lt O(n!)\lt O(n^n)$$ 记法 常、对、幂、指、阶…
408 算法设计题怎么答才不丢分
- 408 算法设计题的答案由哪几部分组成:一般按小问分三部分:① 基本设计思想 ,几句话说清用什么方法、每一步做什么;②算法描述,用 C 或 C++ 写代码,关键语句加注释;③说明时间复杂度和空间复杂度。 步骤 先读清数据的存储形式(顺序表、带不带头结点的单链表、二叉链表、邻接矩…
- 想不出最优算法时该怎么办:先写一个 确定正确 的朴素解法,并如实写出它的复杂度,不要硬凑自己没把握的巧解。 步骤 常用的退路依次是:先排序再处理($O(n\log n)$);开辅助数组计数或标记(多用 $O(n)$ 空间);双重循环暴力比较($O(n^2)$)。 …
- 算法题的设计思想应该写到什么程度:写到 别人不看代码也能照着实现 :用了哪些指针或辅助结构、扫描几趟、每一步做什么、什么时候结束、特殊情况怎么处理。一般三到五句。 例 找单链表倒数第 k 个结点,可以这样写:「设两个指针 p、q,开始都指向第一个结点;p 先向后走 k 步…
- 写算法代码时要先想到哪些边界情况:常见边界有五类: 空表或空树 ;只有一个元素;目标在表头或表尾;参数越界(如 k 不是正数或超过表长);所有元素都相同。 步骤 写完代码用三组小数据手走:空的、只有 1 个元素的、3 到 5 个元素的一般情况。 易错 链表里访问 p->n…
- 算法题的时间和空间复杂度应该怎么表述:先写明 n 代表什么 ,再给出时间、空间复杂度,各用一句话说明理由。 例 「设链表长度为 n。算法只扫描链表一趟,时间复杂度为 $O(n)$;只用了两个指针变量,空间复杂度为 $O(1)$。」 易错 有两个规模时要 分开写 :归并长度为 …
- 从题目条件能看出哪些解题方向:题目里的限定词往往就是提示: 「有序」:折半查找、双指针、归并 「原地」或空间 $O(1)$:下标或指针交换、逆置、覆盖 元素是 范围有限的整数 (如 0 到 n 之间):计数数组,用值当下标 单链表里的位置关系(中点、倒数第 k 个、相…
顺序表与数组类算法题的常用套路
- 怎样原地删除顺序表中所有值为 x 的元素:用下标 k 记录 已保留的元素个数 :从头扫描,不等于 x 的元素搬到 A[k] 并让 k 加 1,扫完把表长改为 k。时间 $O(n)$,空间 $O(1)$。 k=0; for(i=0;i<n;i++) if(A[i]!=x) A[k+…
- 有序顺序表怎样原地去掉重复元素:有序表里相同的元素一定相邻。让 k 指向 已保留部分的最后一个元素 ,i 向后扫描, A[i] 与 A[k] 不同才保留。时间 $O(n)$,空间 $O(1)$。 k=0; for(i=1;i<n;i++) if(A[i]!=A[k]) …
- 怎样把数组循环左移 p 位:做 三次逆置 :先逆置前 p 个元素,再逆置后 n−p 个元素,最后把整个数组逆置。时间 $O(n)$,空间 $O(1)$。 例 数组 1、2、3、4、5、6、7 循环左移 3 位:逆置前 3 个得 3、2、1、4、5、6、7;逆置后 4…
- 有序数组中怎样找出和为 s 的两个数:用 两端夹逼 :i 指向最小元素,j 指向最大元素;两数之和小于 s 就让 i 右移,大于 s 就让 j 左移,等于 s 就找到;i 与 j 相遇还没找到则不存在。时间 $O(n)$,空间 $O(1)$。 例 升序数组 1、3、4、6、9…
- 两个等长升序序列的中位数怎么求:稳妥的做法是 按归并的方式数数 :两个下标同时扫描两个序列,每次取较小的那个并后移,但不真的合并,数到第 n 个就停(两个长为 n 的序列共 2n 个数,这里约定中位数是第 n 小的数)。时间 $O(n)$,空间 $O(1)$。 例 A …
- 怎样找出数组的主元素(出现次数过半):分两趟:第一趟 投票选出候选 ,第二趟数候选出现的次数,超过 n 的一半才是主元素。时间 $O(n)$,空间 $O(1)$。 步骤 候选 c 取第一个元素,计数 cnt 为 1。往后每遇到一个元素:若 cnt 为 0,就把它设为新候选、c…
- 怎样找出数组中未出现的最小正整数:长度为 n 的数组,答案一定在 1 到 n+1 之间 。开一个标记数组 B(下标 1 到 n,初值 0):扫描原数组,值 v 满足 $1\le v\le n$ 就把 B[v] 置 1;再从 1 开始扫 B,第一个为 0 的下标就是答案,全…
- 折半查找的代码最容易错在哪几处:三处:循环条件要写 low<=high (写成小于会漏掉只剩一个元素的情况);缩小区间要写 low=mid+1 和 high=mid-1 (写成等于 mid 可能 死循环 );前提是表有序且顺序存储。 while(low<=high){ …
单链表类算法题的常用套路
- 怎样一趟扫描找到单链表的中间结点:用 快慢指针 :slow 每次走 1 步,fast 每次走 2 步,fast 走到表尾时 slow 正好在中间。时间 $O(n)$,空间 $O(1)$。 slow=fast=head; while(fast!=NULL && fast->…
- 怎样找单链表的倒数第 k 个结点:用 先后指针 :p、q 都从第一个数据结点出发,p 先走 k 步,然后两者同步后移,p 变为空时 q 所指就是倒数第 k 个结点。只扫描一趟,时间 $O(n)$,空间 $O(1)$。 例 链表 1、2、3、4、5,k 为 2:p 先走 2…
- 怎样判断单链表有没有环:用快慢指针:slow 每次 1 步、fast 每次 2 步, 两者相遇就有环 ,fast 走到空则无环。进环后 fast 与 slow 的距离每步缩小 1,所以一定能追上。时间 $O(n)$,空间 $O(1)$。 例 链表 1、2、3、4…
- 怎样找两个单链表的第一个公共结点:两个链表一旦相交,从公共结点起 后面完全重合 ,所以把两表的尾部对齐即可:先求出表长 m 和 n,让长表的指针先走 |m−n| 步,然后两个指针同步后移,第一次指向同一个结点时就是答案。时间 $O(m+n)$,空间 $O(1)$。 例 表…
- 怎样把单链表重排成首尾交替的次序:把 $a_1,a_2,\dots,a_n$ 重排成 $a_1,a_n,a_2,a_{n-1},\dots$,用三个基本操作拼起来:①快慢指针找到中间结点,从它后面断开;②把 后半段原地逆置 (逐个摘下结点,用头插法接到新表的表头);③把后…
- 怎样删除链表中绝对值重复的结点:已知结点数据的绝对值不超过 n 时,用 空间换时间 :开长度 n+1 的标记数组(初值 0),扫描链表,某结点数据的绝对值已被标记就删除该结点,否则把它标记。设表长为 m,时间 $O(m)$,空间 $O(n)$。 例 链表 3、−3、5、…
- 两个升序单链表怎样合并成一个升序表:用 尾插法归并 :尾指针 r 指向结果表的最后一个结点,比较两表当前结点,把较小的接到 r 后面,对应指针后移;一个表取完后,把另一个表剩下的部分整体接上。直接复用原结点,时间 $O(m+n)$,空间 $O(1)$。 例 表 1、4、6 …
- 单链表算法题有哪些通用的易错点:常见的有五个: 改指针前没有 保存后继 ,断链后找不回后面的结点 没判空就访问 p->next 带头结点和不带头结点混用:不带头结点时,对第一个结点的插入、删除要单独处理 删除结点后忘了释放,或者释放之后还在使用它 循环条件写混: p!=…
二叉树类算法题的常用套路
- 写二叉树递归算法前要想清哪三件事:三件事:①函数的含义,返回值代表什么;② 递归出口 ,空树时返回什么;③本层怎样用左右子树的结果得出自己的结果。 例 求度为 2 的结点个数,记作 f(T):空树返回 0;否则返回 f(左子树) 加 f(右子树),如果 T 的左右孩子都不…
- 怎样用递归求二叉树的带权路径长度:带权路径长度(WPL)是所有 叶结点 的权值乘以它到根的路径长度(经过的边数)之和。先序递归时把当前深度作为参数往下传:遇到叶子就累加「权值乘深度」,否则对左右子树递归并把深度加 1。根的深度记为 0。 例 根的左孩子是叶子(权 4),右…
- 怎样求二叉树的宽度:宽度是结点最多的那一层的结点数。做层序遍历, 每次处理一整层 :开始处理某层时,队列里的元素个数就是这一层的结点数,取各层的最大值。 步骤 根入队;队列不空时:记下当前队长 size 并更新最大值,连续出队 size 个结点,把它们的非空…
- 怎样判断一棵二叉树是不是二叉排序树:做中序遍历,检查得到的序列是否 严格递增 :用一个变量 pre 保存中序前驱的值,每访问一个结点就和 pre 比较,不大于 pre 就判定不是。 例 根为 10,左孩子为 5,5 的右孩子为 12:中序序列是 5、12、10,其中 10 …
- 怎样判断一棵二叉树是不是完全二叉树:做层序遍历, 空孩子也入队 ;出队时一旦遇到空指针,就检查队列里剩下的是否全为空:若还有非空结点,就不是完全二叉树。 例 A 的孩子是 B、C,B 只有右孩子 D:出队顺序为 A、B、C、空(B 的左孩子)、D,空指针之后又出现了 D,不…
- 怎样把表达式树输出成带括号的中缀表达式:按中序遍历输出, 给每棵非根的运算符子树加一对括号 :进入一个不是根的非叶结点时先输出左括号,处理完它的右子树后输出右括号;叶结点(操作数)直接输出;根结点不加括号。递归时带一个深度参数来区分根。 例 根是乘号,左子树是加号(左右孩子为 …
- 怎样求二叉树中两个结点的最近公共祖先:用后序递归。设函数 f(T, p, q):T 为空,或 T 就是 p 或 q,返回 T;否则分别在左、右子树里递归得到 L 和 R: L 和 R 都不为空 ,说明 p、q 分在 T 的两侧,T 就是答案;只有一个不为空就返回那个。 例 A…
- 怎样输出二叉树中某个结点的所有祖先:用带返回值的递归查找:函数 f(T, x) 表示「以 T 为根的子树里有没有 x」。T 为空返回假;T 就是 x 返回真;否则在左、右子树里查找, 只要有一边返回真 ,T 就是 x 的祖先,输出 T 并返回真。 例 A 的孩子是 B、C,…
图、排序与查找思想在算法题里的用法
- 怎样用广度优先搜索求无权图的单源最短路径:从源点做广度优先搜索,某顶点 第一次被访问时 的层数就是它到源点的最短路径长度,因为广度优先是按距离由近到远扩展的。邻接表存储时时间 $O(n+e)$。 步骤 数组 dist 全部置为 −1(兼作访问标记),源点的 dist 置 0 并入…
- 怎样判断有向图中有没有环:借用拓扑排序:反复删去入度为 0 的顶点和它发出的边, 输出的顶点数小于 n 就有环 。邻接表存储时时间 $O(n+e)$。 步骤 求出各顶点入度;入度为 0 的顶点入栈;每出栈一个顶点,计数加 1,并把它指向的各顶点入度减 1,减到 0…
- 怎样判断连通无向图能不能一笔画:看度为奇数的顶点有几个:连通无向图存在「每条边恰好经过一次」的路径,当且仅当 奇度顶点的个数是 0 或 2 。个数为 0 时可以回到起点;个数为 2 时这两个顶点分别是起点和终点。 步骤 用邻接矩阵存储时,统计每一行非零元素的个数得到各顶…
- 怎样用快速排序的划分找第 k 小的元素:做一趟划分,枢轴最终落在下标 p(从 0 起)就说明它是第 p+1 小的元素:p+1 等于 k 就找到了;k 较小就 只在左半部分 继续划分,k 较大就只在右半部分继续。不必把整个数组排好,平均时间 $O(n)$,最坏 $O(n^2)$。…
- 怎样从 n 个数里选出最小的 k 个:维护一个容量为 k 的 大根堆 :先用前 k 个数建堆;之后每来一个数就和堆顶比较,比堆顶小就替换堆顶并向下调整,否则丢弃。扫描结束时堆里就是最小的 k 个数。时间 $O(n\log k)$,空间 $O(k)$。 例 在 8、3、10、1…
- 什么时候能用计数数组把算法降到线性时间:当元素是 取值范围已知且不大 的整数时(如 0 到 n−1、绝对值不超过 n、26 个小写字母),可以把元素值当下标,开数组做计数或标记,一趟扫描完成统计、去重、找缺失。设取值范围大小为 m,时间 $O(n+m)$,空间 $O(m)$。 …
- 怎样判断一个无向图是不是一棵树:无向图是一棵树,当且仅当它 连通且恰有 n−1 条边 (n 为顶点数)。做法:从任一顶点做一次深度优先搜索,统计访问到的顶点数;再统计图的边数(邻接表中边结点总数的一半)。访问到的顶点数等于 n 且边数等于 n−1,就是树。时间 $O(n…
本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。