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

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

课程英文名称：DataStructuresandAlgorithm

课程编号：0801330学分：2学时：22+10

-、课程教学对象

本教学大纲适用于非计算机专业理工科相关专业的普通本科学生数据结构课程的理论教学和课

内实验教学。

二、课程性质及教学目的

数据结构与算法是非计算机专业理工科相关专业的选修课程。本课程的教学活动必须实现满足学

生学习后继专业课程的基本需要；为学生今后进行各种软件的开发打下扎实的理论和实践基础的目的，

使学生在编程能力方面得到比较系统的训练。为此，本课程强调理论和实践的统一，在对学生进行基

本数据结构的理论、技术和方法培养的同时，强调学生实践能力的培养，突出学生针对实际问题进行

基本数据结构分析和设计能力的培养。鼓励学生学以致用，将学到的知识用以解决实际问题。

三、对先修知识的要求

本课程的先修课程为高级程序设计语言、离散数学等。对先修课程的具体要求是掌握程序设计语

言的基本概念；掌握结构化程序设计的基本原理以及初步的面向对象程序设计知识、具备良好的程序

设计习惯和较好的程序调试能力；掌握离散数学的基本理论；具有一定的逻辑思维和推理能力。

四、课程的主要内容、基本要求和学时分配建议（总学时数：22）

知识模块知识点要求学时学习方式课外学习要求

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

1.2数据结构的基本概念A课堂讲授

1、数据结构

1.3抽象数据类型的概念B2课堂讲授

概念

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

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

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

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

2.3顺序表的存储结构、基本操

2、线性表A2课堂讨论

作算法及其时间性能

2.4各种链表结构中实现线性表

A课堂讲授

操作的基本方法

3、栈和队列3.1栈的定义及其操作特性B2课堂讲授

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

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

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

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

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

4.3二叉树的定义及特点、二叉树

B课堂讲授

的基本性质

4、树和二叉4.4二叉树的各种存储结构方法、

A4课堂讲授

树遍历方法

4.5树、森林与二叉树树的转换方

B课堂讨论

法

4.6哈夫曼树的构造方法和哈夫

A课堂讲授

曼编码方法

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

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

5、图5.3最小生成树B4课堂讲授

5.4最短路径B课堂讲授

5.5AOV网与AOE网B课堂讨论

6.1算法与程序A课堂讲授

6、算法概述2

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

7.1递归的概念A课堂讲授

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

7、递归与分

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

治策略

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

7.5Strassen矩阵乘法A课堂讲授

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

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

8、动态规划8.3矩阵连乘问题A2课堂讲授

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

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

注：知识点中粗体字部分为本课程的重点或难点

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

[1J王红梅，胡明，王涛.数据结构（C++版）（第2版）[M].北京：清华大学出版社，2011

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

2006

[3J严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2002

[4]王晓东.计算机算法设计与分析[M].北京：电子工业出版社，2007

[5]余祥宣，崔国华，邹海明.计算机算法基础（第三版）[M].武汉：华中科技大学出版社，2006

[6]苏德富，钟诚.计算机算法设计与分析[M].北京：电子工业出版社，2001

[7]曹新谱.算法设计与分析[M].长沙：湖南科学技术出版社，1984

[8]王晓东.算法设计与分析习题解答[M].北京：清华大学出版社，2006

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

六、课程考核方式

本课程采用笔试闭卷的考核方式，要求学生熟练掌握课程教学目标要求的内容，并能有效表达和

运用，以达到该课程的能力培养目标。

采用平时成绩和期末考试成绩相结合的方式：平时表现（考勤、随堂提问、作业、随堂测验、实

验环节）：30%,期末考试：70%o

七、课内实验（实训）环节及要求（总学时数：10）

根据实际教学情况和学生意愿，在以下实验中选择5个实现项目（10学时），并通过课外编程进行

学时补充。

序号实验（实训）项目实验（实训）内容实验（实训）目的及要求学时

运用高级语言（C++/Java）

理解线性表的顺序存储结构

顺序表处理程序的设编写一个至少包含四个基

1的实现方法及其各种操作的2

计本功能的顺序表处理程

算法设计方法。

序，调试、给出正确结果。

运用高级语言（C++/Java）

理解线性表的链接存储结构

链接表处理程序的设编写一个至少包含四个基

2的实现方法及其各种操作的2

计本功能的链接表处理程

算法设计方法。

序，调试、给出正确结果。

运用高级语言（C++/Java）

编写一个包含入栈、出栈

3栈的基本操作理解栈的应用2

基本操作的程序，调试、