软考——软件设计师:第四章:数据结构&算法分析与设计考点总结(完整篇)(下)

简介: 软考——软件设计师:第四章:数据结构&算法分析与设计考点总结(完整篇)(下)

文章目录:


6. 

6.1 基本概念

6.2 图的存储

6.2.1 邻接矩阵 

6.2.2 邻接表

6.3 图的遍历

6.4 拓扑排序

6.5 最小生成树

6.5.1 普里姆算法(以顶点为中心,适合稠密图)

6.5.2 克鲁斯卡尔算法(以边为中心,适合稀疏图) 

7.排序与查找

7.1 查找 

7.1.1 顺序查找与二分查找 

7.1.2 散列表 

7.2 排序

7.2.1 直接插入排序

7.2.2 希尔排序

7.2.3 简单选择排序

7.2.4 堆排序

7.2.5 冒泡排序

7.2.6 快速排序

7.2.7 归并排序

7.2.8 基数排序

7.2.9 排序算法的时间复杂度、空间复杂度及稳定性 

8.算法

8.1 算法的特性

8.2 算法的时间复杂度和空间复杂度


6.图


6.1 基本概念

6.2 图的存储


6.2.1 邻接矩阵

6.2.2 邻接表

6.3 图的遍历

6.4 拓扑排序

上图的拓扑排序序列除了这四种,还有:0124635702146357。可见,对于同一张图的拓扑序列是不唯一的!!!


6.5 最小生成树


6.5.1 普里姆算法(以顶点为中心,适合稠密图)

我们首先从顶点A出发,找到与A相连的所有边的最小值,即A→B100,将这条边加进来,此时最小生成树中有AB两个结点;之后,我们再将与AB两个结点相连的所有边中的最小值加进来,可以看到应该是A→E200,此时最小生成树中有ABE三个结点;不断重复上述这样的步骤,直到遍历图中的所有结点,最终得到的就是普里姆算法的最小生成树。

注意:求解最小生成树的过程中,一定不能产生环路!!!例如上图中,当我们将结点FD都加进来之后,下来要寻找与这些结点相连的所有边中的最小值,可以看到F→B300D→C300,但是如果我们选择F→B这条路径,那么就产生了环路:A→F→B→A,这是错误的!!!所以只能选择D→C(图中的12345表示加入这条边的顺序,冒号后面的是对应边的具体值)


6.5.2 克鲁斯卡尔算法(以边为中心,适合稀疏图)

我们纵观图中的所有边,首先选出最小的一条边,也就是A→B100,此时最小生成树中有AB两个结点;之后再从图中找出值最小的边,可以看到有两条A→E200F→D200,加进来这两条边之后,并没有产生环路的现象,所以可以加入,此时最小生成树中有ABEFD这些结点;接下来,继续寻找值最小的边,应该时A→F250,将其加入;最后因为不能产生环路,所以只能添加值最小的边D→C300。至此,已遍历全图的顶点。(图中的1234表示加入这条边的顺序,冒号后面的是对应边的具体值)

7.排序与查找


7.1 查找


7.1.1 顺序查找与二分查找

我们看上面这个例题,使用二分查找关键字17,具体过程如下:👇👇👇

\left \lfloor \left (1+12 \right )/2 \right \rfloor=6,所以定位到数组下标为6的元素的位置,比较得1718,可知关键字在前半部分[15]

\left \lfloor \left ( 1+5 \right )/2 \right \rfloor=3,所以定位到数组下标为3的元素的位置,比较得1710,可知关键字在后半部分[45]

\left \lfloor \left ( 4+5 \right )/2 \right \rfloor=4,所以定位到数组下标为4的元素的位置,比较得1716,可知关键字在后半部分[55]

此时二分查找的区间只剩一个元素,即第五个元素17,比较得17=17,所以查找成功。(一共进行了4次比较)

二分查找在查找成功时,关键字得比较次数最多为:\left \lfloor log2n \right \rfloor+1。时间复杂度为O\log 2n)。


7.1.2 散列表


7.2 排序

7.2.1 直接插入排序

7.2.2 希尔排序

7.2.3 简单选择排序

7.2.4 堆排序


7.2.5 冒泡排序


7.2.6 快速排序


7.2.7 归并排序

7.2.8 基数排序

7.2.9 排序算法的时间复杂度、空间复杂度及稳定性

8.算法


8.1 算法的特性

8.2 算法的时间复杂度和空间复杂度

相关文章
|
5月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
188 4
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
49 1
|
3月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
87 6
|
2月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月,中央网信办发布第十二批深度合成算法备案信息,全国389款产品通过备案,服务提供者占比超七成。截至7月14日,全国累计备案达3834款,覆盖文本、图像、音视频等多模态场景,广泛应用于生活服务、医疗、金融等领域。广东以135款居首,数字人、AI客服等C端应用主导,民营企业成主力,国企聚焦公共服务。随着AI政策推动,备案已成为AI产品合规上线关键环节。
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
56 0
|
3月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
176 3
|
5月前
|
存储 监控 算法
员工行为监控软件中的 Go 语言哈希表算法:理论、实现与分析
当代企业管理体系中,员工行为监控软件已逐步成为维护企业信息安全、提升工作效能的关键工具。这类软件能够实时记录员工操作行为,为企业管理者提供数据驱动的决策依据。其核心支撑技术在于数据结构与算法的精妙运用。本文聚焦于 Go 语言中的哈希表算法,深入探究其在员工行为监控软件中的应用逻辑与实现机制。
137 14
|
6月前
|
自然语言处理 算法 安全
境内深度合成服务算法备案通过名单分析报告
本报告基于《境内深度合成服务算法备案通过名单》,分析了2023年6月至2025年3月公布的10批备案数据,涵盖属地分布、行业应用及产品形式等多个维度。报告显示,深度合成算法主要集中于经济发达地区,如北京、广东、上海等地,涉及教育、医疗、金融、娱乐等多行业。未来趋势显示技术将向多模态融合、行业定制化和安全合规方向发展。建议企业加强技术研发、拓展应用场景、关注政策动态,以在深度合成领域抢占先机。此分析旨在为企业提供参考,助力把握技术发展机遇。
境内深度合成服务算法备案通过名单分析报告
|
6月前
|
供应链 算法 搜索推荐
从公布的前十一批其他算法备案通过名单分析
2025年3月12日,国家网信办发布算法备案信息,深度合成算法通过395款,其他算法45款。前10次备案中,深度合成算法累计3234款,其他类别647款。个性化推送类占比49%,涵盖电商、资讯、视频推荐;检索过滤类占31.53%,用于搜索优化和内容安全;调度决策类占9.12%,集中在物流配送等;排序精选类占8.81%,生成合成类占1.55%。应用领域包括电商、社交媒体、物流、金融、医疗等,互联网科技企业主导,技术向垂直行业渗透,内容安全和多模态技术成新增长点。未来大模型检索和多模态生成或成重点。
从公布的前十一批其他算法备案通过名单分析
|
6月前
|
人工智能 自然语言处理 供应链
从第十批算法备案通过名单中分析算法的属地占比、行业及应用情况
2025年3月12日,国家网信办公布第十批深度合成算法通过名单,共395款。主要分布在广东、北京、上海、浙江等地,占比超80%,涵盖智能对话、图像生成、文本生成等多行业。典型应用包括医疗、教育、金融等领域,如觅健医疗内容生成算法、匠邦AI智能生成合成算法等。服务角色以面向用户为主,技术趋势为多模态融合与垂直领域专业化。

热门文章

最新文章