数据结构与算法课程是学习计算机软件设计与开发的基础课程。通过学习，学生将学会分析研究计算机加工的数据结构的特性，掌握基本数据结构及算法，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。培养从数学与自然科学角度分析信息处理、控制与管理问题的能力，提高计算机应用和程序开发能力，提升设计程序解决问题的能力。

本课程注重培养学生的数据抽象能力，用规范的数学语言描述数据结构的定义及其数学特性，同时课程也非常重视理论与实践的结合，本课程的学习过程也是复杂程序设计的训练过程，通过数据结构建模和程序表达，引导学生关注编写的程序要结构清晰、正确、易读，符合软件工程的规范，通过课程教学和上机实践了解程序设计、开发软件工程的基本内涵和方法。

目标1：掌握数据结构和操作系统基本概念，能分辨不同结构、不同算法的特点。掌握算法的开销评估和优化方法，能够根据问题解决目标，对问题采用数据结构模型和算法伪代码等方式进行分解，推演、分析，利用数据结构抽象模型、算法、策略解决问题的过程，评价解决方法和效果。

目标2：掌握常用算法框架及关键技术，能够在信息处理与软件控制等方面，设计相适应的数据结构，编制迭代或递归模式的算法以及多任务并发处理软件，对复杂问题进行抽象和描述，获得有效结论。

目标3：掌握至少一种程序语言及程序编译、调测工具，对复杂问题进行建模，并完成程序上机调测，解决问题或得到仿真结果，并对结果进行分析和评测。

目标4：从数据结构基本要素的关系理解抽象与具体的辩证关系、主要矛盾与次要矛盾的关系。通过几种典型算法的设计比较中，认识代价与效率的平衡。

本课程考核成绩由三个部分组成：平时考核、实验考核和期末考试。

建议各部分考核分配比例如下：

1.        平时考核

平时考核至少包括两部分，例如随堂测验，作业完成质量等，占总成绩20%。

2.        实验考核

上机实验完成情况和质量，包括实验当场表现和实验报告，占总成绩20%。

3.        期末考核

期末考核全课程知识点掌握情况，采用闭卷考试方式，占总成绩60%。

1、熟练操作计算机

2、先修课程《高级语言程序设计》（C/C++），熟练掌握指针、结构体、链表、递归等高级内容

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

课程英文名称：Data Structures and Algorithms

课程代码：R0112030                        学 时 数 ：52                     学 分 数：3

课程类型：学科基础课

适用学科专业：网络工程、物联网工程、通信工程、电子信息工程、信息对抗技术等计算机类、电子信息类专业

先修课程：《高级语言程序设计》

执 笔 者：段景山、潘晔、王忠荣    编写日期：2022年5月11日         审 核 人： 凌翔

 

一、课程简介

本课程是计算类或相关专业的程序设计、开发的基础课程。课程内容包括线性结构、非线性结构、查找与排序算法等内容。在学生已经掌握基本的程序设计语言语法和程序结构的基础上，针对利用计算机进行控制、管理等非数值处理问题，通过组织数据与数据之间的关系，选择合适的数据处理方式，编写高质量程序，解决信息分析、处理、控制和管理中的基本问题。计算机系统软件和应用软件都要用到各种类型的数据结构和算法，因此学好本课程对于进一步学习计算机类的其他课程，如操作系统、数据库管理系统、软件工程、人工智能等都十分有益。

This course is specialized elective for fundamental computer science knowledge learning and software implementation practicing. The content of this course includes the linear structures, nonlinear structures, searching and sorting algorithms. The spirit and the ability of computer application and software programing in problem solving will be pursued during the course, especially for further learning in operate systems, database management systems, software engineering , AI etc.

二、课程目标

（一）课程目标

数据结构与算法课程是学习计算机软件设计与开发的基础课程。通过学习，学生将学会分析研究计算机加工的数据结构的特性，掌握基本数据结构及算法，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法。培养从数学与自然科学角度分析信息处理、控制与管理问题的能力，提高计算机应用和程序开发能力，提升设计程序解决问题的能力。

本课程注重培养学生的数据抽象能力，用规范的数学语言描述数据结构的定义及其数学特性，同时课程也非常重视理论与实践的结合，本课程的学习过程也是复杂程序设计的训练过程，通过数据结构建模和程序表达，引导学生关注编写的程序要结构清晰、正确、易读，符合软件工程的规范，通过课程教学和上机实践了解程序设计、开发软件工程的基本内涵和方法。

目标1：掌握数据结构和操作系统基本概念，能分辨不同结构、不同算法的特点。掌握算法的开销评估和优化方法，能够根据问题解决目标，对问题采用数据结构模型和算法伪代码等方式进行分解，推演、分析，利用数据结构抽象模型、算法、策略解决问题的过程，评价解决方法和效果。

目标2：掌握常用算法框架及关键技术，能够在信息处理与软件控制等方面，设计相适应的数据结构，编制迭代或递归模式的算法以及多任务并发处理软件，对复杂问题进行抽象和描述，获得有效结论。

目标3：掌握至少一种程序语言及程序编译、调测工具，对复杂问题进行建模，并完成程序上机调测，解决问题或得到仿真结果，并对结果进行分析和评测。

目标4：从数据结构基本要素的关系理解抽象与具体的辩证关系、主要矛盾与次要矛盾的关系。通过几种典型算法的设计比较中，认识代价与效率的平衡。

Through this course, students will learn the general characteristics of computer processing of data structures, learn to master those basic data structures and algorithms, how to choose appropriate data logic structure, storage structure and related algorithm for the special implement. Training the ability to analysis information processing and controlling problems from the perspective of mathematics and natural science, improving the ability of problem solving with programing.

（二）对毕业要求的支撑

表1 课程目标对毕业要求指标点的支撑关系

毕业要求	指标点	课程目标
工程知识	指标点1.3 能将相关知识和数学模型方法用于推演、分析专业工程问题。	目标1
问题分析	指标点2.2 能基于相关科学原理和数学模型方法正确表达复杂工程问题。	目标2
研究	指标点4.4 能对实验结果进行分析和解释，并通过信息综合得到合理有效的结论。	目标3

（三）课程目标对课程思政要求的支撑：

表2 课程目标对课程思政要求的支撑关系

课程思政要求	课程目标
科学精神与工匠精神	课程目标4：从数据结构基本要素的关系理解抽象与具体的辩证关系、主要矛盾与次要矛盾的关系。通过几种典型算法的设计比较中，认识代价与效率的平衡。

 

三、课程内容安排和要求

本课程理论授课32学时，实验教学20学时。

理论授课采用讲授方式，下面分章说明教学内容和要求。其中，掌握指能深刻理解概念，并能够编写代码；理解指清楚概念及相关结构，能看懂代码；应用指能够应用公式、图形、伪代码等方式描述解决方案；了解表示知道并区分概念。

（一）教学内容、要求及教学方法

第一章 基本概念，授课学时3

1)     数据结构的定义，掌握

2)     数据结构三个层次概念以及关系，掌握

3)     存储结构的四种类型，理解

4)     运用数据结构方法，抽象描述客观事物，应用

5)     算法基本概念，理解

6)     常用算法思想：分治、递归、贪心、迭代等，了解

7)     算法复杂度定义及分析方法，应用

教学建议：本部分教学应重视利用数据结构描述客观事物，它既是对数据结构三个层次掌握程度的检验，也是对从数据结构的角度观察问题的训练，是运用数学与自然科学建立问题解决模型的基础。

第二章 线性结构

2.1 线性表 授课学时5，建议上机实验4学时

1)     线性表的定义和特点，掌握

2)     顺序表的结构声明与插入、删除算法，掌握

3)     单向链表的结构声明、特点，理解

4)     单向链表的创建、插入、删除、查找算法，掌握

5)     双向链表的结构及插入和删除算法，掌握

6)     循环链表的结构特点，掌握

7)     利用顺序表和链表解决简单问题，应用

2.2 栈和队列 授课学时2，建议上机实验4学时

1)     栈的定义、特点，顺序栈、链栈的入栈和出栈算法，掌握

2)     利用栈的特点解决简单问题，应用

3)     队列的定义、特点，循环队列的特点和算法，掌握

4)     利用队列的特点解决简单问题，应用

2.3 串（自学）

2.4 数组和广义表 授课学时1

1)     矩阵的定义，掌握

2)     二维矩阵数据元素的顺序表示与存储位置计算，应用

3)     二维矩阵的压缩方法，稀疏矩阵的三元组方法，应用

4)     广义表的定义和存储，应用

教学建议：二、三、四章教学应注意对比数组实现方法和链表实现方法和算法的执行效率，通过对比引导学生建立连续处理和离散处理的方法模型，引导他们根据问题特点和实际需求，理性思考、定量测算和做出合理决策。

第三章 非线性结构

3.1 树与二叉树 授课学时5，建议上机实验4学时

1)     树结构的定义和相关术语，掌握

2)     二叉树的定义和结构声明，理解

3)     二叉树的顺序存储结构，理解

4)     二叉树的链接存储结构，掌握

5)     二叉树的遍历算法，掌握

6)     二叉树（排序树）的创建，理解

7)     二叉树的重构，应用

8)     树、森林和二叉树的转换，应用

3.2 图结构 授课学时3

1、  图的定义和相关术语，掌握

2、  利用邻接矩阵存储图，理解

3、  利用邻接表存储图，理解

4、  图的深度优先和广度优先遍历算法，应用

5、  最小生成树与最短路径，了解

教学建议：本部分可引入递归算法，对比递归和迭代算法的框架、特点和应用场景，引导学生建立这两种基本的问题解决方法的框架模型。

本部分还可以与常用算法结合，例如最短路中贪心思想的应用。

第四章 查找与排序

4.1 查找 授课学时2，建议上机实验2学时

1)       顺序查找算法，识记，平均查找长度的计算，掌握

2)       二分查找的特点和算法，掌握

3)       分块查找的特点，了解

4)       二叉排序树的查找算法和特点，理解

5)       哈希查找的特点及线性探测再散列、二次探测再散列方法，了解

4.2 排序 授课学时3，建议上机实验2学时

1)       排序的基本概念，掌握

2)       简单插入算法、简单选择算法，冒泡排序算法，掌握

3)       快速排序算法，理解

4)       排序算法性能比较，理解

教学建议：本部分可以集中对比各种算法的执行效率和优化思路，引入算法的时空概念、相互转换和平衡。

第五章 资源管理

5.1 操作系统的概念 建议授课2学时

1)       操作系统的定义、功能，理解

2)       操作系统的分类，了解

5.2 多道程序设计 建议授课4学时

1)       并发程序设计概念，理解

2)       进程与线程，理解

3)       进程的互斥与同步，掌握

4)       进程间通信，理解

5.3 存储空间管理 建议授课2学时

1)       内存管理：内存分配的策略、分类、共享与保护等，理解

教学建议：本部分主要培养学生理解资源管理的概念，能进行并发多任务程序设计。

 

（二）自学内容和要求

1、  什么是串，理解

2、  串的存储，了解

3、  串的模式匹配与应用，了解

4、  哈夫曼树及树的应用，了解

5、  其他快速排序算法，例如归并、基数、希尔等，了解

6、  外存文件的概念、结构和实现，了解

 

（三）实践性教学环节和要求

上机实验是将本课程理论知识转化为解决实际问题能力的重要环节，课程利用实践环节在程序设计与实现的基本技能上对学生有足够的指导和训练。本部分列出根据课程内容制定的上机实验的建议内容和计划，教师可在以下内容基础上自行设计实践环节。

建议总上机学时20

1、  顺序表的创建、插入、删除，2学时

2、  链表的创建、插入、删除，2学时

3、  栈和队列的创建，入栈、出栈、入队、出队、应用，4学时

4、  二叉树的创建、遍历、应用，4学时

5、  顺序检索、二分检索， 2学时

6、  简单插入、简单选择、冒泡排序算法，2学时

7、  并发程序设计，4学时

教学建议：通过布置适当的上机作业题目，锻炼学生问题解决的分析能力和设计算法、编写程序解决问题的实际软件工程能力，在上机指导过程中，应引入软件工程的一些基本原则和方法。

 

（四）课程目标与教学内容和方法的对应关系

本课程的学习目标与教学内容和方法的对应关系如表3。

表3 课程目标与课程内容和方法的对应关系表

课程 目标	对应的教学内容和方法
	（一） 第一章	（一） 第二章	（一） 第三章	（一） 第四章	（一） 第五章	（三） 实践教学
1	P	P	P	P	P
2	P	P	P	P	P	P
3	P			P		P

 

四、考核方式

本课程考核成绩由三个部分组成：平时考核、实验考核和期末考试。

建议各部分考核分配比例如下：

1.        平时考核

平时考核至少包括两部分，例如随堂测验，作业完成质量等，占总成绩20%。

2.        实验考核

上机实验完成情况和质量，包括实验当场表现和实验报告，占总成绩20%。

3.        期末考核

期末考核全课程知识点掌握情况，采用闭卷考试方式，占总成绩60%。

课程目标与考核方式的关系如表4所示。

表4 课程目标与考核方式的关系表

课程目标	对应的考核方式
	平时考核	实践考核	期末考试
1	P		P
2	P	P	P
3		P	P

 

五、建议教材及参考资料

（一）建议教材：

数据结构（C语言版）第2版，严蔚敏等，人民邮电出版社2015-02

软件技术基础（第4版），黄迪明等编著，电子科技大学出版社2014-04

（二）参考资料：

数据结构与算法图解，杰伊·温格罗（Jay Wengrow）著，袁志鹏译，人民邮电出版社2019-04

数据结构与算法—C语言版，传智播客，清华大学出版社2016-09

深入理解计算机系统（原书第3版），兰德尔 E.布莱恩特（Randal E.·Bryant）著，龚奕利，贺莲译，机械工业出版社2021-01

操作系统――精髓与设计原理（第九版）William，Stallings（威廉.斯托林斯）著，陈向群译，电子工业出版社2020-07

计算机软件技术基础（第四版）徐士良，葛兵著，清华大学出版社2014-09

数据结构与算法分析 C语言描述（原书第2版），马克·艾伦·维斯（Mark，Allen，Weiss）著，冯舜玺译，机械工业出版社2019-04

 

六、课程目标的达成途径和评价办法

通过分别设置课堂讲授、自学、实践性教学环节，并合理安排相应的学时数来达到本课程的目标。与之相对应，课程的考核评价指标综合考虑了平时、期中考试、实验和期末考试四个方面，并分配各个部分的比例权重。

课程目标的达成度评价办法及参考权重如表5，可根据实际考核内容进行调整。

表5：课程目标达成度评价表

课程名称：                      学年-学期：       

授课教师：                      学生样本来源：  授课班                 学生人数：  人

评价结论、问题分析及改进措施

评价结论：

问题分析：

改进措施：

任课教师签字：                                      课程组负责人签字：             

             年     月     日                                       年     月     日

（一）建议教材：

数据结构（C语言版）第2版，严蔚敏等，人民邮电出版社2015-02

软件技术基础（第4版），黄迪明等编著，电子科技大学出版社2014-04

（二）参考资料：

数据结构与算法图解，杰伊·温格罗（Jay Wengrow）著，袁志鹏译，人民邮电出版社2019-04

数据结构与算法—C语言版，传智播客，清华大学出版社2016-09

深入理解计算机系统（原书第3版），兰德尔 E.布莱恩特（Randal E.·Bryant）著，龚奕利，贺莲译，机械工业出版社2021-01

操作系统――精髓与设计原理（第九版）William，Stallings（威廉.斯托林斯）著，陈向群译，电子工业出版社2020-07

计算机软件技术基础（第四版）徐士良，葛兵著，清华大学出版社2014-09

数据结构与算法分析 C语言描述（原书第2版），马克·艾伦·维斯（Mark，Allen，Weiss）著，冯舜玺译，机械工业出版社2019-04