企业官网建设流程全解析

第1题 单向循环链表插入结点

答案：B

1、题目代码如下：

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 → 20

（3）如果反过来做：

head->next=newNode;

那么20就找不到了。

（4）所以：

一定先保存原来的next，再修改head。

4、第三步：对应代码

（1）原来：

head ↓ 10 ----->20

（2）执行

newNode->next = head->next;

（3）变成：

99 ----->20

（4）再执行

head->next = newNode;

（5）结果：

10 ->99->20

完全正确。

5、答案：

newNode->next = head->next; head->next = newNode;

就是B。

6、为什么其它错？

（1）A选项：

newNode->next = head;

变成

99→head

完全接错地方。

不是插到后面。

（2）C选项：

head->next = newNode; newNode->next = head->next;

注意第二句。

此时

head->next

已经是newNode自己。

于是：

newNode ↓ newNode

自己指向自己。

后面的链全部丢失。

这是典型错误。

（3）D选项：

head = newNode;

只是修改局部变量。

外面的head一点没变。

根本没插进去。

7、本题知识点

⭐⭐⭐⭐⭐

单链表插入口诀：

先连后，再改前。

永远都是：

new->next = p->next; p->next = new;

第2题 循环单链表遍历

答案：C

1、为什么不能用while？

（1）普通链表：

1→2→3→nullptr

最后：

p==nullptr

停止。

（2）但是循环链表：

1→2→3 ↑ ↓ └────┘

永远没有nullptr。

所以：

while(p!=nullptr)

永远成立。

是死循环。

2、正确方法

（1）循环链表有一个特点：

重新回到head时说明走完一圈。

（2）所以：

do { ... }while(p!=head);

第一次一定执行。

（3）然后：

1 ↓ 2 ↓ 3 ↓ head

停止。

因此答案C。

3、为什么要do while？

（1）假如只有一个节点：

head ↑ │ └───

（2）如果写

while(p!=head)

第一次：

p=head

条件就是假。

一次都不会输出。

（3）所以必须：

do { }while(...)

4、其它选项为什么错？

（1）A选项：

普通链表写法。

循环链表死循环。

（2）B选项：

while(p->next!=nullptr)

循环链表永远没有nullptr。

死循环。

（3）D选项：

for循环本质也是

p!=nullptr

仍然死循环。

5、本题知识点

⭐⭐⭐⭐⭐

循环链表遍历口诀：

不是看nullptr，而是看是否回到起点。

第3题 删除双向链表中间节点

答案：A

1、故事说明

（1）三位同学：

A ⇄ B ⇄ C

现在B毕业了。

应该怎么办？

不是把B直接删掉就完事。

（2）而是B删掉前：

A和C要互相拉手。

A ⇄ C

（3）所以：

第一步：

A.next=C

第二步：

C.prev=A

最后：

delete B

（4）对应代码：

p->prev->next = p->next; p->next->prev = p->prev; delete p;

这正是A选项。

2、为什么其它错？

（1）其它三个选项都把：

prev next

连错了。

（2）例如：

p->next->prev = p->next;

表示：

C.prev=C

自己指自己。

链断掉。

3、删除双向链表：

一定要改两根线。

前驱.next 后继.prev

缺一不可。

第4题 欧几里得算法（最大公约数）

答案：B

1、函数：

int gcd(int a, int b) { return b ==0 ? a : gcd(b,a%b); }

2、要求计算：

gcd(105,45)

（1）第一次：

105%45=15

得到

gcd(45,15)

（2）第二次：

45%15=0

得到

gcd(15,0)

（3）结束。

因此：

gcd(105,45) ↓ gcd(45,15) ↓ gcd(15,0)

答案是B。

第5题 欧拉筛（线性筛）

答案：A

1、这是五级的经典考点。

（1）代码：

if(__________) break;

为什么要break？

因为：

欧拉筛要求：

每个合数只被最小质因子筛一次。

（2）什么时候停止？

当：

i能被primes[j]整除

说明：

primes[j]

已经是最小质因子。

后面不用筛。

（3）所以：

i % primes[j] == 0

答案是A。

2、为什么不是其它？

（1）B选项：

质数%i

毫无意义。

（2）C选项：

恰好反了。

（3）D选项：

根本不是判断条件。

3、记忆口诀

欧拉筛：

遇到第一个能整除自己的质数，就停止。

即：

if(i%prime==0) break;

第6题 埃氏筛

答案：B

1、有的同学还是容易把：

埃氏筛

欧拉筛

混淆。

2、埃氏筛思想：

（1）假设发现质数2。

那么把2的倍数：

4 6 8 10 12 ...

全部标记。

（2）发现3。

再标记3的倍数：

6 9 12 15 ...

（3）所以：

每发现一个质数，就把它所有倍数划掉。

因此：

答案是B。

3、为什么A选项错？

（1）A选项说：

每个合数只筛一次

这是：

欧拉筛！

不是埃氏筛。

（2）例如：

12

埃氏筛法会被：

2

筛一次。

又被：

3

筛一次。

所以会有重复。

4、五级考试考点

埃氏筛：

一个合数可能被划很多次。

欧拉筛：

一个合数只划一次。

第7题 快速幂体现什么思想

答案：C 分治

1、看代码：

power(x,n) { res=power(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 Conquer）

3、为什么不是其它？

（1）A 选项：枚举

程序没有一个一个试。

（2）B 选项：贪心

没有局部最优。

（3）D 选项： 模拟

没有按过程模拟。

4、本题知识点

（1）快速幂核心：

power(x,n) ↓ power(x,n/2)

问题规模减半。

（2）时间复杂度：

O(log n)

这是典型的分治。

第一部分 1～7题知识总结