数据结构与算法主要概念及对比

数据结构与算法主要概念及对比 一、绪论 1.什么是算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个 *** 作。此外，一个算法还包括
五个重要特性：
1）有穷性
2）确定性
3）可行性
4）输入
5）输出

2.什么是时间复杂度

算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算
的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此算法的时间复杂度记为
				T(n) = O(f(n))。

2.什么是空间复杂度

算法的空间复杂度S(n)定义为该算法耗费的存储空间，它是问题规模n的函数。记为
				S(n) = O(g(n))。
				
ps：算法原地工作是指算法所需的辅助空间为常量，即O(1)。

二、线性表 1.什么是线性表

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一
个元素外，每个元素有且仅有一个直接后继。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

2.顺序表和链表的区别

区别：
1.顺序表是用一段物理地址连续的存储单元，而链表是一种物理存储结构上非连续、非顺序的存储结构。
2.顺序表支持随机访问，链表只能顺序访问。
3.顺序表便于查找，链表便于插入删除。

三、栈和队列 1.什么是栈和队列

栈：栈是只允许在一端进行插入或删除 *** 作的线性表。 *** 作特点是后进先出。
队列：队列也是一种 *** 作受限制的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。 *** 作特点是先进先出。

2.什么是共享栈

共享栈是为了更好地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。

3.什么是顺序队列的“假溢出”及避免方法

假溢出：
当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间。
避免方法：
将顺序队列想想称一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
队头指针进1: Q.front = (Q.front+1) % MaxSize
队尾指针进1: Q.rear = (Q.rear+1) % MaxSize
判空： Q.rear == Q.front
判满： (Q.rear+1) % MaxSize == Q.front

四、串 1.什么是模式匹配

从主串S的第一个字符起，与模式T的第一个字符比较，若相等，则匹配成功，函数值为与模式T中第一个字符相等的字符在主串
S中的序号，否则匹配不成功函数值为0.

2.什么是KMP算法

如果已匹配相等的前缀序列中有某个后缀刚好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i
指针无需回溯。

五、树与二叉树 1.树与二叉树区别

1.二叉树的结点最大度数只能为2而树没有限制。
2.二叉树结点有左右之分，而树没有。
3.树不能为空集，而二叉树可以为空。

2.为什么要引入线索二叉树

引入线索二叉树的目的是加快查找节点前驱或后继的速度。

3.构建平衡二叉树

1）LL平衡旋转

	原因：结点A的左孩子的左子树插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡。
	解决方法：将A的左孩子B右上旋转代替A成为根结点，将A向右下旋转成为B的右子树的根结点，而B的原右子树成为A结点
	的左子树。

2）RR平衡旋转
	
	原因：结点A的右孩子的右子树插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡。
	解决方法：将A的右孩子B左上旋转代替A成为根结点，将A向左下旋转成为B的左子树的根结点，而B的原左子树成为A结点
	的右子树。

3）LR平衡旋转

	原因：结点A的左孩子的右子树插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡。
	解决方法：先把A结点的右孩子B的左子树的根结点C向右旋转提升至B结点的位置，再把C向左上旋转提升至A的位置。

3）RL平衡旋转

	原因：结点A的右孩子的左子树插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡。
	解决方法：先把A结点的左孩子B的右子树的根结点C向左旋转提升至B结点的位置，再把C向右上旋转提升至A的位置。

六、图 1.广度优先搜索算法思想

首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，...，wi，然后依次访问w1，w2，...
，wi的所有未被访问过的邻接顶点，直到图中所有顶点被访问为止。

ps：迪杰斯特拉算法和Prim最小生成树算法也应用了类似思想。

2.深度优先搜索算法思想

首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点
w2......重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问，则从该顶点
开始继续上述搜索过程，直到图中所有顶点均被访问过为止。

七、查找 1.m阶B树和B+树主要差异

1）在B+树中，n个关键字只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
2）在B+树中，每个结点的关键字个数n的范围是「m/2 <=n <= m；在B树中，每个结点的关键字个数n的范围是「m/2 - 1
 <=n <= m - 1
3）在B+树中，叶子结点包含信息，而所有非叶子结点仅起索引作用，非叶子结点中的每个索引项只含有对应子树的最大关键字
和指向该子树的指针，不含有该关键字对应记录的存储地址。
4）在B+树中，叶子结点包含所有关键字，即在非叶子结点中出现的关键字也会出现在叶结点中，而在B树中，叶结点包含的关
键字和其他结点包含的关键字是不重复的。