《数据结构与算法》教学大纲.doc

《数据结构与算法》教学大纲
一、课程概述
1. 课程研究对象和研究内容
算法与数据结构是通讯工程专业选修课，主要研究典型的算法及其数据的逻辑结构及其基本操作在计算机中的表示和实现。
本标准的编写依据是2008级专业教学计划，适用于通讯工程专业及计算机科学与技术专业
2. 课程在整个课程体系中的地位
算法与数据结构是通讯工程专业的任选课程。前修课程包括：离散数学、C语言等，后续课程：软件工程、人工智能，该课程可以在大学三、四年级开设。
二、课程目标
1．知道《算法与数据结构》这门学科的性质、地位和独立价值。知道这门学科的研究范围、分析框架、研究方法、学科进展和未来方向。
2．理解这门学科的基本概念、主要结构类型和算法，尤其是典型的算法及其评价指标、数据结构的三要素、存储结构的实现和算法的评价策略。
3．学会分析研究计算机加工的数据的结构特性，以便为实际应用问题所涉及到的数据选择适当的逻辑结构、存储结构及其算法。
逐步理解算法的时间分析和空间分析的技术。
5．培养数据抽象能力；训练复杂程序设计的技能；要求编写的程序结构清楚和正确易读，养成良好程序设计习惯。

三、课程内容和要求
这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下：
知道———是指对这门学科和教学现象的认知。
理解———是指对这门学科涉及到的概念、原理、策略与技术的说明和解释，能提示所涉及到的教学现象演变过程的特征、形成原因以及教学要素之间的相互关系。
掌握———是指运用已理解的教学概念和原理说明、解释、类推同类教学事件和现象。
学会———是指能模仿或在教师指导下独立地完成某些教学知识和技能的操作任务，或能识别操作中的一般差错。
教学内容和要求表中的“√”号表示教学知识和技能的教学要求层次。
本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。
教学内容及教学要求表
教学内容
知道
理解
掌握
学会
1 绪论
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表示与实现
1.4 算法和算法分析
1.5 算法的复杂度与评价

√

√

√

√
√

2 线性表
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 一元多项式的表示及相加

√

√
√

√

3 栈和队列
3.1 栈
3.2 栈的应用举例
3.3 栈与递归的实现
3.4 队列

√

√
√

√

4 树和二叉树
4.1 树的定义和基本术语
4.2 二叉树
4.3 遍历二叉树
4.4 线索二叉树
4.5 树和森林
4.6 赫夫曼树及其应用

√

√
√

√
√

√
5 图
5.1 图的定义和术语
5.2 图的存储结构
5.3 图的遍历
5.4 拓扑排序
5.5 关键路径
5.6 最短路径

√
√

√

√

√
√
6 查找
6.1 静态查找表
6.2 动态查找表
6.3 哈希表

√
√
√

7 内部排序
7.1 概述
7.2 插入排序
7.3 冒泡排序
7.4 快速排序
7.5 选择排序
7.6 树排序
7.7 堆排序

√

√
√
√

√
√
√

四、课程实施
算法与数据结构可以作为通信工程专业选修课。一般情况下，每周安排3课时，共54课时。具体课时安排如下：
课时安排及教学方法表
教学内容
课时建议
(54课时)
教与学的方法建议
1 绪论
4课时
讲述、演示
2 线性表
8课时
讲述、演示
3 栈和队列
8课时，其中实验2课时
讲述、演示
4 树和二叉树
8课时，其中实验2课时
讲述、演示
5 图
8课时，其中实验2课时
讲述、演示
6 查找
8课时，其中实验2课时
讲述、演示
7 内部排序
8课时，其中实验2课时
讲述、演示
总复习
2课时
讲述
合计：54课时中含理论课44课时。
五、教材和参考书目
1、 算法与数据结构(C语言版)第2版. 陈守孔,孟佳娜,武秀川编著. 机械工业出版社
2、 数据结构(C语言版). 严蔚敏,吴伟民编著. 清华大学出版社
六、课程评价
1．本课程的评价与考核依据是本课程标准规定的课程目标、教学内容和要求。
2．考试时间：120分钟。
3．考试方式、分制与分数解释
采用闭卷、笔试的方式，以百分制评分，60分为及格，满分为100分。
学期总评分 = 考试成绩（70% ）+平时成绩（30%）
其中：平时成绩（30%） = 作业成绩（10%）+实验成绩（10%）＋期中考试成绩（10％）
4．样题与目标定位示例
A．术语解释：（着重考查学生对知识的认知程度）
例：数据类型
B．单选题：（着重考查学生对知识的识别程度）
例：铁路转轨网络进行车厢调度，且两侧铁道均为单向行驶道。若进站的车厢序列为123，则不可能得到的出站车厢序列是（ ）。
a） 123 b） 231 c） 312 d） 213 e） 132 f） 321
C．填空题：（着重考查学生对知识的理解程度）
例：时间复杂度为O(nlogn)的排序算法有＿＿＿＿、＿＿＿＿和＿＿＿＿。
D．判断说明题：（着重考查学生对知识的理解程度）
例：AOV–网即边表示活动的网。（ ）
E．简答题：（着重考查学生对知识的理解与掌握程度）
例：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
F．算法设计题：（着重考查学生对知识的掌握与学会程度）
例：2-路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试写一个算法在链表结构上实现这一策略。

制定该课程标准小组成员：
审核者：