一、图论计算公式必考1. 无向图边数最大值n(n−1)/2度数之和 2× 边数连通图最少边数n−12. 有向图边数最大值n(n−1)入度总和 出度总和 总边数3. 二叉树万能公式结点总数nn0n1n2永久定理n0n21叶子结点 度 2 结点 1满二叉树高度h 结点总数2h−1 叶子数2h−1完全二叉树 高度⌊log2n⌋1 度 1 结点只有 0 或 1 个4. MQ二叉树、树转森林树的边数 结点数 − 1森林边数 总节点数 − 树的棵数✅最容易记混别减 1二、排序时间复杂度死记表格排序最好平均最坏稳定性冒泡O(n)O(n2)O(n2)稳定直接插入O(n)O(n2)O(n2)稳定简单选择O(n2)O(n2)O(n2)不稳定希尔O(n)O(n1.3)O(n2)不稳定快速O(nlogn)O(nlogn)O(n2)不稳定归并O(nlogn)O(nlogn)O(nlogn)稳定堆排序O(nlogn)O(nlogn)O(nlogn)不稳定三、磁盘计算高频必考磁盘总容量 柱面数 × 磁头数 × 扇区数 × 每扇区字节数存取总时间 寻道时间 旋转延迟 传输时间旋转延迟 旋转周期 ÷ 2数据传输时间 (扇区数 / 总扇区) × 旋转周期流水线吞吐 / 工厂模式总时间 加工时间 流转时间流水线公式第一条完整时间 (n-1)× 流水线周期四、地址存储计算存储单元个数 结束地址 − 起始地址 1字节转 KB÷10241KB1024B 1MB1024KB五、像素 / 图像公式图像容量 分辨率 × 颜色深度 ÷ 8 单位字节颜色深度n位 → 颜色总数 2n六、可靠性计算公式1. 串联系统总可靠度总 总失效率总2. 并联系统总可靠度总七、CRC 校验 海明码CRC 循环冗余生成多项式r位 → 校验位占r位原始数据后补r个 0模 2 除法求余数余数拼接在原数据后即为 CRC 编码海明码校验位个数k满足2k≥nk1n为数据位作用可纠错、可检错奇偶校验仅检错无法纠错八、软件测试四大覆盖强度从小到大语句覆盖最弱走完所有语句即可判定覆盖分支覆盖所有判断真假分支各走 1 次条件覆盖每个判断内的小条件均取真假各 1 次路径覆盖最强走完所有执行路径强度排序语句判定条件路径九、UML 关系必考组合同生共死整体消失部分随之消失店铺→商品聚合整体消失部分独立存在购物车→商品泛化继承关系子类→父类实现类→接口关联普通业务联系强弱组合聚合关联十、分布式数据库三大透明分片透明最高级别用户不知数据分片、不知存储位置位置透明知晓数据分片不知分片存储位置逻辑透明局部映像透明最低级别知晓分片 知晓存储位置十一、算法分类考场秒选贪心哈夫曼编码、Dijkstra、Prim、Kruskal、活动选择、部分背包分治快排、归并排序、二分查找动态规划 DP01 背包、Floyd、最长公共子序列回溯八皇后、迷宫、DFS分支限界BFS、旅行商问题十二、耦合度从低到高无直接耦合数据耦合标记耦合控制耦合外部耦合内容耦合十三、数据独立性物理独立性修改存储结构应用程序无需改动逻辑独立性修改表逻辑结构应用程序无需改动十四、浮点数核心口诀总长固定阶码大→范围大、精度低尾数大→精度高、范围小十五、排序稳定性速记稳定冒泡、插入、归并、基数 不稳定简单选择、希尔、快排、堆排序原码、反码、补码 最值全套公式直接背约定机器字长n 位含 1 位符号位一、定点整数最常考1. 原码最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-(2^{n-1} - 1)}\)2. 反码和原码数值范围一模一样最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-(2^{n-1} - 1)}\)3. 补码【重中之重】最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-2^{n-1}}\) 核心考点补码负数范围多一个原码反码有正负 0补码只有一个 0二、举例8 位字长 n8考场直接套用8 位补码 最大正\(\boldsymbol{127}\) 最小负\(\boldsymbol{-128}\)8 位原码 / 反码 最大正\(\boldsymbol{127}\) 最小负\(\boldsymbol{-127}\)三、定点小数顺带记偶尔考n 位符号位 1 位补码小数最大正数\(\boldsymbol{1 - 2^{-(n-1)}}\)最小负数\(\boldsymbol{-1}\)四、移码只记一句话移码 补码符号位取反移码全 0 最小、全 1 最大常用于浮点数阶码五、海明码必考公式设数据位 n 位校验位 k 位 \(\boldsymbol{2^k \ge n k 1}\) 作用纠错 检错六、CRC 码生成多项式阶数 校验位位数 r原始数据后面补 r 个 0再做模 2 除法七、进制最值速记口诀原反码正负对称正负最大值数值一样补码负数多一格下限更小整数补码最小负数直接记 \(\boldsymbol{-2^{位数-1}}\)正数原、反、补码最大值全部一样八、极简考场一句话总结正数三码最大值都相同负数补码范围最大能取到更小数值8 位熟记补码 -128127原反码 -127127人人皆为创造者共创方能共成长每个人都是使用者也是创造者是数字世界的消费者更是价值的生产者与分享者。在智能时代的浪潮里单打独斗的发展模式早已落幕唯有开放连接、创意共创、利益共享才能让个体价值汇聚成生态合力让技术与创意双向奔赴实现平台与伙伴的快速成长、共赢致远。原创永久分成共赴星辰大海原创创意共创、永久收益分成是东方仙盟始终坚守的核心理念。我们坚信每一份原创智慧都值得被尊重与回馈以永久分成锚定共创初心让创意者长期享有价值红利携手万千伙伴向着科技星辰大海笃定前行拥抱硅基 生命与数字智能交融的未来共筑跨越时代的数字文明共同体。东方仙盟拥抱知识开源共筑数字新生态在全球化与数字化浪潮中东方仙盟始终秉持开放协作、知识共享的理念积极拥抱开源技术与开放标准。我们相信唯有打破技术壁垒、汇聚全球智慧才能真正推动行业的可持续发展。开源赋能中小商户通过将前端异常检测、跨系统数据互联等核心能力开源化东方仙盟为全球中小商户提供了低成本、高可靠的技术解决方案让更多商家能够平等享受数字转型的红利。共建行业标准我们积极参与国际技术社区与全球开发者、合作伙伴共同制定开放协议 与技术规范推动跨境零售、文旅、餐饮等多业态的系统互联互通构建更加公平、高效的数字生态。知识普惠共促发展通过开源社区 、技术文档与培训体系东方仙盟致力于将前沿技术转化为可落地的行业实践赋能全球合作伙伴共同培育创新人才推动数字经济 的普惠式增长阿雪技术观在科技发展浪潮中我们不妨积极投身技术共享。不满足于做受益者更要主动担当贡献者 。无论是分享代码、撰写技术博客还是参与开源项目 维护改进每一个微小举动都可能蕴含推动技术进步的巨大能量。东方仙盟是汇聚力量的天地我们携手在此探索硅基 生命为科技进步添砖加瓦。Hey folks, in this wild tech - driven world, why not dive headfirst into the whole tech - sharing scene? Dont just be the one reaping all the benefits; step up and be a contributor too. Whether youre tossing out your code snippets , hammering out some tech blogs, or getting your hands dirty with maintaining and sprucing up open - source projects, every little thing you do might just end up being a massive force that pushes tech forward. And guess what? The Eastern FairyAlliance is this awesome place where we all come together. Were gonna team up and explore the whole silicon - based life thing, and in the process, well be fueling the growth of technology
2026年软考算法知识点—计算机等级考试—软件设计师考前备忘录—东方仙盟
一、图论计算公式必考1. 无向图边数最大值n(n−1)/2度数之和 2× 边数连通图最少边数n−12. 有向图边数最大值n(n−1)入度总和 出度总和 总边数3. 二叉树万能公式结点总数nn0n1n2永久定理n0n21叶子结点 度 2 结点 1满二叉树高度h 结点总数2h−1 叶子数2h−1完全二叉树 高度⌊log2n⌋1 度 1 结点只有 0 或 1 个4. MQ二叉树、树转森林树的边数 结点数 − 1森林边数 总节点数 − 树的棵数✅最容易记混别减 1二、排序时间复杂度死记表格排序最好平均最坏稳定性冒泡O(n)O(n2)O(n2)稳定直接插入O(n)O(n2)O(n2)稳定简单选择O(n2)O(n2)O(n2)不稳定希尔O(n)O(n1.3)O(n2)不稳定快速O(nlogn)O(nlogn)O(n2)不稳定归并O(nlogn)O(nlogn)O(nlogn)稳定堆排序O(nlogn)O(nlogn)O(nlogn)不稳定三、磁盘计算高频必考磁盘总容量 柱面数 × 磁头数 × 扇区数 × 每扇区字节数存取总时间 寻道时间 旋转延迟 传输时间旋转延迟 旋转周期 ÷ 2数据传输时间 (扇区数 / 总扇区) × 旋转周期流水线吞吐 / 工厂模式总时间 加工时间 流转时间流水线公式第一条完整时间 (n-1)× 流水线周期四、地址存储计算存储单元个数 结束地址 − 起始地址 1字节转 KB÷10241KB1024B 1MB1024KB五、像素 / 图像公式图像容量 分辨率 × 颜色深度 ÷ 8 单位字节颜色深度n位 → 颜色总数 2n六、可靠性计算公式1. 串联系统总可靠度总 总失效率总2. 并联系统总可靠度总七、CRC 校验 海明码CRC 循环冗余生成多项式r位 → 校验位占r位原始数据后补r个 0模 2 除法求余数余数拼接在原数据后即为 CRC 编码海明码校验位个数k满足2k≥nk1n为数据位作用可纠错、可检错奇偶校验仅检错无法纠错八、软件测试四大覆盖强度从小到大语句覆盖最弱走完所有语句即可判定覆盖分支覆盖所有判断真假分支各走 1 次条件覆盖每个判断内的小条件均取真假各 1 次路径覆盖最强走完所有执行路径强度排序语句判定条件路径九、UML 关系必考组合同生共死整体消失部分随之消失店铺→商品聚合整体消失部分独立存在购物车→商品泛化继承关系子类→父类实现类→接口关联普通业务联系强弱组合聚合关联十、分布式数据库三大透明分片透明最高级别用户不知数据分片、不知存储位置位置透明知晓数据分片不知分片存储位置逻辑透明局部映像透明最低级别知晓分片 知晓存储位置十一、算法分类考场秒选贪心哈夫曼编码、Dijkstra、Prim、Kruskal、活动选择、部分背包分治快排、归并排序、二分查找动态规划 DP01 背包、Floyd、最长公共子序列回溯八皇后、迷宫、DFS分支限界BFS、旅行商问题十二、耦合度从低到高无直接耦合数据耦合标记耦合控制耦合外部耦合内容耦合十三、数据独立性物理独立性修改存储结构应用程序无需改动逻辑独立性修改表逻辑结构应用程序无需改动十四、浮点数核心口诀总长固定阶码大→范围大、精度低尾数大→精度高、范围小十五、排序稳定性速记稳定冒泡、插入、归并、基数 不稳定简单选择、希尔、快排、堆排序原码、反码、补码 最值全套公式直接背约定机器字长n 位含 1 位符号位一、定点整数最常考1. 原码最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-(2^{n-1} - 1)}\)2. 反码和原码数值范围一模一样最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-(2^{n-1} - 1)}\)3. 补码【重中之重】最大正数\(\boldsymbol{2^{n-1} - 1}\)最小负数\(\boldsymbol{-2^{n-1}}\) 核心考点补码负数范围多一个原码反码有正负 0补码只有一个 0二、举例8 位字长 n8考场直接套用8 位补码 最大正\(\boldsymbol{127}\) 最小负\(\boldsymbol{-128}\)8 位原码 / 反码 最大正\(\boldsymbol{127}\) 最小负\(\boldsymbol{-127}\)三、定点小数顺带记偶尔考n 位符号位 1 位补码小数最大正数\(\boldsymbol{1 - 2^{-(n-1)}}\)最小负数\(\boldsymbol{-1}\)四、移码只记一句话移码 补码符号位取反移码全 0 最小、全 1 最大常用于浮点数阶码五、海明码必考公式设数据位 n 位校验位 k 位 \(\boldsymbol{2^k \ge n k 1}\) 作用纠错 检错六、CRC 码生成多项式阶数 校验位位数 r原始数据后面补 r 个 0再做模 2 除法七、进制最值速记口诀原反码正负对称正负最大值数值一样补码负数多一格下限更小整数补码最小负数直接记 \(\boldsymbol{-2^{位数-1}}\)正数原、反、补码最大值全部一样八、极简考场一句话总结正数三码最大值都相同负数补码范围最大能取到更小数值8 位熟记补码 -128127原反码 -127127人人皆为创造者共创方能共成长每个人都是使用者也是创造者是数字世界的消费者更是价值的生产者与分享者。在智能时代的浪潮里单打独斗的发展模式早已落幕唯有开放连接、创意共创、利益共享才能让个体价值汇聚成生态合力让技术与创意双向奔赴实现平台与伙伴的快速成长、共赢致远。原创永久分成共赴星辰大海原创创意共创、永久收益分成是东方仙盟始终坚守的核心理念。我们坚信每一份原创智慧都值得被尊重与回馈以永久分成锚定共创初心让创意者长期享有价值红利携手万千伙伴向着科技星辰大海笃定前行拥抱硅基 生命与数字智能交融的未来共筑跨越时代的数字文明共同体。东方仙盟拥抱知识开源共筑数字新生态在全球化与数字化浪潮中东方仙盟始终秉持开放协作、知识共享的理念积极拥抱开源技术与开放标准。我们相信唯有打破技术壁垒、汇聚全球智慧才能真正推动行业的可持续发展。开源赋能中小商户通过将前端异常检测、跨系统数据互联等核心能力开源化东方仙盟为全球中小商户提供了低成本、高可靠的技术解决方案让更多商家能够平等享受数字转型的红利。共建行业标准我们积极参与国际技术社区与全球开发者、合作伙伴共同制定开放协议 与技术规范推动跨境零售、文旅、餐饮等多业态的系统互联互通构建更加公平、高效的数字生态。知识普惠共促发展通过开源社区 、技术文档与培训体系东方仙盟致力于将前沿技术转化为可落地的行业实践赋能全球合作伙伴共同培育创新人才推动数字经济 的普惠式增长阿雪技术观在科技发展浪潮中我们不妨积极投身技术共享。不满足于做受益者更要主动担当贡献者 。无论是分享代码、撰写技术博客还是参与开源项目 维护改进每一个微小举动都可能蕴含推动技术进步的巨大能量。东方仙盟是汇聚力量的天地我们携手在此探索硅基 生命为科技进步添砖加瓦。Hey folks, in this wild tech - driven world, why not dive headfirst into the whole tech - sharing scene? Dont just be the one reaping all the benefits; step up and be a contributor too. Whether youre tossing out your code snippets , hammering out some tech blogs, or getting your hands dirty with maintaining and sprucing up open - source projects, every little thing you do might just end up being a massive force that pushes tech forward. And guess what? The Eastern FairyAlliance is this awesome place where we all come together. Were gonna team up and explore the whole silicon - based life thing, and in the process, well be fueling the growth of technology
