下载掌阅APP，畅读海量书库
立即打开
数据结构与算法主要是考试中所涉及的数据结构、算法、算法描述和分析。本章在考纲中主要有以下内容：
● 数据结构（数组、链表、队列、栈、树、图、哈希）。
● 算法（排序、查找）。
● 算法描述和分析（流程图、效率分析、递归、分治、回溯、贪心、动态规划）。
数据结构与算法考点如图3-1所示，用星级★标示知识点的重要程度。
图3-1 数据结构与算法考点
统计2010年至2020年试题真题，在上午考核的基础知识试卷中，本章主要考点分值为8～10分，在下午考核的案例应用试卷中，本章会考一道大题，15分，合计23～25分。历年真题统计如表3-1所示。
表3-1 历年真题统计
（续）
3.1.3.1 数据结构
1.数组
定义：把线性表的节点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。
a [ i ]的存储地址为： a + i ×len。
对于二维数组 a [ m ][ n ]：
a [ m ][ n ]的存储地址（按行存储）为： a +（ i × n + j ）×len。
a [ m ][ n ]的存储地址（按列存储）为： a +（ j × m + i ）×len。
基本操作：插入、查找、删除。
顺序表的优点：无须为表示节点间的逻辑关系而增加额外的存储空间，可以方便地随机存取表中的任一节点。
顺序表的缺点：插入和删除运算不方便，由于要求占用连续的存储空间，因此存储分配只能预先进行。
2.链表
链表是指用一组任意的存储单元来依次存放线性表的节点，这组存储单元既可以是连续的，也可以是不连续的，甚至是随机分布在内存中的任意位置上的，即链表中节点的逻辑次序和物理次序不一定相同。单链表结果如图3-2所示。
图3-2 单链表
（1）带表头节点的单链表
表头节点位于表的最前端，本身不带数据，仅标示表头。设置表头节点的目的是统一空表与非空表的操作，简化链表操作的实现。
（2）循环链表
循环链表是单链表的变形，如图3-3所示。循环链表最后一个节点的next或link指针不为NULL，而是指向了表的前端。为了简化操作，在循环链表中往往加入表头节点。循环链表的特点是：只要知道表中某一节点的地址，就可以搜寻到所有其他节点的地址。实际中多采用尾指针表示单循环链表。
图3-3 循环链表
（3）双向链表
双向链表如图3-4所示，双向链表的头节点也直接指向尾部。双向链表的特点是：“查询”和单链表相同，“插入”和“删除”需要同时修改两个方向上的指针。
图3-4 双向链表
（4）链表的特点
① 为了能够用指针来反映节点之间的逻辑关系，需要为每个节点额外增加相应的指针域，从而使节点的存储密度比顺序表中节点的存储密度要小。
② 在链式存储结构中要查找某一节点，一般要从链头开始沿链进行扫描才能找到该节点，其平均时间复杂度为 O （ n ）。因此，链式存储结构是一种非随机存储结构。
3.队列
队列是只允许在一端删除在另一端插入的线性表，如图3-5所示。队头（front）是允许删除的一端，队尾（rear）是允许插入的一端。队列的特点是：先进先出（First In First Out，FIFO）。
图3-5 队列
4.栈
栈是只允许在一端插入和删除的线性表，如图3-6所示。允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈的特点是：后进先出（Last In First Out，LIFO）。
图3-6 栈
5.树
（1）性质
● 度为 k 的树中第 i 层上至多有 k i -1 个节点。
● 二叉树第 i 层的节点数最多有2 i -1 （ i ≥1）个。
● 深度为 h 的二叉树至多有2 h -1（ h ≥1）个节点。
● 具有 n 个节点的完全二叉树的深度为└log 2 n ┘+1或┌log 2 （ n +1）┐。
● 对于具有 n 个节点的完全二叉树，对其节点进行编号，则对于编号为 i 的节点，有：左孩子的编号为2 i ，右孩子的编号为2 i +1。
（2）树的遍历
树的遍历就是按照某种顺序访问树中的每个节点，并使每个节点被访问一次且只被访问一次。
①前序遍历。若二叉树非空，则进行如下操作：
● 访问根节点。
● 按前序遍历次序遍历根节点的左子树。
● 按前序遍历次序遍历根节点的右子树。
②中序遍历。若二叉树非空，则进行如下操作：
● 按中序遍历次序遍历根节点的左子树。
● 访问根节点。
● 按中序遍历次序遍历根节点的右子树。
③后序遍历。若二叉树非空，则进行如下操作：
● 按后序遍历次序遍历根节点的左子树。
● 按后序遍历次序遍历根节点的右子树。
● 访问根节点。
④层次遍历。若二叉树非空，则进行如下操作：
● 遍历之前先将二叉树的根节点存入队列。
● 然后依次从队列中取出队头节点，每取出一个节点，都先访问该节点。
● 接着分别检查该节点是否存在左、右孩子，若存在则先后入列。
● 如此反复，直到队列为空为止。
6.图
图是由顶点（Vertex）集合及顶点间的关系集合组成的一种数据结构：
Graph=( V , E )
其中， V ={ x | x ∈某个数据对象}是顶点的有穷非空集合。
E ={（ x ， y ）| x ， y ∈ V }或 E ={＜ x ， y ＞| x ， y ∈ V &&Path （ x ， y ）}
（1）图的属性
完全无向图：有 n 个顶点的无向图有 n （ n -1）/2条边。
完全有向图：有 n 个顶点的有向图有 n （ n -1）条边。
邻接顶点：如果（ u ， v ）是 E （ G ）中的一条边，则称 u 与 v 互为邻接顶点。
子图：设有两个图 G =（ V ， E ）和 G′ =（ V′ ， E′ ）。若 V′ ⊆ V 且 E′ ⊆ E ，则称图 G′ 是图 G 的子图。
权：某些图的边具有与它相关的数，称为权。这种带权图叫作网络。
稠密图和稀疏图：若边或弧的个数 e ＜ n log 2 n ，则称作稀疏图，否则称作稠密图。
顶点的度：一个顶点 v 的度是与它相关联的边的条数。
入度：以 v 为终点的有向边的条数。
出度：以 v 为始点的有向边的条数。
路径：在图 G =（ V ， E ）中，若从顶点 v i 出发，沿一些边经过一些顶点 v p 1 ， v p 2 ，…， v pm 到达顶点 v j ，则称顶点序列（ v i v p 1 v p 2 … v pm v j ）为从顶点 v i 到顶点 v j 的路径。
（2）图的遍历
①深度优先遍历（DFS）。
在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w 1 ；再从 w 1 出发，访问与 w 1 邻接但还没有访问过的顶点 w 2 ；然后从 w 2 出发，进行类似的访问，如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其他没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
②广度优先遍历（BFS）。
在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未被访问过的邻接顶点 w 1 ， w 2 ，…， w t ，再顺序访问 w 1 ， w 2 ，…， w t 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，访问它们的所有还未被访问过的邻接顶点，如此进行下去，直到图中所有顶点都被访问到为止。广度优先遍历是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先遍历那样有往回退的情况。
7.哈希
哈希（Hash，或称为散列）依据关键码直接得到其对应的数据元素位置，即要求关键码与数据元素间存在一一对应关系，通过这个关系能很快地由关键码得到对应的数据元素位置。
（1）构造好的哈希函数
①所选函数尽可能简单，以便提高转换速度。
②所选函数对关键码计算出的地址应在哈希地址集中大致均匀分布，以减少空间浪费。
（2）解决冲突的方案
①开放定址法（闭散列表法）。
● 线性探测再散列。
● 平方探测再散列。
● 随机探测再散列（双散列函数探测，即双哈希函数探测）。
②链地址法（开散列表法）。
3.1.3.2 算法
1.排序
（1）冒泡排序
比较相邻的元素，如果第一个比第二个大，就交换它们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这一步骤做完后，最后的元素会是最大的数。
针对所有的元素重复以上步骤，除了最后一个。
持续对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
（2）选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复此过程，直到所有元素均排序完毕。
（3）插入排序
将第一待排序序列的第一个元素看作一个有序序列，把第二个元素到最后一个元素当成未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入相等元素的后面）。
（4）希尔排序
选择一个增量序列 t 1 ， t 2 ，…， t k ，其中 t i ＞ t j ， t k =1。按增量序列个数 k 对序列进行 k 趟排序，每趟排序根据对应的增量 t i 将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
（5）归并排序
①申请空间，使其大小为两个已经排序的序列之和，该空间用来存放合并后的序列。
②设定两个指针，最初位置分别为两个已经排序的序列的起始位置。
③比较两个指针所指向的元素，选择相对小的元素放入合并空间，并移动指针到下一个位置。
④重复步骤③直到某一指针到达序列尾部。
⑤将另一序列剩下的所有元素直接复制到合并后的序列尾部。
（6）快速排序
从数列中挑出一个元素，称为“基准”（Pivot）。
重新排序数列，所有元素比基准值小的放在基准前面，所有元素比基准值大的放在基准后面（相同的数可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这称为分区（Partition）操作。
递归地把小于基准值的元素的子数列和大于基准值的元素的子数列排序。
（7）堆排序
①创建一个堆 H [0… n -1]。
②把堆首（最大值）和堆尾互换。
③把堆的尺寸缩小1，并调用shift_down（0），目的是把新的数组顶端的数据调整到相应位置。
④重复步骤②，直到堆的尺寸为1。
2.查找
（1）顺序查找
适合使用顺序查找的存储结构：顺序存储、链式存储。
（2）二分查找
先确定待查记录所在的范围（区间），然后逐步缩小范围，直到找到或找不到该记录为止。
（3）二叉排序树
二叉排序树要么是一棵空树，要么是具有下列性质的二叉树：
每个节点都有一个作为搜索依据的关键码（Key），所有节点的关键码互不相同。左子树（如果存在）上所有节点的关键码都小于根节点的关键码。右子树（如果存在）上所有节点的关键码都大于根节点的关键码。左子树和右子树也是二叉排序树。
（4）索引查找
在索引表中确定记录所在区间（可用顺序查找或二分查找），在顺序表的某个区间内进行查找（可用顺序查找）。
索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度
3.1.3.3 算法描述和分析
1.流程图
流程图用一些图框来表示各种类型的操作，在框内写出各个步骤，然后用带箭头的线把它们连接起来，以表示执行的先后顺序。用图形表示算法，直观形象，易于理解。程序框图表示程序内各步骤的内容以及它们的关系和执行的顺序，它说明了程序的逻辑结构。框图应该足够详细，以便可以按照它顺利地写出程序，而不必在编写时临时构思，甚至出现逻辑错误。流程图不仅可以指导编写程序，而且可以在调试程序时用来检查程序的正确性。如果框图是正确的而结果不对，则按照框图逐步检查程序很容易发现其错误。流程图还能作为程序说明书的一部分提供给别人，以便帮助别人理解你编写程序的思路和结构。流程图有三种结构：顺序结构、选择结构和循环结构。
2.效率分析
（1）算法效率衡量方法
算法效率可按照以下几个要点来衡量：
①算法采用的策略和方案。
②编译产生的代码质量。
③问题的输入规模。
（2）符号表示
有三种表示时间复杂度的符号，分别是 O 、 Ω 和 θ 。
O （ n ）表示增长次数小于等于 n 的算法。
Ω （ n ）表示增长次数大于等于 n 的算法。
θ （ n ）表示增长次数等于 n 的算法。
（3）复杂度
时间复杂度：分析算法中主要执行语句的执行频率。例如排序的时间复杂度可用算法执行中的数据比较次数与数据移动次数来衡量。后面一般都按平均情况进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。
空间复杂度：需要使用的辅助存储空间。
3.递归
从算法的观点看，对于许多问题采用递归的方法，使得用简洁、容易理解和有效的算法来解决复杂问题成为可能。
在最简单的形式中，递归是这样一个过程：将问题分解成一个或多个子问题，这些子问题在结构上和原来的问题一模一样，然后解决这些子问题，把这些子问题的解组合起来，从而得到原来问题的解。
（1）递归算法的基本模式
①明确递归的终止条件，即给出最小问题的条件。
②提取重复的逻辑，即给出问题分解的处理方法。
③给出递归终止条件下的处理方法，即直接求解基本情形。
（2）递归算法的优点
①读写简明。
②算法的正确性易于用数学归纳法来验证。
③算法的复杂性往往可利用递归关系来分析。
（3）递归算法的缺点
①算法的执行流程不易理解。
②递归调用往往需要额外的时空开销。
4.分治
对 k 个子问题分别求解，如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归地进行下去，直到问题规模足够小，很容易求出其解为止。分治法所能解决的问题一般具有以下几个特征：
● 该问题的规模缩小到一定的程度就很容易解决。
● 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
● 利用该问题分解出的子问题的解可以合并为该问题的解。
● 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
5.回溯
（1）回溯法的一般步骤
①将解空间表示成一棵树（解空间树），求解问题就转化为在树 T 中搜索解对应的树节点。
②定义剪枝操作（需考虑约束条件和目标值两方面）。
③ 从树 T 的根节点开始，用深度优先法搜索该树，而跳过肯定不包含问题解对应的节点的子树的搜索（剪枝），以提高效率。
（2）适用范围
回溯法适用范围较广，适用于存在性问题和最优性问题的求解。
有许多问题，当需要找出其解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法的基本做法是搜索。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，能避免不必要的搜索。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该节点是否包含问题的解。如果肯定不包含，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
6.贪心
贪心算法通常用来求解最优化问题。它通常包含一个用以寻找局部最优解的迭代过程。贪心算法在少量计算的基础上做出正确猜想而不急于考虑以后的情况，这样一步一步地来构造解，每一步均是建立在局部最优解的基础上，每一步又都扩大了部分解的规模，做出的选择产生最大的直接收益，又保持了可行性。
贪心算法是根据一种贪心准则（greedy criterion）来逐步构造问题的解的方法，在每一个阶段都做出了相对该准则最优的决策，决策一旦做出就不可更改。
由贪心算法得到的问题的解可能是最优解，也可能只是近似解。能否产生问题的最优解需要加以证明。所选的贪心准则不同，则得到的贪心算法不同，贪心解的质量当然也不同。因此，好的贪心算法的关键在于正确地选择贪心准则。
7.动态规划
（1）适用范围
对于多阶段决策的最优化问题，最优解满足最优性原理，子问题具有重叠性的情况适用。
（2）基本思想
将原问题分解为子问题来求解，求出子问题的解并由此来构造出原问题的解（即自下而上来求解）。在求解过程中不必回头看以前的情况。
（3）设计一个动态规划算法的4个步骤
①刻画最优解结构（即证明满足最优性原理）。
②递归定义最优解的值。
③按自下而上的方式计算最优解的值。
④由计算的结果构造出一个最优解。