《数据结构与算法分析》教学大纲

课程编号：CE203003

课程名称：数据结构与算法分析           英文名称：Data Structure andAlgorithm Analysis

学分/学时：3/48 （32+32）           课程性质：专业平台基础课

适用专业：信息安全、网络工程、网络空间安全

建议开设学期：2

先修课程：计算机导论与程序设计         开课单位：网络与信息安全学院

一、课程的教学目标与任务

本课程是信息安全、网络工程、网络空间安全等专业学生掌握程序设计技能的一门重要专业平台基础课，是计算机学科的公认主干课。

本课程的教学目标：

使学生通过本课程的学习，熟悉解决程序设计问题所需的基本数据结构和基础算法，掌握各种程序设计中常用的数据结构的基本概念、对应的逻辑结构和存储结构及其基本运算，各种数据结构的基本特点和典型应用场景。熟练使用基础数据结构进行算法程序设计。

本课程的教学要求：

通过课程的教授，使学生能够熟练掌握各种数据结构，理解算法的设计和分析方法，并从计算机领域经典设计案例中体会数据结构与算法的相互依存关系，以此为基础掌握应用数据结构和算法解决问题的能力。通过课程的教授，使学生建立起数据结构与算法设计的整体概念，能够编制、调试一定规模的程序，并具备良好的软件工程习惯和软件思维方法，为后续各门专业课程的算法设计提供基础。

本课程完成后，学生将具备如下能力：

1.在工程实践中能够依据数学模型选择合适的数据结构和算法，或能够根据具体问题设计数据结构和算法；

2.通过编程解决具体问题，并达到一定的精度要求；

3.能够选择适当的开发工具完成从设计到实现的全部流程；

4.对选择的数据结构和设计的算法进行性能分析，能够分析算法性能优劣对环境、社会可持续发展的影响；

本课程的性质：本课程是实践性较强的一门课程，在教学过程中理论教学和实践教学并重，理论课程占32学时，实验课时占32学时，是每位选课学生必须完成的。

二、课程具体内容及基本要求

(一) 绪论 ( 1学时)

软件工程的概念；

数据结构的概念；

程序设计的关键技术。

1.基本要求

（1）熟练掌握软件概念、程序设计技术。

（2）熟练掌握数据结构的概念、名词和术语。

2.重点、难点

重点：数据结构的概念、名词和术语。

难点：数据结构的概念。

3. 作业及课外学习要求

（1）仔细阅读教材中的程序设计实例

（2）阅读参考书目中关于软件工程的相关章节。

（二）线性表（3学时）

线性表的基本概念和运算；

顺序表的基本运算；

单链表的基本运算；

顺序表和链表的应用实例分析。

1.基本要求

（1）熟练掌握线性表的基本概念及运算。

（2）熟练掌握线性表的顺序存储表示及算法。

（3）熟练掌握线性表的链式存储表示及算法。

（4）顺序表及链表的应用实例。

2.重点、难点

重点：线性表的逻辑结构、存储结构及运算。

难点：线性表的链式存储及运算。

3. 作业及课外学习要求

（1）完成课后作业；

（2）复习顺序表、单链表的计算方法；

（3）比较顺序表、单链表的优缺点。

4. 上机实践（占用4上机学时）

完成教材中指定习题的上机练习。

（三）栈和队列（4学时）

栈的存储表示和应用

队列的存储表示和应用

1.基本要求

（1）熟练掌握栈的定义及存储表示。

（2）栈的应用实例。

（3）熟练掌握队列的定义及存储表示。

（4）队列的应用实例。

2.重点、难点

重点：栈和队列的逻辑结构特点及其运算。

难点：栈的递归应用，顺序队列。

3.作业及课外学习要求

（1）完成课后作业；

（2）复习栈的存储表示和基本操作；

（3）复习队列的存储表示和基本操作；

（4）复习地图染色算法的算法实现。

4. 上机实践

完成教材中指定习题的上机练习（占用4上机学时）

（四）串和数组（4学时）

1.基本要求

（1）熟练掌握串的定义、运算和存储表示的特点。

（2）熟练掌握串运算的实现。

（3）熟练掌握数组的定义及顺序存储。

（4）掌握矩阵的压缩存储。

2.重点、难点

重点：串的存储表示及其运算的实现，矩阵的压缩存储。

难点：模式匹配算法、特殊矩阵的压缩存储。

3. 作业及课外学习要求

（1）完成课后作业；

（2）复习串的存储方法和基本操作实现，拓展阅读参考书目中关于串的其他运算；

（3）复习数组的存储方法和基本操作实现。

4. 上机实践

完成教材中指定习题的上机练习（占用4上机学时）

（五）树（7学时）

数、二叉树、森林的基本概念；

二叉树的遍历方法；

树和森林之间的转换方法；

二叉树的应用。

1.基本要求

（1）熟练掌握树结构的基本概念、术语。

（2）熟练掌握二叉树的性质和存储表示。

（3）熟练掌握二叉树的遍历及递归算法的运用。

（4）掌握树和森林（存储表示、转化方法、树的遍历）。

（5）二叉树的应用（哈夫曼树及应用、二叉排序树）。

2.重点、难点

重点：二叉树的性质和存储表示、二叉树的遍历及递归算法的运用。

难点：递归算法的运用、线索的应用、哈夫曼编译码。

3. 作业及课外学习要求

（1）完成课后作业；

（2）着重复习二叉树的遍历算法及其应用；

4. 上机实践

完成教材中指定习题的上机练习（占用4上机学时）

（六）图（8学时）

图的基本概念；

图的存储方法；

图的遍历算法；

生成树和最小生成树；

最短路径；

拓扑排序；

关键路径。

1.基本要求

（1）熟练掌握图的基本概念、术语。

（2）熟练掌握图的存储方法（邻接矩阵、邻接表）。

（3）熟练掌握图的DFS和BFS搜索算法及相关应用。

（4）掌握生成树和最小生成树（Prime算法、Kruskal算法）。

（5）掌握最短路径。

（6）掌握拓扑排序。

（7）了解关键路径。

2.重点、难点

重点：图的存储表示、图的遍历及其应用。

难点：Prime算法、Dijkstra算法、拓扑排序算法。

3. 作业及课外学习要求

（1）完成课后作业；

（2）复习图的遍历算法、最短路径算法和关键路径算法；

（3）阅读其他参考书目中关于图的应用的章节。

4. 上机实践

完成教材中指定习题的上机练习（占用4上机学时）

（七）索引结构与散列技术（2学时）

索引结构；

散列表的概念；

散列函数的构造方法；

解决冲突的方法；

1.基本要求

（1）熟练掌握索引结构的表示及应用。

（2）熟练掌握散列表的概念、散列表的构造及散列表的查找。

2.重点、难点

重点：索引表的应用，散列表的构造及查找。

难点：散列函数的设计及冲突的处理。

3. 作业及课外学习要求

（1）完成课后作业；

（2）复习索引和散列的存储方法；

（3）拓展阅读其他参考书目中关于散列技术在计算机存储设计中的应用。

（八）缩小规模算法（3学时）

分治与递归算法设计；

动态规划的基本要素；

贪心算法。

1.基本要求

（1）掌握递归与分治算法。

（2）掌握动态规划算法。

（3）掌握贪心算法。

2.重点、难点

重点：递归算法，分治算法，贪心算法，动态规划算法。

难点：递归算法，贪心算法，动态规划算法。

3. 作业及课外学习要求

（1）完成课后作业；

（2）通过拓展阅读参考书或在网上查找资料，加深对分治、递归、动态规划和贪心算法应用场景的理解。

三、教学安排及方式

总学时 64 学时，其中：讲授 32 学时，实验 0 学时，上机 24 学时，实践 8 学时，线上 0 学时。

注：教学方式包括面授和线上，其中面授包括：讲授、实验、上机、实践。

四、考核及成绩评定方式

最终成绩由综合大作业成绩、上机考试成绩和期末考试成绩三部分组合而成。各部分所占比例如下：

综合大作业成绩：15%。主要考核综合大作业的完成情况，考核运用所学各种数据结构及算法设计技术来解决相关工程问题，编制出具有一定规模的程序的能力。

上机考试成绩：15%。主要考核学生对知识点的综合理解、掌握和应用程度。

期末考试成绩：70%。主要考核基础知识的掌握程度。书面考试形式。题型为选择题、判断题、填空题、问题求解题和算法设计题等。

过程成绩提交时间和总评成绩计算说明表

注：上表用于说明授课过程中分项成绩提交时间，教师应在规定的时间内提交对应成绩，提前或逾期无法提交，一旦提交无法修改。大纲可以根据需要自行定义提交成绩的次数、时间和名称或说明，总评成绩计算必须与考核和成绩评定方式中描述的一致。

五、教材及参考书目

教材：《数据结构与算法分析》，荣政等编著，西安电子科技大学出版社，2012.

参考书目：

1.《计算机软件技术基础》（第一版），刘彦明等编著，人民邮电出版社，2005.

2.《数据结构（C语言版）》（第一版），严蔚敏编著，清华大学出版社，2002.

3.《计算机算法设计与分析》，（第一版），王晓东编著，电子工业出版社，2001.

4. M. H. Alsuwaiyel, Algorithms DesignTechniques and Analysis, 电子工业出版社影印，2003年1月。

5. Thomas H.Cormen, Charles E.Leiserson,Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5月。

六、说明

（一）与相关课程的分工衔接

先修课程“计算机导论与程序设计”使学生能掌握C语言的基本语法、程序设计的基本思想、基本概念和基本方法，并能运用所学的知识进行简单的程序设计；而“数据结构与算法分析”则使学生在掌握基本程序设计能力的基础上，运用所学各种数据结构及算法设计技术来解决实际问题，编制出具有一定难度的中型程序，并通过课程的学习，掌握良好的软件工程习惯和软件思维方法。“数据结构与算法分析”课程是后续计算机相关课程，如操作系统、网络对抗原理、高级语言程序设计、软件逆向工程、智能终端安全技术等的重要基础课。

（二）其他说明

1．课堂讲述的内容只是核心或有特色的知识内容，还有一定数量的篇章内容留给学生自学。

2．“数据结构与算法分析”课注重上机训练，所有作业都必须配有规范的文档。上机训练由平时的上机实践和综合大作业两部分组成。

3．该课程强调能力的培养，有独到见解的综合作业予以适当加分。

教材

《数据结构与算法分析》，荣政等编著，西安电子科技大学出版社，2012.

参考目录

1. 《计算机软件技术基础》（第一版），刘彦明等编著，人民邮电出版社，2005.

2. 《数据结构（C语言版）》（第一版），严蔚敏编著，清华大学出版社，2002.

3.《计算机算法设计与分析》，（第一版），王晓东编著，电子工业出版社，2001.

4.  M. H. Alsuwaiyel,Algorithms Design Techniques and Analysis, 电子工业出版社影印，2003年1月.

5.  Thomas H.Cormen, CharlesE.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5月。

本课程完成后，学生将具备如下能力：

1.在工程实践中能够依据数学模型选择合适的数据结构和算法，或能够根据具体问题设计数据结构和算法；

2.通过编程解决具体问题，并达到一定的精度要求；

3.能够选择适当的开发工具完成从设计到实现的全部流程；

4.对选择的数据结构和设计的算法进行性能分析，能够分析算法性能优劣对环境、社会可持续发展的影响；