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

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

数据结构与算法DataStructure1、学分：4.5 学时（理论学时实验学时：16）2、课程性质：学科专业基础课3、适用专业：计算机科学与技术专业、计算机软件工程专业4、适用对象：本科课5、先修课程：计算机语言(C)程6、教材与参考书目：基《数据结构(C语言版)》，严蔚敏吴伟民，清华大学出版社，1997本《数据结构(用面向对象方法与C++描述)》，殷人昆，清华大学出版社，1998情《C++数据结构与程序设计（美）RobertL.Kruse/AlexanderJ.Ryba著/钱丽萍译》，况清华大学出版社，2004《算机算法设计与分析（2版730~4060~70％8、教学环境：课堂、多媒体，实验室课程数据结构是计算机程序设计的重要理论基础。也是计算机专业教学中的核心专业基础教课程。它所讨论的知识内容和提倡的技术方法，对进一步学习计算机领域的其他课程、从学事软件工程的开发，都有着不可替代的作用。是从事计算机科学研究及应用的科技人员必目须具备的重要基础知识。的1绪论（4学时）课 1.1什么是数据结构（理解程 1.2基本概念和术语（掌握内 1.3抽象数据类型的表示与实现（了解容 1.4算法和算法分析、 1.4.1算法（掌握）学 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一元多项式的表示及相加（理解）（6+2学时）（掌握）3.1.l抽象数据类型栈的定义3.1.2栈的表示和实现栈的应用举例（了解）数制转换括号匹配的检验行编辑程序迷宫求解表达式求值（了解）队列课 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求子串位置的定位函数本 4.3.2模式匹配的一种改进算法要 4.4串操作应用举例（理解求 4.4.1文本编辑4.4.2建立词索引表数组和广义表学时）（掌握）（掌握）（理解）5.3.l特殊矩阵（理解）5.3.2稀疏矩阵（理解）（掌握）（理解）m元多项式的表示（了解）（了解）求广义表的深度复制广义表建立广义表的存储结构树和二叉树（10+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广度优先搜索（掌握）图的连通性问题无向图的连通分量和生成树（理解）有向图的强连通分量（理解）（掌握）（了解）（了解）拓扑排序关键路径最短路径（掌握）从某个源点到其余各项点的最短路径每一对顶点之间的最短路径8查找（10+2学时）（掌握）8.1.l顺序表的查找（掌握）（掌握）静态树表的查找（掌握）索引顺序表的查找（掌握）（了解）二叉排序树和平衡二叉树课 8.2.2B-树和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选择排序（掌握）树形选择排序（理解）堆排序（理解）归并排序（理解）基数排序（了解）多关键字的排序链式基数排序各种内部排序方法的比较讨论（掌握）序号实验名称序号实验名称实验学时每组人数实验性质开出要求实验一顺序表21验证必做实验二链表21验证必做实验三栈和队列21验证必做实验四串的匹配21验证必做实验五二叉树的遍历21综合必做实验六图的深度和广度遍历21验证必做实验七查找21验证必做实验八 排序 2 1 验证 必做序号实验四实验内容实验五实验八

内容提要1、顺序表的建立、插入、删除和查找等算法的设计与编制2、程序调试1、单链表的建立、插入、删除和查找等算法的设计与编制2、JOSEPHUS问题1、堆栈的建立、入栈、出栈等算法的设计与编制2、队列的建立、入队、出队等算法的设计与编制1、BF算法的设计与编制2、矩阵三元表算法1、二叉树的建立算法的设计与编制2、二叉树的递归遍历算法的设计与编制3、二叉树的非递归遍历算法的设计与编制1、图的建立算法的设计与编制2、图的深度和广度遍历算法的设计与编制1、前哨法查找的设计与编制2、二分法查找的设计与编制1、插入排序算法的设计与编制2、交换排序算法的设计与编制3、选择排序算法的设计与编制备注大纲编写应