《数据结构》课程大纲

数据结构课程教学大纲

一、课程性质和目标L课程性质数据结构是计算机类专业的一门核心、学科基础课

2.课程目标通过本课程的理论教学和实践训练，使学生具备以下能力:

（1）掌握数据结构的基本概念，深刻理解各种数据结构的逻辑特性和存储表示方法具有依据工程实际问题的需求来合理组织数据、并在计算机中有效地存储数据的能力；能够对复杂工程中的算法问题进行抽象、提取和归纳

（2）能够在各种数据结构基础上进行算法设计与描述，掌握算法时空间复杂度的分析方法能够设计数据结构和算法，具有算法分析的能力；能够运用数据结构的基础知识，表达和分析计算机领域的复杂工程问题

（3）能够针对复杂工程中的算法问题，设计出比较合理的解决方案，并通过具体的编程语言加以实现，同时体现一定的创新思维能力

（4）能够基于数据结构基本原理和文献研究，针对复杂工程中的算法问题设计合理的研究方案课程要求达到的知识目标、能力目标和素养目标如下知识目标掌握数据结构的基本概念，掌握各种数据结构的逻辑特性、存储表示和基本算法能力目标针对复杂工程中的算法问题，能够设计数据结构和算法，进行算法分析，并通过具体的编程语言加以实现，具有计算思维能力和创新思维能力，能够为算法设计提出合理的改进建议素养目标具有工程素养，能够坚持职业操守和道德规范，具有精益求精的工匠精神和探索未知终身学习的意识，具有科技报国的社会责任感

3.课程目标与毕业要求的对应关系毕业要求指标点课程目标（1（2级指标）级指标）

1.2能够基于数学、自然科学和计算机专业知识对涉及计算机应用

1.工程知识课程目标

（1）领域软件设计、算法设计的复杂工程问题进行建模与求解

三、哈夫曼编码【课后作业】

1.课后配套习题、实验

2.数据结构0J平台上机练习http:〃www.bjfuacm.com/structure/【实验内o容】二叉树的应用【实验要求】能够借助二叉树的基本操作来解决某些实际应用问题，如哈夫曼编码问题、利用表达式树进行表达式求值的问题等【课程思政教学案例】根据树结构的特点引申出家族、家谱的概念，通过讲解家谱的发展历程，鼓励学生学习传统文化，辩证地传承传统文化，取其精华，去其糟粕教育学生要爱自己的家，家庭成员要团结友爱，家庭是社会的细胞，一个个家庭的幸福才能组成国家的幸福另一方面，祖国是我们共同的家，只有祖国强大了，我们才能有一个安定、团结的社会环境因此爱家、爱家族、爱祖国是统一的，不能将他们割裂开来第六章图理论8学时，实验2学时，支撑课程目标

1、2【教学目标】掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系熟练掌握图的两种搜索路径的遍历深度优先搜索和广度优先搜索的算法掌握构造最小生成树的两种算法及拓扑排序算法的思想，掌握迪杰斯特拉算法了解关键路径的概念和求解方法，了解弗洛伊德算法【重点难点】重点图的逻辑结构和存储结构；图的深度优先搜索和广度优先搜索两种遍历算法；图的连通性和生成树的概念；拓扑排序、最短路径的含义及算法难点图的遍历；关键路径；最短路径【教学内容】第一节图的定义和术语第二节图的存储结构

一、邻接矩阵

二、邻接表

三、十字链表第三节图的遍历

一、深度优先搜索

二、广度优先搜索第四节图的连通性问题

一、无向图的连通分量和生成树

二、最小生成树第五节有向无环图及其应用

一、拓扑排序

二、关键路径第六节最短路径

一、单源最短路径

二、每对顶点之间的最短路径【课后作业】

1.课后配套习题、实验

2.数据结构0J平台上机练习http:〃www.bjfuacm.com/structure/o【实验内容】图的应用【实验要求】能够借助图的基本操作来解决某些实际应用问题，如最短路问题、最小生成树问题等【课程思政教学案例】

1.在最小生成树的学习过程中，介绍城市之间修建高速公路或铺设管道的案例，而在讲解过程中可以就势引申出高铁修建、进藏公路建设、等内容，进而可以针对这些内容对学生进行相关的爱国主义精神教育，提升学生的民族自豪感，帮助学生形成正确的人生观和良好的职业素养，培养学生的工程素养，能够坚持职业操守和道德规范

2.对于最短路径、关键路径、拓扑排序等关键算法，了解发明者的生平和事迹，体会算法之美，认识数据结构和算法在计算学科中的重要作用，提倡工匠精神，激励创新和改造，培养学生探索未知终身学习的意识第七章查找（理论6学时，实验2学时，支撑课程目标

（2）、

（3）、

（4））【教学目标】熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查找算法及其实现，了解平衡二叉树、B-树和B+树的各种操作熟练掌握散列表的构造方法、处理冲突的方法，深刻理散列表与其他结构的表的实质性的差别，了解各种散列函数的特点掌握描述折半查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度【重点难点】重点查找的基本概念；查找的基本方法；顺序查找、二分查找和分块查找；二叉排序树查找；哈希函数和解决冲突的方法难点二叉排序树查找；平衡二叉排序树【教学内容】第一节静态查找表

一、顺序表的查找

二、有序表的查找

三、分块查找第二节动态查找表

一、二叉排序树

二、平衡二叉树

三、B-树和B+树第三节哈希表

一、什么是哈希表

二、哈希函数的构造方法

三、处理冲突的方法

四、哈希表的查找及其分析【课后作业】

1.课后配套习题、实验

2.数据结构0J平台上机练习:http://www.bjfuacm.com/structure/o【实验内容】查找算法的应用【实验要求】能够根据实际应用问题选用合适的查找算法，并能够通过计算ASL分析其查找性能【课程思政教学案例】在顺序查找、二叉排序树查找和散列表查找中给学生传达“提高效率”的思想，引导学生在解决复杂工程问题时尽量以节省时间和空间成本为目标来设计解决方案，将统筹规划、大局意识、不断创新、追求卓越融入到课程难点讲授中第八章内部排序（理论6学时，实验2学时，支撑解目标

（2）、

（3）、

（4））【教学目标】明确排序的基本概念，排序方法的分类深刻理解排序算法的过程、特点及其依据的原则，并能加以灵活应用掌握各种排序方法的时间和空间复杂度的分析方法能从关键字间的比较次数和移动次数分析算法的平均情况和最坏情况的时间性能理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的快速排序、堆排序和归并排序等高效排序方法是本章的学习重点和难点【重点难点】重点排序的基本概念，几种排序方法，各种排序方法性能比较难点堆排序；快速排序；归并排序【教学内容】第一节概述第二节插入排序

一、直接插入排序

二、其他插入排序

三、希尔排序第三节交换排序

一、冒泡排序

二、快速排序第四节选择排序

一、简单选择排序

二、树形选择排序

三、堆排序第五节归并排序第六节基数排序第七节各种内部排序方法的比较讨论【课后作业】

1.课后配套习题、实验

2.数据结构0J平台上机练习http://www.bjfuacm.com/structure/【实验内o容】排序算法的应用【实验要求】能够根据实际应用问题选用合适的排序算法，并能够从时间和空间复杂度上分析其排序的性能【课程思政教学案例】通过引入锦标赛制建立、螺钉与螺母问题向学生传递“讲究秩序”的观念，实际生活中银行排队叫号系统根据各类情况进行排序，在指定位置享受一对一的服务，通过这种方式，巧妙减轻了银行的压力，增强了人们的秩序感，避免了由于人工排队引起的不必要的冲突，同时还能够使等待的人先去处理其他的事或者休息，极为人性化课程实验过程中的思政教学思想以上教学内容和安排中实验环节包含了复杂的程序设计实验操作，将思政教育中对个人精神品格能力的培养渗透到实验实践环节过程中也是专业课程进行课程思政建设的重要途径一方面是团队协作精神的培养，通过学生分组完成相关的实践作业，可以有效地提升学生团队精神，提高协作意识；而另一方面很多实践操作都需要学生从一个又一个的错误中走出来，对于学生克服困难，勇攀高峰的无畏精神塑造是非常有利的这就要求指导实践操作的教师能因势利导，充分利用实践教学的有利契机，将思政教育的内容引入其中数据结构实验教学大纲课程名称数据结构适用专业计算机科学与技术、软件工程、数字媒体技术、信息安全、教育技术学实验室名称先修课程C/C++程序设计、离散数学

一、课程简介数据结构是一门专业基础课，是学习其他软件开发与设计等方面课程的基础主要内容包括线性表、栈和队列、串、数组和广义表、树、图、查找算法和排序算法数据结构研究数据的组织方式，内容丰富、学习量大，隐含在各部分内容中的方法和技术多，旨在让学生掌握计算机软件系统所必需的数据结构的算法要求学生掌握贯穿全课程的动态链表存储结构，掌握算法设计的动态性和抽象性要求学生学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应算法，初步掌握算法的时间与空间性能分析技巧,并培养复杂程序设计的技能

二、实验教学任务和目的上机实践是对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验通过上机实验，使学生深入地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后续课程奠定基础

三、主要仪器设备硬件计算机软件Visual C++

6.0

四、实验方式与基本要求利用C/C++语言完成算法设计和程序设计，上机调试通过实验程序，输入数据，检验程序运行结果，给出具体的算法分析，包括时间复杂度和空间复杂度等，撰写实验报告

五、实验课时安排具体实验和课时安排见下表实验组开设序号实验名称学时实验者类别类型数要求实验一线性表及其应用设计性本科生必做21实验二栈、队列及其应用设计性本科生必做21实验三树及其应用设计性本科生必做21实验四图及其应用设计性2本科生1必做实验五查找验证性2本科生1必做实验六排序验证性2本科生1必做实验七二叉排序树的基本操作设计性2本科生1选做实验八哈希表的查找操作设计性2本科生1选做实验九图的最小生成树设计性2本科生1选做实验十综合设计综合性4本科生1-3必做学时总计22学时（其中必做16学时）

六、实验教学内容实验一实验目的

1.深入了解线性表的各种存储结构

2.熟练掌握在各种存储结构上进行插入、删除等操作的算法

3.通过线性表结构解决现实中的一些问题实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据，检验程序运行结果4给出具体的算法分析，包括时间复杂度和空间复杂度等.

5.撰写实验报告实验内容分别使用顺序表和单链表实现线性表的初始化、插入、删除和显示功能实现两个有序单链表合并为一个有序单链表的功能，要求不额外增加存储空间^4实义器计算机、Visual C++

6.0实验二实验目的

1.深入了解栈和队歹U的特性

2.掌握栈和队列在不同存储结构下的基本操作

3.掌握栈和队列的典型应用实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.撰写实验报告实验内容

1.使用栈的顺序存储结构实现栈的基本操作和逆序输出、数制转换、括号匹配3个应用；

2.使用循环队列实现带功能菜单的银行业务办理排号系统^4实义器计算机、Visual C++

6.0实验三实验目的

1.熟悉树的各种存储结构的特性

2.掌握二叉树的前、中、后序遍历算法和非递归算法的实现

3.会应用树的结构解决具体问题实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序，检验程序运行的正确性

3.进行算法的时间复杂度和空间复杂度分析

4.撰写实验报告实验内容编写二叉树先、中、后序的递归遍历算法、中序遍历二叉树的非递归函数，编写求二叉树中叶子结点数目的递归算法^4实义器计算机、Visual C++

6.0实验四实验目的

1.熟悉图的各种存储结构的特性

2.掌握图的深度优先和广度优先算法

3.会应用图的结构解决具体问题实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告实验内容编写邻接矩阵或邻接表存储结构下图的创建、深度优先遍历、广度优先遍历和求连通子图的个数的算法^4实义器6算机、Visual C++

6.0实验五实验目的

1.熟悉查找的基本概念，平均查找长度

2.掌握基于线性表的查找顺序查找、折半查找

3.掌握基于树表的查找二叉排序树实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告实验内容实现线性表的带监视哨的顺序查找和折半查找算法^4实义器计算机、Visual C++

6.0实验六实验目的

1.熟悉常用排序方法的特性

2.应用排序方法解决具体问题实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告

2.2能够通过文献综述和分析，研究获得解决计算机应用领域复杂

2.问题分析课程目标

（2）工程问题的多种可行方案

3.设计/开发解

3.3能够根据设计目标在系统设计和过程组织中体现改进和创新意课程目标

（3）决方案识

4.1能够针对计算机应用领域复杂工程问题进行理论分析和实验方

4.研究课程目标

（4）案设计

二、课程教学内容及要求

1.教学内容掌握数据结构的基本概念和常用术语；理解线性表、树、图、查找、排序的结构及特点；掌握顺序和链式存储结构下基本数据结构及其常用算法的编写；初步了解算法的时间分析和空间分析技术；会将所学知识应用于解决实际问题，培养学生的数据抽象能力和程序设计的能力

2.教学要求有关本课程的基本概念、基本知识和基本算法设计与实现，作为教学的重点内容，要求学生牢固掌握并熟练运用讲授时，以具体案例为主,深入地介绍算法的基本思想，积极引导学生将主要精力放在掌握基本算法的设计和实现上鼓励学生自学，培养学生的自学能力，调动学生学习的主观能动性,注意将培养和提高学生的分析问题和解决问题的能力放在重要位置课程开展线上线下混合式教学，通过课前、课中和课后各环节进行线上线下的设计与配合同时安排有上机实验环节，要求学生完成实验代码并提交实验报告，配套有专题0J平台实验网站综合设计环节要求学生分组完成，充分发挥主观能动性、团结协作，针对较为复杂的应用问题，能够综合运用所学的各种数据结构进行算法设计和实现，注重学生数据抽象能力和算法设计能力的培养积极挖掘课程思政元素，将课程思政典型案例融入相应教学过程

三、课程教学重点和难点重点本课程的有关基本理论和基本概念，常用数据结构的逻辑结构、存储结构及相应的算法，顺序和链式存储结构下基本操作的算法实现和区别，对算法的时间分析和空间分析技术难点复杂结构尤其是树、图的存储结构定义及算法实现，图的应用如最短路径和关键路径学生数据抽象能力和程序设计能力的培养

四、课程考试形式和要求实验内容编写代码分别以直接插入排序、改进的冒泡排序和归并排序实现整数数组的排序，并分析时间复杂度^4实义器计算机、Visual C++

6.0实验七实验目的

1.掌握二叉排序树的含义及其在计算机中的存储实现

2.掌握在二叉排序树上查找操作的算法实现

3.掌握二叉排序树的插入、删除操作的算法实现实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告实验内容

1.建立二叉排序树

2.在二叉排序树上实现对给定值进行查找操作（验证性内容）

3.在二叉排序树上实现插入、删除一个指定结点（设计性内容）

4.判断一棵二叉树是否为二叉排序树（设计性内容）^4实义器计算机、Visual C++

6.0实验八实验目的

1.掌握哈希表、哈希函数与哈希冲突的概念

2.掌握哈希表的构造方法及其计算机的表示与实现

3.掌握哈希表查找算法的实现实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告实验内容

1.以开放地址法中的线性探测再散列法处理冲突，实现哈希表的建立、查找和插入操作

2.以链地址法，也叫拉链法处理冲突，实现哈希表的建立，查找和插入操作

3.用哈希查找法实现班级信息的查找^4实义器计算机、Visual C++

6.0实验九实验目的

1.掌握图的相关概念

2.掌握用邻接矩阵和邻接表的方法描述图的存储结构

3.掌握图的深度优先搜索和广度优先搜索遍历的方法及其计算机实现

4.实现最小生成树的有关算法实验注意事项

1.利用C/C++语言完成算法设计和程序设计

2.上机调试通过实验程序

3.输入数据,检验程序运行结果

4.给出具体的算法分析，包括时间复杂度和空间复杂度等

5.撰写实验报告实验内容用邻接矩阵作为图的存储结构建立一个网，并构造该网的最小生成树^4实义器计算机、Visual C++

6.0实验十实验目的着眼于原理与应用的结合，学会把学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能起到深化理解和灵活掌握教学内容的目的综合设计是软件设计的综合训练，包括问题分析（需求分析）、总体结构设计和用户界面设计（概要设计）、程序设计基本技能和技巧等，即一整套软件工程规范的训练和科学作风的培养实验注意事项

1.「3名同学为一组，选出一名组长，自由结合，每组选择一个题目

2.上交设计材料

（1）撰写设计报告（含纸质打印稿和电子稿）

（2）上交设计代码设计报告主要包括以下部分

1.需求分析（10分）

2.概要设计（20分）

（1）抽象数据类型的描述

（2）程序结构图（功能模块图）

3.详细设计（30分）

（1）存储结构的描述（含描述对象的存储结构）

（2）算法的详细设计（对复杂算法画出其程序流程图）

（3）函数的调用关系图

4.调试分析（10分）

5.用户使用说明（10分）

6.测试结果（10分）

7.附录（10分）源程序清单（包括注释）实验内容每组自选一题，可从参考题目中选取，也可自拟题目（需经老师审核）^4实义器计算机、Visual C++

6.0

七、实验考核方式与成绩评定根据实验报告、综合设计报告评分，计入学生平时成绩

八、实验教材和参考资源

1.实验教材李冬梅《数据结构习题解析与实验指导》，人民邮电出版社，2017年8月

2.参考资源程杰《大话数据结构》，清华大学出版社，2011年6月

九、说明通过数据结构课程实验，培养学生对课程的兴趣，使学生深入地理解常见数据结构的逻辑结构和物理结构的基本概念、基本操作及相关应用，培养基本的、良好的程序设计技能，编制高效可靠的程序，为后续软件开发与设计类课程打下基础数据结构课程设计课程代码学时实践1周学分1课程类别学科基础课（实践）开课学期3编写日期

一、德程42质我目标

1.课程性质数据结构课程设计是计算机类专业的一门核心、学科基础课，是数据结构课程的集中实践环节

2.课程目标通过数据结构课程设计实习的训练，使学生具备下列能力

（1）针对复杂工程问题能够运用数据结构的理论知识给出算法的设计思想，能够根据数据逻辑结构的知识区分出复杂工程问题数据之间存在的关系，并能够给出数据的存储结构

（2）能够在复杂工程问题的设计和实现环节，融入社会、健康、安全、法律、文化和环境等因素，科学开展实验

（3）能够运用数据结构的理论知识，借助文献综述和分析，设计并给出复杂工程问题的多种解决方案，并利用相应开发工具给出解决方案的实验结果

3.课程目标与毕业要求的对应关系（1毕业要求级课程目标（2指标）指标点级指标）

2.问题分析课程目标

（1）

2.3能够通过文献综述和分析，研究获得解决计算机应用领域复杂工程问题的多种可行方案课程目标

（2）

3.设计/开发解

3.4能够在计算机应用领域复杂工程的设计和实现环节，考虑社会、决方果健康、安全、法律、文化和环境等因素

4.研究课程目标

（3）

4.2能够根据实验方案构建实验系统、搭建仿真实验平台，安全开展实验并获取有效的结果数据

二、锦程敖皆为容、皆时台肥和基洋要求教学内容（支撑叫目标⑴、⑵、

（3））:结合实际问题，给定一个综合性的题目，题目涉及常见的数据结构（如线性表、栈、队列、树、图等）及其基本操作题目示例1:基于不同策略的英文单词的词频统计和检索系统一篇英文文章存储在一个文本文件中，从该文件中读取英文单词，过滤掉所有的标点然后分别基于线性表、二叉排序树和哈希表不同的存储结构，完成单词词频的统计和单词的检索功能其中，检索策略总计包括以下6种基于顺序表的顺序查找、基于链表的顺序查找、基于顺序表的折半查找、基于二叉排序树的查找、基于开放地址法的散列查找、基于链地址法的散列查找不论采取哪种检索策略，实现的功能均相同同时计算不同检索策略下的平均查找长度ASL,通过比较ASL的大小，对不同检索策略的时间性能做出相应的比较分析题目示例2美团餐馆预订管理信息系统基于给定的美团餐馆和个人信息的相关数据，设计并实现一个美团餐馆预订管理信息系统，系统包括个人用户、商家（餐馆）和后台管理员三种用户类型其中，个人用户可对用户本人的个人信息进行管理，并可查询餐馆信息、进行餐馆预订、获取推荐餐馆等，商家可对自身的餐馆信息进行管理、处理餐馆预订信息等，后台管理员可对个人用户和商家进行管理进度分配第1天问题分析根据设计题目的要求，理解实习任务，明确相关算法，搜集可用资源，熟悉实习环境第2天方案设计包括逻辑设计和详细设计

（1）逻辑设计对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图

（2）详细设计定义相应的存储结构并写出各函数的伪码算法在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架第3-5天代码编写把详细设计的结果进一步求精为程序设计语言程序同时加入一些注解，使程序中逻辑概念清楚第6天代码调试与测试采用自底向上，分模块进行，即先调试低层函数能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果第7天结果分析与报告撰写程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果，对算法的时间、空间复杂度进行分析，依据模板撰写课程设计报告基本要求能够将数据结构课程中所学的基本知识融会贯通，综合运用所学的知识解决相关的实际问题，能够把所学知识（包括算法和结构）在计算机上用编程语言加以实现，并且能够根据实际需求创建自己的数据结构和实现自己的算法

三、薛程号其它锦福的联系和今工本课程是学生学到的程序设计知识和数据结构理论知识的综合运用，是数据结构课程的具体实践，先修课为程序设计基础、离散数学和数据结构本课程可以C/C++或Java语言作为算法描述和上机实践的工具同时，本课程又是软件开发与设计等课程的基础，如算法设计与分析、数据库系统、操作系统、编译原理等课程

四、锦程考核方式

1.考核方式课程设计成绩为百分制，通过出勤情况、提交的源程序和设计报告三方面来考核其中，课堂情况占总成绩的10%,源程序占60%,设计报告占30%

2.评分标准源程序主要考查程序是否正确、健壮、高效并具有良好的操作界面，代码是否结构清楚设计报告包括所涉及的数据结构说明、算法流程图、算法时间和空间复杂度分析,重点考核是否符合设计规范，是否灵活运用所学知识评分项目评分标准分数课堂情况独立完成算法设计、代码编写和调试10分（共10分）查阅资料后独立完成算法设计、代码编写和调试8分查阅资料并合作讨论后完成代码编写和调试6分借助资料和讨论后完成基本功能的代码编写5分及以下源程序情况（共60分）56-60分代码思路清晰明确，程序正确、健壮、高效并具有良好的操作界面51-55分代码思路合理，程序正确、健壮，具有良好的操作界面代码思路较合理，程序正确，具有良好的操作界面45-50分代码思路合理性一般，程序正确，操作界面一般44分以下设计报告情况（共30分）26-30分设计报告包括了所涉及的数据结构说明、算法流程图、算法时间和空间复杂度分析，符合设计规范并能灵活运用所学知识21-25分设计报告包括了所涉及的数据结构说明、算法流程图，符合设计规范，知识运用能力良好15-20分设计报告包括了所涉及的数据结构说明、算法流程图，符合设计规范，知识运用能力一般15分以下设计报告包括了所涉及的数据结构说明、算法流程图，符合设计规范，知识运用能力较差

五、建衩敖材与敖学参考书建议教材严蔚敏，李冬梅，吴伟民.数据结构（C语言版第2版）[M].北京:人民邮电出版社,

2021.建议教学参考书

[1]李冬梅.数据结构习题解析与实验指导[M].北京:人民邮电出版社,

2022.

[2]程杰.大话数据结构[M].北京清华大学出版社,

2020.

[3]啊哈！算法[M].北京:人民邮电出版社,

2014.该课程为考试课，采用纸质闭卷形式进行课程考试成绩由“平时成绩”（占30%）和“期末成绩”（占70%）构成其中，平时成绩以学生平时出勤、课堂讨论表现、作业及实验（线上评价+实验报告）完成情况等方面予以评分;期末考试主要考查数据结构的基本概念、基本理论、基本知识、算法的应用和基本算法的设计，测评学生的理解、判断、课后作业形章目教学内容教学时数教学方式或手段式备注弟一早绪论4讲授（多媒体）习题实验一弟一线性表8讲授（多媒体）习题A早A*-*实验二第二早栈和队列4讲授（多媒体）习题第四章4讲授（多媒体）习题串、数组和广义表实验三第五章树和二叉树8讲授（多媒体）习题实验四第六章图8讲授（多媒体）习题实验五第七章查找6讲授（多媒体）习题实验六第八章内部排序6讲授（多媒体）习题实验一线性表及其应用2实验实验报告实验二栈和队列及其应用2实验实验报告实验三二叉树的应用2实验实验报告实验四图的应用2实验实验报告实验五查找算法的应用2实验实验报告实验六排序算法的应用2实验实验报告实验七综合设计4实验设计作品分析、应用和算法设计等能力

五、课程教学时数分配计64（理论48+实验16）第一章绪论（理论4学时，支撑课程目标

（1）、

（2））【教学目标】掌握数据结构的基本概念，掌握算法的时间复杂度和空间复杂度的分析方法,了解抽象数据类型的定义和使用，了解算法的描述方法【重点难点】重点数据结构中常用的基本概念和术语；算法描述和分析方法难点算法时间复杂度的分析【教学内容】第一节基本概念和术语

一、什么是数据结构

二、数据、数据元素和数据对象

三、数据结构

四、数据类型和抽象数据类型第二节抽象数据类型的表示与实现

一、类C语言介绍

二、抽象数据类型示例第三节算法和算法分析

一、算法

二、算法设计的要求

三、算法效率的度量

四、算法的存储空间需求【课后作业】

1.说说数据结构和程序设计的关系？

2.数据的逻辑关系、数据的存储结构及数据的运算之间存在怎样的关系？【课程思政教学案例】在概述中结合前沿应用重点介绍数据结构的研究对象和算法性能评价方法，通过介绍一个“好”算法的衡量标准来向学生传达大局意识，统筹兼顾；另外强调这门课“怎么学”，打牢基础，深入理解算法，结合芯片领域坚定学生实现关键核心技术自主可控的决心，将“大局意识”和“合作精神”融入整门课的学习第二章线性表（理论8学时，实验2学时，支撑课程目标

（1）、

（2）、

（4））【教学目标】熟练掌握顺序存储结构（顺序表）和链式存储结构（链表）的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等掌握顺序表的查找、插入和删除算法，掌握链表的查找、插入和删除算法能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合【重点难点】重点线性数据结构的定义与存储；顺序表、单链表、循环链表、双链表的特点以及基本运算和算法难点双链表插入、删除运算的算法；利用链表结构设计算法【教学内容】第一节线性表的类型定义

一、线性表的特点

二、线性表的抽象数据类型第二节线性表的顺序表示和实现

一、线性表的顺序存储表示

二、顺序表中基本操作的实现第三节线性表的链式表示和实现

一、单链表的定义和表示

二、单链表基本操作的实现

三、循环链表

四、双向链表第四节一元多项式的表示及相加

一、一元多项式的表示

二、一元多项式的加法【课后作业】

1.比较线性表的顺序存储结构和链式存储结构的优缺点

2.课后配套习题、实验

3.数据结构0J平台上机练习http:〃www.bjfuacm.com/structure/0【实验内容】线性表及其应用【实验要求】能够分别以顺序表和单链表两种不同的存储结构创建一个学生表或图书表，并能够基于不同的存储结构分别实现相关的创建、查找、插入、删除、排序等算法【课程思政教学案例】通过讨论顺序结构的“优劣”，向学生传达唯物辩证法基本观点；并在一元多项式的求和应用问题中，介绍秦九韶算法，通过介绍中国古代算法，增加学生的民族自豪感第三章栈和队列（理论4学时，实验2学时，支撑课程目标（D、

（2）、

（4））【教学目标】掌握栈和队列的特点，并能在相应的应用问题中正确选用熟练掌握栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件掌握利用栈实现表达式求值的算法，了解迷宫求解算法理解递归算法执行过程中栈的状态变化过程，了解将递归程序转换为非递归程序的方法熟练掌握循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况了解队列的应用【重点难点】重点栈和队列的定义及存储；栈和队列的基本运算和应用难点后缀表达式的算法；数制的换算；循环队列的特点及判断溢出的条件；利用队列的特点设计相关的应用问题【教学内容】第一节栈

一、栈的定义和特点

二、顺序栈的表示和实现

三、链栈的表示和实现第二节栈的应用

一、数制转换

二、括号匹配的检验

三、行编辑程序

四、迷宫求解

五、表达式求值第三节队列

一、队列的类型定义

二、循环队列一一队列的顺序表示和实现

三、链队列一一队列的链式表示和实现【课后作业】

1.课后配套习题、实验

2.数据结构0J平台上机练习http://www.bjfuacm.com/structure/【实验内o容】栈和队列及其应用【实验要求】能够借助栈和队列的基本操作来解决某些实际应用问题，如表达式求值、迷宫问题、舞伴问题等【课程思政教学案例】L队列作为一种常用的数据结构，其特点是先进先出，其与日常生活中的排队情况本质一致，可引申到遵守社会秩序、尊重社会公德的层面，进而对学生进行社会主义核心价值观教育

3.递归思想是“数据结构”众多算法实现的一个基础在讲解该思想时就可以把个人的所作所为抽象成递归最终的回溯结果，引申出的道理就是每个人的所作所为可能是渺小的，但所有重大的变革或发展都最终是众多个体努力的结果，进而可以教导学生培养脚踏实地的工匠精神，机会永远垂青的是有所准备的人第四章串、数组和广义表理论4学时，支撑课程目标

1、2【教学目标】了解串的顺序存储结构和堆存储结构掌握串的古典的模式匹配算法掌握数组的地址计算方法了解稀疏矩阵的两种压缩存储方法的特点和适用范围了解广义表的结构特点及其存储方法【重点难点】重点串的表示实现；多维组的两种顺序存储方式；稀疏矩阵的三元组表表示方法难点串的模式匹配；稀疏矩阵的压缩存储表示下的运算实现【教学内容】第一节串类型的定义第二节串的表示与实现

一、定长顺序存储表示

二、串的常用操作实现第三节串的模式匹配算法

一、求子串位置的定位函数Index

二、模式匹配的改进第四节数组

一、数组的定义

二、数组的顺序表示与实现第五节矩阵的压缩存储

一、特殊矩阵

二、稀疏矩阵第六节广义表

一、广义表的定义

二、广义表的存储结构【课后作业】

1.课后配套习题

2.数据结构0J平台上机练习http://www.bjfuacm.com/structure/o【课程思政教学案例】对于字符串的应用案例可以拓展网络入侵检测问题，讲解该问题时介绍信息安全的相关背景、应用和建立网络安全检测的重要性及必要性，补充“国家网络安全宣传周”的知识，培养学生的家国情怀和科技报国的社会责任感；另外引入与串相关的《张邱建算经》百钱买百鸡问题、与数组相关的《九章算法》杨辉三角，介绍中国古今算法，增强学生的民族自豪感第五章树和二叉树（理论8学时，实验2学时，支撑课程目标

（1）、

（2）、

（4））【教学目标】了解树和森林的概念，包括树的定义、树的术语掌握二叉树的概念、性质及二叉树的表示熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法了解树的存储、树和森林与二叉树的转换方法掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算【重点难点】重点树的基本概念；二叉树及二叉树的存储结构；二叉树的遍历及线索二叉树；树与二叉树的转换；哈夫曼树及哈夫曼编码难点二叉树遍历算法的设计；利用二叉树遍历算法，解决简单应用问题；哈夫曼树的算法【教学内容】第一节树的定义和基本术语第二节二叉树

一、二叉树的定义

二、二叉树的性质

三、二叉树的存储结构第三节遍历二叉树和线索二叉树

一、遍历二叉树

二、线索二叉树第四节树和森林

一、树的存储结构

二、森林与二叉树的转换

三、树和森林的遍历第五节哈夫曼树及其应用

一、哈夫曼树的基本概念

二、哈夫曼树的构造。