《数据结构Ⅰ》课程教学大纲.docx

数据结构I
Data Structure 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并实现；L 4算法分析（3学时）
（1）了解算法、时间复杂度等的含义；
（2）理解算法的效率度量方法；
（3）掌握算法的特征，算法的描述；算法的时间复杂度，包括最坏和平均时间复杂度的含 义；
重点：算法基本概念；
难点：算法的时间复杂度；第2章线性表（10学时）
2.1 线性表的定义（3学时）
（1） 了解线性结构的特点；
（2）理解线性表的ADT定义;
（3）掌握线性表的实际应用实例；
重点：线性表的基本概念；
难点：线性表的复杂操作，如合并排序等；2线性表的顺序表示和实现（3学时）
1 1） 了解线性结构的两种存储方法的含义；
（2）理解线性表顺序存储方式的优缺点；
（3）掌握线性表顺序存储方式的具体实现、顺序表的元素查找、插入和删除操作及时间复 杂度分析；
重点：线性表顺序存储方式的基本概念；
难点：线性表顺序存储方式的实现；.3线性表的链式表示和实现（4学时）
（1）了解线性表链式存储方式、循环链表、双向链表的含义；
(2)理解线性表链式存储方式的优缺点；
(3)掌握线性表链式存储方式的具体实现、单链表上的查找、插入和删除等基本运算的实 现及时间复杂度分析；
重点：线性表链式存储方式的基本概念；
难点：线性表链式存储方式的实现；第3章栈和队列(7学时)
3. 1栈的定义(1学时)
(1) 了解栈结构的特点；
(2)理解栈结构的定义；
(3)掌握栈结构的具体实现；
重点：栈的基本概念；
难点：栈的具体实现；2栈的应用举例(3学时)
1 1) 了解栈结构的具体应用场合；
2 2)理解栈结构的后进先出特性；
3 3)掌握栈结构的具体应用实现，如数制转换、括号匹配、迷宫求解和表达式求值等； 重点：栈结构的应用特点；
难点：栈结构的具体应用实现；.3队列(3学时)
(1) 了解队列、循环队列的定义；
(2)理解队列的ADT定义;
(3)掌握链队列、循环队列的表示和实现，熟练掌握入栈和出栈运算的实现；
重点：队列和栈的定义及基本运算；
难点：循环队列的具体实现；第4章数和二叉树(9学时)
2. 1树的定义和术语(1学时)
2.1 了解非线性结构的特点；
(2)理解树的递归定义、常见术语；
(3)掌握树结构的ADT定义；
重点：树的基本概念；
难点：树的ADT实现；二叉树(2学时)
(1)了解二叉树的定义；
（2）理解二叉树的性质；
（3）掌握二叉树的二叉链表存储表示；
重点：二叉树的基本概念；
难点：二叉树的存储结构；遍历二叉树和线索二叉树（2学时）
（1） 了解遍历二叉树、线索二叉树的概念；
（2）理解二叉树的先序、中序、后序、层序遍历的含义；
（3）掌握二叉树的先序、中序、后序、层序遍历过程及相应的遍历算法、线索二叉树的存 储结构；
重点：遍历二叉树、线索二叉树的基本概念；
难点：遍历二叉树的遍历过程实现、二叉树的线索化处理过程；树和森林（3学时）
（1） 了解树的孩子表示法和双亲表示法；
（2）理解树的孩子一兄弟表示法；
（3）掌握树与二叉树的相互转化方法、树和森林的遍历；
重点：树的存储实现；
难点：树与二叉树的相互转化赫夫曼树及其应用（1学时）
（1）了解赫夫曼树的定义；
（2）理解赫夫曼树的应用；
（3）掌握赫夫曼树的构造；
重点：赫夫曼树的基本概念；
难点：赫夫曼树的构造；第5章 图（4学时）
5.1图的基本概念（1学时）
（1）了解图的定义；
（2）理解图常见的术语；
（3）掌握路径与连通的概念；
重点：图的基本概念；
难点：各种术语的含义；2图的存储结构（2学时）
（1） 了解图的存储结构类型；
（2）理解图的邻接表、十字链表等结构的含义；
（3）掌握图的邻接表、十字链表等结构的具体实现；
重点：图的各种存储结构的区别；
难点：图的各种存储结构的实现；3图的遍历(1学时)
(1) 了解图的遍历含义；
(2)理解图的深度优先遍历和广度优先遍历的含义；
(3)掌握图的深度优先遍历和广度优先遍历算法的具体实现；
重点：图的各种遍历的区别；
难点：图的各种遍历算法的具体实现；第6章查找(5学时)
3. 1静态查找表(3学时)
1 1) 了解查找、查找成功的概念；
(2)理解顺序查找的过程、索引顺序表的查找；(3)掌握有序表的查找，如折半查找、斐波那契查找和插值查找等方法，并进行性能分析。 重点：顺序查找的基本概念；
难点：各种有序表查找方法的实现过程；.2动态查找表(2学时)
(1)了解二叉排序树、平衡二叉树、哈希表等的概念；
(2)理解B树的定义及查找过程；
(3)掌握静态查找、动态查找的定义及平均查找长度的定义；
重点：动态查找表的含义；
难点：动态查找表和哈希表的应用。
四、课程考核
(1)作业等：作业：5次，课程论文：0篇；
(2)考核方式：闭卷考试；
(3)总评成绩计算方式：平时及实验成绩占20%、期中考试成绩占20%,期末考试成绩占 60%o五、参考书目
(1)严蔚敏、吴伟民著，《数据结构题集(C语言版)》，清华大学出版社，2003年；
(2)张乃孝主编，《算法与数据结构一C语言描述》，高等教育出版社，2006年；
(3) Mark Allen Weiss著，冯舜玺译，《数据结构与算法分析一一C语言描述》，机械工业 出版社，2004年。