《数据结构与算法》教学大纲22+10

《数据结构与算法》课程教学大纲课程英文名称DataStructuresandAlgorithm课程编号0801330学分2学时22+10-、课程教学对象本教学大纲适用于非计算机专业理工科相关专业的普通本科学生数据结构课程的理论教学和课内实验教学

二、课程性质及教学目的数据结构与算法是非计算机专业理工科相关专业的选修课程本课程的教学活动必须实现满足学生学习后继专业课程的基本需要；为学生今后进行各种软件的开发打下扎实的理论和实践基础的目的使学生在编程能力方面得到比较系统的训练为此，本课程强调理论和实践的统一，在对学生进行基本数据结构的理论、技术和方法培养的同时，强调学生实践能力的培养，突出学生针对实际问题进行基本数据结构分析和设计能力的培养鼓励学生学以致用，将学到的知识用以解决实际问题

三、对先修知识的要求本课程的先修课程为高级程序设计语言、离散数学等对先修课程的具体要求是掌握程序设计语言的基本概念；掌握结构化程序设计的基本原理以及初步的面向对象程序设计知识、具备良好的程序设计习惯和较好的程序调试能力；掌握离散数学的基本理论；具有一定的逻辑思维和推理能力

四、课程的主要内容、基本要求和学时分配建议（总学时数22）注知识点中粗体字部分为本课程的重点或难点

五、建议使用教材及参考书

[1]王红梅，胡明，王涛.数据结构（C++版）（第2版）[M]北京清华大学出版社，2011⑵王红梅，胡明，王涛.数据结构（C++版）学习辅导和实验指导[M].北京清华大学出版社2006

[9]张永，李睿，年福忠.算法与数据结构[M].北京国防工业出版社，2008

六、课程考核方式本课程采用笔试闭卷的考核方式，要求学生熟练掌握课程教学目标要求的内容，并能有效表达和运用，以达到该课程的能力培养目标采用平时成绩和期末考试成绩相结合的方式平时表现（考勤、随堂提问、作业、随堂测验、实验环节）30%期末考试70%o

七、课内实验（实训）环节及要求（总学时数10）根据实际教学情况和学生意愿，在以下实验中选择5个实现项目（10学时），并通过课外编程进行学时补充知识模块知识点要求学时学习方式课外学习要求

1、数据结构概念

1.1数据结构的研究对象C2课堂讲授

1.2数据结构的基本概念A课堂讲授L3抽象数据类型的概念B课堂讲授

1.4算法的基本概念B课堂讲授

1.5算法复杂度的基本概念B课堂讨论

2、线性表

2.1线性表的定义及其逻辑特征B2课堂讲授

2.2线性表的抽象数据类型定义B课堂讲授

2.3顺序表的存储结构、基本操作算法及其时间性能A课堂讨论

2.4各种链表结构中实现线性表操作的基本方法A课堂讲授

3、栈和队列

3.1栈的定义及其操作特性B2课堂讲授

3.2顺序栈的实现方法A课堂讨论

3.3队列的定义及其操作特性B课堂讲授

3.4顺序队列的实现方法A课堂讨论

4、树和二叉树

4.1树的定义及其基本术语C4课堂讲授

4.2树和森林的遍历方法B课堂讲授

4.3二叉树的定义及特点、二叉树的基本性质B课堂讲授

4.4二叉树的各种存储结构方法、遍历方法A课堂讲授

4.5树、森林与二叉树树的转换方法B课堂讨论

4.6哈夫曼树的构造方法和哈夫曼编码方法A课堂讲授

5、图

5.1图的逻辑结构及遍历方法A4课堂讲授

5.2图的存储结构及其实现A课堂讲授

5.3最小生成树B课堂讲授

5.4最短路径B课堂讲授

5.5AOV网与AOE网B课堂讨论

6、算法概述

6.1算法与程序A2课堂讲授

6.2算法复杂性分析B课堂讲授

7、递归与分治策略

7.1递归的概念A4课堂讲授

7.2分治法的基本思想A课堂讲授

7.3二分搜索技术A课堂讲授

7.4大整数的乘法A课堂讲授

7.5Strassen矩阵乘法A课堂讲授

8、动态规划

8.1动态规划算法的基本思想B2课堂讲授

8.2动态规划算法的基本要素A课堂讲授

8.3矩阵连乘问题A课堂讲授

8.4最长公共子序列A课堂讲授

8.5最大子段和问题B课堂讲授

[3]严蔚敏.

[4]王晓东.[5J余祥宣，16]苏德富，

[7]曹新谱.

[8]王晓东.数据结构（C语言版）[M].北京清华大学出版社，2002计算机算法设计与分析[M].北京电子工业出版社，2007崔国华，邹海明.计算机算法基础（第三版）[M].武汉华中科技大学出版社，2006钟诚.计算机算法设计与分析[M].北京电子工业出版社，2001算法设计与分析[M].长沙湖南科学技术出版社，1984算法设计与分析习题解答[M].北京清华大学出版社，2006序号实验（实训）项目实验（实训）内容实验（实训）目的及要求学时1顺序表处理程序的设计运用高级语言（C++/Java）编写一个至少包含四个基本功能的顺序表处理程序，调试、给出正确结果理解线性表的顺序存储结构的实现方法及其各种操作的算法设计方法22链接表处理程序的设计运用高级语言（C++/Java）编写一个至少包含四个基本功能的链接表处理程序，调试、给出正确结果理解线性表的链接存储结构的实现方法及其各种操作的算法设计方法23栈的基本操作运用高级语言（C++/Java）编写一个包含入栈、出栈基本操作的程序，调试、给出正确结果理解栈的应用24队列的基本操作运用高级语言（C++/Java）编写一个循环顺序队列的程序实例，调试、给出正确结果理解循环队列的应用25递归与分治策略及其运用C++语言求解输油学会使用递归与分治策略解2应用管道问题决实际问题6动态规划及其应用运用C++语言求解

①租用游艇问题

②最少费用购物问题学会使用动态规划解决实际问题2。