数据结构课程教学大纲

数据结构课程教学大纲课程英文名称：DataOrganization课程编号：0500600学分:32+16（实验）学时:3.0一、课程教学对象数学与计算科学学院信息与计算科学专业的本科学生。二、课程性质及教学目的课程性质：本课程是数学与计算科学学院信息与计算科学本科专业的核心专业课。课程包括理论教学（32学时）和课内实验（16学时）两个环节。目的和任务：使学生获得计算机科学各领域的数据结构知识及有关的应用软件所要用到的各种数据结构知识；从数据结构及其实现的角度系统地学习和掌握常用基本数据结构及其不同的实现方法，了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同算法实现的原则和方法，为后继课程的学习打下良好的基础，♦掌握常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识；提高软件设计和编程技能。学会初步对不同的存储结构和相应算法的对比，有一定的算法改进能力。通过学习本门课程，学生应该了解典型的数据结构与算法的关系；应该具有结合实际应用，设计出高效算法和数据结构的能力；初步具备结合专业应用，将数据结构知识用于专业程序设计中的能力。本课程是一门实践性较强的课程。学生应结合理论教学的进度，通过对本课程的知识传递、算法设计和上机实践的训练，进一步加深对数据结构和算法的理解，培养学生的数据抽象能力、逻辑思维能力和程序设计的能力，提高分析问题和解决问题的能力和实际动手能力。该课程概念性、实践性很强，教学中强调理论联系实际，并结合现代计算机技术，在教学方法与手段方面进行改革。三、对先修知识的要求C++程序设计、离散数学等四、课程的主要内容、基本要求和学时分配建议（总学时数:理论课32学时）知识模块知识点要求学时学习方式课外学习要求1、绪论1.1数据结构的基本概念C1课堂讲授1.2算法计算法分析C1课堂讲授2、线性表2.1线性表的逻辑结构B1课堂讲授2.2线性表的顺序存储结构及实现A1课堂讲授2.3线性表的链接存储结构及实现A1课堂讲授2.4顺序表和单链表的比较B1课堂讲授2.5线性表的其他存储方式C1课堂讲授2.6应用举例C1课堂讲授3、特殊线性表栈、队列和串3.1栈A1课堂讲授3.2队列B1课堂讲授3.3串B1课堂讲授3.4应用举例C1课堂讲授4、广义线性4.1多维数组B1课堂讲授表——多维数组和广义表4.2矩阵的压缩存储B1课堂讲授4.3广义表B1课堂讲授4.4应用举例C1课堂讲授5、树和二叉树5.1树的逻辑、存储结构B1课堂讲授5.2二叉树的逻辑结构B1课堂讲授5.3二叉树的存储结构及实现A1课堂讲授5.4应用举例C1课堂讲授6、图6.1图的逻辑结构B1课堂讲授6.2图的存储结构及实现A1课堂讲授6.3图的连通性B1课堂讲授6.4应用举例C1课堂讲授7、查找技术7.1概述C1课堂讲授7.2线性表的查找技术A1课堂讲授7.3树表的查找技术B1课堂讲授7.4散列表的查找技术A课堂讲授8、排序技术8.1插入排序A1课堂讲授8.2交换排序B1课堂讲授8.3选择排序A1课堂讲授8.4归并排序C1课堂讲授五、建议使用教材及参考书I、理论课教材：王红梅，胡明，王涛等.数据结构（C++版）[M].北京：清华大学出版社，2005.72、实验课教材：王红梅，胡明，王涛等.数据结构（C++版）学习辅导与实验指导[M].北京：清华大学出版社，2005.93、主要参考书：[1]严蔚敏，吴伟民.数据结构[M].北京清华大学出版社,1997[2]齐得昱.数据结构与算法[M].北京：清华大学出版社，2003[3]辛运帏，刘憬等.数据结构与算法[M].北京：高等教育出版社,2006[4]傅清祥，王晓东.算法与数据结构[M].北京：电子工业出版社，2001[5]陈慧南.数据结构与算法一C++语言描述.[M].高等教育出版社，2005六、课程考核方式以闭卷考试为主，结合平时成绩和上机实验报告评定成绩。其中平时成绩占10%(含作业和考勤)，上机实验报告占20%,期末笔试考试成绩占70%。七、课内实验环节及要求(16学时)序号实验项目实验内容实验目的及要求学时1基础实验(1)在一维整型数组中顺序查找与给定值相等的元素(2)在一个数组中确定第k小的元素(至少采用两种方法求解)(1)比较顺序查找最好、最坏和平均的时间性能(2)比较解决相同问题的不同算法的时间性能22线性表实验(1)建立含有若干个元素的顺序表(2)用头插法(或尾插法)建立带头结点的单链表(3)对已建立的顺序表、(1)掌握线性表的的顺序及链接存储结构(2)验证顺序表、单链表及其基本操作的实现(3)掌握数据结构及算法的2单链表实现插入、删除、查找等基本操作程序实现的基本方法3特殊线性表——栈、队列和串实验(1)建立一个空栈，对已建立的栈进行插入、删除、取栈顶元素等基本操作(2)建立一个空队列，对已建立的队列进行插入、删除、取队头元素等基本操作(3)创建两个串，采用顺序存储，并实现串的插入、删除、求子串等基本操作(1)掌握栈的顺序存储、队列的链接存储及串的顺序存储结构(2)掌握栈、队列、串的操作特性(3)掌握基于顺序栈、链队列及顺序串的基本操作的实现方法24广义线性表——多维数组和广义表实验(1)建立一个n*n的对称矩阵，并用一维数组存储(2)采用头尾表示法建立广义表并求其深度(1)掌握对称矩阵的压缩存储方法及寻址方法(2)掌握广义表的逻辑结构、头尾表示法存储结构及其基本操作在头尾表示法上的实现方法25树和二叉树实验(1)采用孩子兄弟表示法建立一棵树，并实现树的前序遍历操作(2)建立一颗含有n个结点的二叉树，采用二叉链表存储，前序(或中序、后序)遍历该二叉树(1)掌握树的逻辑结构及孩子兄弟存储结构(2)掌握基于树的孩子兄弟存储结构的遍历方法(3)掌握二叉树的逻辑结构及二叉链表存储结构(4)掌握基于二叉链表存储的二叉树的遍历操作的实现26图实验(1)建立一个无向图的邻接矩阵存储，对其进行深度优先、广度优先遍历(2)建立一个有向图的邻接表存储结构，对其进行深度优先、广度优先遍历(1)掌握图的逻辑结构、邻接矩阵存储结构及邻接表存储结构(2)掌握图在邻接矩阵存储结构下和邻接表存储结构下遍历算法的实现27查找技术试验(1)对给定的数组，利用顺序查找算法，查找数组中与给定值相等的元素(2)对给定的一组无序序歹IJ,建立一颗二叉排序树，并对建立的二叉排序树实现查找操作(3)对给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表，并设计一个查找算法，验证查找性能(1)掌握顺序查找算法、折半查找算法的基本思想、实现方法及时间性能(2)掌握二叉排序树的定义、特性、建立方法及查找性能，并实现基于二叉排序