第一部分 选择题 17第1题单链表尾部插入究竟有多快题目小杨用单链表保存任务序列并同时维护头指针head和尾指针tail。在链表非空且已知tail的情况下在表尾插入新结点的时间复杂度是 。答案A一、先想象一个“排队的小火车”单链表可以想象成一列小火车head ↓ [任务1] → [任务2] → [任务3] → nullptr ↑ tail每个结点里面有两个东西struct Node { int value; Node *next; };一个存数据value一个负责指向下一个结点next二、如果没有 tail会发生什么假设我们只有head现在想在最后面添加[1] → [2] → [3] → [4]我们不知道谁是最后一个。只能从头开始找1 → 2 → 3 → 4 ↑ 从这里开始找如果有n个结点就可能需要走n步。所以时间复杂度O(n)三、可是题目说我有 tail现在head ↓ [1] → [2] → [3] ↑ tail要加入[4]直接tail-next newNode; tail newNode;只做两三件固定的事情。不管链表里面有10个 100个 10000个 1000000个都差不多这么几步。所以O(1)⭐ 小学生记忆法有尾指针 tail找队伍最后一个人就不用从头找。已知 tail → 尾部插入 O(1)第2题双向链表删除结点题目说在不带哨兵结点的双向链表中结点p既不是头结点也不是尾结点。删除p的正确代码是 。答案C。一、先认识“双向链表”单链表A → B → CB 只知道后面是谁双向链表则是A ⇄ B ⇄ CB 不但知道 CB.next C还知道 AB.prev A所以prev next ← → [A] ⇄ [B] ⇄ [C]二、现在要删除 B原来A ⇄ B ⇄ C删除 B 后我们希望变成A ⇄ C那么要修改哪两个“指针”第一步让 A 跳过 B直接指向 Cp-prev-next p-next;图A.next C第二步让 C 反过来指向 Ap-next-prev p-prev;图C.prev A最后delete p;所以完整代码p-prev-next p-next; p-next-prev p-prev; delete p;答案C⭐ 为什么其他思路容易错比如p-prev p-next;这只是修改了p 自己的 prev。但是我们真正需要修理的是A.next C.prev也就是说删除一个结点不是只修改“自己”而是要把前后两个邻居重新牵手。 记忆口诀删除双向链表中的p前面的 next 跳过 p 后面的 prev 跳过 p 最后 delete p即p-prev-next p-next; p-next-prev p-prev; delete p;第3题快慢指针寻找链表中点题目给出了Node *middle(Node *head) { Node *slow head; Node *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; ______________________ } return slow; }答案Bfast fast-next-next;原题程序结构见试卷。一、什么叫“快慢指针”想象学校运动会上有两位同学小慢一次走1格小快一次走2格例如1 → 2 → 3 → 4 → 5一开始slow ↓ 1 fast ↓ 1每轮slow走1步 fast走2步二、跑一跑第一轮1 → 2 → 3 → 4 → 5 ↑ slow ↑ fast第二轮1 → 2 → 3 → 4 → 5 ↑ slow ↑ fast此时slow 3刚好来到中间三、为什么这么神奇因为fast速度 slow速度 × 2当 fast 走完整条链表时fast走了 n slow只走了 n/2所以 slow 就停在中间附近。四、横线应该写什么slowslow slow-next;一次走一步。那么 fast 就必须fast fast-next-next;一次走两步。答案B⭐ 记忆口诀慢指针一步走快指针两步走。看到slow fast脑袋里立刻出现 一步 两步第4题欧几里得算法求最大公约数题目int gcd(int a, int b) { return b 0 ? a : gcd(b, a % b); }求gcd(105,45)答案C15。一、什么是最大公约数105 和 45 的公约数1 3 5 15最大的15所以gcd(105,45)15不过考试不会让我们一个一个试。这里使用的是非常经典的欧几里得算法也叫辗转相除法。二、看看代码到底在干什么核心gcd(a,b)会变成gcd(b,a%b)我们一步一步算。第一次105 ÷ 45余数15所以gcd(105,45) gcd(45,15)第二次45 ÷ 15余数0所以gcd(45,15) gcd(15,0)第三次因为b 0于是return a;返回15⭐ 记忆口诀欧几里得算法就像大石头不断用小石头去除最后剩下的那个“最后的非零余数”就是最大公约数。口诀gcd(a,b) ↓ gcd(b,a%b) ↓ 直到 b0 ↓ 答案就是 a第5题怎么判断一个数是不是质数题目bool isPrime(int n) { if (n 2) return false; for (int i 2; __________________; i) { if (n % i 0) return false; } return true; }选项A. i n B. i n / 2 C. i * i n D. (long long)i * i n答案D。一、什么是质数质数就是大于1并且只能被1和自己整除的数。例如2、3、5、7、11、13……不是质数4、6、8、9、10……二、最笨的方法判断97是不是质数。最笨2、3、4、5、6、7、……96全部试。太慢了三、其实只需要检查到 √n为什么假设n a × b如果a √n那么b √n也就是说如果一个数是合数那么它一定至少有一个因数≤ √n所以我们只需要检查i × i n四、为什么选 DD(long long)i * i n它表示i² ≤ n也就是i ≤ √n这正是最经典的质数判断范围。五、为什么还要(long long)这个细节非常重要如果i是int那么i * i可能发生整数溢出。例如 i 很大的时候i × i超过int能表示的范围就可能出问题。所以写(long long)i * i更加安全。⭐ 记忆口诀判断质数不必试到 n只试到 √n。代码模板for (int i 2; (long long)i * i n; i)看到它就应该马上想到质数判断第6题线性筛为什么能做到“一合数只筛一次”这一题开始稍微有点难度了。题目给出的核心代码for (int p : primes) { if ((long long)i * p n) break; composite[i * p] true; if (__________________) break; }选项A. p % i 0 B. i % p 0 C. i p D. i * p n答案Bi % p 0原题线性筛代码见试卷。一、先理解“筛子”我们想找2、3、5、7、11……这些质数。而4、6、8、9、10……都是合数。线性筛的目标非常牛每一个合数只让它被自己的最小质因子筛掉一次。二、什么叫最小质因子例如12 2 × 2 × 3最小质因子是215 3 × 5最小质因子335 5 × 7最小质因子5三、关键问题来了代码composite[i * p] true;说明i × p被筛掉。但是什么时候应该停止答案if (i % p 0) break;四、举个例子i 1212 2 × 2 × 3质数从小到大2、3、5、7……首先p 2筛12 × 2 24然后12 % 2 0成立说明2 是 12 的最小质因子这时候break;停止。五、为什么必须停止因为如果继续12 × 3 36以后又可能通过其他方式把36筛掉。线性筛就是想做到一个合数只认一个“最小质因子”不重复处理。所以if (i % p 0) break;答案B 一句话记住线性筛遇到“p 能整除 i”说明 p 已经是 i 的最小质因子该停了。第7题唯一分解定理——质因数分解题目根据唯一分解定理整数……的正确质因数分解是 。本题在 PDF 的文字解析中题目的具体被分解整数和选项公式出现了排版丢失因此仅凭当前提取文本无法可靠还原第7题的具体数字和四个选项。原卷目录位置明确显示第7题紧接在线性筛之后。但这道题考察的知识点可以确定是唯一分解定理 质因数分解第7题答案是A。一、什么叫“唯一分解定理”一个大于 1 的整数都可以写成若干个质数相乘的形式而且这种分解方式是唯一的除了质因子的排列顺序不同。例如12可以分解12 2 × 2 × 3也可以写12 3 × 2 × 2虽然顺序不同但是本质完全一样2² × 3二、再看一个例子比如60不断拆60 ↓ ÷2 30 ↓ ÷2 15 ↓ ÷3 5 ↓ ÷5 1所以60 2 × 2 × 3 × 5也就是60 2² × 3 × 5这就是质因数分解。三、为什么叫“唯一”比如60你无论怎么拆60 2 × 30 2 × 2 × 15 2 × 2 × 3 × 5最终都会得到2、2、3、5不会出现另外一套完全不同的质因数。所以大整数就像一座城堡质数是它最基本的砖块。城堡可以有不同的拆墙顺序但是最后使用的“砖块种类和数量”是固定的。 17题串起来看这一组题其实不是七个完全孤立的知识点。我们把它们串起来第1题 单链表 ↓ 第2题 双向链表 ↓ 第3题 快慢指针 ↓ 第4题 最大公约数 ↓ 第5题 质数判断 ↓ 第6题 线性筛 ↓ 第7题 质因数分解可以把它看成一场“算法升级冒险” 第一关链表村学会head tail next prev核心思想指针就是“告诉你下一个人在哪里”。 第二关快慢赛跑学会slow一步 fast两步用来寻找链表中点。 第三关数学魔法欧几里得算法gcd(a,b) → gcd(b,a%b)不断缩小问题。 第四关质数侦探不要傻傻检查2n-1只检查2√n⚡ 第五关线性筛普通筛法一个合数可能被标记很多次。线性筛一个合数只让最小质因子负责。 第六关质因数分解最终发现所有大于1的整数都可以拆成唯一的一组质数“积木”。 考试最后一分钟速记表题目核心知识记忆口诀1单链表尾插有tail尾插O(1)2双向链表删除前next跳过后prev跳过3快慢指针slow一步fast两步4gcdgcd(a,b)gcd(b,a%b)5质数判断只检查到√n6线性筛i%p0就停止7唯一分解每个数都有唯一的质因数“积木”如果把这 7 道题压缩成7 句话同学们可以这样记① 有 tail尾插 O(1)。② 删 p前后邻居重新牵手。③ 慢一快二找中点。④ gcd 不断换成(b, a%b)。⑤ 质数只查到 √n。⑥ 线性筛遇到i%p0就停。⑦ 每个整数都有唯一的质因数积木。
