软件设计师考点5 数据结构与算法基础

数组:

软件设计师考点5  数据结构与算法基础

稀疏矩阵:一个矩阵中记录的元素大量元素为零。考点:计算稀疏矩阵中某个元素的下标。

软件设计师考点5  数据结构与算法基础

数据结构:

数据逻辑结构:

①线性数据机构

②非线性数据结构:树,图

线性表:线性结构的表现方式

①顺序表:连续的空间

②链表:单链表,双向链表,循环链表

顺序存储和链式存储对比:

软件设计师考点5  数据结构与算法基础

队列:先进先出。

栈:先进后出。

循环队列:对空条件:head = tail,队满条件:(tail +1)%size = head

软件设计师考点5  数据结构与算法基础

软件设计师考点5  数据结构与算法基础

广义表:

软件设计师考点5  数据结构与算法基础

例二:head(head(tail(LS1)))

表头是最外层的第一个元素,表尾是除了表头的其他所有元素。

树与二叉树:

节点的度:一个节点拥有的孩子节点数。

树的度:树中所有节点度数最高的节点的度。

叶子节点:没有孩子节点。

分支节点:有相应分支。

内部节点:既非叶子节点也非根节点。

完全二叉树:除了最下面的一层其他的都是满的,最下面一层左边排满。

软件设计师考点5  数据结构与算法基础

二叉树遍历:

①层次遍历:从上到下从左到右遍历

②前序遍历:先访问根节点,在访问左子树和右子树节点。

③中序遍历:先访问左子树,在访问根节点再访问右子树节点。

④后序遍历:先访问左子树,右子树再访问根节点。

前中后序遍历的区别就是什么时候访问根节点。

反向构造二叉树:知道二叉树的遍历序列,推导出二叉树的结构。

数转二叉树:

软件设计师考点5  数据结构与算法基础

查找二叉树:所有的左子树小于根节点,右子树大于根节点的二叉树。

软件设计师考点5  数据结构与算法基础

最优二叉树:哈夫曼树

软件设计师考点5  数据结构与算法基础

权:叶子节点代表的字符出现的频度。

带权路径长度:权值*路径

线索二叉树:

平衡二叉树:任意节点的左右节点的平衡度相差不超出1.

图:

软件设计师考点5  数据结构与算法基础

邻接矩阵

邻接表:

图的遍历:

软件设计师考点5  数据结构与算法基础

拓扑序列

软件设计师考点5  数据结构与算法基础

图的最小生成树:一个图中能生成的最小边的树。一个有N个节点的树,最多有N-1个边。

算法:普卢姆算法,克鲁斯卡尔算法。

算法的特性:

软件设计师考点5  数据结构与算法基础

算法复杂度:

时间复杂度:算法执行过程所需要的时间。

空间复杂度:执行过程中临时占用存储空间大小的度量。

软件设计师考点5  数据结构与算法基础

查找:顺序查找,二分查找。

软件设计师考点5  数据结构与算法基础

顺序查找法时间复杂度为O(n)。二分查找法时间复杂度为:O(log2n)

散列表查找:

软件设计师考点5  数据结构与算法基础

处理机制:线性探测法,伪随机数法

排序:稳定排序和不稳定排序。稳定排序:相同数值经过排序后顺序不变。

排序方法:插入类排序,交换类排序,选择类排序,归并排序,基数排序。

直接插入排序:

软件设计师考点5  数据结构与算法基础

软件设计师考点5  数据结构与算法基础

直接选择排序:

软件设计师考点5  数据结构与算法基础

软件设计师考点5  数据结构与算法基础

软件设计师考点5 数据结构与算法基础

上一篇:python多进程,多线程实例


下一篇:python装饰器理解