辽宁科技大学课程教学大纲

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐辽宁科技大学课程教学大纲辽宁科技高校课程教学大纲

课程名称：数据结构

英文名称：DataStructure

课程编号：X2050876

学时数：64

其中试验（实训）学时数：20课外学时数：0

学分数：4.0

适用专业：软件工程(升本)

一、课程的性质和任务

数据结构是软件工程专业的核心专业基础课。也是计算机及相关专业的硕士讨论生入学考试的专业课程之一。通过学习，使同学能够分析数据对象特征，按照问题的需要，确定规律结构并挑选合适的存储结构，实现典型算法设计及性能分析。要求同学把握典型算法及其程序实现，进而培养和提高同学算法分析与设计能力，建立数据结构的概念，为后续课程的学习及软件开发打好基础。

二、课程教学内容的基本要求、重点和难点

1、绪论

把握数据元素、规律结构、存储结构等基本概念；理解算法的定义、描述办法及算法分析办法；

了解《数据结构》的课程体系。

重点：数据结构的概念及算法描述办法。

难点：算法的效率度量。

2、线性结构

理解线性表的定义及思想；理解线性表的挨次，链式存储实现；娴熟把握线性表的插入、删除、查找等基本操作；把握线性表的逆置、分解、合并等典型算法；理解栈和队列的定义及动态思想；把握栈、队列的存储实现和基本操作；理解栈与递归的关系，把握栈、队列的应用问题：递归算法的设计原则及如何利用栈实现非递归算法的设计、表达式求值等问题；了解串的定义及存储实现，把握串的模式匹配算法；了解数组的定义，把握特别矩阵（对称矩阵、三角矩阵）的压缩存储实现。

重点：线性表的基本算法及典型算法，栈、队列的基本算法（操作）。

难点：栈与递归的关系。

3、树

了解树、二叉树的概念、性质；把握二叉树的存储实现；娴熟把握二叉树的遍历办法及算法实现；

理解二叉树的递归算法的设计原则，把握二叉树的应用算法（求叶子，高度等）；了解树的遍历及存储；理解树与二叉树的转换关系；把握哈夫曼树的概念、构造算法及编码。

重点：二叉树的遍历及算法

难点：二叉树递归算法的理解及如何利用栈实现非递归算法

4、图

了解图的定义及相关术语；把握图的邻接矩阵、邻接表的存储实现；把握图的遍历算法的思想及其实现，并能够基于存储结构写出遍历序列；理解图的连通性概念及算法；理解最小生成树、拓扑排序、最短路径的概念及算法；了解关键路径的概念及算法思想。

重点：图的存储及遍历算法，图的典型算法实现

难点：遍历及应用算法的实现

5、排序和查找

了解排序的相关概念；把握直接插入、容易挑选、冒泡、迅速排序和堆排序的算法思想及实现；理解希尔、归并、基数排序的算法思想；理解各种算法的适用条件及其效率；了解线性表、树表和散列表查找的相关概念；娴熟把握挨次、折半查找算法，理解查找算法效率度量的办法，会计算查找算法的ASL值；把握二叉排序树的构造和查找算法；了解散列函数的选取原则和常见办法，能够按照散列函数和矛盾处理办法构造散列表并把握散列表的查找算法；了解B+、B-树的概念。

重点：把握几种常见排序算法及特点；常见查找办法的算法及适用条件。

难点：迅速排序的非递归实现

三、教学方式及学时分配

四、课程其他教学环节要求

（二）数据结构课程设计

要求：同学自立完成课程设计的任务，查阅相关资料、编写程序并写出说明书。

（三）作业

为提高课堂教学质量，催促同学听课，任课老师可举行适当的随堂小测试；每章讲授结束后，各留2-3道综合题（应用题）、有试验的章节留2-3道典型算法设计题作为作业，批改后做集中讲评，讲解作业中浮现的问题。作业的题型以算法设计为主。

（四）课外

首先完成老师布置的作业，预备试验程