分块查找，也叫索引查找，是将表分成若干块，分块的原则是数据元素的关键字在块与块之间是有序的，而块内元素的关键字是无序的。其可以适应动态变化的要求。关于题目所说的适应动态变化的要求，这里的动态变化应该是说频繁的插入删除元素；因为分块查找的特点是“块间有序，块内无序”，因此适合做频繁的插入删除

相关概念 排序方法的稳定性 排序方法的分类 根据数据对象的存储位置分类：内排序和外排序 2.根据排序原则分类3.根据时间复杂度分类 排序过程的基本操作 由排序的基本操作，引入排序的时间开销 待排序序列的存储方式 以顺序表为待排记录序列的存储结构的几种排序方式 顺序表数据类型的定义 直接插入排序：插入排序的简单...

下面哪种排序方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（插入排序    ） 对序列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入队，然...

一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（  条件不足，无法确定   ） 必须是完全二叉树才能确定，如下图：当为完全二叉树时，为2i+1 下面几个符号串编码集合中，不是前缀编码的是（    B ）。 A. ...

哈夫曼树 在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。 上面的二叉树当中，从根结点A到叶子结点H的路径，就是A，B，D，H。 在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。 仍然用刚才的二叉树举例子，从根结点A到叶子结点H，共经...

a b c a a b b c a b c a a b d a b maxl 0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2 next 0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 nextval 0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

若串 S=’software’,其子串的数目是（ 36）。 1+2+...+8=8*9/2=36，但是值得注意的是，software没有重复字符，若有重复字符，要注意去除重复字符的情况 下面说法不正确的是(1) 广义表的表头总是一个广义表 广义表的表尾总是一个广义表 广义表难以用顺序存储结构 广义表可以是一个多层次的结构 广义表第一个元素是表头，其...

解析：依次判断表达式中的每个字符，若是左括号就入栈，若是右括号则出栈，出栈的时候判断是否为空，如果为空，则说明不匹配；最后读到表达式末尾没有字符了，再判断一下栈是否为空，如果为空，则说明匹配，不为空，说明不匹配。

归并排序 例子 迭代实现递归排序 性能分析 基数排序 多关键字排序 链式基数排序 各种排序方法比较

直接选择排序 选择的含义在于每一趟选出一个最小的来，放在前边 性能分析 树形选择排序 性能分析 堆排序 堆的定义 根节点的左右子树节点都来得比他小或者比他大 算法思想 小顶堆自上而下的调整过程 小顶堆的建立过程 算法 性能分析

起泡排序 就像冒泡一样，每次把一个最值浮到最上边或下沉到最下边 性能分析 起泡排序是稳定的 快速排序 性能分析 每一趟排序都会找到此趟的枢轴元素排好序后所在的位置

概述 排序的分类 值得注意的是，我们这一章介绍的主要是内部排序 待排记录的数据类型定义 插入排序 类别 直接插入排序 性能分析 25与25* 排序前后顺序没有变化，可见直接插入排序是稳定的 折半插入排序 性能分析 2-路插入排序 性能分析 表插入排序 性能分析 重排记录的方法 表插入排序结束时每个节点link域位序没有规律...

动态查找表 动态查找表要同时考虑查找的效率和插入删除的效率，而折半法只考虑了查找的效率 二叉排序树 上图不是二叉排序树，因为66不满足二叉排序树定义（在50左子树，但是比50大） 平衡二叉树：是特殊的二叉排序树，是在其基础上的改进，相较二叉排序树查找效率更高 B-树 二叉排序树每个节点最多有两个子树，如果n非常...

查找的概念 查找表的概念 查找表的分类 关键字（类似主键） 查找 静态查找表 顺序查找表 查找过程 顺序表中表长比元素个数多一个，0号是空的，不存储元素，而是将被查找元素存在0号单元里，从尾部进行查找，这样最终一定能找到，从而提高效率。0号单元叫做监视哨 查找效率 顺序查找比较低效，要平均比较一半元素，当n大...

栈 顺序栈 值得注意的是，top指针不存储栈中元素，指向栈顶元素的下一个位置 共享栈：程序中定义多个栈，多个栈占用一个存储空间 链栈 队列 链式队列 循环队列 首先看顺序队列 此时其实存在空间，但是却在front前边没法使用，造成溢出。因此我们通过建立循环队列让队列首尾相连，解决假溢出问题 为了解决循环队列队空和...

字符串的表示与实现 字符串与模式匹配

数组 一维数组 二维数组 三维数组 特殊矩阵的压缩储存 对称矩阵的压缩存储 下三角矩阵与存储数组元素的对应关系 上三角矩阵与存储数组元素的对应关系 三对角矩阵的压缩储存 稀疏矩阵 稀疏矩阵的三元组顺序表表示 如何根据稀疏矩阵的三元组表获得其转置矩阵的三元组表 方法一 方法二 广义表 广义表的存储结构：表节点和原...

森林与二叉树的转换以及树的遍历 森林的二叉树表示（类似左子女右兄弟表示，把每棵树的根都看作兄弟） 普通树的遍历 普通树的先根遍历就是转换完成后二叉树的前序遍历 普通树的后根遍历就是对应二叉树的中序遍历 二叉树的计数 由前序遍历找根节点，由中序遍历找左子树和右子树；在左右子树中如此反复，就得到了最终结果 ...

二叉树的存储结构 顺序存储 由于二叉树比较灵活，顺序表示会浪费大量的空间，因此一般不使用，除非是完全二叉树或满二叉树 链式表示 静态链表 以线性结构存储，所以对于存储空间的分配不是很灵活，如果实现已知长度的树，要插入删除数据就不可以 二叉树遍历的递归算法 二叉树遍历应用 二叉树遍历的非递归算法 树的存储结...

树的概念 类似人的家族关系 定义 内容 结点 存储的数据元素以及指向子树的分支 结点的度 结点的子树个数 叶结点 度为0的结点 子女（双亲） 直接后继（直接前驱） 兄弟 同一结点的子女 祖先 根到该结点路径上的所有结点 子孙 子树上的任意结点 树的深度（高度） 树的结点的最大层次数 树的度 树各结点中最大的度 有序树 ...

广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。

当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；

邻接矩阵 {代码...} 邻接表 {代码...}

最小生成树 最小生成树性质 求最小生成树的算法：普里姆算法 拓扑排序 活动网络 AOV网络 总是县访问入度为0的节点，拓扑排序不一定不唯一 拓扑排序 值得注意的是，拓扑排序总是先访问入度为0的节点，且结果不一定唯一 算法描述 关键路径 AOE网络 AOE与AOV网络不同，AOV网络用顶点表示活动，AOE网络用边表示活动 AOE网络...

图类型 概念 定义 无向图 连通图 图中任意一对顶点都是连通的 无向图 连通分量 非连通图的极大连通子图 有向图 强连通图 任意一对顶点来回都是连通的 有向图 强连通分量 非强连通图的极大强连通子图

十字链表的实现 当稀疏矩阵的非零元数量和位置在操作过程中变化较大时（如矩阵相加），便不再适宜采用顺序存储，此时使用链式存储更为恰当。 十字链表的实现 {代码...} 十字链表的创建 {代码...} 实现矩阵相加 int Insert(CrossList M,OLink p)`//把p所指向的节点插入到十字链表中` { int i,j,e; OLink q,q1; i=p->i;...

在起点与终点之间存在障碍物的前提下，向两侧扫描获取周围障碍物信息，并确定子节点。子节点不断扫描和更新下一级子节点，从而扫描到终点，并通过终点反选父节点确定最终路线。减少了传统算法规划路径中最终的结果并非最优解的问题

引入 在数据分析中常出现一些阶数很高的矩阵，同时在矩阵中有许多零元素或者相同元素。为了节省储存空间，可对这些矩阵进行压缩储存。 压缩储存：对多个相同的值只分配一个储存空间；对零元素不分配储存空间 两种可压缩储存矩阵 名称 特点 特殊矩阵 零元素或相同元素分布有规律 稀疏矩阵 零元素多于非零元素，但分布没有...