第1题位运算—— 和 | 到底在计算什么正确答案C81. 题目内容给出下面的 C 程序#include iostream using namespace std; int main() { int a 5, b 3; cout (a b) (a | b) endl; return 0; }问程序最后输出什么选项A. 6B. 7C. 8D. 92. 先理解计算机为什么喜欢二进制同学们我们平时使用十进制数字比如5310100但是计算机内部更喜欢使用二进制也就是只有两个数字0 和 1。我们先把数字5和3转换成二进制。十进制二进制5010130011这里为了方便观察我们统一写成4位。3. 第一个运算符 按位与的名字叫作按位与Bitwise AND。它的规则非常简单两个位置上的数字都为1结果才是1否则就是0。我们来看一个小表格左边右边左边 右边000010100111现在计算5 3把两个数字写成二进制0101 0011 ------ 0001逐位观察位数53结果第4位000第3位100第2位010第1位111所以5 3 14. 第二个运算符| 按位或|的名字叫作按位或Bitwise OR。它的规则是两个位置上只要有一个是1结果就是1。左边右边左边 | 右边000011101111现在计算5 | 3二进制计算0101 | 0011 ------ 0111而二进制0111转换成十进制4 2 1 7因此5 ∣ 3 75. 最后计算整个表达式原来的表达式是(a b) (a | b)我们已经知道a b 1 a | b 7所以1 7 8最终答案C8本题最重要的知识点两个都是1结果才是1。|两个只要有一个是1结果就是1。位运算是对二进制的每一位分别进行运算。举一反三如果int a 6, b 3; cout (a b) endl; cout (a | b) endl;请同学们先自己计算再用程序验证。第2题数学函数——cmath 中的函数究竟返回什么正确答案D1. 题目内容使用cmath或math.h中的数学库函数下列说法正确的是A.pow(2, 3)的返回值类型为intB.sin(30)的参数30表示30度C.sqrt(4)的返回值类型为intD.log(1)的返回值为0.0且类型为double这道题主要考查我们对 C 数学函数的理解。2. 先认识四个数学函数C 提供了很多数学工具就像我们数学课上的计算器一样。函数数学意义示例pow(a,b)a 的 b 次方pow(2,3)sqrt(x)x 的平方根sqrt(4)sin(x)正弦函数sin(0)log(x)自然对数log(1)使用这些函数时通常需要#include cmath3. 逐个分析选项选项Apow(2,3)返回 int我们先算一下2 ^ 3 8但是pow()函数的返回值类型是double而不是int。例如double x pow(2, 3); cout x;结果为8注意虽然屏幕上显示8但它的返回值类型仍然是double。所以A错误。选项Bsin(30)表示30度这里有一个非常容易出错的知识点C 的三角函数使用的是弧度制不是角度制。我们知道180∘ π 弧度因此30∘ π / 6 (弧度如果想计算30度的正弦值应该写#include iostream #include cmath using namespace std; int main() { double x sin(30.0 * acos(-1.0) / 180.0); cout x endl; return 0; }其中acos(-1.0)可以用来获得圆周率 π。而sin(30)实际上计算的是30弧度的正弦值并不是30度。所以B错误。选项Csqrt(4)返回 int我们知道但是sqrt(4)返回类型依然是double。也就是说虽然计算结果是2但类型不是int。例如double x sqrt(4);所以C错误。选项Dlog(1)返回0.0类型为double我们先回忆一下自然对数因此double x log(1);结果为0返回类型为double。所以D正确。最终答案D七级考试需要记住pow()返回double。sqrt()返回double。sin()、cos()使用弧度制。log()表示自然对数log(1)0。课堂小练习下面四个表达式分别是多少pow(3, 2) sqrt(25) log(1) sin(0)答案分别是9.0 5.0 0.0 0.0它们的返回类型都是double。第3题哈夫曼树——出现次数少的字符为什么编码更长正确答案C31. 题目内容有4个字符出现次数分别为1, 2, 3, 4构造哈夫曼树后出现次数为1的字符的哈夫曼编码长度是多少选项A. 1B. 2C. 3D. 4这道题考查的是哈夫曼树Huffman Tree。2. 先讲一个故事魔法王国的密码传递假设有一个魔法王国国王每天都要向四个村庄发送消息。四个村庄收到消息的次数分别是村庄收到消息次数A村1次B村2次C村3次D村4次国王想设计一种二进制密码每个村庄对应一个编码。编码只能使用0和1。不同村庄的编码不能产生前缀冲突。经常收到消息的村庄最好使用短编码。很少收到消息的村庄可以使用长编码。为什么呢因为经常发送的消息如果每次都使用很长的编码就会浪费很多空间。这就是哈夫曼编码的核心思想出现频率越高的字符通常越靠近树根出现频率越低的字符通常越靠近树叶。3. 哈夫曼树的构造规则请记住一个非常重要的口诀哈夫曼树口诀每次选两个最小的合并成一个新的再放回去重新排序。现在开始构造。原始数据1 2 3 4第一步选出最小的两个数。最小的是1和2。合并1 2 3现在剩下3 3 4注意这里的第一个3是新合并出来的节点第二个3是原来出现次数为3的字符。第二步继续选出最小的两个数。现在有3 3 4选择两个33 3 6剩下4 6第三步继续合并。4610最终得到一棵哈夫曼树。4. 画出哈夫曼树为了更清楚我们把每次合并画成树10 / \ 6 4 / \ 3 3 / \ 1 2现在观察频率为1的字符。从根节点10出发到达字符110 → 6 → 3 → 1一共经过了3条边。因此它的哈夫曼编码长度就是​5. 为什么不是4因为编码长度看的是从根节点到叶子节点经过的边数而不是节点的数量。例如根节点 | 中间节点 | 叶子节点经过2条边编码长度就是2而不是3。最终答案C3本题记忆 哈夫曼树每次合并两个最小权值某个字符的编码长度等于它在哈夫曼树中的深度。第4题排列组合——网格中一共有多少条不同的走法正确答案B351. 题目内容从一个 4×54\times54×5 个点连接成的网格的左上角走到右下角每次只能向右或者向下移动。问不同的路径共有多少条选项A. 20B. 35C. 70D. 1262. 先看懂网格这里有一个非常容易出错的地方题目说的是4×5个点而不是4×5个小方格我们把网格画出来从最左上角到最右下角横向需要走4列之间的间隔也就是向右3次。纵向需要走5行之间的间隔也就是向下4次。所以无论怎么走必须完成3 4 7一共7步。3. 把走路问题变成排列问题假设我们用R 表示向右走一步。D 表示向下走一步。那么一条合法路径就相当于排列下面7个字母R R R D D D D例如R R R D D D D R D R D R D D D D R R R D D这些都是不同的走法。问题变成7个位置中选出3个位置放R剩下4个位置自然放D有多少种选择这就是组合数学中的组合数计算 35所以一共有35条不同路径。4. 也可以使用动态规划理解同学们也可以使用动态规划来解决。设dp[i][j]表示从起点走到第 i 行、第 j 列的不同路径数量。每个位置只能从两个方向到达上面的格子向下走过来。左边的格子向右走过来。因此dp[i][j] dp[i−1][j] dp[i][j−1]边界条件dp[1][1] 1我们得到下面的表格第1列第2列第3列第4列第1行1111第2行1234第3行13610第4行141020第5行151535这里表格是按4列、5行的点排列的。右下角的答案就是35。最终答案B35本题记忆点 网格路径题先数清楚必须向右几次、向下几次再使用组合数或者使用动态规划。第5题二叉搜索树——查找一个数需要多少时间正确答案A1. 题目内容在含有 nnn 个结点的二叉排序树中查找一个元素平均时间复杂度和最坏时间复杂度分别为A. O(log⁡n),O(n)B. O(n),O(log⁡n)C. O(log⁡n),O(log⁡n)D. O(1),O(n)这道题主要考查二叉搜索树Binary Search Tree简称BST和时间复杂度。2. 什么是二叉搜索树先讲一个故事。假设森林里有一棵神奇的数字树每个节点都遵守一个规定左边的数字比自己小。右边的数字比自己大。这就是二叉搜索树的基本规则。例如我们依次插入8 / \ 4 12 / \ / \ 2 6 10 14我们想查找数字10。应该怎么做3. 查找数字10的过程第一步从根节点8开始。因为10 8所以往右边走。第二步来到12。因为10 12所以往左边走。第三步来到10。找到了一共只需要访问3个节点。如果这棵树有15个节点8 / \ 4 12 / \ / \ 2 6 10 14只要树保持比较均衡我们每次都能排除掉大约一半的搜索范围。这就像猜数字游戏老师心里想一个1到100之间的数字你每次都猜中间的数字老师告诉你大了还是小了。每猜一次可能范围缩小一半。因此平均查找时间复杂度可以达到O(log⁡n)4. 最坏情况树变成一条长链但是同学们需要注意二叉搜索树不一定永远长得这么漂亮。如果我们按照下面的顺序插入数字1、2、3、4、5可能形成1 \ 2 \ 3 \ 4 \ 5这时候二叉搜索树就变成了一条链。如果我们要查找数字51 → 2 → 3 → 4 → 5可能需要访问所有节点。假设有 nnn 个节点就可能访问 nnn 个节点。所以最坏时间复杂度是O(n)5. 对比总结情况树的形状查找复杂度平均情况比较均衡O(log⁡n)最坏情况退化成链O(n)最终答案A平均时间复杂度O(log⁡n)最坏时间复杂度O(n第6题贪心算法——相邻石子的合并问题正确答案B191. 题目内容有4堆石子数量分别为1, 2, 3, 4每次可以合并相邻两堆。合并代价为两堆石子数量之和。将所有石子合并成一堆的最小总代价是多少选项A. 17B. 19C. 20D. 23这道题非常有意思它考查的是贪心思想而且有一个容易混淆的地方只能合并相邻的两堆不能随便挑选任意两堆。2. 先理解合并代价我们有第1堆1颗 第2堆2颗 第3堆3颗 第4堆4颗如果合并第一堆和第二堆1 2 3这次的合并代价就是3。合并完成后3 3 4注意原来的两堆已经变成一堆3颗石子。最终我们要把所有石子合并成一堆并且让每次合并代价的总和最小。3. 尝试不同的合并方案我们来当一回石子合并小队长方案一先合并最左边的两堆。初始状态1 2 3 4第一次1 2 3代价为3。剩余3 3 4第二次3 3 6代价为6。剩余6 4第三次6 4 10代价为10。总代价3 6 10 19方案二先合并中间两堆。初始状态1 2 3 4第一次2 3 5代价为5。剩余1 5 4第二次合并相邻的5和45 4 9代价为9。剩余1 9第三次1910代价为10。总代价591024方案三先合并最右边的两堆。初始状态1 2 3 4第一次3 4 7代价为7。剩余1 2 7第二次123代价为3。剩余3 7第三次3710代价为10。总代价7310204. 三种方案比较合并方案第一次第二次第三次总代价方案一361019方案二591024方案三731020方案一得到19。但是仅仅比较这三个方案还不能证明19一定是最小值。我们还需要理解它与哈夫曼树的关系。5. 为什么这道题不能直接套普通哈夫曼算法普通哈夫曼树的规则是每次选取全局最小的两个权值合并。而本题要求只能合并相邻的两堆。这两种限制并不相同对于本题的四堆石子可以先合并1和2。可以先合并2和3。可以先合并3和4。不能直接合并1和4。本题属于带有相邻限制的合并问题。在这组数据中方案一的19确实是最小总代价。最终答案B19本题关键 每次合并必须选择相邻的两堆而且要考虑后续合并造成的总代价不能只看眼前哪一次最便宜。6. 进一步拓展区间DP如果石子数量变多例如4 5 9 2 7 3 8我们就不能仅靠简单地尝试几种方案来解决。可以使用区间动态规划。设sum[i][j]表示第 i 堆到第 j 堆石子的总数量。设dp[i][j]表示将第 i 堆到第 j 堆合并成一堆的最小总代价。状态转移这里的 k 表示最后一次合并时左边和右边的分界位置。这道题是一个区间DP。第7题BFS广度优先搜索——dist究竟代表什么正确答案A1. 题目内容在无权图中使用 BFS 从起点开始遍历并在访问由结点 uuu 扩展的相邻结点 vvv 时记录dist[v] dist[u] 1;起点的dist为0。问最终dist[v]表示什么选项A. 起点到结点v的最少边数B. 结点v的度数C. 从起点到结点v的路径上经过的最大边权D. 包含结点v的连通块大小2. 先回忆什么是图我们把图想象成一个城市交通网络。每个城市是一个顶点。城市之间的道路是边。例如假设我们从A城市出发希望找到其他城市。问题是从A到其他城市最少需要经过多少条道路这就是 BFS 的经典应用。3. BFS为什么使用队列BFS 的英文全称是Breadth First Search中文叫作广度优先搜索。它有一个重要特点先访问距离起点近的节点再访问距离起点远的节点。这就像水滴落在池塘里第一圈水波最先到达附近位置。第二圈水波再向外扩散。第三圈继续向外扩散。所以 BFS 也可以理解为一层一层地搜索。为什么使用队列因为队列遵守先进先出FIFO。先进入队列的节点先被取出来扩展。这样就能保证先处理距离近的节点。4. 重点理解dist数组我们先看一个简单的图A —— B —— D | C —— E从A出发A到自己的距离是0。A到B只需要1条边。A到C只需要1条边。A到D需要2条边。A到E需要2条边。因此节点dist值含义A0自己到自己不需要走边B1最少经过1条边C1最少经过1条边D2最少经过2条边E2最少经过2条边所以dist[v] dist[u] 1;实际上表示我们从距离起点为dist[u]的节点u出发再经过一条边到达节点v。因此v的距离比u多1。5. 为什么一定是最少边数这是本题最重要的地方。因为图是无权图每条边都看成长度1。BFS按照距离从小到大的顺序访问第0层起点 第1层距离起点1条边的节点 第2层距离起点2条边的节点 第3层距离起点3条边的节点当我们第一次访问到某个节点时已经通过最少边数到达了它。所以dist[v]就是起点 到 节点v 的最少边数6. BFS的标准C模板同学们下面这份BFS代码一定要熟悉。#include iostream #include queue #include vector using namespace std; const int N 1005; vectorint g[N]; int dist[N]; int main() { int n, m; cin n m; for (int i 1; i m; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } int start; cin start; for (int i 1; i n; i) { dist[i] -1; } queueint q; dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i (int)g[u].size(); i) { int v g[u][i]; if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } for (int i 1; i n; i) { cout dist[i] ; } return 0; }这里有三个非常重要的操作dist[start] 0;起点距离自己为0。dist[v] dist[u] 1;新节点距离比当前节点多1。q.push(v);把新发现的节点加入队列等待后续扩展。最终答案Adist[v]表示起点到结点v的最少边数也就是无权图中的最短距离。7. 一个特别重要的拓展无权图和有权图这里要提醒同学们BFS求最短路有一个重要前提每条边的权值相同通常都是1。如果道路长度不同A --2-- B A --1-- C --1-- B从A到B直接走距离2。经过C距离112。如果换成A --10-- B A --1-- C --2-- B那么最短距离就变成3。这时候不能简单地使用普通BFS来求加权最短路需要学习Dijkstra等算法。七道题中最值得注意的几个易错点第1题不要把位运算当成逻辑运算。是按位与。是逻辑与。|是按位或。||是逻辑或。这四个符号一定要区分。第2题数学函数的结果和返回类型是两回事。例如sqrt(4)虽然结果是2但是返回类型是double。第3题哈夫曼树不能直接看出现次数判断编码长度。必须先按照规则构造整棵树再计算叶子节点的深度。第4题一定要分清楚点和格子。4×5个点不代表4×5个小方格。第5题普通二叉搜索树不一定平衡。平均复杂度和最坏复杂度不能混淆。第6题相邻合并不能直接套用普通哈夫曼算法。本题有相邻限制扩展到更多堆时需要考虑区间DP。第7题BFS求最短路需要注意无权图这个前提。有权图不能直接照搬普通BFS的最短路方法。