二叉查找树 (Binary Search Tree) 概念 二叉查找树又称二叉搜索树，二叉排序树，特点如下: 左子树上所有结点值均小于根结点 右子树上所有结点值均大于根结点 结点的左右子树本身又是一颗二叉查找树 二叉查找树中序遍历得到结果是递增排序的结点序列。 BST 的操作代价分析： 查找代价： 任何一个数据的查找过程都需要从根…

R-B Tree，全称Red-Black Tree，又称为红黑树，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树的特性：

B树中所有结点中孩子结点个数的最大值成为B树的阶，通常用m表示，从查找效率考虑，一般要求m>=3。一棵m阶B树或者是一棵空树，或者是满足以下条件的m叉树。 1）每个结点最多有m个分支（子树）；而最少分支数要看是否为根结点，如果是根结点且不是叶子结点，则至少要有两个分支，非根非叶结点至少有ceil(m/2)个分支，这…

线性表 线性表的基本概念 线性表的定义 线性表是具有相同数据类型的n(n>=0)个元素的有限序列。 线性表的基本操作 什么时候要传入参数的引用“&”？ 一种是值类型，使用时会直接复制原值，修改参数不会影响原值 一种是引用类型，使用时操作的是原值，修改时直接修改原值！（C语言不支持这种引用类型！） 为什么要实…

算法 基本概念 什么是算法？ 程序=数据结构+算法 算法的特性 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。注：算法必须是有穷的，二程序可以是无穷的。 确定性：算法每一条指令必须有确切的含义，对于相同的输入只能得出相同的输出 可行性：算法描述的操作都可以通过已经实现的基本运算…

绪论第二节——算法 基本概念 什么是算法？ 程序=数据结构+算法 算法的特性 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。注：算法必须是有穷的，二程序可以是无穷的。 确定性：算法每一条指令必须有确切的含义，对于相同的输入只能得出相同的输出 可行性：算法描述的操作都可以通过已经实…

1.线性表[ 矩阵|数组|字符串|堆栈|队列 ] {代码…} 2.树 {代码…} 3.图 {代码…} 4.查找 {代码…} 5.排序 {代码…} 2).外排序(内存无法容纳,需要借助外部存储设备) {代码…} 内容出自<<数据结构>>仅供学习/复习参考

下面哪种排序方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（插入排序    ） 对序列15, 9, 7, 8, 20, -1, 4进行排序，若经一趟排序后的排列为9, 15, 7, 8, 20, -1, 4，则采用的是（   C  ）排序。 A.选择 B.堆 C.直接插入 D.冒泡 选择排序是每次选择未排序子列中最…

首先明确何为强连通图：对一个有向图，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。判定方法：任取有向图G的某结点S，从S开始进行深度优先搜索，若可以遍历G的所有结点；再将G的所有边反向，再次从S开始进行深度优先搜索，如果再次能够遍历G的所有结点，则G是强连通图，两次搜索有一次无法遍历所…

深度优先遍历：类似于树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点。广度优先遍历：类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然…