《数据结构与算法》课程教学大纲

1、数据结构与算法课程教学大纲课程代码课程名称数据结构与算法Data Structure课程基本情况1、学分： 4.5 学时：80 （理论学时：64 实验学时：16）2、课程性质：学科专业基础课3、适用专业：计算机科学与技术专业、计算机软件工程专业 4、适用对象：本科5、先修课程：计算机语言(C) 6、教材与参考书目：数据结构(C语言版)，严蔚敏 吴伟民，清华大学出版社，1997数据结构(用面向对象方法与C+描述) ，殷人昆，清华大学出版社，1998C+数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译， 清华大学出版社，2004 算机算法设计与分

2、析（第2版），王晓东， 电子工业出版社， 20047、考核方式：考试、闭卷 平时成绩3040、期终考试6070 8、教学环境：课堂、多媒体，实验室课程教学目的数据结构是计算机程序设计的重要理论基础。也是计算机专业教学中的核心专业基础课程。它所讨论的知识内容和提倡的技术方法，对进一步学习计算机领域的其他课程、从事软件工程的开发，都有着不可替代的作用。是从事计算机科学研究及应用的科技人员必须具备的重要基础知识。课程内容、学时分配及教学基本要求1 绪论 （4学时）1.1什么是数据结构 （理解）1.2基本概念和术语 （掌握）1.3抽象数据类型的表示与实现 （了解）1.4算法和算法分析 1.4.1算法

3、（掌握）1.4.2算法设计的要求 （掌握）1.4.3算法效率的度量 （掌握）1.4.4算法的存储空间需求（理解） 2 线性表 （6+4学时）2.l线性表的类型定义 （掌握）2.2线性表的顺序表示和实现 （掌握）2.3线性表的链式表示和实现2.3.1线性链表（掌握）2.3.2循环链表（掌握）2.3.3双向链表（掌握）课程内容、学时分配及教学基本要求2.4一元多项式的表示及相加（理解）3 栈和队列 （6+2学时）3.1栈 （掌握）3.1.l抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例（了解）3.2.1数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解

4、 3.2.5表达式求值 3.3栈与递归的实现 （了解）3.4队列 3.4.1抽象数据类型队列的定义 （掌握）3.4.2链队列-队列的链式表示和实现 （掌握）3.4.3循环队列-队列的顺序表示和实现 （掌握）3.5离散事件模拟 （了解）4 串 （4+2学时）4.1串类型的定义 （掌握）4.2串的表示和实现 4.2.1定长顺序存储表示 （掌握）4.2.2堆分配存储表示 （了解）4.2.3串的块链存储表示 （了解）4.3串的模式匹配算法 （理解）4.3.l求子串位置的定位函数Index（S,T,pos） 4.3.2模式匹配的一种改进算法 4.4串操作应用举例 （理解）4.4.1文本编辑 4.4.2建

5、立词索引表5 数组和广义表（4学时）5.1数组的定义 （掌握）5.2数组的顺序表示和实现 （掌握）5.3矩阵的压缩存储 （理解）5.3.l特殊矩阵 （理解）5.3.2稀疏矩阵 （理解）5.4广义表的定义 （掌握）5.5广义表的存储结构 （理解）5.6 m元多项式的表示（了解）5.7广义表的递归算法 （了解）5.7.1求广义表的深度 5.7.2复制广义表 课程内容、学时分配及教学基本要求5.7.3建立广义表的存储结构 6 树和二叉树 （10+2学时）6.1树的定义和基本术语 （掌握）6.2二叉树 （掌握）6.2.1二叉树的定义 6.2.2二叉树的性质 6.2.3二叉树的存储结构 6.3遍历二叉树

6、和线索二叉树 6.3.1遍历二叉树 （掌握）6.3.2线索二叉树 （理解）6.4树和森林 （理解）6.4.1树的存储结构 6.4.2森林与二叉树的转换 6.4.3树和森林的遍历 6.5树与等价问题（理解）6.6赫夫曼树及其应用 （掌握）6.6.1最优二叉树（赫夫曼树） 6.6.2赫夫曼编码 6.7回溯法与树的遍历 （理解）6.8树的计数 （了解）7 图（10+2学时）7.1图的定义和术语 （掌握）7.2图的存储结构 （掌握）7.2.1数组表示法 （掌握）7.2.2邻接表 （掌握）7.2.3十字链表 （理解）7.2.4邻接多重表 （理解）7.3图的遍历 7.3.l深度优先搜索 （掌握）7.3.2

7、广度优先搜索 （掌握）7.4图的连通性问题 7.4.1无向图的连通分量和生成树（理解）7.4.2有向图的强连通分量（理解）7.4.3最小生成树 （掌握）7.4.4关节点和重连通分量 （了解）7.5有向无环图及其应用 （了解）7.5.1拓扑排序 7.5.2关键路径 7.6最短路径（掌握）7.6.1从某个源点到其余各项点的最短路径 7.6.2每一对顶点之间的最短路径 课程内容、学时分配及教学基本要求8 查找（10+2学时）8.1静态查找表 （掌握）8.1.l顺序表的查找 （掌握）8.1.2有序表的查找 （掌握）8.1.3静态树表的查找（掌握）8.1.4索引顺序表的查找（掌握）8.2动态查找表 （了

8、解）8.2.1二叉排序树和平衡二叉树 8.2.2 B- 树和B+树8.2.3键树 8.3哈希表 （理解）8.3.1什么是哈希表 8.3.2哈希函数的构造方法 8.3.3处理冲突的方法 8.3.4哈希表的查找及其分析 9 内部排序（10+2学时）9.1概述 （掌握）9.2插入排序 9.2.1直接插入排序 （掌握）9.2.2其他插入排序（理解）9.2.3希尔排序（理解）9.3快速排序 （掌握）9.4选择排序 9.4.1简单选择排序 （掌握）9.4.2树形选择排序（理解）9.4.3堆排序（理解）9.5归并排序（理解）9.6基数排序 （了解）9.6.1多关键字的排序 9.6.2链式基数排序 9.7各种

9、内部排序方法的比较讨论（掌握）课内实验序号 实验名称 实验学时 每组人数 实验性质 开出要求实验一 顺序表 2 1 验证 必做 实验二 链表 2 1验证 必做实验三 栈和队列 2 1 验证 必做实验四 串的匹配 2 1 验证 必做实验五 二叉树的遍历 2 1 综合 必做实验六 图的深度和广度遍历 2 1 验证 必做实验七 查找 2 1 验证 必做实验八 排序 2 1 验证 必做实验内容序号内容提要实验一1、 顺序表的建立、插入、删除和查找等算法的设计与编制2、 程序调试实验二1、 单链表的建立、插入、删除和查找等算法的设计与编制2、JOSEPHUS问题实验三1、 堆栈的建立、入栈、出栈等算法的设计与编制2、队列的建立、入队、出队等算法的设计与编制实验四1、 BF算法的设计与编制2、矩阵三元表算法实验五1、 二叉树的建立算法的设计与编制2、 二叉树的递归遍历算法的设计与编制3、二叉树的非递归遍历算法的设计与编制实验六1、 图的建立算法的设计与编制2、图的深度和广度遍历算法的设计与编制实验七1、 前哨法查找的设计与编制2、二分法查找的设计与编制实验八1、 插入排序算法的设计与编制2