《数据结构与算法》教学大纲.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-路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试写一个算法在链表结构上实现这一策略。制定该课程标准小组成员： 审核者：