数据结构学习总结（用于考研复试）

自己整理的哈，有错误还请各位大哥指正！

1.什么是O

O表示算法复杂度 ，他需要通过时间复杂度和空间复杂度来描述。

①时间复杂度:一个语句的频度即该语句被执行的次数，程序中所有语句的频度之和记为T(n)，时间复杂度就是T(n)的数量级函数，其中n表示问题的规模。

如常见的冒泡排序最坏时间复杂度为O(n^2)，即初始数据为逆序排序。

②空间复杂度:算法所耗费的存储空间，也是问题规模n的函数。

若算法所需辅助空间为常量，则空间复杂度是O(1)，即原地工作。

2.数据结构三要素

①逻辑结构：指数据之间的逻辑关系，与存储关系无关。主要有集合；线性（一对一）；树形（一对多）；图（多对多）四类。

②存储结构：指数据在计算机中的表示。只要有顺序存储；链式存储；索引存储；散列存储。

③数据的运算：施加在数据上的运算。

3.循环与递归

递归优点：代码简洁清晰

　　缺点：每递归一层,就会在内存生成一个栈保存递归的信息，如果递归深度过深,有栈溢出的问题。循环则不会有这样的问题。

循环优点：结构简单易实现

　　缺点：没有递归简介明了（我认为所有递归都可以写成循环，但比较麻烦）

4.贪心，dp及分治的区别

贪心：只考虑当前最优解，而非全局最优。

dp：考虑到全局最优，求解子问题过程中保留可能的局部最优解，从下往上，一步步对比出全局最优解。

分治：顾名思义分而治之，将问题分为若干规模小且与原问题相似的子问题，递归解决再合并结果。如归并排序。

5.顺序表和链表：

空间上：顺序表需要连续存储空间

内存上：链表有指针额外占用空间

随机存取上：顺序表支持

插入删除上：链表只需修改指针，而顺序表需大量移动元素

6.头指针和头节点：

头指针：不管有没有头节点，永远指向链表第一个节点。作用：具有标识作用。

头节点：带头节点链表中的第一个节点，通常不存储信息。作用：使得第一个节点和其他节点的操作统一；使得空表和非空表操作统一。

7.栈和队列：

栈：先进后出，只能在一端进行插入删除。

队列：先进先出，只能在一端插入另一端删除。

相同点：都可链式顺序存储，都是操作受限的线性表。

8.共享栈：

两个顺序栈共享一个一维数组空间，栈底分别设在两端，插入数据时向中间延申，所以只有空间被占满时才上溢。

9.判断循环队列的空满：

一般牺牲一个单元格：当(队尾+1）%maxnum=队头时则为队满；当队头=队尾时则为队空。

也可以增设一个数据成员表示队内元素个数来判断：个数=0队空，个数=maxnum为队满。

10.kmp算法中next数组的计算：

当第j个字符匹配失败时，记1~j-1的字符串为S；则next【j】=S的模式串最长相等前后缀长度+1，特别地next【1】=0。

改进后的nextvel数组：记next【j】的值为x，当模式串下标为x的字符=当前模式串所指字符，说明就算移动也会匹配失败，所以直接nextvel【j】=nextvel【x】（即参考前面的相同字符的nextval值。

11.线索二叉树：

作用：使得不用遍历的情况下直接找到某结点的前驱或后继。

先序线索化不能直接找前驱，后序线索化不能直接找后继

12.二叉排序树

空树或：左子树结点的值小于他，右子树结点的值大于他，且左右都是二叉排序树。

13.平衡二叉树

空树或：左右子树高度差绝对值不超过1且左右都是平衡二叉树。

14.哈夫曼树

带权路径最小的树，也称为最优二叉树

14.树的存储结构

顺序存储和链式存储（一般二叉树才有可能用顺序存储）

三种方法：双亲表示法（存该结点的父亲），孩子表示法（链式存储该节点的所有孩子），孩子兄弟表示法（左边存孩子右边存兄弟）

15.B树(多路平衡查找树)m阶B树的结点最多m个子树

要求根的子树个数为【2，m】，关键字数=【1，m-1】；非根的子树为【m/2，m】；关键字数=【(m/2)-1，m-1】

查找：同二叉排序树(大了往右，小了往左)，只不过不是两路分支而是多路分支

插入：同二叉排序树一样找到位置插入，然后不满足B树条件时进行不断分裂(中间位置的关键字去父节点中，左边的关键字不动，右边的关键字新生成一个结点)

删除：①直接删：删除后仍满足B树条件。

　　　②兄弟够借：父子互换法，兄弟顶替被删的关键字且父子互换。

　　    ③兄弟不够借：父亲下坠法，父亲下来与兄弟合并。

16.B树和B+树区别：

B+树是应数据库所需而出现的一种B树的变形。

B+树结点的子树个数=关键字个数。而B树子树个数-1=关键字个数。

B+树仅在叶子节点存储索引对应信息（而B树则每个节点中都存放了索引对应信息），所以一个磁盘可以存下更多的索引元素，大大减少磁盘访问操作。这也是为什么大多数数据库选择B+树的主要原因。

B+树叶子节点间有双向的指针，支持顺序查找、范围查找。

17.数据库为什么用B+树不用B树：因为查询操作需要读磁盘，而磁盘是慢速设备，所以当然是读的次数越少越好，也就是树的高度越小越好。而B+树相对B树而言，它的非叶子节点不存储关键字对应信息，只存储关键字，所以规定的磁盘空间就能存放更多关键字，树也越矮，查找速度更快。且叶子节点有双向的指针，支持顺序查找、范围查找。

18.排序

d是关键字数，r时队列数，n是待排序数。

 19.快排复杂度怎么来的：

最好为O（nlogn）。每次需要将数组分成两半进行比较交换，最好情况下每次都分为等长两个部分，则需要logn次划分。最差情况下分为n-1个元素和0个元素，则需n次划分。

不管最好还是最差划分 每趟排序都需要对元素进行n次比较，所以最好为nlogn，最差为n^2。

改进：每次随机选择基准元素可以使得最坏情况几乎不会发生。

20.基数排序：

将所有待比较数统一为同样的长度，不足的前面补零 。然后对每个数的第i位数进行比较，插入相应的队列，最后将队列用指针链接。如此循环直到最高位比较完毕。

时间复杂度为d（n+r），其中d为关键字个数。r为队列数，n为排序数。