遵义师范学院课程教学大纲《数据结构课程》.docx

遵义师范学院课程教学大纲数据结构课程教学大纲课程编号320055适用专业一计算机大类学时数64学分数3.5执笔人及编写日期杨茂强2017年5月审核人及审核日期院别信息工程学院教研室软件工程编印日期2017年6月一、课程性质和教学目标1 .课程授课对象：计算机相关专业2 .课程性质：（专业基础课、专业选修课、公共选修课等）专业必修课。3 .在人才培养过程中的地位及作用：本课程是计算机科学与技术专业的专业基础课程之一，通过本课程的学习，使学生能够运用数据结构的思想，针对不同数据对象的特性，能够选择适当的数据结构和存储结构以及相应的算法，解决实际的问题。4 .课程教学目标：数据结构是计算机科学与技术专业本科生的一门综合性的专业基础课。本课程主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。二、课程教学内容学时分配表讲次内容学时教学形式第一讲数据结构与算法概述2讲授、提问第二讲线性表6讲授、提问、任务第三讲线性表实验2实验第四讲栈和队列6讲授、提问、讨论第五讲栈和队列实验2实验第六讲串4讲授、讨论、翻转第七讲串实验2实验第八讲数组和广义表6讲授、问答、翻转第九讲数组和广义表实验2实验第十讲树8讲授、提问、讨论第十一讲树实验4实验第十二讲图4讲授、提问、讨论第十三讲查找6讲授、提问、讨论第十四讲查找实验2实验第十五讲内部排序6讲授、提问、讨论第十六讲综合实验2实验合计64第一讲绪论2 .重难点：数据结构概念与分类，抽象数据类型，算法复杂度3 .教学目标：了解数据结构的概念和基本术语，算法的特性及其与数据结构的关系。理解算法与数据结构在程序设计中的作用。掌握抽象数据类型的表示与实现。4 .教学内容：数据结构概念与分类，抽象数据类型，算法的概念与特性，算法复杂度第二讲线性表1 .学时：6学时2 .重难点：线性表的顺序存储原理及顺序存储实现，线性表的链式存储原理及链式存储实现。3 .教学目标，了解循环链表和双向链表的操作实现。掌握线性表的逻辑结构特性，顺序存储结构和链式存储结构的描述方法。4 .教学内容：线性表的概念与性质，线性表的顺序存储原理及顺序存储的实现，线性表的链式存储原理及链式存储的实现，双向链表定义与实现，循环链表定义与实现，约瑟夫环。第三讲线性表实验1 .学时：2学时2 .实验目的：掌握线性表的基本操作和应用。3 .实验内容：编写程序，实现链表的插入、删除、查找等操作。第四讲栈和队列1 .学时：6学时2 .重难点：栈的链式存储及实现，栈的递归应用，顺序队列的实现，链式队列的实现。3 .教学目标：理解循环队列的概念和实现方。掌握栈和队列的特点，栈和队列的逻辑结构和存储结构，能利用栈实现简单的四则运算，栈的递归应用。4 .教学内容：栈的概念，栈的顺序存储和实现，栈的连式存储和实现，栈的四则运算，栈的递归应用，队列的概念，顺序队列的实现，链式队列的实现，循环队列。第五讲栈和队列实验2 .学时：2学时3 .实验目的：熟练掌握栈和队列的基本使用方法。4 .实验内容：编写程序，实现栈的入栈和出栈等操作。第六讲串2 .重难点：串的存储，串的模式匹配算法。3 .教学目标：了解串的顺序/链式存储。掌握字符串的特点与处理方法，串的基本运算和实现。4 .教学内容：串的概念，串的存储，串的模式匹配算法。第七讲串实验5 .学时：2学时2 .实验目的：掌握字符串的基本运算和实现。3 .实验内容：编写程序，实现串的模式匹配操作。第八讲数组和广义表1 .学时：6学时2 .重难点,数据的逻辑结构定义和存储方式，矩阵的存储结构，广义表的定义与存储结构,广义表的递归运算。3 .教学目标：理解特殊矩阵和稀疏矩阵的压缩存储原理。掌握二维数组的逻辑结构定义和存储方式，广义表的定义、存储结构及相关操作。4 .教学内容：数组的逻辑结构定义与存储方式，矩阵的数据类型定义与分类，矩阵的存储结构，稀疏矩阵的创建、存储及运算，广义表的定义，广义表的存储结构，广义表的递归运算。第九讲数组和广义表实验5 .学时：2学时2 .实验目的：掌握二维数组的逻辑结构定义和存储方式，广义表的定义和递归运算。3 .实验内容：编写程序，实现稀疏矩阵的各种操作。第十讲树1 .学时：8学时2 .重难点：二叉树的分类、性质、存储结构，二叉树的遍历方式，二叉树基于递归的运算线索二叉树。3 .教学目标：了解霍夫曼编码在数据压缩中的实际意义。掌握树的基本概念，二叉树的分类、性质、存储结构和相关操作的实现方法，二叉树的遍历算法，并能使用递归方式实现树的遍历，霍夫曼树的构造方法。4 .教学内容：树的基本概念，二叉树的分类、性质、存储结构，二叉树的遍历方式，二叉树基于递归的运算，二叉树的非递归遍历，二叉树与树、森林之间的转换，二叉树的构建线索二叉树，霍夫曼树的定义与构造，霍夫曼编码。第十一讲树实验5 .学时：4学时2 .实验目的：掌握二叉树的创建、遍历等相关操作。3 .实验内容：编写程序，实现二叉树的建立、遍历、求深度等相关操作。第十二讲图1 .学时：4学时2 .重难点：图的深度/广度优先遍历，最小生成树的求解算法，最短路径求解，关键路径求解。3 .教学目标：理解的定义与基本术语。掌握图的存储结构，图的深度/广度优先遍历算法，最小生成树和最短路径的求解步骤。4 .教学内容：图的定义与基本术语，图的基本操作，图的存储结构，图的遍历，最小生成树，最短路径的定义与求解，拓扑排序，关键路径。第十三讲查找1 .学时：6学时2 .重难点,顺序查找算法的原理与实现，折半查找算法的原理与实现，二叉排序树的相关操作。3 .教学目标：了解其它树表的查找原理，哈希表的相关概念和原理。掌握顺序查找算法的原理与实现，折半查找算法的原理与实现，二叉排序树的相关操作。4 .教学内容：顺序查找算法的原理与实现，折半查找算法的原理与实现，索引顺序查找，二叉排序树的相关操作，平衡二叉树的概念及操作，B树的概念及操作，哈希表的相关概念和原理。第十四讲查找实验6.学时：2学时2 .实验目的：掌握基于数据结构的多种查找方式。3 .实验内容：编写程序，实现顺序查找和二分查找等常见的查找算法。第十五讲内部排序1 .学时：6学时2 .重难点：冒泡排序，快速排序，希尔排序，堆排序，归并排序算法的原理及实现3 .教学目标：了解外部排序算法的实现方式。理解各种排序算法的特点。掌握各种排序算法的原理及实现方式。4 .教学内容：冒泡排序算法的原理及实现，快速排序算法的原理及实现，直接插入排序算法的原理及实现，折半插入排序算法的原理及实现，希尔排序算法的原理及实现，简单选择排序算法的原理及实现，堆排序算法的原理及实现，归并排序算法的原理及实现，基数排序算法的原理及实现，内部排序算法的性能比较，外部排序的存储原理与结构，外部排序算法最佳归并书。第十六讲综合实验7.学时：2学时2 .实验目的：掌握项目的分析步骤及模块划分和项目开发流程。3 .实验内容：贪吃蛇三、教学基本要求1 .备课：独立备课与集体备课相结合。2 .教学方法、教学手段：根据教学课程的内容，在教学过程中拟采取讲授法、提问法、任务驱动法、实验法、翻转课堂法等多种方法结合。3 .教学辅助资料：教材、教案、讲稿、翻转课堂、多媒体教学设备、其他辅助教学材料等。4 .课后研修：完成课后作业不少于16次（含实验），完成章节练习。6.考核：根据学生的学习情况采取灵活的考核方式（如考试、大作业、实验等）。主要是从知识面广度和深度上进行考核。期末总评成绩=平时成绩（30%）+期末考试成绩（70%）,任课教师可以根据具体情况做适当的变更。四、与其它课程的联系与分工本课程计算机科学与技术、软件工程本科专业必修的专业基础课程，也是操作系统、数据库原理、软件工程等课程的先修课程。五、建议教材及参考教材1 .数据结构与算法一一C语言版，传智播客，清华大学出版社。2 .数据结构（C语言版），严前敏，清华大学出版社。六、学生自主学习资源（网址和网络课程名称；书籍、文献、参考资料等）1 .博学谷：2 .学堂在线：3 .MooC中国: