软件设计师--数据结构考点细节总结

                                   

 

 

👨‍💻个人主页：@元宇宙-秩沅

hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅!

本文由 秩沅 原创

收录于专栏  软件设计师高频考点合集

视频2022软件设计师-提炼高频考点-个人学习过程的总结，仅供参考！_哔哩哔哩_bilibili

目录

1，栈

2,二叉树

3，HUFFMAN

特点：

4，文件压缩比

5，拓扑排序 -- 有向无环图

6，查找

7,排序算法

---

1，栈

栈空间[1,....n] ,栈底指针，栈满之后指针为 top[ n+1]

2,二叉树

（1）总节点数 2^n -1

（2）叶子节点数（度为0的节点数） ： = 度为2的节点+1

（3）第n层节点的总数： 2^(n-1)

3，HUFFMAN

（1）小的在左边，大的在右边

（2）左0右1

（3）编码是从上往下数，权值越大的离我们根节点越近

特点：

（1）节点数是奇数

（2）不存在子树为1的节点

（3）huffman不一定是满二叉树或完全二叉树

4，文件压缩比

首先看文档中包含几个字符，如果是5个 ， 2^3 > 5 所以 ，我们每个字符它所占 3个位

5，拓扑排序 -- 有向无环图

①先看入度为0的节点，输出

②而后删除该节点的出度，之后 再看入度为0的节点

6，查找

（1）顺序查找 -----最坏时间复杂度 :n

（2）二分查找 ----最坏时间复杂度 ： log 2 n

7,排序算法

稳定的：直接插入排序 ，冒泡排序，归并排序

一，插入排序 ----适用一个基本有序的序列

（1）直接插入排序：打牌，遍历每一张牌，找到合适的位置插入进去（合适的位置：比左大，比右小）

（2）希尔排序(增量选取)：插入排序的升级版，特点是，把牌分成几份然后进行插入

二，选择排序

（1）简单选择排序：每一轮选择出最大的和最小的，分别排在上一轮选出的大小王后面

（2）堆排序：类似于二叉树，每一轮输出最大的或者最小的，输出完之之就出局

三，交换排序

（1）冒泡排序：每个数不停的轮完一次和右边的数的交换

（2）快速排序：选择基准数（通常用最右边的），两边来回比较，直到分组只剩下一个数时

四，归并排序

（1）不停的二路拆开，到单独个体之后排序，然后合并

1.不稳定： 快，选，堆，希

2.特别的： 快（最坏n^2）， 选(最坏最好n^2)， 希(平均n^1.3)

3.易混淆的排序：（平均复杂度最小的的：“快堆并”，最坏情况下最小的：“堆并"）

你们的点赞👍 收藏⭐ 留言📝 关注✅是我持续创作，输出优质内容的最大动力！