数据结构(信管)教学大纲

1、数据结构教学大纲课程代码：040631703课程英文名称：Data Structure课程总学时：48 讲课： 40 实验： 0 上机： 8适用专业：信息管理与信息系统大纲编写（修订）时间：2017.06一、大纲使用说明（一）课程的地位及教学目标本课程是信息管理与信息系统专业的一门重要的专业基础课, 它较详细地阐述了使用计算机解决具体问题时，所建立的数学模型的逻辑结构与存储结构的多种类型，以及对数据进行具体操作的算法实现。通过本课程的学习，使学生了解和掌握使用高级语言编程时组织数据的基本理论和方法，是学生进一步学习其他专业课程的必备基础。通过本课程的学习，学生将达到以下要求：1 了解数据结构及

2、其分类、数据结构与算法的密切关系；2 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；3 掌握设计算法的步骤和算法分析的方法；4 掌握数据结构在排序和查找等常用算法中的应用。（二）知识、能力及技能方面的基本要求要求学生了解各种形式多样的客观问题中所涉及的数据对象可通过适当的分解，从而可以对应几种数据结构。学生应该能够使用高级语言正确定义数据的逻辑结构和选择有效的存储结构，以解决具体问题。其操作的实现算法应注重时间效率和空间效率。对数据对象的查找与排序操作时较常用的基本操作，学生应掌握基本的算法，并学会合理使用。（三）实施说明1 教学方法：本课程对学生的动手能力要求较强，应配置

3、相应的上机实验。使学生在编程的训练中，真正掌握算法的实现方法。在教师的讲解过程中应深入浅出、循序渐进、联系实际、结合实例，才能收到较好的效果。应培养学生良好的算法设计思想、方法与技巧，强化程序抽象能力与数据抽象能力。2 教学手段：本课程属于专业基础课，在教学中采用多媒体教学为主，辅以板书讲解。确保在有限的学时内，全面、高质量地完成课程教学任务。（四）对先修课的要求要求学生有计算机程序设计基础知识与编程经验。（五）对习题课、实践环节的要求1 对重点、难点章节（如：线性表的链表实现、二叉树的遍历、图的存储结构和遍历、排序算法的实现等）应安排习题课。2 课后作业要少而精，内容要多样化，作业题内容必须

4、包括基本概念、基本算法理论及设计方面的内容，作业要能起到巩固理论，掌握数据结构算法的分析和设计技巧。对作业中的重点、难点，课上应做必要的提示，并适当安排课内讲评作业。学生必须独立、按时完成课外习题和作业，作业的完成情况应作为评定课程成绩的一部分。3 每个学生要完成大纲中规定的必修上机实验，通过实验环节，学生应掌握典型数据结构的设计及实现方法。实验成绩作为评定课程成绩的一部分。（六）课程考核方式1 .考核方式：考试。2 .考核目标：在考核学生对数据结构基本知识、算法的理论和设计方法的基础上，重点考核学生的问题分析能力和算法设计能力。3 .成绩构成：本课程的总成绩主要由三部分组成：平时成绩（包括中

5、期考试、作业、小测验、提问、出勤情况等）占 10%实验成绩占20%期末考试成绩占70%平时成绩由任课教师视具体情况按百分制给出；实验成绩由实验老师参照相关规定按百分制给出，实验无成绩或实验不及格，取消期末考试资格，总成绩直接以不及格计。（七）主要参考书目：数据结构（C语言版）严蔚敏 清华大学出版社2013.4数据结构李筠，姜学军清华大学出版社2008.8二、中文摘要本课程是信息管理与信息系统专业学生必修的一门专业基础课程。通过对本课程的讲授， 使得学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结 构、存储结构及其相应的算法。课程主要内容包括数据结构基本概念、线性

6、表、栈和队列、串、 数组和广义表、树和二叉树、图、查找、排序等。本课程将为后续课程的学习以及毕业设计奠定 重要的基础。三、课程学时总体分配表序号教学内容学时讲课实验上机1绪论222线性表8623栈和队列6424串445数组和广义表446树和二叉树10827图448查找449内部排序642合计48408四、教学内容及基本要求第1部分绪论总学时（单位：学时）:2讲课:2 实验:0上机:0具体内容：1） 基本概念与术语2）抽象数据类型的表示与实现3）算法与算法分析重 点：有关数据结构中的基本概念难点：算法的描述方法习题：算法时间复杂度的计算第 2 部分 线性表总学时 (单位：学时):8 讲课 :6

7、实验 :0 上机 :2具体内容：1) 线性表的类型定义2) 线性表的顺序表示和实现3) 线性表的链式表示和实现4) 循环链表和双向链表重点:顺序存储结构、链式存储结构、双向链表的特点，双向链表的类型定义及相关操作的实现难点:顺序表的插入删除算法中数据元素的移动链表的插入与删除算法习题:顺序表和各种链表的插入和删除操作实验:线性表的应用实验(2 学时)第 3 部分 栈和队列总学时 (单位：学时):6 讲课 :4 实验 :0 上机 :2具体内容：1) 栈概念2) 栈的基本运算3) 栈的表示和实现4) 队列的基本运算5) 队列的顺序存储结构6) 队列的链式存储结构重 点:堆栈和队列的各种运算方法难

8、点:链式存储结构及其实现方法习题:栈和队列的基本操作实验:栈应用实验(2 学时)第 4 部分 串总学时 (单位：学时):4 讲课 :4 实验 :0 上机 :0具体内容：1) 串类型的定义2) 串的表示和实现3) 串的模式匹配算法4) 串操作应用举例重点:基本概念和存储结构难点:串的模式匹配第 5 部分 数组和广义表总学时 (单位：学时):4 讲课 :4 实验 :0 上机 :0具体内容：1) 数组的定义2) 数组的顺序表示和实现3) 矩阵的压缩存储4) 广义表的定义5) 广义表的存储结构重点:数组的几种常用表示方法、矩阵的存储、广义表的存储结构方法难点:广义表的存储结构方法第 6 部分 树和二叉

9、树总学时 (单位：学时):10 讲课 :8 实验 :0 上机 :2具体内容：1) 二叉树的定义和性质2) 二叉树的存储结构3) 遍历二叉树4) 线索二叉树5) 树和森林重 点:二叉树的定义和性质，遍历二叉树难点:线索二叉树习题:二叉树的遍历，树与二叉树的转换实 验:实现二叉树的遍历实验(2 学时)第 7 部分 图总学时(单位：学时):4 讲课 :4 实验 :0 上机 :0具体内容：1) 图的定义和术语2) 图的存储结构3) 图的遍历4) 图的连通性重 点:图的存储结构，图的遍历难点:图的遍历，最小生成树习题:图的存储表示及遍历算法第 8 部分 查找总学时 (单位：学时):4讲课 :4实验 :0 上机 :0具体内容：1) 顺序表的查找2) 有序表的查找3) 动态查找表4) 哈希表重 点:有序表的查找，动