考研 408 数据结构 选择题易错点速记

这张图讲什么

「考研 408 数据结构 选择题易错点速记」是 SeekFlaw 编辑团队整理的思维导图,分 6 个一级分支:栈、队列、数组和串的选择题易错点;树和二叉树的结论别记反;图的概念、存储与算法条件的易错点;查找:比较次数和 ASL 怎么数;排序:稳定性、趟数与一趟结果判断;线性表易错点,共 70 个节点、69 张记忆卡,含 6 张配图。

这张图把 408 数据结构选择题常见的易错点做成速记卡,共六块:栈、队列、数组与串,树和二叉树,图,查找,排序,线性表。每张卡只讲一个错因:先给结论,再给一个自编的小算例或反例,最后写易错。建议先看各分支首段,再把每个算例自己重算一遍。

5 个要点

  • 栈、队列、数组和串的选择题易错点:这一枝的选择题几乎都能用一个小算例判断:出栈序列用「后面比它小的要递减」,下标换算先写清是第几行第几列、从 0 还是从 1 起…
  • 树和二叉树的结论别记反:这一枝的选择题是「结论 + 一个小算例」:结点数、叶子数、高度范围,遍历序列还原,二叉排序树查找路径,哈夫曼 WPL,AVL 插入。
  • 图的概念、存储与算法条件的易错点:图的选择题主要考「边数的极值」「存储结构的度和空间」和「算法的适用条件」。
  • 查找:比较次数和 ASL 怎么数——查找题先分清是成功还是失败、顺序还是折半,再数比较次数。
  • 排序:稳定性、趟数与一趟结果判断——排序的选择题分三类:稳定性(找反例)、复杂度(与初始序列有关还是无关)、一趟之后的结果(看特征)。

适用:考研备考。用法:点开任一节点先自己答,再翻面核对。

配图:入栈 1 到 5 得到出栈序列 3,5,4,2,1 的逐步操作表;6 阶三对角矩阵每个非零位置对应的一维数组下标;权 2、3、5、7、11 的哈夫曼树和带权路径长度;含负权边的三顶点有向图,Dijkstra 得到错误的最短路;表长 7 的线性探测散列表,插入 8、15、22、5 后的结果;同一初始序列经冒泡、选择、插入、快速排序一趟后的结果对照。

发布于

一句话:这张图把「考研 408 数据结构 选择题易错点速记」整理成 70 个节点、69 张记忆卡;点开节点翻面就能看答案。

按栈队列、树、图、查找、排序、线性表六块,把数据结构选择题里最容易错的结论配小算例和反例整理成速记卡,适合考前过一遍。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。

SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。

70 个节点 · 69 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-20。

先看这 3 条

  1. 怎样判断一个出栈序列是否合法:入栈次序固定为 1、2、…、n 时,出栈序列合法的条件是:对其中任一元素,排在它 后面且比它小 的元素,必须按 递减 次序出现。
  2. n 个顶点的无向图至少几条边一定连通:边数大于 $C_{n-1}^{2}$ 时一定连通,即至少 $C_{n-1}^{2}+1$ 条。
  3. 哪种链表结构表头和表尾的插入删除都是 O(1):双向循环链表(只要有头指针或头结点,其前驱就是尾结点)能让表头、表尾的插入删除都是 O(1);带头、尾两个指针的双向链表也可以。

栈、队列、数组和串的选择题易错点

  • 怎样判断一个出栈序列是否合法:入栈次序固定为 1、2、…、n 时,出栈序列合法的条件是:对其中任一元素,排在它 后面且比它小 的元素,必须按 递减 次序出现。 例 入栈 1~5:序列 3,5,4,2,1 合法(1、2、3 入栈后 3 出,4、5 入栈后 5、4 出,再…
  • 第一个出栈的是 k 时,出栈序列受什么限制:第一个出栈的是 k,说明 1~k−1 此时都在栈里(自底向上为 1 到 k−1),它们之后只能按 k−1、…、1 的 相对次序 出栈;k+1 到 n 可以穿插进来。 例 入栈 1~4,第一个出栈是 3:合法序列只有 3,2,1,4;3,2…
  • 共享栈怎样判空和判满:两个栈共用数组 data[0..M-1] ,栈 1 从下标 0 端向右增长,栈 2 从下标 M−1 端向左增长。栈 1 的 top1 初值 −1,栈 2 的 top2 初值 M。判满条件是 top1 + 1 = top2 ;栈 1 空是 …
  • 循环队列判空判满的三种方案有什么不同:设数组容量为 M,front 指向队头,rear 指向下一个入队位置。①牺牲一个单元:空 front = rear,满 (rear+1) mod M = front,最多存 M−1 个;②设元素个数 size:空 size = 0,满 s…
  • 中缀表达式转后缀时,运算符栈最深有多深:栈深要看扫描全过程的最大值:每遇运算符先弹出栈内优先级 不低于 它的运算符再压入,左括号直接压入,右括号弹到左括号为止。 例 a+b*(c-d)/e:扫描到 + 入栈 [+];* 优先级高,入栈 [+,*];( 入栈 [+,*,(];- …
  • 二维数组按行优先存放时元素地址怎么算:行优先时,下标从 0 起的 $A[i][j]$ 的地址为首地址加 $(i\times n+j)\times L$,n 是 列数 ,L 是每个元素的字节数;列优先时用 $(j\times m+i)\times L$,m 是行数。 例 数组 …
  • 对称矩阵压缩存储时元素下标怎么算:n 阶对称矩阵只存下三角(含对角线),共 $n(n+1)/2$ 个元素,按行优先放进一维数组。矩阵下标从 1 起,数组下标从 0 起时,$i\ge j$ 的元素 $a_{i,j}$ 的数组下标为 $i(i-1)/2+j-1$。 例 5 阶…
  • 三对角矩阵怎样压缩存储,下标怎么算:n 阶三对角矩阵只有 $|i-j|\le 1$ 的位置非零,共 $3n-2$ 个元素,按行优先存一维数组。矩阵下标从 1 起、数组下标从 0 起时,$a_{i,j}$ 的数组下标是 $2i+j-3$。 例 6 阶矩阵,$a_{4,5}$ …
  • 稀疏矩阵用三元组存储什么时候才省空间:三元组表对每个非零元存(行号、列号、值)三项,所以 t 个非零元占约 ${3t}$ 个单元,比整个矩阵 $m\times n$ 省的条件是 $3t\lt mn$,即非零元少于总数的 三分之一 。 例 100×100 的矩阵有 1000 个…
  • KMP 的 next 和 nextval 怎么求:采用下标从 1 起的常用约定:next[1]=0;next[j] 等于模式前 j−1 个字符的最长相等前后缀长度加 1。nextval 在 next 基础上,若 $p_j=p_{next[j]}$,就取 nextval[next[j]],…

树和二叉树的结论别记反

  • 树的结点数和各结点度数之和有什么关系:树中 结点数 = 度数之和 + 1 ,因为除根以外每个结点恰好是一个结点的孩子。 例 一棵树中度为 4、3、2、1 的结点分别有 2、1、3、4 个,叶子数为 $n_0$。度数之和 $2\times4+1\times3+3\times2+…
  • 完全二叉树的叶子数怎么算:完全二叉树至多有一个度为 1 的结点。结点数 n 为偶数时 $n_1=1$,叶子数 $n_0=n/2$;n 为奇数时 $n_1=0$,$n_0=(n+1)/2$。 例 $n=700$:$n_1=1$,$n_0+n_2=699$,$n_0=…
  • 二叉树高度和结点数的范围怎么记:高度为 h 的二叉树,结点数最少 h 个(单支树),最多 $2^h-1$ 个(满二叉树)。反过来,n 个结点的二叉树,最小高度是 $\lceil\log_2(n+1)\rceil$,最大高度是 n。 例 100 个结点:$2^6=64\l…
  • n 个结点的 m 叉树最小高度怎么求:结点数一定时,高度最小的 m 叉树是完全 m 叉树。高度为 h 的满 m 叉树有 $\frac{m^h-1}{m-1}$ 个结点,所以最小高度是满足 $\frac{m^h-1}{m-1}\ge n$ 的最小 h,即 $\lceil\log…
  • 二叉链表有多少个空指针:n 个结点的二叉链表共有 ${2n}$ 个指针域,其中 $n-1$ 个指向孩子(每个非根结点被指向一次),所以空指针有 $2n-(n-1)=n+1$ 个, 与树形无关 。 例 100 个结点的二叉树,二叉链表的空指针有 101 个;中序线…
  • 前序和后序遍历序列能唯一确定二叉树吗:一般 不能 。前序序列 AB、后序序列 BA 对应的二叉树有两棵:B 是 A 的左孩子,或 B 是 A 的右孩子。 区分 前序加中序、后序加中序、层序加中序都能唯一确定;若树中 没有度为 1 的结点 ,前序加后序也能唯一确定。 易错 唯一…
  • 例:由前序和中序序列还原二叉树:前序 ABDECF、中序 DBEAFC:前序第一个是根 A;A 在中序里把序列分成左 DBE、右 FC。左部前序 BDE,根 B,中序 D|B|E,得 D 为 B 的左孩子、E 为右孩子;右部前序 CF,根 C,中序 F|C,F 是 C …
  • 怎样判断一个序列是不是二叉排序树的查找路径:沿路径每走一步,关键字的取值范围就收缩一次:比当前结点小就走左,范围的上界变成该结点;比当前结点大就走右,下界变成该结点。路径上后面的每个结点都必须落在当前范围内。 例 查找 45:序列 20,60,35,50,40,45 合法(范围依次…
  • 例:哈夫曼树的结点数和带权路径长度:n 个叶子的哈夫曼树没有度为 1 的结点,总结点数 $2n-1$。权值 2、3、5、7、11:每次合并最小的两个,依次得 5、10、17、28,WPL 等于所有非叶结点的权之和 $5+10+17+28=\mathbf{60}$。 步骤 验…
  • 森林转成二叉树后,遍历和结点怎么对应:森林的先序遍历对应二叉树的 先序 遍历,森林的中序遍历(即依次对各树做后根遍历)对应二叉树的 中序 遍历。森林中叶子的个数,等于二叉树中 没有左孩子 的结点个数;森林中树的个数,等于二叉树根沿右指针链的结点个数。 例 森林由两棵树组成:A…
  • 20 个结点的 AVL 树最大高度是几:设高度为 h 的 AVL 树最少有 $N_h$ 个结点,则 $N_h=N_{h-1}+N_{h-2}+1$,$N_1=1$,$N_2=2$。依次得 $N_3=4$,$N_4=7$,$N_5=12$,$N_6=20$。结点数为 20 时, …
  • AVL 树插入和删除后各最多调整几次:插入一个结点后,只需对 最小失衡子树 做一次调整(单旋转或双旋转),整棵树就恢复平衡;删除结点后可能要从下往上多次调整。 例 依次插入 1、2、3:插入 3 后结点 1 失衡(右右型),一次左单旋转得到以 2 为根的树。 易错 插入后的调…

图的概念、存储与算法条件的易错点

  • n 个顶点的无向图至少几条边一定连通:边数大于 $C_{n-1}^{2}$ 时一定连通,即至少 $C_{n-1}^{2}+1$ 条。不连通时最多有 $C_{n-1}^{2}$ 条边(一个孤立点加其余 n−1 个顶点的完全图)。 例 $n=7$:$C_6^2=15$,所以 15…
  • 有向图强连通最少和最多几条边:n 个顶点的强连通有向图至少 n 条 边(一个有向环)。不强连通时最多有 $(n-1)^2$ 条边:把顶点分成两部分,其中一个方向不连边,边数为 $n(n-1)-|A||B|$,$|A||B|$ 最小取 $n-1$。 例 $n=5$:强连…
  • 邻接矩阵和邻接表各怎样表示度和边:无向图的邻接矩阵对称,第 i 行的非零元素个数就是顶点 i 的度;有向图第 i 行之和是出度,第 j 列之和是入度。邻接表中,无向图每条边出现 两次 ,边结点共 ${2e}$ 个,有向图为 e 个。 区分 有向图的邻接表求出度容易、求入度…
  • 邻接矩阵的 k 次幂的元素表示什么:邻接矩阵 A(0/1)的 k 次幂 $A^k$ 中,第 i 行第 j 列的元素等于从顶点 i 到顶点 j 长度为 k 的路径条数 (长度指边数)。 例 有向图边为 1→2、2→3、1→3:$A^2$ 的 (1,3) 位置等于 1,对应路径…
  • Dijkstra 遇到负权边为什么会出错:Dijkstra 每次把当前最短的顶点确定下来,之后不再更新,这个做法要求 边权非负 。有负权边时,已确定的顶点可能还有更短的路径。 例 边 A→B 权 2,A→C 权 5,C→B 权 −4。从 A 出发,Dijkstra 先确定 B=2…
  • 最小生成树是唯一的吗:最小生成树的 权值之和唯一 ,但树不一定唯一。若图中所有边权互不相同,则最小生成树唯一。 例 三角形三条边权都是 1:任取两条边都是最小生成树,共 3 种,权值和都是 2。 易错 Prim 与 Kruskal 得到的权值和相同,但选出的边…
  • 最小生成树能当作最短路径树吗:不能。最小生成树只能让整棵树的权值之和最小,并不能使树上两点之间的路径最短。 例 三个顶点 A、B、C,边 AB=3、BC=3、AC=5:最小生成树是 AB 和 BC,权值和 6;但 A 到 C 在树上要走 6,而直接走边 AC 只要 5…
  • DFS 和 BFS 的复杂度和遍历序列唯一性:用邻接矩阵存储时,遍历的时间复杂度是 $O(n^2)$,用邻接表是 $O(n+e)$。邻接矩阵下,从同一个顶点出发的遍历序列是 唯一 的(按列号从小到大找邻接点);邻接表下,序列依赖链表中邻接点的顺序, 不唯一 。 易错 遍历序列是否唯一…
  • 邻接矩阵是三角矩阵与拓扑排序有什么关系:若有向图的邻接矩阵是(对角线为 0 的)三角矩阵,则图中无环,一定存在拓扑序列; 反过来不一定 ,没有环的图,顶点编号不合适时邻接矩阵也不是三角的。 例 顶点 1、2、3,边 3→1、1→2:没有环,拓扑序列 3,1,2;但边 3→1 在…

查找:比较次数和 ASL 怎么数

  • 折半查找成功时最多比较几次:n 个元素的有序顺序表,折半查找成功时最多比较 $\lfloor\log_2 n\rfloor+1$ 次,等于判定树的高度 $\lceil\log_2(n+1)\rceil$。 例 $n=12$:$\lfloor\log_2 12\rfl…
  • 折半查找判定树怎样求平均查找长度:判定树第 k 层有 $2^{k-1}$ 个结点(满时),查找该层结点要比较 k 次,成功的 ASL 等于各层「结点数 × 层数」之和除以 n。 例 $n=7$:三层结点数 1、2、4,$ASL=\frac{1\times1+2\times…
  • 折半查找中间位置向下取整和向上取整有什么不同:设 low 和 high 为当前区间两端。向下取整时 $mid=\lfloor(low+high)/2\rfloor$,每个结点的 右子树结点数不少于左子树 ;向上取整时相反,左子树不少于右子树。 例 4 个元素 1~4:向下取整 mid…
  • 顺序查找中查找概率不等时 ASL 怎么变:顺序查找的 ASL 等于各元素「查找概率 × 比较次数」之和; 概率大的元素放前面 ,ASL 最小。 例 4 个元素的查找概率 0.4、0.3、0.2、0.1:按这个次序排,$ASL=0.4+0.6+0.6+0.4=2.0$;按相反次序排…
  • B 树和 B+ 树在结构和查找上有哪些区别:B 树每个结点有 k 个关键字时有 k+1 棵子树,查找可以在内部结点 命中就结束 ;B+ 树每个结点的 k 个关键字对应 k 棵子树,所有关键字都在叶子结点中出现,叶子之间有链指针,非叶结点只作索引,查找必须 走到叶子 。 区分 B+ …
  • 同样的关键字,插入次序不同二叉排序树的 ASL 一样吗:不一样。同一组关键字按不同次序插入,得到的二叉排序树形状不同,查找效率也不同。 例 关键字 1、2、3:按 1,2,3 的次序插入成单支树,$ASL=(1+2+3)/3=2$;按 2,1,3 的次序插入成平衡的三结点树,$ASL=(1+2…
  • 例:线性探测法建散列表并求成功查找的 ASL:表长 7,散列函数 $H(k)=k\bmod 7$,依次插入 8、15、22、5。8 放在地址 1;15 的地址 1 冲突,放地址 2;22 的地址 1、2 冲突,放地址 3;5 放地址 5。成功查找各需 1、2、3、1 次,$ASL=\…
  • 平方探测法对表长有什么要求:平方探测的探测序列是 $H(k)\pm1^2,\pm2^2,\dots$(模表长)。当表长 m 是形如 $4k+3$ 的 素数 时,这个序列能探测到整个散列表。 例 $m=7=4\times1+3$,$H(k)=1$:依次探测地址 1、2…
  • 二叉排序树的中序遍历有什么性质:二叉排序树的 中序遍历序列是递增有序 的;反过来,一棵二叉树的中序序列递增,它就是二叉排序树(任意两个关键字不相等时)。 例 一棵树的前序序列为 5、3、2、4、8,中序序列为 2、3、4、5、8,中序递增,可以确认它是二叉排序树。 易错…

排序:稳定性、趟数与一趟结果判断

  • 简单选择和快速排序为什么不稳定:两者都不稳定,各有一个反例。 例 简单选择排序:序列(2a, 2b, 1)升序,第一趟选最小的 1,与第一个元素 2a 交换,得 (1, 2b, 2a),两个 2 的相对次序变了。快速排序:(3a, 3b, 1),以 3a 为枢轴,一趟后…
  • 哪些排序的比较次数或时间与初始序列无关:简单选择排序的比较次数固定为 $n(n-1)/2$,与初始序列无关;堆排序和二路归并排序的时间复杂度始终是 $O(n\log n)$。直接插入、冒泡(带交换标志)和快速排序的时间与初始序列 有关 。 例 $n=10$ 的简单选择排序,无论…
  • 快速排序什么时候最慢,空间复杂度是多少:每次划分极不均衡时最慢:取第一个元素为枢轴时,初始序列 已经有序或逆序 ,每次只划出一个元素,时间 $O(n^2)$,递归栈深度达 $O(n)$。平均时间 $O(n\log n)$,递归栈平均深度 $O(\log n)$。 易错 快速排序…
  • 建堆的时间和二路归并的趟数怎么算:自底向上建初始堆的时间是 $O(n)$,不是 $O(n\log n)$;堆排序的总时间是 $O(n\log n)$。二路归并排序把 n 个元素逐趟两两合并,趟数是 $\lceil\log_2 n\rceil$,每趟 $O(n)$。 例 $…
  • 基数排序的趟数由什么决定:基数排序按关键字的每一位分配、收集一次,趟数等于关键字的 位数 d,与元素个数 n 无关;每趟时间 $O(n+r)$(r 为基数),总时间 $O(d(n+r))$,稳定,空间 $O(r)$。 例 关键字是 3 位十进制数,基数 $r=10…
  • 怎样从一趟结果判断是哪种排序:看一趟后的 特征 (按教材默认写法):末尾归位最大值是冒泡;开头归位最小值是简单选择;前几个有序、其余未动是直接插入;有一个元素左小右大地归位是快速排序。 例 初始序列 5、3、8、1、9、2,升序。冒泡一趟:3,5,1,8,2,9;简单…
  • 怎样判断某个元素可能是一趟快速排序的枢轴:一趟快速排序后,枢轴已在最终位置,所以枢轴左边的元素 都比它小 、右边的元素 都比它大 。满足这一点的元素才可能是枢轴。 例 序列 2,1,3,7,5,8:3 左边 2、1 都比它小、右边 7、5、8 都比它大,可能是枢轴;8 左边都小、…
  • 例:希尔排序一趟(增量 4)后的结果怎么看:希尔排序按增量 d 把序列分成 d 个子序列,每个子序列分别做直接插入排序。 例 序列 5,3,8,1,9,2,7,4,增量 4:子序列为 (5,9)、(3,2)、(8,7)、(1,4),分别排序后得 5,2,7,1,9,3,8,4 。 …
  • 怎样判断一个序列是不是小根堆:把序列按层序放进完全二叉树,若每个结点的值都 不大于 它的左右孩子,就是小根堆;数组下标从 1 起时,要求 $a_i\le a_{2i}$ 且 $a_i\le a_{2i+1}$。 例 序列 1,3,2,6,4,5:1≤3、2;3≤6、4…

线性表易错点

  • 哪种链表结构表头和表尾的插入删除都是 O(1):双向循环链表(只要有头指针或头结点,其前驱就是尾结点)能让表头、表尾的插入删除都是 O(1);带头、尾两个指针的双向链表也可以。 只有头指针的单链表:表头插入、删除 O(1);表尾插入、删除要先找尾,O(n) 只有尾指针的单循环链表:表头…
  • 静态链表和顺序表、动态链表有什么不同:静态链表用数组存放结点,每个结点带一个游标(下一个结点的下标)。插入和删除只改游标, 不需移动元素 ;但容量固定,也不能随机存取,查找第 i 个元素仍要沿游标一个个找。 易错 静态链表的存储用数组,但存取方式仍是顺序存取,不要因为用了数组…
  • 顺序存储就是随机存取吗:不是一回事。 顺序存储 说的是结点在内存中地址连续, 随机存取 说的是访问任意第 i 个元素的时间都是 O(1)。顺序表两者兼有;链表的结点地址可以不连续,只能 顺序存取 。 区分 存储结构(顺序、链式、索引、散列)与存取方式(顺序存取、…
  • 折半查找能降低有序顺序表插入的总时间复杂度吗:不能。在有序顺序表中插入,折半查找把查位置的比较降到 $O(\log n)$,但插入时要后移元素,平均移动约 $n/2$ 个,总时间仍是 $O(n)$。 区分 有序链表插入:查位置要从头比较,$O(n)$ 次比较,但插入本身不用移动元素。…

本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。

打开这张导图:点节点翻面看答案 →