60223402数据结构课程教学大纲.docVIP

PAGE

数据结构课程教学大纲

课程名称：

数据结构

课程编码：总学时数：

60

课内实践学时数：

20

学分：

3.5

开课单位：

电信学院

先修课程：

程序设计基础

适用专业对象：

计BZ13级

一、课程性质、目的和任务

《数据结构》课程是计算机科学与技术专业学生必修的专业基础课程之一。通过本课程学习，使学生能较系统地掌握数据结构的逻辑结构和物理结构以及有关算法的基本知识、原理和方法，初步具备一定的算法及程序的分析和设计能力，为学习数据库原理及应用、可视化程序设计VC#和软件工程等课程打下基础。

二、教学内容及教学基本要求

第1章绪论

1．什么是数据结构

了解数据结构的概况。理解数据结构的定义；

2．数据结构的基本概念和术语

了解数据结构的概况：数据结构研究的范围和发展概况；理解数据结构的有关概念：数据、数据类型、数据元素数据对象、结构类型。

3．抽象数据类型的表示与实现

了解抽象数据类型的概念；理解抽象数据类型的表示方法；掌握抽象数据类型的实现。

4．算法描述和算法分析

理解算法的描述形式及要求；掌握算法语言的语法：赋值语句、分支语句、循环语句、输入和输出语句、注释形式。

第2章线性表

1．线性表的类型定义

了解线性表的概念和线性表的分类；熟悉线性表的逻辑结构和物理结构；掌握线性表的运算。

2．线性表的顺序表示和实现

了解顺序表的结构形式；熟悉顺序表的存储实现；掌握顺序表上实现的基本运算。

3．线性表的链式表示和实现

了解循环链表和双向链表；熟悉线性链表的链式存储结构的实现、与顺序表的区别、链式结构的特点；掌握链表的相关运算。

4．一元多项式的表示及相加

熟悉一元多项式的存储形式；掌握一元多项式链表的相加的运算。

第3章栈和队列

1．栈

了解抽象数据类型栈的定义、栈的表示和实现；熟悉栈的定义；掌握栈的基本运算。

2．栈的应用举例

了解括号的匹配检验；熟悉一般表达式转化为后缀表达式掌握计算表达式的值和数制转换。

3．栈与递归的实现

了解递归的步骤；理解递归的概念；掌握应用栈实现递归：求n!。

4．队列

理解队列的定义、队列的运算、队列的物理结构；掌握队列的有关算法。

第4章串

1．串类型的定义

理解串的基本概念；掌握串的基本运算。

2．串的表示和实现

了解串的块链存储表示和定长顺序存储表示；理解串的顺序存储结构；掌握串的链式存储结构的优化：堆分配存储表示。

3．串的模式匹配算法

了解正文模式匹配的概念；理解串的模式匹配的简单算法和串的模式匹配的改进算法；掌握改进算法的时间复杂度的计算。

4．串操作应用举例

理解文本编辑器的使用。

第5章数组与广义表

1．数组的定义

了解数组的概念；掌握数组的分类。

2．数组的顺序表示和实现

理解数组中元素地址的计算方法；掌握数组的顺序存储的两种方式。

3．矩阵的压缩存储

了解特殊矩阵的分类；理解特殊矩阵的压缩存储方法；掌握稀疏矩阵的转置方法。

4．广义表的定义

了解广义表的相关概念；理解广义的的基本运算。

5．广义表的存储结构

理解广义表存储结构的方法。

6．广义表的递归算法

了解递归的概念归算法的执行过程递归算法的设计方法；理解递归过程和运行时栈递归算法的效率分析。

第6章树与二叉树

1．树的定义和基本术语

理解树相关概念

2．二叉树

了解二叉树的分类；理解二叉树的定义；掌握二叉树的性质、二叉树的存储结构。

3．遍历二叉树和线索二叉树

了解遍历的、线索二叉树、线索化的概念和遍历算法；理解二叉树的三种遍历序列；掌握二叉树的遍历的三种方法。

4．树和森林

理解树的存储结构；掌握树、森林到二叉树的转换，二叉树到树、森林的转换，森林和树的遍历。

5．哈夫曼树及其应用

理解哈夫曼树(最优二叉树)和哈夫曼编码的概念；掌握带权路径长度的概念和计算方法、哈夫曼树的构造方法和哈夫曼编码生成方法。

第7章图

1．图的定义和术语

理解图的相关概念和术语。

2．图的存储结构

了解十字链表、邻接多重表；理解邻接表表示法、逆邻接表表示法；掌握邻接矩阵表示法。

3．图的遍历

了解图的遍历的概念；理解度优先遍历和广度优先遍历算法；掌握图的遍历的分类和方法。

4．图的连通性问题

熟悉MST的两种生成算法：普里姆(Prim)算法、克鲁斯卡尔（Kruskal）算法；

掌握无向图的连通分量、生成树、最小生成树（MST）的生成方法；

5．有向无环图及其应用

了解AOV网的概念；掌握拓扑排序和关键路径的算法。

6．最短路径

了解最短路径的概念；理解迪杰斯特拉（Dijkstra）算法时间复杂度；掌握迪杰斯特拉（Dijkstra）算法。

第8章查找

1．静态查找表

了解查找的相关概念：文件、关键字、查找；理解索引顺序表的查找算法；掌握顺序表的查找方法。

2．动态查找表

理解二叉树概