第8题 Floyd还能继续更新吗答案B1、题目已经用 Dijkstra 求出了所有点对最短路。现在又把这个 dist 数组拿去执行完整 Floyd。问执行结束以后dist 会怎样A.发生变化B.不会变化C.可能变大D.死循环2、先理解 Floyd 在干什么1Floyd 每次都会尝试i \ \ k \ \ j2看看i→k→j是不是比i→j更短。3代码就是dist[i][j]min( dist[i][j], dist[i][k]dist[k][j] );3、但是现在呢题目已经说所有最短路已经正确算出来了。说明现在dist[i][j]已经就是最优答案。再去更新min(最短路,另外一条路)永远还是最短路。4、因此不会发生任何变化。答案B5、一个生活例子假如你已经知道上海→北京最快高铁4小时。现在再去查上海→南京→北京上海→济南→北京上海→武汉→北京都不会比4小时更快。所以答案保持不变。第9题 最短路算法判断答案B1、逐个选项分析。1A选项Dijkstra能处理负边错误。例如A ----5---- B A ----2---- C C ----(-4)--- B真正最短A→C→B-2但是Dijkstra会先确定B距离5。于是出错。所有边权 ≥ 0 时Dijkstra 的贪心选择是正确的。有负权边失效原因负权边允许在“已处理”的节点之后通过一条负权边产生更短的距离使之前被选中的节点不再是全局最小而算法不会再回头更新它。所以A错。2B选项Floyd可以处理负边。不能有负环。正确。答案就是B。3C选项无向图不能做最短路当然错误。DijkstraBFSSPFABellman全部可以。4D选项Dijkstra每次选择距离最远完全相反。每次都选择最近因此错误。2、八级口诀负边 不能Dijkstra 可以Floyd 可以Bellman 可以SPFA第10题 排列组合答案C1、题目6个人排队。甲乙必须相邻。丙不能站第一。排法有几种2、第一步甲乙绑一起。变成(甲乙) 丙 丁 戊 己共5个单位。排列5!但是甲乙还能交换。甲乙 乙甲所以5!×22403、第二步减去非法丙站第一。第一固定丙剩下甲乙 丁 戊 己4个单位。4!×2484、最后240-48 192答案C5、八级技巧看到必须相邻第一反应捆绑法看到不能……第一反应总数减非法第11题 Floyd代码填空答案C1、原代码if(________) dist[i][j]...2、真正更新必须满足下列条件。第一i→k 存在第二k→j 存在否则INF5可能溢出。第三确实更短。即dist[i][k]!INF dist[k][j]!INF dist[i][k]dist[k][j] dist[i][j]答案C。3、为什么不能只比较大小例如INFINF可能超过int。甚至变负数。程序直接WA。这是很多同学第一次写Floyd最容易犯的错误。第12题 五位偶数答案B1、数字0 1 2 3 4全部使用。不能重复。组成五位偶数。2、偶数最后一位只能0 2 4分类讨论。1最后一位0前四位1 2 3 4排列4! 242最后一位2剩0 1 3 4第一位不能0。第一位3种剩3位3!所以3×6183最后一位4同理18总数241818 60答案B。3、技巧遇到首位不能0 末位有限制一般都是分类讨论。第13题 Prim填空答案A1、Prim思想不断更新每个点连接生成树的最小边。2、更新条件必须①有边graph[u][v]②没访问!inMST[v]③更小graph[u][v]minEdge[v]三个条件缺一不可。因此答案A。3、Prim口诀更新边时有边 没选 更优第14题 判断三点共线答案C1、三个点A B C如何判断2、很多人想到比较斜率。例如k1k2但是存在问题。假如x2x1斜率不存在。程序炸了。3、正确方法叉积。AB×AC如果0说明共线。4、但是浮点数不能直接0应该fabs(叉积) 1e-85、答案C。6、例如理论0计算机可能得到0.0000000003所以不能0必须fabs(...) 1e-87、八级考点以后所有几何题判断相等不要而是fabs(a-b)eps第15题 sizeof与指针答案A1、代码int a[4]; int (*p)[4]a; int *qa;第一空sizeof(a)数组4个int。4×4 16第二空sizeof(p)指针。64位。都是8第三空sizeof(p1)注意不是内容。还是指针。仍然8第四空sizeof(q1)也是指针。还是8第五空(p1)-p这里最容易错。p类型int (*)[4]每次跳过整个数组。跨度4个int但是指针相减返回的是跨过了几个数组对象。因此1不是16。第六空(q1)-q普通int指针。前进一步。也是1所以输出16 8 8 8 1 1答案A。第一部分815题总结题号知识点必须掌握8Floyd算法最短路已正确时再执行 Floyd 不会改变结果9最短路算法Dijkstra 不支持负边Floyd 可处理负边但不能有负环10排列组合相邻问题用“捆绑法”限制条件常用“总数减非法”11Floyd代码更新前必须判断两段路径都不是INF再比较是否更短12排列计数首位不能为 0、末位有限制时优先分类讨论13Prim算法更新条件有边 未加入 MST 更优14计算几何三点共线用叉积判断浮点数比较使用fabs(...) 1e-815C底层理解sizeof、数组指针int (*)[4]与普通指针int*的区别本套选择题考情分析这套八级选择题覆盖了五大高频模块组合数学第1、4、10、12题图论算法第6、7、8、9、11、13题二叉搜索树第5题计算几何基础第14题C语言底层与指针第15题
