第1题 单向循环链表插入结点答案B1、题目代码如下void insertAfterHead(Node* head, int x) { Node* newNode new Node; newNode-val x; ________ ________ }2、第一步先认识链表1假设现在有这样一个循环链表head ↓ 10 → 20 → 30 ↑ ↓ └──────────┘2现在要插入数字99。要求head ↓ 10 → 99 → 20 → 30 ↑ ↓ └───────────────┘也就是说99插到head后面。3、第二步故事理解1想象成一列小火车。原来火车头(head) │ ▼ 10 ——20——30现在新来了一节车厢99。2正确操作一定是第一步99先拉住20。99 → 20第二步head再拉住99。10 → 99于是10 → 99 → 203如果反过来做head-nextnewNode;那么20就找不到了。4所以一定先保存原来的next再修改head。4、第三步对应代码1原来head ↓ 10 -----202执行newNode-next head-next;3变成99 -----204再执行head-next newNode;5结果10 -99-20完全正确。5、答案newNode-next head-next; head-next newNode;就是B。6、为什么其它错1A选项newNode-next head;变成99→head完全接错地方。不是插到后面。2C选项head-next newNode; newNode-next head-next;注意第二句。此时head-next已经是newNode自己。于是newNode ↓ newNode自己指向自己。后面的链全部丢失。这是典型错误。3D选项head newNode;只是修改局部变量。外面的head一点没变。根本没插进去。7、本题知识点⭐⭐⭐⭐⭐单链表插入口诀先连后再改前。永远都是new-next p-next; p-next new;第2题 循环单链表遍历答案C1、为什么不能用while1普通链表1→2→3→nullptr最后pnullptr停止。2但是循环链表1→2→3 ↑ ↓ └────┘永远没有nullptr。所以while(p!nullptr)永远成立。是死循环。2、正确方法1循环链表有一个特点重新回到head时说明走完一圈。2所以do { ... }while(p!head);第一次一定执行。3然后1 ↓ 2 ↓ 3 ↓ head停止。因此答案C。3、为什么要do while1假如只有一个节点head ↑ │ └───2如果写while(p!head)第一次phead条件就是假。一次都不会输出。3所以必须do { }while(...)4、其它选项为什么错1A选项普通链表写法。循环链表死循环。2B选项while(p-next!nullptr)循环链表永远没有nullptr。死循环。3D选项for循环本质也是p!nullptr仍然死循环。5、本题知识点⭐⭐⭐⭐⭐循环链表遍历口诀不是看nullptr而是看是否回到起点。第3题 删除双向链表中间节点答案A1、故事说明1三位同学A ⇄ B ⇄ C现在B毕业了。应该怎么办不是把B直接删掉就完事。2而是B删掉前A和C要互相拉手。A ⇄ C3所以第一步A.nextC第二步C.prevA最后delete B4对应代码p-prev-next p-next; p-next-prev p-prev; delete p;这正是A选项。2、为什么其它错1其它三个选项都把prev next连错了。2例如p-next-prev p-next;表示C.prevC自己指自己。链断掉。3、删除双向链表一定要改两根线。前驱.next 后继.prev缺一不可。第4题 欧几里得算法最大公约数答案B1、函数int gcd(int a, int b) { return b 0 ? a : gcd(b,a%b); }2、要求计算gcd(105,45)1第一次105%4515得到gcd(45,15)2第二次45%150得到gcd(15,0)3结束。因此gcd(105,45) ↓ gcd(45,15) ↓ gcd(15,0)答案是B。第5题 欧拉筛线性筛答案A1、这是五级的经典考点。1代码if(__________) break;为什么要break因为欧拉筛要求每个合数只被最小质因子筛一次。2什么时候停止当i能被primes[j]整除说明primes[j]已经是最小质因子。后面不用筛。3所以i % primes[j] 0答案是A。2、为什么不是其它1B选项质数%i毫无意义。2C选项恰好反了。3D选项根本不是判断条件。3、记忆口诀欧拉筛遇到第一个能整除自己的质数就停止。即if(i%prime0) break;第6题 埃氏筛答案B1、有的同学还是容易把埃氏筛欧拉筛混淆。2、埃氏筛思想1假设发现质数2。那么把2的倍数4 6 8 10 12 ...全部标记。2发现3。再标记3的倍数6 9 12 15 ...3所以每发现一个质数就把它所有倍数划掉。因此答案是B。3、为什么A选项错1A选项说每个合数只筛一次这是欧拉筛不是埃氏筛。2例如12埃氏筛法会被2筛一次。又被3筛一次。所以会有重复。4、五级考试考点埃氏筛一个合数可能被划很多次。欧拉筛一个合数只划一次。第7题 快速幂体现什么思想答案C 分治1、看代码power(x,n) { respower(x,n/2); return res*res; }2、故事1计算2^16普通方法2×2×2×……16次。2快速幂2^16 ↓ (2^8)^2 ↓ (2^4)^2 ↓ (2^2)^2 ↓ (2^1)^2不断把问题砍成一半。3这就是分治思想Divide and Conquer3、为什么不是其它1A 选项枚举程序没有一个一个试。2B 选项贪心没有局部最优。3D 选项 模拟没有按过程模拟。4、本题知识点1快速幂核心power(x,n) ↓ power(x,n/2)问题规模减半。2时间复杂度O(log n)这是典型的分治。第一部分 17题知识总结题号考点一句话口诀1单链表插入先接后再改前2循环链表遍历回到head结束不看nullptr3双链表删除改前驱next改后继prev4欧几里得算法gcd(a,b)gcd(b,a%b)5欧拉筛遇到最小质因子立即break6埃氏筛每个质数筛所有倍数7快速幂不断减半就是分治