重点：
① 数组和矩阵元素的存储方式。
② 二叉树的性质。
③ 查找算法的基本思想和查找性能分析。
④ 各种排序算法实现的基本思想及实现。

难点：
① 矩阵元素的存储方式，广义表的定义及基本运算。
② 树的特点、基本运算及其实现。
③ 图的特点、存储结构、常用算法及实现。
④ 各种查找算法的基本思想和查找性能分析方法。
⑤ 各种排序算法实现的基本思想及实现。

亮点/应用/重要性：
　　这部分内容对各个级别的软考都是必考的，在软件设计师考试中尤其占有非常重要的地位。要求掌握一些基本数据结构的存储方法及其有关的操作，重点掌握线性表、数组、二叉树、图的一些基本算法。特别要掌握常用的查找和排序算法。

主要内容：
① 各种线性结构的特点、基本运算及其实现。
② 矩阵元素的存储方式，广义表的定义及基本运算。
③ 树的特点、基本运算及其实现。
④ 图的特点、存储结构、常用算法及实现。
⑤ 顺序查找和二分查找方法及实现。
⑥ 二叉排序树的定义和查找、插入及删除运算和实现。
⑦ 平衡二叉树的定义及其平衡处理方法，B-树的概念及查找。
⑧ 各种查找算法的查找性能分析方法。
⑨ 各种排序方法及实现。

一、数据结构(20060306)在线专题授课音视频

（本课程正式学员可登录学习系统，进入对应课程，在窗口左边的“课程资料室”内进行在线浏览。）

二、数据结构(20060306)在线答疑整理

1. 关于线性表的插入和删除运算

（1）基于顺序存储结构的运算：

插入元素前要移动元素，以挪出空的存储单元，然后再插入元素；删除元素时同样需要移动元素，以填充被删除的元素空出来的存储单元。

（2）基于链式存储结构的运算：

2. 二叉树的性质：

（1）二叉树第i层（ ）上至多有 个结点。

（2）深度为k的二叉树至多有 个结点（ ）。

（3）对任何一棵二叉树，若其终端结点数为 ，度为2的结点数为 ，则 。

（4）具有n个结点的完全二叉树的深度为 。

（5）对一棵有n个结点的完全二叉树的结点按层次自左到右进行编号，则对任一结点i( )有：

1）若i=1，则结点i是二叉树的根，无双亲；若i>1，则其双亲为 。

2）若2i>n，则结点i无左孩子，否则其左孩子为2i。

3）若2i+1>n，则结点i无右孩子，否则其右孩子为2i+1.

若深度为k的二叉树有 个结点，则称其为满二叉树。深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。 

3. 内部排序方法的比较和选择

4. 对称矩阵的存储结构

若矩阵An×n中的元素有以下特点:

则称之为n阶对称矩阵。

以行为主序存储下三角（包括对角线）中的元素。假设以一维数组作为n阶对称矩阵A的存储结构，则

5. 图的遍历

图的遍历是从某个顶点出发，沿着某条搜索路径对图中所有顶点进行访问且只访问一次。

（1）深度优先搜索（DFS）

从图G中任一结点v出发按深度优先搜索法进行遍历的步骤如下：

1）设立搜索指针p，使p指向顶点v；

2）访问p结点，并使p指向与p顶点相邻接的且尚未被访问过的结点；

3）若p不空，则重复步骤2），否则执行步骤4）；

4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤2），直至所有的顶点均被访问为止。

当以邻接表示作为存储结构时，深度优先搜索遍历图的时间复杂度为 。

（2）广度优先搜索（BFS）

从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先访问的顶点的邻接点”先于“后访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。