《数据结构与算法》课程教学大纲Word文档下载推荐.docx
《《数据结构与算法》课程教学大纲Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《《数据结构与算法》课程教学大纲Word文档下载推荐.docx(9页珍藏版)》请在冰点文库上搜索。
(二)教育目标:
通过本课程的学习,使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,培养基本的、良好的程序设计技能,编制高效可靠的程序,为学习操作系统、编译原理和数据库等课程奠定基础。
四、课程教学内容与基本要求
第一部分绪论
(一)教学内容
数据结构的基本概念和术语;
抽象数据类型的表示;
算法和算法分析。
(二)重点、难点
重点:
数据结构的基本概念及相关术语。
难点:
算法的时间复杂度分析。
(三)教学基本要求
知识要求:
了解:
抽象数据类型及面向对象概念;
理解:
算法的定义及算法的特性;
掌握:
数据结构的基本概念、算法的性能分析与度量方法。
第二部分线性表
1.线性表的定义及操作;
2.线性表的顺序存储定义及操作实现;
3.单链表的定义;
单链表中的插入与删除;
带表头结点的单链表;
静态链表;
4.循环链表的类定义及运算;
5.双向链表的类定义及运算;
6.线性表的应用:
多项式及其相加。
顺序表的数组定义方式及实现,单链表的定义及实现。
循环链表和双向链表的定义及实现。
静态链表。
线性表的定义及操作。
顺序表的数组定义方式及实现,单链表、循环链表和双向链表的定义及实现。
第三部分栈和队列
1.栈的抽象数据类型;
栈的顺序存储表示;
栈的链式存储表示;
栈的两种存储表示上的基本运算;
2.栈的应用;
3.队列的抽象数据类型;
队列的顺序存储表示及基本运算;
队列的链式存储表示及基本运算;
4.队列的应用举例。
栈的定义及实现;
队列的定义及实现。
栈的应用中的表达式求值;
循环队列(队列的顺序存储)。
队列的应用。
栈的应用中的递归算法。
第四部分串、数组和广义表
(一)教学内容
1.字符串的抽象数据类型;
字符串操作的实现;
字符串的模式匹配
2.数组的逻辑结构定义和存储方法;
特殊矩阵和稀疏矩阵的压缩存储方法;
3.广义表的概念;
广义表的表示及操作;
广义表存储结构的实现;
4.广义表的访问算法;
广义表的递归算法。
串和数组的基本概念、存储结构。
广义表的概念和存储结构及其相关运算的实现。
串的模式匹配算法,特殊矩阵和稀疏矩阵的压缩存储。
串的一些基本处理操作、矩阵的相关运算。
第五部分树和二叉树
1.树的基本概念;
2.二叉树的定义、性质、存储表示及相关运算;
二叉树的遍历;
线索二叉树;
3.森林和二叉树的相互转换;
4.哈夫曼树及哈夫曼编码。
二叉树的定义、性质、存储表示;
二叉树的相关运算。
线索二叉树上的复杂运算实现。
森林和二叉树的相互转换;
哈夫曼树及哈夫曼编码。
第六部分图
1.图的基本概念、存储表示(邻接矩阵、邻接表、十字链表,邻接多重表);
2.图的遍历与连通性:
深度优先搜索;
广度优先搜索;
连通分量;
重连通分量;
3.最小生成树:
克鲁斯卡尔算法;
普里姆算法;
4.最短路径;
5.拓扑排序、关键路径。
图的存储表示;
图的遍历;
最小生成树;
最短路径;
关键路径的求解。
图的存储结构中的邻接多重表。
图的遍历算法。
图的存储表示(邻接矩阵、邻接表);
拓扑排序、关键路径。
第七部分查找
1.静态查找(顺序查找、折半查找、分块查找);
2.动态查找(二叉排序树);
3.哈希查找。
静态查找;
二叉排序树的建立。
二叉排序树的删除;
平衡二叉树的调整。
查找的相关概念、作用。
哈希函数的构造。
二叉排序树的相关知识;
哈希查找法和解决冲突的方法。
第八部分排序
1.排序概念;
2.插入排序、交换排序、选择排序、归并排序、基数排序;
3.各种排序方法的比较。
交换排序、选择排序。
堆排序。
各种排序方法的时间复杂度的分析方法。
排序方法“稳定”或“不稳定”的含义。
各种方法的排序过程及其依据的原则。
第九部分文件
1.基本概念;
2.文件组织;
3.顺序文件、随机文件、索引文件、倒排文件。
(二)重点、难点
基本概念;
顺序文件;
索引文件。
文件的使用。
能力要求:
即通过本课程的学习,学生具备基本的、良好的程序设计技能,能够编制高效可靠的程序。
素质要求:
具备良好的编程习惯和能力。
五、学时(理论和实践)分配表
序号
教学内容
课时分配
理论教学
实践教学
考核权重
1
绪论
2
5%
线性表
4
22%
3
栈和队列
5
串、数组和广义表
4
3%
树和二叉树
6
25%
图
20%
7
查找
10%
8
排序
8%
9
文件
2%
总计
34
100%
六、学习教学场地、设施要求(课程中的实践部分)
项目(实验)名称
学习教学场地、设施要求
线性表的应用
实践教学在机房进行,机器需要安装有C语言环境。
栈和队列的应用
串的简单操作
二叉树的算法实现
图的遍历
分块查找
冒泡排序
说明:
分实践项目列出场地、设施要求,如每个实践项目的场地和设施基本相同,也可以一次性描述。
七、考核及评分办法
考核的原则:
闭卷考试。
考试;
期末考试;
笔试(闭卷);
各教学环节占总分的比例:
实验、作业占30%,期末考试占70%。
八、学习资源的选用
建议使用教材:
《实用数据结构基础》,陈元春编着,中国铁道出版社,版别(2007年6月,第1版)
建议参考书:
(一)《数据结构》严蔚敏等着清华大学出版社1997
(二)《数据结构》安训国着大边理工出版社版别(2015年9月,第5版)
大纲执笔人:
方新丽
专业大纲编写组组长审阅:
冯川放
系主任审定:
制定日期: