辽宁科技大学课程教学大纲
- 格式：doc
- 大小：52.50 KB
- 文档页数：3
辽宁科技大学课程教学大纲
课程名称：数据结构
英文名称：Data Structure
课程编号：X2050876
学时数：64
其中实验（实训）学时数：20 课外学时数：0
学分数：4.0
适用专业：软件工程(升本)
一、课程的性质和任务
数据结构是软件工程专业的核心专业基础课。
也是计算机及相关专业的硕士研究生入学考试的专业课程之一。
通过学习，使学生能够分析数据对象特征，根据问题的需要，确定逻辑结构并选择合适的存储结构，实现典型算法设计及性能分析。
要求学生掌握典型算法及其程序实现，进而培养和提高学生算法分析与设计能力，建立数据结构的概念，为后续课程的学习及软件开发打好基础。
二、课程教学内容的基本要求、重点和难点
1、绪论
掌握数据元素、逻辑结构、存储结构等基本概念；理解算法的定义、描述方法及算法分析方法；
了解《数据结构》的课程体系。
重点：数据结构的概念及算法描述方法。
难点：算法的效率度量。
2、线性结构
理解线性表的定义及思想；理解线性表的顺序，链式存储实现；熟练掌握线性表的插入、删除、查找等基本操作；掌握线性表的逆置、分解、合并等典型算法；理解栈和队列的定义及动态思想；掌握栈、队列的存储实现和基本操作；理解栈与递归的关系，掌握栈、队列的应用问题：递归算法的设计原则及如何利用栈实现非递归算法的设计、表达式求值等问题；了解串的定义及存储实现，掌握串的模式匹配算法；了解数组的定义，掌握特殊矩阵（对称矩阵、三角矩阵）的压缩存储实现。
重点：线性表的基本算法及典型算法，栈、队列的基本算法（操作）。
难点：栈与递归的关系。
3、树
了解树、二叉树的概念、性质；掌握二叉树的存储实现；熟练掌握二叉树的遍历方法及算法实现；
理解二叉树的递归算法的设计原则，掌握二叉树的应用算法（求叶子，高度等）；了解树的遍历及存储；理解树与二叉树的转换关系；掌握哈夫曼树的概念、构造算法及编码。
重点：二叉树的遍历及算法
难点：二叉树递归算法的理解及如何利用栈实现非递归算法
4、图
了解图的定义及相关术语；掌握图的邻接矩阵、邻接表的存储实现；掌握图的遍历算法的思想及
其实现，并能够基于存储结构写出遍历序列；理解图的连通性概念及算法；理解最小生成树、拓扑排序、最短路径的概念及算法；了解关键路径的概念及算法思想。
重点：图的存储及遍历算法，图的典型算法实现
难点：遍历及应用算法的实现
5、排序和查找
了解排序的相关概念；掌握直接插入、简单选择、冒泡、快速排序和堆排序的算法思想及实现；理解希尔、归并、基数排序的算法思想；理解各种算法的适用条件及其效率；了解线性表、树表和散列表查找的相关概念；熟练掌握顺序、折半查找算法，理解查找算法效率度量的方法，会计算查找算法的ASL值；掌握二叉排序树的构造和查找算法；了解散列函数的选取原则和常见方法，能够根据散列函数和冲突处理方法构造散列表并掌握散列表的查找算法；了解B+、B-树的概念。
重点：掌握几种常见排序算法及特点；常见查找方法的算法及适用条件。
难点：快速排序的非递归实现
三、教学方式及学时分配
四、课程其他教学环节要求
要求：课前按实验要求认真准备实验内容；课堂完成算法测试并得到正确结果，并提交程序代码（二）数据结构课程设计
要求：学生独立完成课程设计的任务，查阅相关资料、编写程序并写出说明书。
（三）作业
为提高课堂教学质量，督促学生听课，任课教师可进行适当的随堂小测试；每章讲授结束后，各留
2-3道综合题（应用题）、有实验的章节留2-3道典型算法设计题作为作业，批改后做集中讲评，讲解作业中出现的问题。
作业的题型以算法设计为主。
（四）课外
首先完成教师布置的作业，准备实验程序，及时复习；其次利用实验室开放时间进行自主学习，编写并调试实验中未完成的代码或基于基础算法的改进算法。
五、本课程与其他课程的联系
本课程的先修课是C++程序设计、离散数学，后续课程是编译原理、算法设计与分析等。
六、教学参考书目
1、数据结构（Java语言描述），刘小晶，杜选主编清华大学出版社
2、数据结构（Java版），叶核亚主编电子工业出版社
3、数据结构:Java语言描述，朱战立编著清华大学出版社
4、数据结构与算法:Java语言版/(美) Adam Drozdek著周翔, 王建芬，黄小青等译机械工业出版社
大纲撰写人：张秀梅
大纲审阅人：田莹
负责人：吴建胜。
