数据结构课程教学大纲.doc

辽宁科技大学课程教学大纲课程名称：数据结构英文名称：Data Structures课程编号：x2050661学 时 数：80其中实验（实训）学时数：20 课外学时数：0学 分 数：5.0适用专业：软件工程、网络工程一、课程的性质和任务数据结构是软件工程、网络工程专业的专业基础课，也是培养计划课程体系中的一门核心课程，同时也是计算机相关专业的研究生入学考试的专业课程之一。本课程围绕数据结构的逻辑结构、存储结构和算法实现三个方面，详尽介绍常见的线性表、栈、队列、串、数组、树和二叉树、图等结构的存储实现和基本运算以及常见的排序和查找方法的数据存储及算法实现。要求学生能够根据实际问题的需要，确定逻辑结构并选择合适的存储结构，实现计算机中的表示，设计相关算法，并了解常见算法时空效率。培养学生程序调试能力、算法设计与分析能力、创新能力和自学能力，能够编写结构清晰、正确易懂，符合软件工程规范的程序，建立数据结构的概念，为后续课程的学习及软件开发打好基础。二、课程教学内容的基本要求、重点和难点1、绪论掌握数据元素、逻辑结构、存储结构等基本概念；理解算法的定义、描述方法及算法分析方法；了解数据结构课程的研究对象和课程体系。重点：数据结构的概念及算法描述方法。难点：算法的效率度量。2、线性结构掌握线性表的逻辑结构；理解线性表的顺序存储，链式存储实现；熟练掌握基于顺序存储和链式存储的线性表的插入、删除、查找、逆置等基本算法和线性表的分解、合并等应用算法；理解栈和队列的定义及动态思想；掌握栈、队列的顺序存储、链式存储实现和基于存储的基本算法；理解栈与递归的关系及递归算法的设计原则；掌握栈、队列的应用问题：利用栈实现非递归算法设计、括号匹配、表达式求值等；了解串的定义及存储实现，掌握串的模式匹配算法；了解数组的定义，掌握特殊矩阵（对称矩阵、三角矩阵）的压缩存储实现；重点：线性表的基本算法及应用，栈、队列的基本算法。难点：栈与递归的关系。3、树了解树、二叉树的基本概念、性质；掌握二叉树的顺序存储和二叉链表、线索链表的存储实现；熟练掌握二叉树的先序、中序、后序、层次遍历算法及基于顺序存储、二叉链表存储的算法实现（含利用栈实现的非递归算法） ；掌握二叉树的递归算法的设计原则和二叉树的递归算法（如求叶子个数，计算树的高度等） ；理解树的遍历及存储实现；理解树与二叉树的转换关系；掌握哈夫曼树的概念、构造算法及编码。重点：二叉树的存储实现，遍历算法及应用算法；哈夫曼编码算法难点：二叉树递归算法的理解及如何利用栈实现非递归算法 4、图了解图的定义及相关术语；掌握图的邻接矩阵、邻接表的存储实现；熟练掌握图的遍历算法的思想及其实现，并能够基于存储结构写出遍历序列；理解图的连通性概念及相关算法；理解最小生成树、拓扑排序、最短路径的概念及算法；了解关键路径的概念及算法思想。重点：图的存储及遍历算法，图的典型应用算法：Prim 算法、拓扑排序算法等难点：图的遍历及应用算法的实现5、排序和查找 了解排序的相关概念：关键字，稳定与不稳定排序，算法效率度量；熟练掌握直接插入、简单选择、冒泡、快速排序和堆排序的算法思想及实现；理解希尔、归并、基数排序的算法思想及实现；理解各种算法的适用条件及其效率；了解线性表、树表和散列表查找的相关概念及适用条件；理解查找算法效率度量的方法；熟练掌握顺序查找、折半查找算法及效率；掌握二叉排序树的构造和查找等算法；了解 AVL 树的定义及平衡调整规则；了解散列函数的选取原则和常见方法，掌握散列表的线性探测法和链地址法冲突处理方法，能够根据散列函数和冲突处理方法构造散列表并掌握散列表的插入、查找等算法；了解B+、B-树的概念。重点：常见排序算法（快速、直接插入、冒泡、堆等）的每趟排序步骤及算法实现；常见的查找方法（折半查找、BST 树查找、散列表查找）的算法实现及适用条件。难点：快速排序的非递归实现、堆排序算法、AVL 树的平衡调整规则三、教学方式及学时分配序号 主要内容 主要教学方式 学时分配 辅导答疑比例一 绪论 讲授 2 2 ：1二 线性表 讲授+实验 12+4 2 ：1三 栈、队列和串、广义表 讲授+实验 10+2 2 ：1四 树和二叉树 讲授+实验 10+4 2 ：1五 图 讲授+实验 10+2 2 ：1六 查找技术 讲授+实验 8+2 2 ：1七 排序技术 讲授+实验 8+2 2 ：1八 创新性实验 实验 4 2 ：1四、课程其他教学环节要求1、实验环节序号 实验题目 实验内容 学时 实验类别1 线性表顺序表、链表的基本相关操作和应用操作（有序表的插入、链表合并、分解、约瑟夫问题求解，一元多项式相加等）4 设计性2 栈和队列 栈、队列的基本运算、括号匹配、回文匹配、表达式求值等 2 设计性3 二叉树二叉树的构造、各种遍历、计算高度、叶子等和哈夫曼树的构造、编码、计算 WPL 值4 设计性4 图 图的非递归遍历算法、图的连通性、拓扑排序等 2 设计性5 查找、排 序折半查找、二叉排序树的查找、散列查找算法实现及效率比较，实现常见的排序算法的实现及效率比较4 综合性6 创新实验在已学过的查找、排序算法基础上，改进或设计新的排序、查找算法；学生管理系统4 创新性要求：所有实验项目均配置在在线评测系统软件平台上，要求学生注册账号，按时完成实验项目，并提交。每次实验结束，部分学生参与实验答辩。2、数据结构课程设计要求：学生独立完成课程设计的任务，查阅相关资料、编写程序并写出说明书。详见课程设计说明书。3、作业为提高课堂教学质量，督促学生听课，任课教师可在下课前进行适当的随堂测试；每章讲授结束后，至少留 2-3 道综合题、有实验的章节留 2-5 道典型算法设计题作为课后作业，要求学生独立完成，教师批改后针对问题做集中讲评。4、课外独立完成作业，认真准备实验（源程序代码、测试数据等），及时复习和预习；利用实验室开放时间进行自主学习，编写并调试实验中未完成的代码或基于基础算法的改进及创新。鼓励优秀学生参加学院 ACM 竞赛小组。五、本课程与其他课程的联系本课程的先修课程是C+程序设计 ，后续课程是算法设计与分析 、Java 程序设计等。六、教学参考书目1、数据结构（C+版）第二版，王红梅等，清华大学出版社，2011.72、数据结构（C+版）学习辅导与实验指导，王红梅等，清华大学出版社，20011.73、数据结构（C 语言版），严蔚敏等，清华大学出版社，2007.74、数据结构与程序设计（C+语言描述） 影印版，高等教育出版社，Robert L. Kruse 2008.1大纲撰写人：马云吉 大纲审阅人：迟呈英负 责 人：吴建胜