《数据结构》课程教学大纲(电子信息、自动化、通信专业).doc

《数据结构》课程教学大纲
（Data Structure）
一、基本信息
课程编号：B3132312
课程类别：学科基础选修课
适用层次：本科
适用专业：自动化，电子信息工程，通信工程
开课学期：第五学期
总学分：2
总学时：32学时（理论课24学时，实验课8学时）
考核方式：考查
二、课程教育目标
本课程是机电类各专业的学科基础选修课。通过本课程的学习，学生可以掌握数据结构的基本知识，学会使用合理的数据组织和清晰的算法编写效率更高的程序，积累编写复杂程序的经验，为从事软件设计工作打下坚实基础。
三、教学内容与要求
1.理论课教学内容
（1）绪论
教学内容：数据结构的原则和地位，抽象数据类型和数据结构，算法和算法的效率。
基本要求：使学生了解学习数据结构的必要性，掌握数据结构的定义。要求学生深刻认识该课程的重要地位。
教学重点：数据结构的定义，算法。
教学难点：算法。
（2）算法分析
教学内容：算法基本概念，最佳、最差和平均情况，渐近分析和程序运行时间的计算，空间代价，时间和空间权衡。
基本要求：本章的目的在于使学生了算法分析的方法 ,要求学生掌握时间和空间权衡的意义。
教学重点：算法分析的方法。
教学难点：算法分析的方法。
（3）线性表、栈和队列
教学内容：线性表，栈和队列等概念。
基本要求：本章的目的是使学生了解线性表、栈和队列及其实现方式与应用。
教学重点：线性表，栈和队列
教学难点：线性表，栈和队列的程序设计。
（4）二叉树
教学内容：二叉树定义及主要特征，周游二叉树，二叉树的实现，二叉检索树和堆的概念与应用。
基本要求：本章的目的是使学生了解二叉树、二叉检索树和堆及其实现方式，并能应用。
教学重点：二叉树。
教学难点：二叉树和堆的应用。
（5）树
教学内容：树的定义与术语，父指针表示法，树的实现，树的顺序表示法。
基本要求：本章的目的是使学生了解树及其实现方式并应用。
教学重点：树的实现。
教学难点：树的程序实现。
（6）图
教学内容：术语与表示法，图的实现，图的周游，最短路径问题。
基本要求：本章的目的是使学生了解图及其实现方式与相关算法，并应用。
教学重点：图的实现。
教学难点：图的程序实现。
（7）内排序
教学内容：排序的术语与记号、三种代价为O（n2）的排序算法、Shell 排序， 快速排序，归并排序，堆排序，基数排序，排序算法的下限。
基本要求：本章的目的是使学生了解各种排序算法。
教学重点：排序算法。
教学难点：排序算法的程序实现。
（8）检索
教学内容：检索已经排序的数组，自组织线性表，集合的检索，散列方法。
基本要求：本章的目的是使学生了解各种检索算法，并能应用。
教学重点：检索已经排序的数组。
教学难点：散列方法。
2.实验课教学内容
实验教学环节有8学时，学生应掌握常见数据结构的程序设计方法。详见《数据结构》课程实验教学大纲。
四、作业、练习的安排与要求
重点课节应安排课后作业。学生应做大量的课外上机练习。
五、学时分配
序号
主 要 内 容
各个教学环节学时分配
备 注
理论课
实验课
习题课
讨论课
小计
1
绪论
2
详见实验大纲

2
算法分析
2

3
线性表、栈和队列
4

4
二叉树
2

5
树
2

6
图
4

7
排序
4

8
检索
4

合计
24
8

32

六、相关联的课程
1.预修课程
计算机程序设计基础、高级程序设计。
七、教材与教学参考书
1.建议教材
[1] 数据结构.刘大有.高等教育出版社
2.建议参考书目
[1] C++程序设计教程.钱能.清华大学出版社
[2] 数据结构.严蔚敏.清华大学出版社
[3] 数据结构.张乃孝.高等教育出版社
八、成绩评定
本课程考核方式为考查。主要根据平时成绩和实验成绩确定学生的成绩，建议比例为：
考勤成绩：20％
平时作业：40％
实验成绩：40％