《数据结构》自学实施计划

来源：发布时间：2006-5-29 16:54:24 点击：

说明：
　　1.本课程自学总学时为95学时。
　　2.本实施计划中的次数是按教学计划中要求的每人每天最少自学2.5学时考虑的。
　　3.根据每章学时数的安排，就能了解本章内容的深广度和重点、难点，以便合理安排自己的学习进度。

　　第1章概论（2*2.5学时/次=5学时）

次数	主要内容	重点	难点
1	1.1	①基本概念和基本术语（数据、数据元素、数据结构、数据类型、抽象数据类型） ②数据结构的有关概念（直接前趋、直接后继、开始结点、终端结点） ③数据结构的四种存储方法（顺序存储、链接存储、索引存储、散列存储）	①区别逻辑结构与数据结构 ②弄清数据的逻辑结构有两大类（线性结构与非线性结构）
2	1.2~1.3	①学习数据结构的意义（算法+数据结构=程序） ②算法的描述 ③选用及评价算法的依据（耗费时间、耗费存储空间、易于理解、易于编码、易于调试）	①时间复杂度的计算

　　第2章线性表（4*2.5学时/次=10学时）

次数	主要内容	重点	难点
3、4	2.1~2.2	①线性表的逻辑结构 ②线性表定义的基本运算（初始化、求表长、取结点、查找结点、插入结点、删除结点），并利用其构造出复杂的运算 ①线性表的顺序存储结构 ②顺序的含义及特点（顺序表如何反映线性表中元素之间的逻辑关系） ③顺序表上实现的基本运算（主要是插入、删除操作） ④顺序表的平均时间性能分析	①插入、删除过程中引起结点位置（数组下标）的变化
5、6	2.3~2.4	①链表如何表示线性表中元素之间的逻辑关系 ②链表中头指针和头结点的使用 ③单链表的建表（头插法、尾插法）查找（按序号查找、按值查找）插入和删除等基本算法并分析其时间复杂度 ④循环链表用尾指针取代头指针的作用以及单循环链表算法与单链表相应算法的异同 ⑤双链表的定义及相关算法 ⑥单链表、双链表、循环链表在链接方式上的区别 ⑦从空间和时间两个方面来比较顺序表和链表	①指针变量与结点变量的区分 ②两个不同存储结构链表的合并与排序 ③同一链表用不同的存储结构来表示

　　第3章栈和队列（3*2.5学时/次=7.5学时）

次数	主要内容	重点	难点
7	3.1	①栈的定义及基本运算 ②栈的逻辑结构及与线性表的区别 ③顺序栈的基本算法（进栈与退栈等） ④链栈的基本算法（进栈与退栈等）	①栈的“上溢”和“下溢”的概念及其判别条件
8	3.2	①队列的定义及基本运算 ②队列的逻辑结构及与线性表的区别 ③顺序队列（主要是循环队列）的入队与出队的算法 ④链对列的出队与入队的算法 ⑤队列的“上溢”与“下溢”的概念及其判别条件	①使用数组实现的循环队列取代普通的顺序队列 ②循环队列中对边界条件的处理方法
9	3.3	①学会如何使用栈或队列来分析和处理我们在日常生活中遇到的各种问题 ②用栈和队列作为数据结构来处理问题的原则（即先进后出用栈来实现，先进先出用队列来实现） ③数制转换与舞伴问题等	①栈与递归问题（递归过程中退栈时分析及其相应值的变化）

　　第4章串（2*2.5学时/次=5学时）

次数	主要内容	重点	难点
10	4.1	①串的基本概念（空串与空白串的区别） ②串的基本运算（求串长、串复制、联接、串比较、字符定位等）	①串与线性表的关系
11	4.2	①串的存储结构（顺序存储、链式存储） ②静态存储分配的顺序串与动态存储分配的顺序串 ③串运算的实现：（顺序串上的子串定位运算与链串上的子串定位运算）	①模式匹配过程中时间复杂度的计算

　　第5章多维数组和广义表（2*2.5学时/次=5学时）

次数	主要内容	重点	难点
12、13	5.1~5.3	①多维数组的逻辑结构特征 ②多维数组的顺序存储结构及地址计算方式（行优先顺序与列优先顺序） ③特殊矩阵（对称矩阵、三角矩阵、对角矩阵）压缩存储时的下标变换方法 ④稀疏矩阵的三元组表表示法及其运算 ⑤广义表的有关概念及其与线性表之间的关系 ⑥广义表的括号表示与图形表示方法及其它们之间的转换	①用带行表的三元组表来存储稀疏矩阵 ②求给定的非空广义表的表头和表尾的运算

　　第6章树（6*2.5学时/次=15学时）

次数	主要内容	重点	难点
14	6.1	①树的定义（两个满足条件） ②有关树结构中常用基本术语（度、叶子、根结点、孩子、双亲、兄弟等） ③树的各种表示方法 ④树的逻辑结构特征	①区别树的度与深度
15	6.2	①二叉树的递归定义及树与二叉树的差别 ②二叉树的性质 ③满二叉树和完全二叉树的性质 ④二叉树的存储结构（顺序存储结构、链式存储结构）	①顺序存储结构中的结点编号
16	6.3	①二叉树遍历的几种方法（先序、中序、后序及先根、中根、后根）并理解其执行过程 ②用递归方法实现二叉树的遍历	①用递归方法实现二叉树的遍历
17	6.4	①线索二叉树的定义 ②二叉树线索化的目的及实质 ③在中序线索树中查找给定结点的中序前趋和中序后继的方法 ④查找给定结点的前序前趋和后序后继并非有效的原因 ⑤遍历线索二叉树的方法	①二叉链表中左孩子、右孩子与械标志、右标志的区别及在线索化过程中指针的变化
18	6.5	①树和森林与二叉树之间的转换方法 ②树的三种存储方法（双亲链表表示法、孩子链表表示法、孩子-兄弟链表表示法） ③树和森林的两种遍历方法	①用孩子兄弟链表法将森林转换为二叉树
19	6.6	①最优二叉树的概念 ②树的带权路径及其算法 ③哈夫曼树的存储结构 ④哈夫曼算法的实现及如何构造哈夫曼树 ⑤最优前缀码的概念及特点 ⑥根据最优二叉树构造相应的哈夫曼编码	①根据给定的叶结点及其权值构造出相应的最优二叉树

　　第7章图（5*2.5学时/次=12.5学时）

次数	主要内容	重点	难点
20	7.1~7.2	①图的一些基本概念及其含义（有向完全图、无向完全图、入度、出度等） ②图的逻辑结构特征 ③图的邻接矩阵表示法 ④图的邻接表表示法 ⑤根据应用问题的特点和要求选择合适的存储结构	①图的逆邻接表
21	7.3	①连通图及非连通图的两种遍历算法（深度优先遍历、广度优先遍历） ②如何确定两种遍历所得到的顶点访问序列（DFS序列、BFS序列） ③图的两种遍历与树的遍历之间的关系 ④遍历过程中的相关算法	①在遍历过程中，如何使用栈或队列来实现其过程
22	7.4	①生成树与最小生成树的概念 ②对给定的图进行遍历，画出深度优先和广度优先生成树或生成森林 ③普里姆算法和克鲁斯卡尔算法的基本思想 ④两种算法的时间性能及其特点 ⑤根据给定的图，用两种算法构造出最小生成树	①用两种算法构造最小生成树的过程
23、24	7.5~7.6	①最短路径的含义 ②用Dijkstra算法求单源最短路径的基本思想及其时间性能 ③对于给定的有向图，如何利用Dijkstra算法求出其最短路径并画出过程示意图 ④拓扑排序的基本思想及其步骤 ⑤运用两种方法对有向图进行拓扑排序(无前趋的顶点优先，无后继的顶点优先) ⑥拓扑排序不成功的原因	①对于给定的有向图，如何利用Dijkstra算法求出其最短路径并画出过程示意图 ②求拓扑序列的过程

　　第8章排序（5*2.5学时/次=12.5学时）

次数	主要内容	重点	难点
25	8.1~8.2	①基本概念（关键字等） ②排序在数据处理中的重要性及其排序方法“稳定性”含义 ③排序方法的分类及算法好坏的评判标准 ④直接插入排序的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析 ⑤直接排序中哨兵的作用	①针对给定的输入实例，要能写出直接插入排序的排序过程
26	8.3	①冒泡排序的基本思想 ②快速排序的基本思想和算法实现，以及在最坏和平均情况下的时间性能分析，并了解算法的稳定性 ③基准元素（划分元）对划分是否平衡的影响	①针对给定的输入实例，能写出快速排序的排序过程
27	8.4	①选择排序的基本思想 ②直接选择排序的基本思想及算法 ③堆、小根堆、大根堆、堆顶等有关概念和定义 ④堆性质及堆与完全二叉树的关系 ⑤直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析	①直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析
28、29	8.5~8.7	①针对给定的输入实例，写出归并排序的排序过程 ②箱排序的基数排序的基本思想和算法实现以及时间性能分析 ③给定的输入实例，能写出箱排序和基数排序的排序过程 ④分配排序与其他几类排序的区别 ⑤各种内部排序方法的比较和选择，通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点	①根据实际出现的问题的特点和要求选择合适的排序方法

　　第9章查找（5*2.5学时/次=12.5学时）

本新闻共2页,当前在第1页 1 2