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

软件设计师专题四：数据结构(20070305)在线专题授课音视频

答疑整理：

图的遍历
图的遍历是从某个顶点出发，沿着某条搜索路径对图中所有顶点进行访问且只访问一次。
（1）深度优先搜索（DFS）
从图G中任一结点v出发按深度优先搜索法进行遍历的步骤如下：
1）设立搜索指针p，使p指向顶点v；
2）访问p结点，并使p指向与p顶点相邻接的且尚未被访问过的结点；
3）若p不空，则重复步骤2），否则执行步骤4）；
4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤2），直至所有的顶点均被访问为止。
当以邻接表示作为存储结构时，深度优先搜索遍历图的时间复杂度为 。
（2）广度优先搜索（BFS）
从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先访问的顶点的邻接点”先于“后访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。