《数据结构A》课程教学大纲（本科）

1、数据结构A(Data Structures A)课程代码：06410035学分：4.0学时：72 （其中：课堂教学学时：56实验学时：0上机学时：16课程实践学时：0 ）先修课程：离散数学、程序设计基础、面向对象程序设计适用专业：网络工程教材：数据结构一C+实现（第二版），缪淮扣等，科学出版社，2014年第二版一、课程性质与课程目标（一）课程性质数据结构A在计算机科学中是一门综合性的专业基础课，不仅是一般程序设计的基础，而 且是设计和实现操作系统、数据库系统、编译程序及其它系统程序和大型应用程序的重要基础。本 课程讨论各种数据组织中的数据的逻辑结构、存储结构以及有关操作的算法。培养学生学会分析

2、研 究计算机所要加工处理的数据的特征的能力，具备组织数据、存储数据和处理数据的能力，通过在 实际应用中选择合适的数据结构和设计相应算法的训练，为今后从事系统软件和应用软件的开发打 下一定的理论和实践基础。（二）课程目标.知识方面理解数据结构的一些基本概念，掌握算法的描述方法，理解算法的时间复杂度和空间复杂 度的概念并掌握其分析方法。理解线性表的基本概念、逻辑特性和基本操作，掌握线性表的存储表示方法，掌握线性表 的基本操作的算法设计与描述，掌握对算法性能进行分析的方法并获得有效结论，理解线性表的应 用。理解栈和队列的基本概念、逻辑特性和基本操作，掌握栈和队列的存储表示方法，掌握栈 和队列的基本操

3、作的算法设计与描述，掌握对算法性能进行分析的方法并获得有效结论，理解栈和(二)教学要求.理解排序的基本思想和基本概念，理解稳定性的概念。.掌握各种排序方法的基本思想、步骤、算法，并具有时空效率分析的能力。, 了解各种典型的内部排序算法的特点和适用范围。(三)重点与难点重点各种排序方法及时空效率分析。难点快速排序、堆排序及其算法实现。三、本课程开设的实验工程编号实验工程名称学时类型要求支撑的课程目标1. 1线性表操作4设计性必做1. 2, 2. 1,2.2, 2. 3,2.42.二叉树操作4设计性必做1. 5, 2. 1,2.2, 2. 3,2.43.2图的操作4验证性必做1.6, 2. 1,2

4、.2, 2. 3,2.44.查找操作2验证性必做1. 7, 2. 1,2.2, 2. 3,2.45.内部排序操作2验证性必做1. 8, 2. 1,2.2, 2. 3,2.4注：L “类型”填验证性、综合性、设计性等；“要求”填必做、选做。实验一线性表操作.实验内容单链表的创立、合并和输出。【扩展内容】以顺序表为存储结构实现类似的功能要求。.实验目的(1)熟悉用Visual C+进行程序设计的方法。(2)掌握单链表的创立、查找、插入和合并等运算。.实验题目本实验要求实现以下功能：(1)从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表(不是通过 排序方法生成)，将该链表输出显示。

5、(2)再从键盘输入顺序任意的5个整数，按有序插入的要求生成第二个有序单链表(不是通 过排序方法生成)，将该链表输出显示。(3)将这两个有序单链表合并成一个有序单链表，可以使用两个单链表的原有空间进行合 并或者合并成新的有序单链表，将生成的有序单链表输出显示。.实验仪器设备(1)学生每个一台PC机。(2)已安装VS.net环境。实验二二叉树操作.实验内容二叉树的建立和遍历。.实验目的(1)进一步掌握指针变量的使用。(2)掌握二叉树的结构特征以及各种存储结构的特点及使用范围。(3)掌握用指针类型描述、访问和处理二叉树的运算。(4)掌握栈或队列的使用。.实验题目本实验要求实现以下功能：(1)按前序次

6、序建立一棵二叉树，以芍表示空。(2)中序、后序遍历该二叉树，输出遍历序列。(3)求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。(4)试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅助存储结构实现二 又树的层次遍历算法。.实验仪器设备(1)学生每个一台PC机。(2)已安装VS.net环境。实验三图的操作.实验内容图的生成和图的遍历。.实验目的(1)掌握图的基本存储方法邻接表和邻接矩阵。(2)熟练掌握图的两种遍历方法。.实验题目本实验要求实现以下功能：(1)以邻接矩阵或邻接表作为存储结构建立一个无向图。(2)按深度优先遍历该无向图，输出遍历序列。(3)按广度优先遍历该无向图，

7、输出遍历序列。.实验仪器设备(1)学生每个一台PC机。(2)已安装VS.net环境。实验四查找操作.实验内容二叉排序树的建立、二叉排序树中结点的查找。.实验目的(1)熟悉二叉排序树的定义。(2)理解二叉排序树的建立过程。(3)掌握二叉排序树中查找结点的算法。.实验题目本实验要求实现以下功能：(1)对从键盘输入的顺序任意的假设干个正整数建立一颗二叉排序树，以-1作为结束。(2)按先序、中序和后序遍历该二叉排序树，输出每种遍历的结果。(3)从键盘输入一个整数，在二叉排序树中查找，给出是否查找成功的结果。.实验仪器设备(1)学生每个一台PC机。(2)已安装VS.net环境。实验五内部排序操作.实验内

8、容快速排序。.实验目的(1)熟悉各种内部排序算法的思想。(2)理解快速排序算法。.实验题目本实验要求实现以下功能：对从键盘输入的顺序任意的8个正整数，通过快速排序使之成为 有序的序列。输出每一趟排序的结果。.实验仪器设备(1)学生每个一台PC机。(2)已安装VS.net环境。注：本课程为专业基础课，授课对象为大二本科生，实验类型主要包括验证性实验和设计性实 验，实验报告主要包括题目、实验内容、程序中使用的数据结构及符号说明、程序的主要流程图、 程序主要模块的功能说明、程序运行时的初值和运行结果、收获及体会、源程序。实验评价内容与 评分比重以及评分细那么参见附录lo四、学时分配及教学方法章教学形

9、式及学时分配主要教学方法支撑的课程目标课堂教学实验上机课程实践小计第一章绪论202讲授1. 1, 2. 3第二章线性表10414讲授+演示1 22 y32y2i422 y第三章栈、队列和递归404讲授+案例+演示1. 3, 2. 1,2.2,2. 3,2.4第四章串、数组和广义表404讲授+演示1. 4, 2. 1, 2. 2, 2. 3第五章树和二又树10414讲授+演示+案例+互动52-*322iJ422J第六章图10414讲授+演示+案例+自学1.6, 2. 1,2.2,2. 3, 2. 4第七章查找8210讲授+案例+演 示+比照+自学1*72*32y21y422 y第八章排序8210

10、讲授+演示+对比182y*32y2iy42*2合计561672五、课程考核（一）考核方式考核形式考核要求考核权重对指标点支持备注平时作业主要考核学生对课堂讲授的知识 点的复习、理解和掌握程度，考核 作业是否提交或按时提交、考核所 完成作业的质量和正确程度。总分数平均计算（取5次作业）10%2.3 (60%)3. 1 (40%)课堂考勤主要考核学生课堂听讲出勤情况。缺勤一次扣1分5%实验完成5个实验，每次3分；主要考 查问题分析能力，编程实现能力和 结果分析能力15%3 (40%)1 (60%)评分细那么见附录1期末考试闭卷70%1.3 (20%)2. 3 (80%)（二）本课程毕业要求达成度计

11、算毕业要求指标点达成度=工5需鬻鬻黑西n乙1 2对应指标点在总评中所占分数说明：课程指标点达成度为对应指标点局部的所有得分除以对应指标点在总评成绩的所占的总分数,对应指标点的得分包括平时作业局部、实验局部、期末考试成绩局部，其中n为总评成绩合格的学生数。六、参考书目及学习资料（书名，主编，出版社，出版时间及版次）.数据结构（C语言版），严蔚敏，清华大学出版社，1997年第1版。.数据结构（用面向对象方法与C+语言描述），殷人昆，清华大学出版社，2007年第2版。.数据结构、算法与应用:C+语言描述数据结构、算法与应用：C+语言描述（Data Structures,Algorithms,and

12、Application in C+），美Sartaj, Sahni 著，王立柱 等译,机械工业出版 社，2015年第2版。七、大纲说明（内容可包括课程基本要求、习题要求及其它一些必要的说明）.采用多媒体和黑板相结合的教学手段，配合例题的讲解及适当的思考题，保证讲课进度的同 时，注意学生的掌握程度和课堂的气氛。.根据各章节的具体情况，课后可布置适当的书面作业或思考题，以加深学生对所学内容的理 解和掌握。.本课程有16个学时的实验，具体实验内容任课教师亦可以根据实际教学情况适当安排。2017年9月15日附录1:实验评价内容与评分比重以及评分细那么实验评价内容与评分比重评分项 编号实验评价内容所占比

13、重要求对毕业要求指标点支撑1问题分析与建模20%要求理解实验要求、合理地组织数 据和存储数据。3. 12编程实现能力与运行结果40%能够编程实现,给出正确的运行结 果。2.33结果分析与表述能力30%能够分析结果的有效性,并清晰表述结论3. 14报告清晰，按时提交10%报告清晰，提交准时3. 1注：具体评分细那么见下表的实验评分细那么。实验评分细那么（每次作也按100分计算）工程优秀(100-90)良好（80-89）中等(70-79)及格(60-69)不及格（59及以下）问题分析与建模20分能够理解本次 实验要求、数据 结构选用恰当、 存储结构设计 很合理；18-20 分能够理解本次 实验要求

14、、数据 结构选用恰当、 存储结构设计 合理；16-17 分能够理解本次 实验要求、数据 结构选用恰当、 存储结构设计 较合理；14-15 分能够理解本次 实验要求、数据 结构选用恰当、 存储结构设计 基本合理；12-13 分对本次实验要 求不理解或理 解不够透彻， 选用的数据结 构不恰当或设 计的存储结构 不合理； 12分以下编程实现能力与运行结果40分程序正确，运行 结果正确且提 示较为清晰和 友好；程序正确，运行 结果正确但提 示不够清晰友 好；程序能运行，但运行结果有少量错误；28-31 分程序能运行，但 运行结果不正 确或程序错误 较多无法运行只有个别程序 能运行或程序 错误较多无法

15、运行或没有程36-40 分32-35 分或没有程序；24-27 分序；24分以下能够依据相关能够依据相关能够依据相关基本上能够依对实验结果的原理清晰明了原理对实验结原理对实验结据相关原理对分析依据不结果分析地对实验结果果进行分析，并果进行分析，并实验结果进行足，结论存在与表述能进行分析，并清得出正确结论；得出结论；分析，并得出结错误：18分以力,30分晰地表述结论；24-26 分21-23 分论；18-20分下27-30 分报告清报告清楚，按时报告较清楚，按报告清楚或较报告不清楚但报告不清楚也晰，按时提交；时提交；清楚，但未按时按时提交未按时提交提交9-10 分8分提交6分6分以下10分7分队

16、列的应用。理解串的定义、存储结构和基本操作，掌握数组的定义以及顺序存储结构表示，理解稀疏 矩阵的定义、存储和操作，理解广义表的定义以及相关概念。理解树和二叉树的基本概念、逻辑特性和基本操作，掌握树和二叉树的存储表示方法，掌 握二叉树的基本操作的算法设计与描述，掌握对算法性能进行分析的方法并获得有效结论，理解二 叉树与树、森林之间的关系，理解二叉树的应用。理解图的基本概念、逻辑特性和基本操作，掌握图的存储表示方法，掌握图的各种应用操 作方法并了解其算法实现，掌握对算法性能进行分析的方法并获得有效结论。理解查找的基本概念，掌握各种查找方法及算法设计与描述，掌握对算法性能进行分析的 方法并获得有效结

17、论。理解排序的基本概念，掌握各种排序方法及算法设计与描述，掌握对算法性能进行分析的 方法并获得有效结论。2.能力与素质方面具备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力。2. 2具备为解决工程实际问题进行算法设计求解的能力2. 3具备对算法性能进行分析的能力。4具备把解决工程实际问题设计的算法通过具体的编程语言加以实现求解的能力。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中毕业要求指标点1. 3, 2. 3, 3.1指标点1.3：具备对复杂工程问题进行计算机求解的工程基础指标点2. 3：具备对复杂工程问题进行分析和求解的能力指标点3.1：具备

18、对复杂网络系统进行需求分析的能力，能够清晰地描述设计任务要求指示点 课程目标指标点1.3指标点2. 3指标点3. 1课程目标VV课程目标1.2VV课程目标L3VV课程目标1.4VV课程目标L5VV课程目标1.6VVV课程目标1.7VV课程目标L8VV课程目标2.1VV课程目标2.2VV课程目标2.3VV课程目标2.4V二、课程内容与教学要求第一章绪论本章支持课程目标1.1:理解数据结构的一些基本概念，掌握算法的描述方法，理解算法的时间 复杂度和空间复杂度的概念并掌握其分析方法。2. 3具备对算法性能进行分析的能力。（一）课程内容.数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结

19、构、数据类 型、算法等。（讲授）.算法时间复杂度和空间复杂度的分析。（讲授）.算法描述方法。（讲授）（二）教学要求. 了解本课程的性质、任务和目的。.掌握数据结构的一些基本概念。.具有对算法的时间复杂度和空间复杂度进行分析的能力。. 了解算法的描述方法。（三）重点与难点. 重点数据、数据元素、数据项；逻辑结构和存储结构在概念上的联系与区别；评价算法优劣的标准及方法。.难点算法与程序的区别；逻辑结构、存储结构的联系与区别；算法的时间复杂度分析 方法。第二章线性表本章支持课程目标1.2：理解线性表的基本概念、逻辑特性和基本操作，掌握线性表的存储表 示方法，掌握线性表的基本操作的算法设计与描述，掌握

20、对算法性能进行分析的方法并获得有效结 论，理解线性表的应用；课程目标2.1：具备依据工程实际问题的需求合理地组织数据，并在计算 机中有效地存储数据的能力；2. 2具备为解决工程实际问题进行算法设计求解的能力；2.3具备对算 法性能进行分析的能力；课程目标2. 4：具备把解决工程实际问题设计的算法通过具体的编程语言 加以实现求解的能力。（-）课程内容.线性表的基本概念和类型定义。（讲授）.线性表的顺序存储表示及基本操作的实现。（讲授+演示）.线性表的链式存储表示及基本操作的实现（单链表、循环链表、双向链表、静态链表）。 （讲授+演示）. 一元多项式的表示及相加。（讲授+演示）（二）教学要求.理解

21、线性表的基本概念和类型定义。.掌握顺序表和单链表上的基本操作方法并具备其算法实现能力。.理解循环链表和双向链表的定义，掌握其插入、删除等操作方法。. 了解静态链表的概念。. 了解一元多项式的表示及相加运算。（三）重点与难点. 重点顺序表和链式表（单链表、双向链表）的基本操作。.难点链式表（单链表、双向链表）的基本操作以及一元多项式的相加运算。第三章栈和队列本章支持课程目标1.3：理解栈和队列的基本概念、逻辑特性和基本操作，掌握栈和队列的存 储表示方法，掌握栈和队列的基本操作的算法设计与描述，掌握对算法性能进行分析的方法并获得 有效结论，理解栈和队列的应用；课程目标2.1：具备依据工程实际问题的

22、需求合理地组织数据, 并在计算机中有效地存储数据的能力；2. 2具备为解决工程实际问题进行算法设计求解的能力；2.3 具备对算法性能进行分析的能力；课程目标2. 4：具备把解决工程实际问题设计的算法通过具体的 编程语言加以实现求解的能力。（-）课程内容.栈的定义，栈的顺序存储表示、链式存储表示及基本操作的实现，栈的应用（表达式 计算）。（讲授+案例+演示）.队列的定义，队列的顺序存储表示（循环队列）、链式存储表示（链队列）及基本操作 的实现。（讲授+案例+演示）.递归。（二）教学要求.理解栈和队列的定义。.掌握顺序存储表示及链式存储表示的栈和队列的基本操作的方法并具备其算法实现能 力。.掌握表

23、达式求值等方法，具有利用栈求解后缀表达式、将中缀表达式转换成后缀表达 式的能力。. 了解递归的概念。（三）重点与难点.重点栈和队列的顺序存储表示、链式存储表示及基本操作的实现。.难点顺序栈的溢出判断条件；循环队列的队空、队满判断条件；递归。第四章串、数组和广义表本章支持课程目标1.4：理解串的定义、存储结构和基本操作，掌握数组的定义以及顺序存储 结构表示，理解稀疏矩阵的定义、存储和操作，理解广义表的定义以及相关概念；课程目标2.1：具 备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2.2具备为解 决工程实际问题进行算法设计求解的能力；2. 3具备对算法性能进行分析的

24、能力。（一）课程内容.串的基本概念。（讲授）.数组的定义以及顺序存储结构。（讲授）.稀疏矩阵的定义、存储和操作。（讲授+演示）.广义表的定义。（讲授）（-）教学要求. 了解串的基本概念。.掌握数组的定义以及顺序存储结构，具有存储地址换算的能力。.掌握稀疏矩阵的定义和压缩存储表示方法。.掌握稀疏矩阵的转置方法并了解其算法。.掌握广义表的定义。（三）重点与难点. 重点数组的定义和数组的存储结构、稀疏矩阵的压缩存储、广义表的定义。.难点稀疏矩阵的压缩存储表示下的运算的实现。第五章树和二叉树本章支持课程目标1.5：理解树和二叉树的基本概念、逻辑特性和基本操作，掌握树和二叉树 的存储表示方法，掌握二叉树

25、的基本操作的算法设计与描述，掌握对算法性能进行分析的方法并获 得有效结论，理解二叉树与树、森林之间的关系，理解二叉树的应用；课程目标2.1：具备依据工 程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能力；2. 2具备为解决工程实 际问题进行算法设计求解的能力；2. 3具备对算法性能进行分析的能力；课程目标2.4：具备把解 决工程实际问题设计的算法通过具体的编程语言加以实现求解的能力。（-）课程内容.树的定义、术语、表示形式、基本操作。（讲授+演示+案例）.二叉树的定义、性质、基本操作、存储结构表示。（讲授）.二叉树的各种遍历方法及实现。（讲授+演示+互动）.线索二叉树。（讲授+演

26、示）.哈夫曼树及其应用。（讲授+演示+案例）.树的存储结构表示，树、森林和二叉树的转换，树和森林的遍历。（讲授+演示）（二）教学要求.理解树的定义、性质。.掌握树的存储结构以及树和森林的遍历方法。.掌握二叉树的定义、性质、存储结构。.掌握二叉树的各种遍历方法及算法实现，并具有对二叉树进行遍历的能力。.掌握二叉树的其他操作方法及算法实现。.掌握线索二叉树的定义和算法实现，并具有将二叉树进行线索化的能力。.掌握树、森林与二叉树的转换方法。.掌握哈夫曼树及其应用。（三）重点与难点. 重点二叉树的概念、遍历及基本操作，二叉树的线索化方法，树的存储结构表示以及树、 森林与二叉树的转换方法、树和森林的遍历

27、方法，哈夫曼树及其应用。.难点二叉树上的复杂运算；线索二叉树的算法实现。第六章图本章支持课程目标1.6：理解图的基本概念、逻辑特性和基本操作，掌握图的存储表示方法， 掌握图的各种应用操作方法并了解其算法实现，掌握对算法性能进行分析的方法并获得有效结论; 课程目标2.1：具备依据工程实际问题的需求合理地组织数据，并在计算机中有效地存储数据的能 力；2. 2具备为解决工程实际问题进行算法设计求解的能力；2. 3具备对算法性能进行分析的能力； 课程目标2. 4：具备把解决工程实际问题设计的算法通过具体的编程语言加以实现求解的能力。（一）课程内容.图的定义、术语、基本操作。（讲授）.图的各种存储结构表

28、示。（讲授）.图的深度优先遍历和广度优先遍历以及图的连通分量。（讲授+演示）.图的生成树和最小生成树。（讲授+演示+案例）.最短路径。（讲授+演示+案例+自学）.活动网络。（讲授+演示+案例+自学）（二）教学要求.理解图的定义和术语。.掌握图的存储结构表示方法。.掌握图的深度和广度优先搜索方法及其实现，并具有利用深度和广度优先搜索方法对 图进行遍历的能力。.掌握求图的最小生成树的普里姆法和克鲁斯卡尔法并了解其实现算法，并具有利用普 里姆法和克鲁斯卡尔法构造图的最小生成树的能力。.掌握求解图的最短路径及其长度的方法并了解其实现算法，并具有构造单源点最短路 径及其长度的能力。.掌握拓扑排序的方法并了解其实现算法，并具有构造拓扑有序序列的能力。（三）重点与难点. 重点图的存储结构、深度和广度优先搜索方法及其实现、图的最小生成树的构造方法、图 的最短路径及其长度的求解方法、有向无环图的拓扑有序序列的构造方法。.难点最小生成树、最短路径的算法思想及其算法实现、拓扑排序的算法实现。第七章查找本章支持课程目标1.7：理解查找的基本概念，掌握各种查找方法及算法设计与描述，掌握对 算法性能进行