辽宁科技大学课程教学大纲课程名称：数据结构英文名称：DataStructures课程编号：x学时数：80其中实验（实训）学时数：20课外学时数：0学分数：5.0适用专业：软件工程、网络工程一、课程的性质和任务数据结构是软件工程、网络工程专业的专业基础课，也是培养计划课程体系中的一门核心课程，同时也是计算机相关专业的研究生入学考试的专业课程之一。本课程围绕数据结构的逻辑结构、存储结构和算法实现三个方面，详尽介绍常见的线性表、栈、队列、串、数组、树和二叉树、图等结构的存储实现和基本运算以及常见的排序和查找方法的数据存储及算法实现。要求学生能够根据实际问题的需要，确定逻辑结构并选择合适的存储结构，实现计算机中的表示，设计相关算法，并了解常见算法时空效率。培养学生程序调试能力、算法设计与分析能力、创新能力和自学能力，能够编写结构清晰、正确易懂，符合软件工程规范的程序，建立数据结构的概念，为后续课程的学习及软件开发打好基础。二、课程教学内容的基本要求、重点和难点1、绪论掌握数据元素、逻辑结构、存储结构等基本概念；理解算法的定义、描述方法及算法分析方法；了解《数据结构》课程的研究对象和课程体系。重点：数据结构的概念及算法描述方法。难点：算法的效率度量。2、线性结构掌握线性表的逻辑结构；理解线性表的顺序存储，链式存储实现；熟练掌握基于顺序存储和链式存储的线性表的插入、删除、查找、逆置等基本算法和线性表的分解、合并等应用算法；理解栈和队列的定义及动态思想；掌握栈、队列的顺序存储、链式存储实现和基于存储的基本算法；理解栈与递归的关系及递归算法的设计原则；掌握栈、队列的应用问题：利用栈实现非递归算法设计、括号匹配、表达式求值等；了解串的定义及存储实现，掌握串的模式匹配算法；了解数组的定义，掌握特殊矩阵（对称矩阵、三角矩阵）的压缩存储实现；重点：线性表的基本算法及应用，栈、队列的基本算法。难点：栈与递归的关系。3、树了解树、二叉树的基本概念、性质；掌握二叉树的顺序存储和二叉链表、线索链表的存储实现；熟练掌握二叉树的先序、中序、后序、层次遍历算法及基于顺序存储、二叉链表存储的算法实现（含利用栈实现的非递归算法）；掌握二叉树的递归算法的设计原则和二叉树的递归算法（如求叶子个数，计算树的高度等）；理解树的遍历及存储实现；理解树与二叉树的转换关系；掌握哈夫曼树的概念、构造算法及编码。重点：二叉树的存储实现，遍历算法及应用算法；哈夫曼编码算法难点：二叉树递归算法的理解及如何利用栈实现非递归算法4、图了解图的定义及相关术语；掌握图的邻接矩阵、邻接表的存储实现；熟练掌握图的遍历算法的思想及其实现，并能够基于存储结构写出遍历序列；理解图的连通性概念及相关算法；理解最小生成树、拓扑排序、最短路径的概念及算法；了解关键路径的概念及算法思想。重点：图的存储及遍历算法，图的典型应用算法：Prim算法、拓扑排序算法等难点：图的遍历及应用算法的实现5、排序和查找了解排序的相关概念：关键字，稳定与不稳定排序，算法效率度量；熟练掌握直接插入、简单选择、冒泡、快速排序和堆排序的算法思想及实现；理解希尔、归并、基数排序的算法思想及实现；理解各种算法的适用条件及其效率；了解线性表、树表和散列表查找的相关概念及适用条件；理解查找算法效率度量的方法；熟练掌握顺序查找、折半查找算法及效率；掌握二叉排序树的构造和查找等算法；了解AVL树的定义及平衡调整规则；了解散列函数的选取原则和常见方法，掌握散列表的线性探测法和链地址法冲突处理方法，能够根据散列函数和冲突处理方法构造散列表并掌握散列表的插入、查找等算法；了解B+、B-树的概念。重点：常见排序算法（快速、直接插入、冒泡、堆等）的每趟排序步骤及算法实现；常见的查找方法（折半查找、BST树查找、散列表查找）的算法实现及适用条件。难点：快速排序的非递归实现、堆排序算法、AVL树的平衡调整规则三、教学方式及学时分配序号主要内容主要教学方式学时分配辅导答疑比例一绪论讲授22：1二线性表讲授+实验12+42：1三栈、队列和串、广义表讲授+实验10+22：1四...
