还剩3页未读,继续阅读
文本内容:
数据结构I DataStructure I
一、课程基本情况课程类别学科基础课课程学分4学分课程总学时64学时,其中讲课44学时,实验(含上机)20学时,课外0学时课程性质必修开课学期第3学期先修课程计算机基础,C语言程序设计适用专业信息管理与信息系统教材《数据结构》,清华大学出版社,严蔚敏,2011年,C语言版开课单位经济管理学院信息管理系
二、课程性质、教学目标和任务本课程是专业必修基础课,是重要的计算机基础课程数据结构是计算机程序设计的基础,本课程的学习目的是要使学生学会分析研究所要解决的问题中涉及的数据结构的特性,并为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,培养数据抽象能力;掌握数据组织、存储和处理的常用方法;使学生掌握了解数据结构的研究内容及其重要性,掌握常用数据结构,主要包括线性结构、树形结构、图形结构,并能灵活运用;掌握顺序存储方法、链式存储方法、常用基本算法(初始化、销毁、求长度、判空、判满、插入、删除、查找、遍历、排序等)设计与评价;掌握常用的数据处理各种算法,并能灵活运用;逐步掌握算法的时间分析和空间分析的技术;训练复杂程序设计的技能;并能够编写出结构清楚和正确易读的程序,养成良好的程序设计习惯《数据结构》是一门实践性很强的课程,必须通过上机操作才能掌握所学的知识,所以要特别强调讲授与上机操作相结合,要保证学生有充分的上机条件根据实际情况安排内容,须依据师生之间共同配合与努力情况来决定在课程实验中不仅要训练计算机实验技能和操作能力,更应包括设计算法的创造性实验能力
三、教学内容和要求第1章数据结构绪论(9学时)
1.1数据结构的概念(2学时)
(1)了解数据结构的概念;
(2)理解计算机能解决的问题中存在不同的数据结构;
(3)掌握为不同的问题选择不同的数据结构进行问题的分析和解决;重点数据结构的概念;难点为应用涉及的数据选择适当的结构;L2常见的数据结构类型(1学时)
(1)了解数据结构的常见类型;
(2)理解不同数据结构类型的区别;
(3)掌握不同数据结构类型的特点重点数据结构的类型;难点区分不同的数据结构类型;
1.3抽象数据类型ADT(3学时)
(1)了解抽象数据类型的概念;
(2)理解ADT的含义;
(3)掌握不同问题的ADT定义及实现;重点ADT的概念;难点为具体问题定义ADT并实现;L4算法分析(3学时)
(1)了解算法、时间复杂度等的含义;
(2)理解算法的效率度量方法;
(3)掌握算法的特征,算法的描述;算法的时间复杂度,包括最坏和平均时间复杂度的含义;重点算法基本概念;难点算法的时间复杂度;第2章线性表(10学时)
2.1线性表的定义(3学时)
(1)了解线性结构的特点;
(2)理解线性表的ADT定义;
(3)掌握线性表的实际应用实例;重点线性表的基本概念;难点线性表的复杂操作,如合并排序等;
2.2线性表的顺序表示和实现(3学时)11)了解线性结构的两种存储方法的含义;
(2)理解线性表顺序存储方式的优缺点;
(3)掌握线性表顺序存储方式的具体实现、顺序表的元素查找、插入和删除操作及时间复杂度分析;重点线性表顺序存储方式的基本概念;难点线性表顺序存储方式的实现;
2.3线性表的链式表示和实现(4学时)
(1)了解线性表链式存储方式、循环链表、双向链表的含义;2理解线性表链式存储方式的优缺点;3掌握线性表链式存储方式的具体实现、单链表上的查找、插入和删除等基本运算的实现及时间复杂度分析;重点线性表链式存储方式的基本概念;难点线性表链式存储方式的实现;第3章栈和队列7学时
3.1栈的定义1学时1了解栈结构的特点;2理解栈结构的定义;3掌握栈结构的具体实现;重点栈的基本概念;难点栈的具体实现;
3.2栈的应用举例3学时11了解栈结构的具体应用场合;22理解栈结构的后进先出特性;33掌握栈结构的具体应用实现,如数制转换、括号匹配、迷宫求解和表达式求值等;重点栈结构的应用特点;难点栈结构的具体应用实现;
4.3队列3学时1了解队列、循环队列的定义;2理解队列的ADT定义;3掌握链队列、循环队列的表示和实现,熟练掌握入栈和出栈运算的实现;重点队列和栈的定义及基本运算;难点循环队列的具体实现;第4章数和二叉树9学时
4.1树的定义和术语1学时
4.1了解非线性结构的特点;2理解树的递归定义、常见术语;3掌握树结构的ADT定义;重点树的基本概念;难点树的ADT实现;
4.2二叉树2学时1了解二叉树的定义;
(2)理解二叉树的性质;
(3)掌握二叉树的二叉链表存储表示;重点二叉树的基本概念;难点二叉树的存储结构;
4.3遍历二叉树和线索二叉树(2学时)
(1)了解遍历二叉树、线索二叉树的概念;
(2)理解二叉树的先序、中序、后序、层序遍历的含义;
(3)掌握二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法、线索二叉树的存储结构;重点遍历二叉树、线索二叉树的基本概念;难点遍历二叉树的遍历过程实现、二叉树的线索化处理过程;
4.4树和森林(3学时)
(1)了解树的孩子表示法和双亲表示法;
(2)理解树的孩子一兄弟表示法;
(3)掌握树与二叉树的相互转化方法、树和森林的遍历;重点树的存储实现;难点树与二叉树的相互转化;
4.5赫夫曼树及其应用(1学时)
(1)了解赫夫曼树的定义;
(2)理解赫夫曼树的应用;
(3)掌握赫夫曼树的构造;重点赫夫曼树的基本概念;难点赫夫曼树的构造;第5章图(4学时)
5.1图的基本概念(1学时)
(1)了解图的定义;
(2)理解图常见的术语;
(3)掌握路径与连通的概念;重点图的基本概念;难点各种术语的含义;
5.2图的存储结构(2学时)
(1)了解图的存储结构类型;
(2)理解图的邻接表、十字链表等结构的含义;
(3)掌握图的邻接表、十字链表等结构的具体实现;重点图的各种存储结构的区别;难点图的各种存储结构的实现;
5.3图的遍历1学时1了解图的遍历含义;2理解图的深度优先遍历和广度优先遍历的含义;3掌握图的深度优先遍历和广度优先遍历算法的具体实现;重点图的各种遍历的区别;难点图的各种遍历算法的具体实现;第6章查找5学时
6.1静态查找表3学时11了解查找、查找成功的概念;2理解顺序查找的过程、索引顺序表的查找;3掌握有序表的查找,如折半查找、斐波那契查找和插值查找等方法,并进行性能分析重点顺序查找的基本概念;难点各种有序表查找方法的实现过程;
2.2动态查找表2学时1了解二叉排序树、平衡二叉树、哈希表等的概念;2理解B树的定义及查找过程;3掌握静态查找、动态查找的定义及平均查找长度的定义;重点动态查找表的含义;难点动态查找表和哈希表的应用
四、课程考核1作业等作业5次,课程论文0篇;2考核方式闭卷考试;3总评成绩计算方式平时及实验成绩占20%、期中考试成绩占20%,期末考试成绩占60%o
五、参考书目1严蔚敏、吴伟民著,《数据结构题集C语言版》,清华大学出版社,2003年;2张乃孝主编,《算法与数据结构一C语言描述》,高等教育出版社,2006年;3Mark AllenWeiss著,冯舜玺译,《数据结构与算法分析一一C语言描述》,机械工业出版社,2004年。