|
课程 代码 |
●B204205 |
课程名称 |
数据结构 |
|
Data Structure |
|||
|
课 程 基 本 情 况 |
1、学分：●2.5 ▲3.5 学时：●48 ▲60 （理论学时：●38 ▲46 实验学时：●10 ▲14） 2、课程性质：学科专业基础课 3、适用专业：计算机科学与技术专业 4、适用对象：本科 5、先修课程：计算机语言(C) 6、教材与参考书目： 《数据结构(C语言版)》，严蔚敏 吴伟民，清华大学出版社，1997 《数据结构(用面向对象方法与数据结构描述) 》，殷人昆，清华大学出版社，1998 《数据结构数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译》， 清华大学出版社，2004 《算机算法设计与分析（第2版）》，王晓东， 电子工业出版社， 2004 7、考核方式：考试、闭卷 平时成绩30％、期终考试70％ 8、教学环境：课堂、多媒体，实验室 |
||
|
课 程 教 学 目 的 |
“数据结构”是计算机程序设计的重要理论基础。也是计算机专业教学中的核心专业基础课程。它所讨论的知识内容和提倡的技术方法，对进一步学习计算机领域的其他课程、从事软件工程的开发，都有着不可替代的作用。是从事计算机科学研究及应用的科技人员必须具备的重要基础知识。 |
||
|
课 程 内 容 、 学 时 分 配 及 教 学 基 本 要 求 |
1 结论 （2学时） 1.1什么是数据结构 （理解） 1.2基本概念和术语 （掌握） 1.3抽象数据类型的表示与实现 （了解） 1.4算法和算法分析 1.4.1算法 （掌握） 1.4.2算法设计的要求 （掌握） 1.4.3算法效率的度量 ●（了解） ▲（掌握） 1.4.4算法的存储空间需求 ●（了解） ▲（掌握）
2 线性表 ●（4+2学时）▲（6+2学时） 2.l线性表的类型定义 （掌握） 2.2线性表的顺序表示和实现 （掌握） 2.3线性表的链式表示和实现 2.3.1线性链表（掌握） 2.3.2循环链表（掌握） 2.3.3双向链表 ●（理解） ▲（掌握） |
||
|
课 程 内 容 、 学 时 分 配 及 教 学 基 本 要 求 |
2.4一元多项式的表示及相加（了解）
3 栈和队列 （4+2学时） 3.1栈 （掌握） 3.1.l抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例（了解） 3.2.1数制转换 3.2.2括号匹配的检验 3.2.3行编辑程序 3.2.4迷宫求解 3.2.5表达式求值 3.3栈与递归的实现 （了解） 3.4队列 3.4.1抽象数据类型队列的定义 （掌握） 3.4.2链队列--队列的链式表示和实现 （掌握） 3.4.3循环队列--队列的顺序表示和实现 （掌握） 3.5离散事件模拟 （了解）
4 串 （2+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 数组和广义表（2学时） 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 树和二叉树 ●（6+2学时）▲（10+2学时） 6.1树的定义和基本术语 （掌握） 6.2二叉树 （掌握） 6.2.1二叉树的定义 6.2.2二叉树的性质 6.2.3二叉树的存储结构 6.3遍历二叉树和线索二叉树 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 图 ●（8学时） ▲（6+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.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 查找 ●（6学时） ▲（6+2学时） 8.1静态查找表 （掌握） 8.1.l顺序表的查找 （掌握） 8.1.2有序表的查找 （掌握） 8.1.3静态树表的查找 ●（了解） ▲（掌握） 8.1.4索引顺序表的查找 ●（了解） ▲（掌握） 8.2动态查找表 （了解） 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 内部排序 ●（6学时） ▲（8+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各种内部排序方法的比较讨论（掌握） |
||
|
课内 实验 |
序号 实验名称 实验学时 每组人数 实验性质 开出要求 实验一 线性表 2 1 验证 必做 实验二 栈和队列 2 1 验证 必做 实验三 串的匹配 2 1 验证 ▲必做 实验四 二叉树的遍历 2 1 验证 必做 实验五 图的深/广度遍历 2 1 验证 ▲必做 实验六 查找 2 1 验证 必做 实验七 排序 2 1 验证 必做 |
||
|
备注 |
●表示 48学时； ▲表示 60学时 |
||