1. 先说点实在的第一章绪论的题为什么反而是挂科重灾区很多同学学《数据结构》翻开书看到第一章绪论觉得全是概念背一背就能过。结果一做题选择题靠蒙判断题凭感觉时间复杂度分析更是直接放弃。等到期中期末或者考研复习的时候才反应过来——第一章的习题根本不是背诵题它考的是你有没有真的理解数据结构这门课在干什么。我自己当年也是这么过来的。第一次做绪论习题觉得逻辑结构和存储结构不就是一回事吗抽象数据类型又是什么拗口的词最后算法的时间复杂度分析直接跳过。后来带过几次课程设计和笔试面试辅导又帮一些考研的同学梳理过真题才慢慢把第一章的知识点从背概念变成了看本质。这篇文章就把我在反复做题、讲题过程中积累下来的东西写出来包括核心考点的拆解、典型习题的解题思路、还有那些课本上不会明说但考题总在挖坑的细节。这篇文章适合谁看适合正在学数据结构的大学生、准备考研计算机专业课的同学也适合那些想快速复盘第一章重点的自学者。不讲虚的直接落到题上落到怎么拿分上。2. 绪论习题到底在考什么先给整章做一个考点地图2.1 数据结构三要素数据的逻辑结构、存储结构、运算绪论整章的逻辑主线其实就是围绕一句话展开的数据结构 逻辑结构 存储结构 运算。习题里的绝大多数概念题、判断题、填空题翻来覆去都是在考这个三要素。什么是逻辑结构说人话就是数据元素之间是什么关系。最常见的四种逻辑结构集合结构元素之间除了属于同一个集合之外没有任何其他关系。就像一堆散落的乒乓球它们只是碰巧在同一个袋子里。线性结构元素之间是一对一的线性关系。就像排队买奶茶你只直接联系你前面的人和后面的人。树形结构元素之间是一对多的层次关系。就像公司的组织架构一个老总管好几个总监每个总监又管好几个员工。图形结构网状结构元素之间是多对多的关系。就像社交网络你认识很多人很多人也认识你没有严格的层级。到这里还比较轻松。真正的坑在于逻辑结构与存储结构的关系这道经典辨析题。我从小到大见过至少五种变体但核心都是一个意思逻辑结构是用户看到的样子、是抽象层面的存储结构是计算机内存里实际存放的样子、是物理层面的。举个例子。同样是线性结构在内存里你可以用连续的一块空间来放这叫顺序存储典型代表是数组也可以用一串不连续的节点通过指针串起来这叫链式存储典型代表是链表。逻辑结构没有变都是一对一的线性关系但物理层面的存储方式完全不同。所以做题的时候遇到逻辑结构是数据的逻辑关系与存储结构无关这种判断题你就要立刻反应过来逻辑结构确实独立于存储结构而存在但每种逻辑结构都必须通过某种存储结构来实现。这两句话不矛盾前者说的是概念上可以分开研究后者说的是实现上必须落地。考试最爱在这里玩文字游戏。2.2 抽象数据类型ADT这个概念做题时到底怎么用抽象数据类型Abstract Data TypeADT是第一章概念题的另一大源。很多同学觉得这个词玄乎其实理解起来特别简单**ADT 就是一个数据集合 在这个集合上能进行的操作。你不需要关心内部是怎么存储的你只需要关心能做什么。这就像你开一台洗衣机你关心的操作是洗衣服甩干你不需要关心里面电机怎么转、齿轮怎么咬合。洗衣机对你来说就是一个抽象数据类型。课本上通常会把 ADT 描述成三元组ADT (D, S, P)其中 D 是数据对象DataS 是数据关系StructureP 是基本操作Operation。习题里如果让你定义一个复数的抽象数据类型你需要做的就是三件事说清楚数据对象是什么比如复数由实部和虚部两个实数构成。说清楚数据关系是什么复数的实部和虚部是有序的二元组关系。说清楚基本操作有哪些比如构造复数、取实部、取虚部、两个复数相加、两个复数相乘。我在批改作业的时候发现大部分同学写定义 ADT只写了操作列表前面两步经常漏。记住完整的三元组缺一个都不算全。有些严一点的学校期末考填空就专门挖 D、S、P 这三个字母让你填。2.3 考频最高的概念辨析题我按踩坑概率给它们排了个名第一章习题里有一批看起来每个字都认识放进题目里就不认识了的句子我把它们在历年各种习题集、考试卷里出现的频率和踩坑概率按从高到低排了一下第一位数据项和数据元素的区别。数据元素是数据的基本单位比如一个学生记录学号、姓名、成绩就是一个数据元素数据项是组成数据元素的最小单位学号是一个数据项姓名是一个数据项。做题的时候题目说一个结点就是一个数据元素对一个数据元素就是一条记录在大多数讨论单个记录的场景下对但严格说记录是数据元素的同义词能互换。真正爱挖坑的是数据元素可以由若干个数据项组成数据项是数据的不可分割的最小单位——这里不可分割四个字很多人不注意选择题就专门在这里设干扰项。第二位算法五个特性有穷性、确定性、可行性、输入、输出。经典的判断题是算法必须有输入否则无法执行——这是错的算法可以没有输入但必须有输出。比如一个算法功能是生成前100个质数它就不需要任何输入但必须有输出。另一个经典判断题是算法必须有穷程序也必须要有穷——这也是错的程序可以无限循环跑下去不退出不能算有穷但算法定义里明确要求必须在执行有限步之后结束这是算法和程序的一个关键区别。第三位好的算法的评价标准。正确性、可读性、健壮性、高效性时间效率高、存储量低。习题里经常出现算法的时间复杂度越低空间复杂度越低算法就一定越好这种极端表述显然不对。因为有时你牺牲一点时间换空间比如压缩存储有时牺牲空间换时间比如哈希表这是工程中的正常取舍。判断题里一出现越……越……就越好这种绝对化表述十有八九是错的。3. 时间复杂度的题怎么解从一道题都不会到拿到分3.1 别再背 O(1)、O(n)、O(n²) 了先理解数量级是什么意思绪论习题里最值钱的分值就是时间复杂度分析。很多同学直接跳过这一部分觉得又是数学又是逻辑太难。但实际只要你掌握了套路这部分是最好拿分的而且后面学线性表、树、图、排序算法都要回来用这一章的知识。先理解什么叫时间复杂度。简单说就是算法执行时间随问题规模 n 增长的变化趋势。我们不关心具体的执行时间是多少毫秒我们只关心当 n 变大的时候执行时间大约变成原来的几倍。比如说一个算法执行次数总是 3n² 2n 1 次当 n 翻倍的时候3n² 变成 12n²翻了4倍2n 变成 4n翻了2倍常数项不变。最终主导增长率的是 n² 这一项。所以我们说这个算法的时间复杂度是O(n²)读作大O n平方。大O记号的含义是渐进上界也就是它表示一个算法运行时间最多不超过某个数量级。刚才那个式子我们说它是 O(n²)因为当 n 足够大的时候3n² 2n 1 的增长速度最多跟 n² 同一个级别。这就是数量级的含义。做题的时候只需要记住一个最核心的操作我称之为找主体循环数执行次数留最高阶去常数系数。3.2 单层循环套路数一数循环体到底执行了几次最简单的题型是单层循环。比如for (i 1; i n; i) { x x 1; }循环体执行 n 次时间复杂度 O(n)。没难度跳过。有难度的单层循环是这个样子for (i 1; i n; i i * 2) { x x 1; }循环变量 i 不是每次加 1而是每次乘 2。那么 i 的取值序列是 1, 2, 4, 8, 16, ...。你要问的问题是i 大概执行多少次会超过 n假设执行了 k 次那么第 k 次的时候 i 2^(k-1)跳出条件就是 2^(k-1) n解出来 k ≈ log₂n 1。所以循环体执行次数是O(log n)级别。注意这里的底数 2 无所谓因为 log₂n 和 log₃n 只差一个常数系数而大O记号会去掉常数系数。所以考试时你写 O(log n) 就行不用纠结底数。我见过最坑的单层循环题是这样的for (i 0; i * i n; i) { x; }这题很多人看到 i * i 就懵了。其实判断条件等价于 i √n所以循环执行次数是O(√n)。你只要把判断条件里的表达式整理成关于 i 的关系式然后求 i 的最大值就行了。3.3 双重循环计数思路决定成败双重循环是时间复杂度题目的大宗也是区分会做和假装会做的分水岭。我见过很多同学一看到嵌套循环就直接写 O(n²)结果错得离谱。先来一个最简单的双层循环for (i 1; i n; i) { for (j 1; j n; j) { x; } }外层执行 n 次内层每次都执行 n 次所以总执行次数 n × n n²时间复杂度 O(n²)。这个没问题。但下面这个就完全不同for (i 1; i n; i) { for (j i; j n; j) { x; } }内层循环次数不是固定的 n而是从 i 跑到 n也就是 n - i 1 次。所以总执行次数是∑(i1 到 n) (n - i 1) n (n-1) (n-2) ... 1 n(n1)/2去掉低阶项和常数系数时间复杂度还是O(n²)。虽然还是 n² 级别但如果你心里没这个计算过程后面遇到更复杂的你肯定撑不住。再来看一个经典的变种for (i 1; i n; i) { for (j 1; j i; j) { x; } }这个和上一个本质上一样总次数也是 1 2 3 ... n n(n1)/2O(n²)。现在来一道全网学生错得最多的类型for (i 1; i n; i) { for (j 1; j i; j j * 2) { x; } }内层循环不是 j而是 j j * 2。所以对于固定的外层 i内层循环执行的次数是 log₂i 级别因为 j 从 1 翻倍增长到超过 i 为止。总执行次数就是∑(i1 到 n) log₂i log₂1 log₂2 ... log₂n log₂(n!)根据斯特林近似log₂(n!) 约等于 n log₂n。所以时间复杂度是O(n log n)。大部分教材都把这一题列为中等难度如果你能在没看答案的情况下推到这里说明你已经真正理解了时间复杂度的计数逻辑。3.4 复杂一点的循环条件别急着写答案先把执行次数表达式写出来有些题目喜欢在循环条件里做文章。比如for (i 1, s 0; s n; i) { s s i; }这题看着是单层循环但是循环条件用的是变量 s而 s 每次增加 i。你要求的是s 从 0 开始第一次加 1、第二次加 2、第三次加 3……一直加到什么时候 s 超过 n。也就是求最小的 k使得 1 2 3 ... k n。左边是 k(k1)/2解 k(k1)/2 ≈ n得到 k ≈ √(2n)。时间复杂度是O(√n)。这类题的精髓就是先把循环体执行了多少次等价成一个数学问题把数学式子列出来再求次数表达式最后转成大O记号。我建议所有初学者都养成写求和式的习惯不要脑子里算一下就写答案。做题时纸笔演算的过程本身就是建立思路的过程。3.5 递归算法的时间复杂度绪论考得不深但要会递推第一章的递归算法时间复杂度题一般不会太难常见的套路是给出一个递归关系式让你求复杂度。比如T(n) 2T(n/2) nT(1) O(1)这种式子可以用主定理直接求解也可以用画递归树的方法。画递归树是这样的每一层的总代价是 n因为下一层两个子问题每个规模 n/2代价加一起是 n下一层四个子问题每个规模 n/4代价加一起还是 n。一共有 log₂n 层因为每次除以 2所以总复杂度是O(n log n)。绪论阶段大家只要掌握两类递推就够用了T(n) T(n-1) O(1)每次只减少 1一共要递归 n 层总复杂度O(n)。T(n) 2T(n/2) O(n)归并排序式的递归总复杂度O(n log n)。见到这种递推式不要慌画递归树或者一层一层展开都能得到答案。3.6 最坏时间复杂度和平均时间复杂度什么时候用哪个做题的时候你会发现有些题目问该算法的最坏时间复杂度有些问平均时间复杂度。这个区分特别重要。最坏时间复杂度在最坏情况下算法执行基本操作的次数。比如快速排序最坏情况下数据已经有序时间复杂度会退化到 O(n²)。平均时间复杂度所有可能输入等概率出现时算法执行次数的加权平均值。快速排序的平均时间复杂度是 O(n log n)。最好时间复杂度最理想情况下的执行次数比如快速排序最好也是 O(n log n)。判断题里经常出现的一句话是对于一个算法其平均时间复杂度总是等于最坏时间复杂度。这显然是错的。另一个常见的说法是算法的性能分析只考虑最坏情况即可不用管平均情况这也是错的。比如在哈希表查找中平均时间复杂度是 O(1)但如果哈希函数写得不好最坏会退化成 O(n)。你要设计一个在多数场景下表现稳定的系统平均复杂度必须看要评估一个系统的底线性能比如地铁闸机在最繁忙时段不能崩溃最坏复杂度必须看。4. 空间复杂度的题另一个容易拿分但总被忽视的考点4.1 空间复杂度算的是额外的辅助空间不是数据本身占的空间很多人对空间复杂度的理解是这个算法占了多少内存这种理解不够准确。做题时我们要算的是算法执行过程中额外需要的存储空间不包括输入数据本身所占用的空间。这个额外课本里叫辅助空间。举个最经典的例子。将一个数组逆序输出有两种写法写法一新建一个同样大小的数组 b把 a 的元素倒着复制过去。辅助空间是 O(n)。写法二用两个指针一头一尾交换对应位置的元素直接在原数组上操作。辅助空间是 O(1)。大多数读者都能看懂写法二更省空间。所以考试时问你原地逆置顺序表的空间复杂度答案就是 O(1)问你借助辅助数组逆置答案就是 O(n)。4.2 递归算法的空间复杂度递归调用的栈空间也算递归算法的空间复杂度是新手最容易漏掉的。每次递归调用都会在系统栈上占用一层空间这一层空间里保存着当前调用的参数、局部变量、返回地址等。所以递归深度是多少额外空间就是多少。比如计算阶乘的递归写法int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }递归深度是 n所以空间复杂度是O(n)。如果写成循环int fact(int n) { int res 1; for (int i 2; i n; i) { res res * i; } return res; }空间复杂度是O(1)。这个对比非常直观地解释了为什么有的教材强调能用循环就不用递归。循环省空间但代码可读性不一定比递归好递归写起来容易但一不小心就爆栈。绪论习题考空间复杂度基本就是考你有没有想到递归调用栈这层空间。4.3 时间换空间、空间换时间判断题里的高频陷阱以时间换空间以空间换时间这两句话在二叉树和排序章节经常用到但绪论阶段就会出判断题。比如题目在数据处理过程中为了提高运行速度采用空间换时间的方法是可行的。判断题答案正确。典型例子是哈希表。为了 O(1) 的查找速度我们通常开辟一个较大的哈希表数组哪怕实际存的数据没那么多让桶稀疏一点冲突少一点查找就快。这就是典型的空间换时间。反过来如果不允许使用额外存储空间只允许在原数组上操作那很多时候都要多花时间比如插入排序它不借助辅助数组但时间复杂度是 O(n²)。这就是时间换空间。做题的时候是否可以额外开辟空间这个约束条件直接决定了你选什么算法。很多稍微复杂一点的数据结构题目核心就是在时间和空间之间做权衡。第一章就在潜移默化地给你灌输这个理念。5. 把这些考点串起来一套模拟绪论习题实战训练概念说了一堆最终还是要落在做题上。我按期末考试和考研选择题的常见风格从习题集里挑了几道有代表性的题目不是直接贴原文而是换了个说法你们可以自己先做再看解析。5.1 概念题组每题建议在30秒内完成第1题单选题以下关于数据的逻辑结构的叙述中正确的是A. 数据的逻辑结构是数据元素之间的逻辑关系的整体B. 数据的逻辑结构是数据在计算机中的存储位置之间的关系C. 数据的逻辑结构与存储结构一一对应D. 数据的逻辑结构分为顺序结构和链式结构答案A。B 说的是存储结构C 错在一一对应同一逻辑结构可以对应多种存储结构D 里顺序结构和链式结构是存储结构的分类不是逻辑结构的分类。这道题四个选项全部围绕逻辑结构和存储结构的混用来设坑选错的基本上就是没分清楚概念。第2题判断题算法必须有输入否则无法执行。答案错。算法可以没有输入但必须有一个或多个输出。比如求 1 到 100 的和不需要任何输入。第3题单选题以下哪一个不是算法的特性A. 有穷性B. 确定性C. 可移植性D. 可行性答案C。算法特性是有穷性、确定性、可行性、输入、输出。可移植性是软件工程里的概念不是算法本身的特性。这种题每年都有学校考就是考你把五个特性背清楚没有。第4题填空题数据结构在计算机中的表示映像称为数据的____结构。答案存储物理结构。注意用词表示或映像就是存储结构逻辑关系才是逻辑结构选择题扣字眼就扣在这里。5.2 复杂度计算题组每题建议在5分钟内完成第5题分析下面程序段的时间复杂度int i 0, s 0; while (s n) { i; s s i; }解析s 每次累加 ii 从 1 递增。设执行 k 次后 s 1 2 ... k k(k1)/2。循环停止条件为 s n即 k(k1)/2 n解的 k ≈ √(2n)。所以复杂度是 O(√n)。第6题分析下面程序段的时间复杂度for (i 1; i n; i) { for (j 1; j n; j) { for (k 1; k n; k) { x x 1; } } }解析三层循环每层都是 n 次总 n³直接写 O(n³)。这题简单但我要提醒一点考试中三层循环如果每层长度都一样直接乘如果内层长度与外层变量有关必须写累加式再化简。第7题分析下面递归算法的时间复杂度和空间复杂度void fun(int n) { if (n 1) { printf(%d, n); fun(n / 2); } }解析n 每次除以 2递归深度约 log₂n 层每层执行一次 O(1) 的打印操作所以时间复杂度O(log n)空间复杂度递归调用栈深度也是O(log n)。这种每次缩小一半的递归模式就是二分思想的雏形后面学折半查找、平衡二叉树都要用到。5.3 应用题如何完整写出一个ADT定义第8题定义一个日期的抽象数据类型写出它的数据对象、数据关系和基本操作。一个合格的参考写法数据对象D {d | d 是一个合法的日期包含 year、month、day 三个整型分量}数据关系R {year, month, month, day}即年、月、日之间存在有序的前后关系基本操作InitDate(d, y, m, t)初始化一个日期GetYear(d)、GetMonth(d)、GetDay(d)取年、月、日CompareDate(d1, d2)比较两个日期的先后NextDay(d)返回下一天的日期注意ADT 定义不是写代码它强调的是抽象。你不需要告诉别人这个日期是用三个 int 存的还是用字符串存的你只告诉别人能通过哪些操作来用这个类型。很多绪论习题的答案写成了一堆 C 语言 struct 定义这反而跑偏了。6. 结语绪论的习题值得你慢下来做一遍如果把整本数据结构教材比作一座大楼第一章就是地基里的钢筋。它看起来不显眼但后面所有的代码、算法、复杂分析、存储结构讨论全都要在这里找根据。我在实际做题和辅导中最大的感受是那些在第一章就把时间复杂度的计数逻辑练扎实的人后期学排序算法、图的遍历、动态规划的时候分析算法效率几乎没有障碍而那些第一章全靠背的人后面一到分析某算法的时间复杂度就卡壳。原因很简单第一章习题练的不是记忆是把算法执行过程抽象成数学表达式的思维习惯。最后给一个实实在在的复习建议做完绪论习题之后不要急着翻下一章。花一个晚上把做错的题全部归类——是概念混淆的错、是复杂度假算的错、还是审题不仔细的错然后再把每道错题对应的知识点在课本里找到用红笔标出来。这个复盘动作看似费时间但它是过完整个数据结构复习周期之后最有回报率的一件事。至少我当年就是这么干的后来看到题目条件里出现额外辅助空间不限或者要求原地操作这种关键词脑子里第一反应就知道出题人要考什么了。 
长河君 · 2026/10/19 8:03:44 · 阅读 1.2k 数据结构绪论习题拿分指南：抽象数据类型与复杂度分析
1. 先说点实在的第一章绪论的题为什么反而是挂科重灾区很多同学学《数据结构》翻开书看到第一章绪论觉得全是概念背一背就能过。结果一做题选择题靠蒙判断题凭感觉时间复杂度分析更是直接放弃。等到期中期末或者考研复习的时候才反应过来——第一章的习题根本不是背诵题它考的是你有没有真的理解数据结构这门课在干什么。我自己当年也是这么过来的。第一次做绪论习题觉得逻辑结构和存储结构不就是一回事吗抽象数据类型又是什么拗口的词最后算法的时间复杂度分析直接跳过。后来带过几次课程设计和笔试面试辅导又帮一些考研的同学梳理过真题才慢慢把第一章的知识点从背概念变成了看本质。这篇文章就把我在反复做题、讲题过程中积累下来的东西写出来包括核心考点的拆解、典型习题的解题思路、还有那些课本上不会明说但考题总在挖坑的细节。这篇文章适合谁看适合正在学数据结构的大学生、准备考研计算机专业课的同学也适合那些想快速复盘第一章重点的自学者。不讲虚的直接落到题上落到怎么拿分上。2. 绪论习题到底在考什么先给整章做一个考点地图2.1 数据结构三要素数据的逻辑结构、存储结构、运算绪论整章的逻辑主线其实就是围绕一句话展开的数据结构 逻辑结构 存储结构 运算。习题里的绝大多数概念题、判断题、填空题翻来覆去都是在考这个三要素。什么是逻辑结构说人话就是数据元素之间是什么关系。最常见的四种逻辑结构集合结构元素之间除了属于同一个集合之外没有任何其他关系。就像一堆散落的乒乓球它们只是碰巧在同一个袋子里。线性结构元素之间是一对一的线性关系。就像排队买奶茶你只直接联系你前面的人和后面的人。树形结构元素之间是一对多的层次关系。就像公司的组织架构一个老总管好几个总监每个总监又管好几个员工。图形结构网状结构元素之间是多对多的关系。就像社交网络你认识很多人很多人也认识你没有严格的层级。到这里还比较轻松。真正的坑在于逻辑结构与存储结构的关系这道经典辨析题。我从小到大见过至少五种变体但核心都是一个意思逻辑结构是用户看到的样子、是抽象层面的存储结构是计算机内存里实际存放的样子、是物理层面的。举个例子。同样是线性结构在内存里你可以用连续的一块空间来放这叫顺序存储典型代表是数组也可以用一串不连续的节点通过指针串起来这叫链式存储典型代表是链表。逻辑结构没有变都是一对一的线性关系但物理层面的存储方式完全不同。所以做题的时候遇到逻辑结构是数据的逻辑关系与存储结构无关这种判断题你就要立刻反应过来逻辑结构确实独立于存储结构而存在但每种逻辑结构都必须通过某种存储结构来实现。这两句话不矛盾前者说的是概念上可以分开研究后者说的是实现上必须落地。考试最爱在这里玩文字游戏。2.2 抽象数据类型ADT这个概念做题时到底怎么用抽象数据类型Abstract Data TypeADT是第一章概念题的另一大源。很多同学觉得这个词玄乎其实理解起来特别简单**ADT 就是一个数据集合 在这个集合上能进行的操作。你不需要关心内部是怎么存储的你只需要关心能做什么。这就像你开一台洗衣机你关心的操作是洗衣服甩干你不需要关心里面电机怎么转、齿轮怎么咬合。洗衣机对你来说就是一个抽象数据类型。课本上通常会把 ADT 描述成三元组ADT (D, S, P)其中 D 是数据对象DataS 是数据关系StructureP 是基本操作Operation。习题里如果让你定义一个复数的抽象数据类型你需要做的就是三件事说清楚数据对象是什么比如复数由实部和虚部两个实数构成。说清楚数据关系是什么复数的实部和虚部是有序的二元组关系。说清楚基本操作有哪些比如构造复数、取实部、取虚部、两个复数相加、两个复数相乘。我在批改作业的时候发现大部分同学写定义 ADT只写了操作列表前面两步经常漏。记住完整的三元组缺一个都不算全。有些严一点的学校期末考填空就专门挖 D、S、P 这三个字母让你填。2.3 考频最高的概念辨析题我按踩坑概率给它们排了个名第一章习题里有一批看起来每个字都认识放进题目里就不认识了的句子我把它们在历年各种习题集、考试卷里出现的频率和踩坑概率按从高到低排了一下第一位数据项和数据元素的区别。数据元素是数据的基本单位比如一个学生记录学号、姓名、成绩就是一个数据元素数据项是组成数据元素的最小单位学号是一个数据项姓名是一个数据项。做题的时候题目说一个结点就是一个数据元素对一个数据元素就是一条记录在大多数讨论单个记录的场景下对但严格说记录是数据元素的同义词能互换。真正爱挖坑的是数据元素可以由若干个数据项组成数据项是数据的不可分割的最小单位——这里不可分割四个字很多人不注意选择题就专门在这里设干扰项。第二位算法五个特性有穷性、确定性、可行性、输入、输出。经典的判断题是算法必须有输入否则无法执行——这是错的算法可以没有输入但必须有输出。比如一个算法功能是生成前100个质数它就不需要任何输入但必须有输出。另一个经典判断题是算法必须有穷程序也必须要有穷——这也是错的程序可以无限循环跑下去不退出不能算有穷但算法定义里明确要求必须在执行有限步之后结束这是算法和程序的一个关键区别。第三位好的算法的评价标准。正确性、可读性、健壮性、高效性时间效率高、存储量低。习题里经常出现算法的时间复杂度越低空间复杂度越低算法就一定越好这种极端表述显然不对。因为有时你牺牲一点时间换空间比如压缩存储有时牺牲空间换时间比如哈希表这是工程中的正常取舍。判断题里一出现越……越……就越好这种绝对化表述十有八九是错的。3. 时间复杂度的题怎么解从一道题都不会到拿到分3.1 别再背 O(1)、O(n)、O(n²) 了先理解数量级是什么意思绪论习题里最值钱的分值就是时间复杂度分析。很多同学直接跳过这一部分觉得又是数学又是逻辑太难。但实际只要你掌握了套路这部分是最好拿分的而且后面学线性表、树、图、排序算法都要回来用这一章的知识。先理解什么叫时间复杂度。简单说就是算法执行时间随问题规模 n 增长的变化趋势。我们不关心具体的执行时间是多少毫秒我们只关心当 n 变大的时候执行时间大约变成原来的几倍。比如说一个算法执行次数总是 3n² 2n 1 次当 n 翻倍的时候3n² 变成 12n²翻了4倍2n 变成 4n翻了2倍常数项不变。最终主导增长率的是 n² 这一项。所以我们说这个算法的时间复杂度是O(n²)读作大O n平方。大O记号的含义是渐进上界也就是它表示一个算法运行时间最多不超过某个数量级。刚才那个式子我们说它是 O(n²)因为当 n 足够大的时候3n² 2n 1 的增长速度最多跟 n² 同一个级别。这就是数量级的含义。做题的时候只需要记住一个最核心的操作我称之为找主体循环数执行次数留最高阶去常数系数。3.2 单层循环套路数一数循环体到底执行了几次最简单的题型是单层循环。比如for (i 1; i n; i) { x x 1; }循环体执行 n 次时间复杂度 O(n)。没难度跳过。有难度的单层循环是这个样子for (i 1; i n; i i * 2) { x x 1; }循环变量 i 不是每次加 1而是每次乘 2。那么 i 的取值序列是 1, 2, 4, 8, 16, ...。你要问的问题是i 大概执行多少次会超过 n假设执行了 k 次那么第 k 次的时候 i 2^(k-1)跳出条件就是 2^(k-1) n解出来 k ≈ log₂n 1。所以循环体执行次数是O(log n)级别。注意这里的底数 2 无所谓因为 log₂n 和 log₃n 只差一个常数系数而大O记号会去掉常数系数。所以考试时你写 O(log n) 就行不用纠结底数。我见过最坑的单层循环题是这样的for (i 0; i * i n; i) { x; }这题很多人看到 i * i 就懵了。其实判断条件等价于 i √n所以循环执行次数是O(√n)。你只要把判断条件里的表达式整理成关于 i 的关系式然后求 i 的最大值就行了。3.3 双重循环计数思路决定成败双重循环是时间复杂度题目的大宗也是区分会做和假装会做的分水岭。我见过很多同学一看到嵌套循环就直接写 O(n²)结果错得离谱。先来一个最简单的双层循环for (i 1; i n; i) { for (j 1; j n; j) { x; } }外层执行 n 次内层每次都执行 n 次所以总执行次数 n × n n²时间复杂度 O(n²)。这个没问题。但下面这个就完全不同for (i 1; i n; i) { for (j i; j n; j) { x; } }内层循环次数不是固定的 n而是从 i 跑到 n也就是 n - i 1 次。所以总执行次数是∑(i1 到 n) (n - i 1) n (n-1) (n-2) ... 1 n(n1)/2去掉低阶项和常数系数时间复杂度还是O(n²)。虽然还是 n² 级别但如果你心里没这个计算过程后面遇到更复杂的你肯定撑不住。再来看一个经典的变种for (i 1; i n; i) { for (j 1; j i; j) { x; } }这个和上一个本质上一样总次数也是 1 2 3 ... n n(n1)/2O(n²)。现在来一道全网学生错得最多的类型for (i 1; i n; i) { for (j 1; j i; j j * 2) { x; } }内层循环不是 j而是 j j * 2。所以对于固定的外层 i内层循环执行的次数是 log₂i 级别因为 j 从 1 翻倍增长到超过 i 为止。总执行次数就是∑(i1 到 n) log₂i log₂1 log₂2 ... log₂n log₂(n!)根据斯特林近似log₂(n!) 约等于 n log₂n。所以时间复杂度是O(n log n)。大部分教材都把这一题列为中等难度如果你能在没看答案的情况下推到这里说明你已经真正理解了时间复杂度的计数逻辑。3.4 复杂一点的循环条件别急着写答案先把执行次数表达式写出来有些题目喜欢在循环条件里做文章。比如for (i 1, s 0; s n; i) { s s i; }这题看着是单层循环但是循环条件用的是变量 s而 s 每次增加 i。你要求的是s 从 0 开始第一次加 1、第二次加 2、第三次加 3……一直加到什么时候 s 超过 n。也就是求最小的 k使得 1 2 3 ... k n。左边是 k(k1)/2解 k(k1)/2 ≈ n得到 k ≈ √(2n)。时间复杂度是O(√n)。这类题的精髓就是先把循环体执行了多少次等价成一个数学问题把数学式子列出来再求次数表达式最后转成大O记号。我建议所有初学者都养成写求和式的习惯不要脑子里算一下就写答案。做题时纸笔演算的过程本身就是建立思路的过程。3.5 递归算法的时间复杂度绪论考得不深但要会递推第一章的递归算法时间复杂度题一般不会太难常见的套路是给出一个递归关系式让你求复杂度。比如T(n) 2T(n/2) nT(1) O(1)这种式子可以用主定理直接求解也可以用画递归树的方法。画递归树是这样的每一层的总代价是 n因为下一层两个子问题每个规模 n/2代价加一起是 n下一层四个子问题每个规模 n/4代价加一起还是 n。一共有 log₂n 层因为每次除以 2所以总复杂度是O(n log n)。绪论阶段大家只要掌握两类递推就够用了T(n) T(n-1) O(1)每次只减少 1一共要递归 n 层总复杂度O(n)。T(n) 2T(n/2) O(n)归并排序式的递归总复杂度O(n log n)。见到这种递推式不要慌画递归树或者一层一层展开都能得到答案。3.6 最坏时间复杂度和平均时间复杂度什么时候用哪个做题的时候你会发现有些题目问该算法的最坏时间复杂度有些问平均时间复杂度。这个区分特别重要。最坏时间复杂度在最坏情况下算法执行基本操作的次数。比如快速排序最坏情况下数据已经有序时间复杂度会退化到 O(n²)。平均时间复杂度所有可能输入等概率出现时算法执行次数的加权平均值。快速排序的平均时间复杂度是 O(n log n)。最好时间复杂度最理想情况下的执行次数比如快速排序最好也是 O(n log n)。判断题里经常出现的一句话是对于一个算法其平均时间复杂度总是等于最坏时间复杂度。这显然是错的。另一个常见的说法是算法的性能分析只考虑最坏情况即可不用管平均情况这也是错的。比如在哈希表查找中平均时间复杂度是 O(1)但如果哈希函数写得不好最坏会退化成 O(n)。你要设计一个在多数场景下表现稳定的系统平均复杂度必须看要评估一个系统的底线性能比如地铁闸机在最繁忙时段不能崩溃最坏复杂度必须看。4. 空间复杂度的题另一个容易拿分但总被忽视的考点4.1 空间复杂度算的是额外的辅助空间不是数据本身占的空间很多人对空间复杂度的理解是这个算法占了多少内存这种理解不够准确。做题时我们要算的是算法执行过程中额外需要的存储空间不包括输入数据本身所占用的空间。这个额外课本里叫辅助空间。举个最经典的例子。将一个数组逆序输出有两种写法写法一新建一个同样大小的数组 b把 a 的元素倒着复制过去。辅助空间是 O(n)。写法二用两个指针一头一尾交换对应位置的元素直接在原数组上操作。辅助空间是 O(1)。大多数读者都能看懂写法二更省空间。所以考试时问你原地逆置顺序表的空间复杂度答案就是 O(1)问你借助辅助数组逆置答案就是 O(n)。4.2 递归算法的空间复杂度递归调用的栈空间也算递归算法的空间复杂度是新手最容易漏掉的。每次递归调用都会在系统栈上占用一层空间这一层空间里保存着当前调用的参数、局部变量、返回地址等。所以递归深度是多少额外空间就是多少。比如计算阶乘的递归写法int fact(int n) { if (n 1) return 1; return n * fact(n - 1); }递归深度是 n所以空间复杂度是O(n)。如果写成循环int fact(int n) { int res 1; for (int i 2; i n; i) { res res * i; } return res; }空间复杂度是O(1)。这个对比非常直观地解释了为什么有的教材强调能用循环就不用递归。循环省空间但代码可读性不一定比递归好递归写起来容易但一不小心就爆栈。绪论习题考空间复杂度基本就是考你有没有想到递归调用栈这层空间。4.3 时间换空间、空间换时间判断题里的高频陷阱以时间换空间以空间换时间这两句话在二叉树和排序章节经常用到但绪论阶段就会出判断题。比如题目在数据处理过程中为了提高运行速度采用空间换时间的方法是可行的。判断题答案正确。典型例子是哈希表。为了 O(1) 的查找速度我们通常开辟一个较大的哈希表数组哪怕实际存的数据没那么多让桶稀疏一点冲突少一点查找就快。这就是典型的空间换时间。反过来如果不允许使用额外存储空间只允许在原数组上操作那很多时候都要多花时间比如插入排序它不借助辅助数组但时间复杂度是 O(n²)。这就是时间换空间。做题的时候是否可以额外开辟空间这个约束条件直接决定了你选什么算法。很多稍微复杂一点的数据结构题目核心就是在时间和空间之间做权衡。第一章就在潜移默化地给你灌输这个理念。5. 把这些考点串起来一套模拟绪论习题实战训练概念说了一堆最终还是要落在做题上。我按期末考试和考研选择题的常见风格从习题集里挑了几道有代表性的题目不是直接贴原文而是换了个说法你们可以自己先做再看解析。5.1 概念题组每题建议在30秒内完成第1题单选题以下关于数据的逻辑结构的叙述中正确的是A. 数据的逻辑结构是数据元素之间的逻辑关系的整体B. 数据的逻辑结构是数据在计算机中的存储位置之间的关系C. 数据的逻辑结构与存储结构一一对应D. 数据的逻辑结构分为顺序结构和链式结构答案A。B 说的是存储结构C 错在一一对应同一逻辑结构可以对应多种存储结构D 里顺序结构和链式结构是存储结构的分类不是逻辑结构的分类。这道题四个选项全部围绕逻辑结构和存储结构的混用来设坑选错的基本上就是没分清楚概念。第2题判断题算法必须有输入否则无法执行。答案错。算法可以没有输入但必须有一个或多个输出。比如求 1 到 100 的和不需要任何输入。第3题单选题以下哪一个不是算法的特性A. 有穷性B. 确定性C. 可移植性D. 可行性答案C。算法特性是有穷性、确定性、可行性、输入、输出。可移植性是软件工程里的概念不是算法本身的特性。这种题每年都有学校考就是考你把五个特性背清楚没有。第4题填空题数据结构在计算机中的表示映像称为数据的____结构。答案存储物理结构。注意用词表示或映像就是存储结构逻辑关系才是逻辑结构选择题扣字眼就扣在这里。5.2 复杂度计算题组每题建议在5分钟内完成第5题分析下面程序段的时间复杂度int i 0, s 0; while (s n) { i; s s i; }解析s 每次累加 ii 从 1 递增。设执行 k 次后 s 1 2 ... k k(k1)/2。循环停止条件为 s n即 k(k1)/2 n解的 k ≈ √(2n)。所以复杂度是 O(√n)。第6题分析下面程序段的时间复杂度for (i 1; i n; i) { for (j 1; j n; j) { for (k 1; k n; k) { x x 1; } } }解析三层循环每层都是 n 次总 n³直接写 O(n³)。这题简单但我要提醒一点考试中三层循环如果每层长度都一样直接乘如果内层长度与外层变量有关必须写累加式再化简。第7题分析下面递归算法的时间复杂度和空间复杂度void fun(int n) { if (n 1) { printf(%d, n); fun(n / 2); } }解析n 每次除以 2递归深度约 log₂n 层每层执行一次 O(1) 的打印操作所以时间复杂度O(log n)空间复杂度递归调用栈深度也是O(log n)。这种每次缩小一半的递归模式就是二分思想的雏形后面学折半查找、平衡二叉树都要用到。5.3 应用题如何完整写出一个ADT定义第8题定义一个日期的抽象数据类型写出它的数据对象、数据关系和基本操作。一个合格的参考写法数据对象D {d | d 是一个合法的日期包含 year、month、day 三个整型分量}数据关系R {year, month, month, day}即年、月、日之间存在有序的前后关系基本操作InitDate(d, y, m, t)初始化一个日期GetYear(d)、GetMonth(d)、GetDay(d)取年、月、日CompareDate(d1, d2)比较两个日期的先后NextDay(d)返回下一天的日期注意ADT 定义不是写代码它强调的是抽象。你不需要告诉别人这个日期是用三个 int 存的还是用字符串存的你只告诉别人能通过哪些操作来用这个类型。很多绪论习题的答案写成了一堆 C 语言 struct 定义这反而跑偏了。6. 结语绪论的习题值得你慢下来做一遍如果把整本数据结构教材比作一座大楼第一章就是地基里的钢筋。它看起来不显眼但后面所有的代码、算法、复杂分析、存储结构讨论全都要在这里找根据。我在实际做题和辅导中最大的感受是那些在第一章就把时间复杂度的计数逻辑练扎实的人后期学排序算法、图的遍历、动态规划的时候分析算法效率几乎没有障碍而那些第一章全靠背的人后面一到分析某算法的时间复杂度就卡壳。原因很简单第一章习题练的不是记忆是把算法执行过程抽象成数学表达式的思维习惯。最后给一个实实在在的复习建议做完绪论习题之后不要急着翻下一章。花一个晚上把做错的题全部归类——是概念混淆的错、是复杂度假算的错、还是审题不仔细的错然后再把每道错题对应的知识点在课本里找到用红笔标出来。这个复盘动作看似费时间但它是过完整个数据结构复习周期之后最有回报率的一件事。至少我当年就是这么干的后来看到题目条件里出现额外辅助空间不限或者要求原地操作这种关键词脑子里第一反应就知道出题人要考什么了。