《数据结构A》教学大纲2015A

《数据结构(A)》课程教学大纲

执笔人：徐薇王志海编写日期：2013年03月

一、课程基本信息

1．课程编号：80L129Q

2．课程名称（中文）：数据结构(A)

3．课程体系/类别：专业基础课/必修课/专业主干课

4．学时/学分：64学时/4学分

5．先修课程：《高级语言程序设计（A）》

6．适用专业：计算机科学与技术、计算机科学与技术（铁路信息技术）、

物联网工程、信息安全

二、课程教学目标及学生应达到的能力

《数据结构》课程是为计算机科学与技术专业、计算机科学与技术专业（铁路信息技术）、物联网工程专业和信息安全专业本科二年级学生开设的一门专业基础课和专业主干课。本课程是计算机科学中一门介于数学、计算机软件和计算机硬件三者之间的核心课程，是计算机学科的重要理论基础，也是软件设计的重要技术基础。本课程在计算机类专业人才培养中长期以来一直占据重要的位置，为后续的多门专业课，如《数据库系统原理》、《编译原理》、《操作系统》等主干课奠定理论和实践基础，在学生专业素质和能力培养体系中发挥重要的作用。

通过本课程的学习，学生能够掌握扎实的专业基础理论知识，包括各种常用的数据结构、数据结构内在的逻辑联系及其在计算机中的存储表示、实现各种操作时的动态性质和算法、以及数据结构的典型应用。

本课程从问题求解的角度，培养学生运用数据结构和算法基本理论来分析和解决问题的能力，除了强调基础数据结构与算法的训练，还兼顾实践能力和工程能力的培养。学生学习该课程后，根据问题性质选择合理的数据结构并控制求解算法的空间和时间复杂性的能力将能得到提高，从而进一步提高软件设计和编写程序的水平。通过本课程的学习，学生的专业基本技能和应用能力、综合运用数据结构理论和技能发现、分析和解决专业相关问题的能力、自主学习和终身学习能力均能得到提升。

本课程结合计算机科学技术的现代前沿研究课题，扩展学生数据结构与算法设计和问题求解的知识体系，培养学生的研究、创新意识和团队合作精神。

三、课程教学内容和要求

本课程的课内总学时为64学时，其中理论学时48学时，实验学时16学时，课外总学时为192学时，其中作业44学时，综合实践102学时，自主学习和研究46学时。课内外学时总体安排见表1。

本课程的课内理论教学内容、重点、难点、教学要求见表2。

本课程针对每个知识点设计了难度不同的配套实验，由教师在实验课上指导完成。具体实验教学内容与教学要求见表3。

本课程要求学生完成一定量的课外实践内容，包括重要知识点的综合实验，具体内容与要求见表4。

本课程要求学生在课下完成的自主学习与研究内容与要求见表5。

本课程设计了贯穿全课的多个案例，从问题求解的角度引导学生学会利用数据结构解决问题的方法。案例学习的内容见表6。

本课程的教学内容和教学要求详细描述如下。

(一）绪论（10学时＝课内教学4＋课外学习6）

主要内容：本课程的教学目标、教学内容、教学组织、考核形式、教材与其他相关课程资源；

数据结构的基本概念；算法设计；时间和空间复杂度。

重点内容：数据结构相关概念；算法时间复杂度。

难点内容：抽象数据类型；时间和空间复杂度。

基本要求：（1）理解本课程的数据结构和算法的内容主线，掌握各章内容结构及其相互关系；

（2）掌握相关的基本概念，包括数据结构、逻辑结构、存储结构、数据类型等；

（3）掌握算法设计的原则，掌握计算语句频度和估算算法时间复杂度的方法；

（4）了解使用类C语言描述算法的方法。

案例分析：通过分析计算机求解电话号码查询问题、两个城市的最短距离问题以及对弈问题，引导学生思考并得出结论，即必须首先选择合适数据结构来描述问题，才能在此基

础上建立高效算法。

学时分配：课堂教学4学时，其中：课程简介1学时，数据结构相关的基本概念为1学时，算法及算法分析为2学时；课外6学时包括自主学习和完成作业的时间。

作业练习：配合知识点（数据结构概念、算法时间复杂度度量）完成配套教材习题。

自主学习：回顾C语言的使用，掌握类C语言描述算法的方法。

课外实践：访问本课程参考网站，了解网站上的学习资源。

（二）线性表（22学时＝课内教学4＋实验教学2＋课外学习16）

主要内容：线性表的逻辑结构；线性表的存储结构及操作的实现；一元多项式的表示。

基本要求：（1）掌握线性表的逻辑结构和存储结构；

（2）掌握线性表在顺序结构和链式结构上实现基本操作的方法；

（3）理解线性表两种存储结构的不同特点及其适用场合；

（4）了解一元多项式的表示方法。

重点内容：顺序结构和链式结构上实现基本操作的方法。

难点内容：使用线性表链式结构解题的能力。

学时分配：课堂教学4学时，其中：线性表的定义为0.5学时，线性表的顺序表示和实现为1.5学时，线性表的链式表示和实现为1.5学时，一元多项式的表示为0.5学时；实验

教学2学时；课外16学时包括完成作业、自主学习，以及实验的准备、算法编写

和程序调试时间。

实验教学：完成实验：顺序表和链表的查找、插入和删除算法的上机调试。

作业练习：配合知识点（顺序表存储和运算、链表存储和运算）完成配套教材习题。

课外实践：约瑟夫（Josephus）环问题、职工信息管理。

（三）栈和队列（38学时＝课内教学4＋实验教学4＋课外学习30）

主要内容：栈的定义、表示及实现；栈的应用；队列的定义、表示及实现；队列的应用。

基本要求：（1）了解栈和队列的特点；

（2）掌握在两种存储结构上栈的基本操作的实现；

（3）掌握栈的各种应用，理解递归算法执行过程中栈状态的变化过程；

（4）掌握循环队列和链队列的基本运算，队列的应用。

重点内容：栈和队列的特点及应用。

难点内容：栈在递归中的应用；使用栈和队列解题的能力。

案例分析：从问题求解的角度讨论地图染色、八皇后问题和斐波那契序列。

学时分配：课堂教学4学时，其中：栈的类型定义及实现1学时，栈的应用为1学时，队列的类型定义及实现1.5学时，队列的应用为0.5学时；实验教学4学时,其中：栈的基

本操作的实现为2学时，队列的基本操作的实现为2学时；课外30学时包括完成

作业、自主学习，以及实验的准备、算法编写和程序调试时间。

实验教学：完成实验：入栈、出栈、入队列、出队列算法的上机调试。

作业练习：配合知识点（栈的性质和应用、队列的性质和应用）完成配套教材习题。

课外实践：完成综合扩展实验：回文、八皇后问题、迷宫求解、四色问题、表达式求值、n阶Hanoi塔问题以及选做实验：斐波那契序列。

（四）串（26学时＝课内教学2＋课外学习24）

主要内容：串的逻辑结构；存储结构；串操作的实现。

基本要求：（1）掌握串的基本运算的定义，了解利用基本运算来实现串的其它运算的方法；

（2）了解在顺序存储结构和在堆存储结构上实现串的各种操作的方法；

（3）理解KMP算法，掌握NEXT函数和改进NEXT函数的定义和计算。

重点内容：KMP算法，手工计算NEXT函数和改进NEXT函数的值。

难点内容：KMP算法。

学时分配：课堂教学2学时，其中：串的类型定义和实现为1学时，串的模式匹配算法为1学时；课外24学时包括自主学习，以及完成专题报告的时间。

自主学习：模式匹配算法的比较研究，搜索引擎相关理论和实现技术研究。

专题报告：以小组为单位提交专题报告“搜索算法的研究”。

（五）数组和广义表（12学时＝课内教学4＋实验教学2＋课外学习6）

主要内容：数组的存储结构；稀疏矩阵的表示及操作的实现；广义表的定义和存储结构；广义表的递归算法。

基本要求：（1）掌握数组在以行为主的存储结构中的地址计算方法；

（2）掌握矩阵压缩存储时的下标变换方法，了解以三元组表示稀疏矩阵的方法；

（3）理解广义表的定义及其存储结构，理解广义表的两种分析方法；

重点内容：矩阵实现压缩存储时的下标变换方法。

难点内容：广义表的存储结构及递归算法。

学时分配：课堂教学4学时，其中：数组的定义和顺序表示为0.5学时，矩阵的压缩存储为1.5学时，广义表的定义、表示和递归算法为2学时；实验教学2学时；课外6学时

包括完成作业和自主学习的时间。

实验教学：完成实验：稀疏矩阵转置。

作业练习：配合知识点（矩阵的存储及地址转换、广义表的两种存储方法）完成配套教材习题。课外实践：鞍点问题。

（六）树和二叉树（50学时＝课内教学8 ＋实验教学2+课外学习40）

主要内容：树的基本概念；二叉树的性质和存储结构；遍历二叉树；线索二叉树；树的存储结构和遍历；哈夫曼树及其应用。

基本要求：（1）掌握二叉树的结构特点和性质，掌握二叉树各种存储结构及适用范围；

（2）熟练掌握按各种次序遍历二叉树的算法，理解二叉树的线索化实质和方法；

（3）掌握树的各种存储结构及其特点，掌握树的各种运算的实现算法；

（4）掌握建立最优二叉树和哈夫曼编码的方法。

重点内容：二叉树的性质；二叉树和树的相互转化；哈夫曼树。

难点内容：按各种次序遍历二叉树的非递归算法。

案例分析：从计算机操作系统中的目录、编译原理中的语法树的实现中讨论树形结构的作用。学时分配：课堂教学8学时，其中：树和二叉树的类型定义为１学时，二叉树的存储结构和遍历为3学时，二叉树的线索化为1学时，树和森林为2学时，最优二叉树和哈夫

曼编码为1学时；实验教学2学时；课外40学时包括完成作业、自主学习，以及

实验的准备、算法编写和程序调试时间。

实验教学：完成实验：按先序遍历的扩展序列建立二叉树的存储结构，二叉树先序、中序、后序遍历的递归算法。

自主学习：标准模板库STL的基本概念，阅读和学习STL中与数据结构相关的代码。对递归和非递归算法进行比较研究。

作业练习：配合知识点（二叉树的建立、树的建立、哈夫曼树）完成配套教材习题。

课外实践：完成实验：二叉树先序、中序、后序遍历的非递归算法，二叉树层次遍历的非递归算法，求二叉树的深度，建立树的存储结构及求树的深度。

（七）图（32学时＝课内教学6＋实验教学2＋课外学习24）

主要内容：图的基本概念；图的存储结构；图的遍历；图的应用（最小生成树、最短路径、拓扑排序和关键路径）。

基本要求：（1）熟练掌握图的基本概念和各种存储结构；

（2）掌握深度优先搜索遍历图和广度优先搜索遍历图的递归和非递归算法；

（3）掌握图的遍历算法，掌握图的各种简单路径问题的求解思想和方法，包括最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。

重点内容：图的存储和遍历；构造最小生成树的算法。

难点内容：最短路径算法。

案例分析：从问题求解的角度讨论枚举、贪心、递归分治、动态规划等经典算法思想，体会数据结构度对于程序设计的重要。

学时分配：课堂教学6学时，其中：图的定义和存储表示为1学时，图的遍历为1学时，最小生成树、最短路径﹑拓扑排序﹑关键路径为4学时；实验教学2学时；课外24学

时包括完成作业、自主学习，以及实验的准备、算法编写和程序调试时间。

实验教学：完成实验：深度优先搜索遍历图和广度优先搜索遍历图的算法。

作业练习：配合知识点（图的深度优先遍历和广度优先遍历、最短路径）完成配套教材习题。课外实践：完成综合扩展实验：普里姆(Prim)算法。

（八）查找（38学时＝课内教学6＋实验教学2＋课外学习30）

主要内容：静态查找表(顺序表,有序表,索引顺序表)；动态查找树表(二叉排序树,平衡二叉树,B-树)的建立和查找；哈希表的建立、查找及分析。

基本要求：（1）熟练掌握各种静态查找和动态查找算法，会计算等概率情况下查找成功时和失败时的平均查找长度；

（2）掌握二叉排序树的建立、插入和删除过程，掌握二叉平衡树的旋转平衡方法；

（3）掌握B-树的建立、插入和删除过程；

（4）熟练掌握哈希表的构造方法，掌握哈希函数的构造方法和处理冲突的方法；

重点内容：折半查找；B-树；哈希查找。

难点内容：二叉平衡树的旋转平衡方法；B-树查找性能的分析。

案例分析：从数据库和搜索引擎的介绍中，提出如何借助数据结构提高数据查找效率。

学时分配：课堂教学6学时，其中：静态查找表为2学时，动态查找树表为2学时，哈希表为2学时；实验教学2学时；课外30学时包括完成作业、自主学习，以及实验的准

备、算法编写和程序调试时间。

实验教学：完成实验：二叉排序树的建立和查询算法。

自主学习：文件索引技术，理解索引是加快查询速度的有效方法。二叉平衡树算法的可视化研究。

作业练习：配合知识点（折半查找、二叉排序树、B-树、哈希表）完成配套教材习题。

课外实践：完成实验：哈希表的建立和查找算法。

（九）排序（26学时＝课内教学8＋实验教学2＋课外学习16）

主要内容：插入排序；交换排序(起泡排序,快速排序)；选择排序(简单选择,堆)；归并排序；基数排序；外部排序。

基本要求：（1）掌握各种排序方法的排序过程；

（2）了解各种排序方法的特点并灵活应用；

（3）理解各种排序方法的时间复杂度分析。

（4）理解外部排序的思想

重点内容：快速排序；堆排序；各种排序方法的比较分析。

难点内容：在实际问题中正确选择排序方法的能力训练。

学时分配：课堂教学8学时，其中：概述、插入排序和交换排序为2学时，选择排序为2学时，归并排序、基数排序和各种排序方法的比较为2学时，外部排序为2学时；实验教

学2学时；课外16学时包括完成作业、自主学习，以及实验的准备、算法编写和

程序调试时间。

实验教学：完成实验：折半插入排序、冒泡排序、快速排序、简单选择排序。

作业练习：配合知识点（各种排序算法的执行过程和稳定性分析）完成配套教材习题。

课外实践：完成实验：归并排序、堆排序。

（十）扩展研究和前沿应用（2学时＝课内教学2）

主要内容：（1）总结各种基本数据结构的逻辑结构、存储结构和运算的实现；

（2）总结各种查找算法和排序方法的特点；

（3）扩展研究和前沿应用（红黑树、后缀树等）；

（4）各主要内容的核心试题及作业的讲解。

学时分配：课堂教学2学时，其中：课程总结为1学时；作业与习题讲解为1学时。

四、课程教学安排

本课程的整体教学安排是按照本教学大纲所规定的教学目标、内容、方法、教学组织、课程基本要求、学时分配、案例分析、作业练习、专题报告及其实践训练等内容进行设计，以教学日历的方式呈现设计结果。教师的教学方案在教学内容、互动方式、讲授方法、训练形式等方面的编写与执行是依据本教学大纲及相应的教学日历而设计的本课程教案组织实施，课程具体内容的展开则由主讲教师编著的电子课件等介质配合课程内容的讲授过程而实现。

本课程运用以解决问题过程为导向的内容组织方式将理论知识教学与实践能力培养相融合，强调通过理论授课、实验技能训练以及创新意识和创新能力组合训练，使学生掌握较扎实的专业基本理论知识，培养学生分析问题的能力、编程解决问题的能力以及自主学习的能力，提高学生根据问题的性质选择合理的数据结构并控制求解算法的空间和时间复杂性的能力，以达到进一步提高软件设计和编写程序水平的目的。本课程的教学组织充分围绕研究性教学展开，从课程整体方案设计、理论教学设计和实验教学设计多方面体现了研究性教学的指导思想。

（一）整体教学安排

首先，本课程从问题求解出发，在基础理论、抽象和设计的三个层次组织课程知识体系。通过逻辑结构和抽象数据类型，培养学生问题分析和问题建模的能力；通过存储设计和算法分析与设计，培养学生解决问题的能力；通过经典数据结构和算法实习，培养学生实际动手的能力。

为达到上述教学目标，本课程设计了多个教学环节和教学手段。其关键教学环节包括：课堂讲授、网上教学、课程实践、作业练习、案例分析、专题训练、自主学习等，这部分内容的基本要求如下：

课堂讲授：是专业基本理论知识传授的主要方式，在课堂教授中采用提问、回顾、联想、讨论等多种教学方法，并结合PPT演示、动画、网络视频、板书等多种教学手段，吸引并调动学生的兴趣，强调知识点的衔接、知识结构的贯通，在传授知识的同时，注意培养学生的批判性思维。课堂讲授的教学内容、方法和手段见表二和表八。

网上教学：是课堂讲授的辅助手段，通过课程网站、算法演示系统等教学辅助系统，向学生提供课下技术支持和帮助。

课程实践：是编程技能训练以及培养学生专业基本技能和应用能力的一种教学环节，主要包括课内的验证性实验和课外的设计综合型实验两种。其中验证性实验与每章理论教学

重点内容的学习同步进行，设计型实验与案例教学、自主学习结合。具体安排见表

三、表四。实验教学采用分层次教学，具体设计参见课程配套研究性训练载体。

作业练习：是对知识重现的一种能力训练方式，本课程每一章都安排了书面作业，包括基本概念、计算及程序设计各种题型，教师根据教学进度和学生习题完成进度，安排问题

解答时间，点评普遍性与重要性的问题。作业内容、要求与目的见表七。

案例分析：本课程对于重点与难点的内容安排了案例教学的环节，从问题求解的角度讨论电话号码查询、最短距离、地图染色、八皇后以及枚举、贪心、递归分治等算法思想。

案例设计见表六。

自主学习：是培养学生自主学习能力、终身学习能力和探究精神的教学环节。理论教学过程中将安排多次自主学习的任务，如了解类C语言的用法、对实现模式匹配的诸多算

法进行比较研究、研究搜索引擎相关理论和实现技术、熟悉标准模板库STL、对

递归和非递归算法进行比较分析、研究二叉平衡树算法的可视化展现和文件索引技

术。优秀自主学习成果共享并在课上报告。自主学习内容安排见表五。

专题训练：考核学生自主学习能力、表达能力、团队合作能力和创新能力的一个重要教学环节。

本课程安排以小组为单位的专题研究任务，小组成员通过自主学习和合作讨论，完

成研究报告“搜索引擎的研究”，并在课上汇报每个小组的研究成果。

（二）研究性理论教学安排

数据结构理论课程的教学组织，特别注意了从课程的整体框架，课程各个知识点的区别与联系、每章的重点和难点等角度来讲解，对于算法采取从粗到精，从简单到复杂的递进式教学方法，符合认知规律。教师认真对待研究性教学内容的组织，每堂课都设计出研究性教学环节，注重启发性和互动性，调动学生的兴趣，发挥学生的主观能动性。部分教学方法和教学手段设计见表8。

（三）研究性实验教学安排

《数据结构》课程涉及大量的算法，实践内容充分体现了理论教学各章重要的算法，与理论教学环节合理衔接。其中基本实验是验证性实验，与理论教学同步完成，设计型实验是各个知识点的高级应用，需要学生主动学习，教师要掌握学生完成实验情况，将发现的问题及时反馈给学生，与学生充分沟通和交流。实验教学以培养和训练学生实际动手能力和创新能力为目标。

为此，课程设计了研究性教学训练载体1和研究性教学训练载体2。研究性教学训练载体1为个人训练，突出基本实验技能的训练，通过经典数据结构和算法实习，培养学生实际动手的能力。研究性教学训练载体2为团队训练，针对课程中部分难度大的算法和综合性要求，注重数据结构和算法的深入分析、比较以及综合训练，力图培养学生的科学研究能力、创新能力和综合设计复杂系统的能力，给学生提出了更高的研究目标和要求。

训练载体1包括三方面内容。第一部分是针对理论教学中四个重要知识点设计了四组验证性算法；第二部分是针对主要的程序设计方法设计了六组综合扩展算法；第三部分是选做实验。训练采用分层教学，这样可使大部分学生都能够在自己的能力范围内完成相应的实验。

训练载体2012也包括三方面内容。第一部分是算法的比较研究，包括实现模式匹配的三种算法的比较以及递归算法与非递归算法的比较。第二部分是算法的可视化研究，对教学难点“二叉树的平衡算法”进行深入研究，以多媒体手段展示算法的实现过程。第三部分是综合的搜索引擎研究，通过研究搜索引擎系统，使学生全面认识数据结构课程中的各个知识点及其联系，以及数据结构和算法的综合应用，从而掌握使用数据结构进行复杂系统设计的方法。

此外，本课程的教学内容和教学组织在保持系统性、稳定性、全面性和先进性的基础上，要根据学科的发展状况随时调整部分作业题目、实验题目和自主学习内容。

五、课程的考核

课程总成绩＝期末考试（70％）＋综合实验（20％）+ 平时成绩（10%）

课程考核加大过程性考核的比重。首先实验考核改变过去期末一次考核为以章节为单位，这样使学生必须及时完成每个单元的实验题目，不能拖后；平时考核综合上课发言、完成作业和专题报告质量评定。

平时作业和期末考试成绩能够评价学生是否掌握课程所要求的专业基本理论知识；课程实践题目的完成数量和完成质量能够评价学生是否具备专业基本技能和应用能力；在理论教学和实验教学内容中选择某个知识点，学生需要自主学习才能掌握或完成，根据完成情况评价学生自主学习能力。

六、本课程与其它课程的联系与分工

先修课程：《高级语言程序设计》，《离散数学》

后续课程：《数据库系统原理》，《编译原理》，《操作系统》

在本课程的先修课《高级语言程序设计》中学生学习了基本的程序设计方法，而本课程是在数据组织的基础上讨论复杂程序的设计问题。先修课《离散数学》中讨论的集合、树和图也是本课程中线性表、树和二叉树、图、网等基本数据结构的理论基础，本课程中更注重研究基本数据结构的逻辑结构、存储结构以及基本操作的实现。

本课程中所讲授的各种数据结构和查找、排序算法在后续课《数据库系统原理》、《编译原理》、《操作系统》中均有应用，例如操作系统中的目录树、编译原理中的语法树、数据库中的索引技术等。

七、建议教材及教学参考书

教材：

[1] 严蔚敏和吴伟民编著。数据结构（C语言版）。北京：清华大学出版社，1997年4月第一版，

2005年6月第30次印刷。

主要参考：

[1] 严蔚敏等．数据结构题集（C语言版）．北京：清华大学出版社（教材配套习题），1998年12

月第2版．

[2] 张铭等．数据结构与算法．北京：高等教育出版社，2008年6月第一版．

[3] 殷人昆等．数据结构（面向对象方法与C＋＋描述）．北京：,清华大学出版社，2007年第2版．

[4] 殷人昆和徐孝凯．数据结构习题解析．北京：清华大学出版社，2002年4月．

[6] William Ford，and William Topp．Data Structure with C++．北京：清华大学出版社，Prentice Hall

联合出版,1996．

[7] Cormen T H ,Leiserson C E , Rivest R L, and Stein C. Introduction to Algorithms (2nd ed.) MIT Press,

2001．

[8] Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. 北京：清华大学

出版社（英文影印版），2003年12月．

[9] Alsuwaiyel M H. Algorithms Design Techniques and Analysis, World Scientific, 1999．

[10] 本课程理论课时可参考教学网站https://www.wendangku.net/doc/559087880.html,/pkujpk/course/sjjg/．

[11] 本课程实验课时可参考ACM ICPC在线评测系统（POJ）https://www.wendangku.net/doc/559087880.html,/JudgeOnline．