2019年1月课程被教育部评为国家精品在线开放课程，2020年被教育部认定为首批国家级一流本科课程（线上）。

1.  课程性质和地位 

    “数据结构”是计算机科学与技术、网络工程、信息安全等专业本科生的专业基础课程中的一门重要的核心课程。

    在计算机学科中，本课程与其他课程的关系如图1所示。图中，大学数学、计算机基础、离散数学、C/C++语言等是本课程的先导课程，而其它课程（如操作系统、编译原理、计算机网络等）均以本课程作为先导课程。图中已罗列出一些专业课所用到本课程中的相关知识，比如，操作系统课程会用到队列、存储管理表等。本课程也是算法分析与设计、计算复杂性理论等高级课程的基础。因此，本课程在计算机教学工作中具有重要的地位。

                                      图1  数据结构课程与其他课程的关系图

2.  课程目标

    通过本课程的教学，使学习者懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，各结构的存储表示和所涉及的运算，完成各运算的算法及其实现方法，学会对算法的评价方法。使学习者具有一定的算法设计能力，较强的程序设计能力，和实际应用能力，能够针对给定的简单问题设计出求解算法，包括问题的抽象、数据的提取、数据的组织、数据结构的确定（逻辑结构）、算法设计、数据的存储形式（物理结构）、编程实现、程序的调试和测试等。也为学习后续专业课程，设计系统程序打下坚实的理论基础和实践基础。

3.  教学环节

    本课程通过视频授课、课外作业、教材阅读、上机实践，以及师生互动等环节实现课程目标。

    学习者通过观看本课程提供的授课视频接受课堂教学，学习基本知识；通过阅读本课程指定的教材（《数据结构与算法》（第二版）．陈卫卫 王庆瑞编著．北京：高等教育出版社.  2015.07），预习和复习视频授课内容；通过完成指定的“书面”练习题和上机练习题，巩固和充实课堂知识；学习者和教师互动，由一方向另一方提出问题请其解答，学习者以其释疑，教师则以其检查学习者完成学业的情况。

4.  课堂教学设计

    课堂教学内容分为三大部分：基础知识（第一讲）、基本模型（第二至九讲）、基本问题（第十讲）。

    基础知识部分是学习后续内容的基础，包括概念（算法的概念，数据结构的概念）、标准（对算法的评价标准）、方法（算法的描述方法和评价方法）。

    基本模型部分是本课程最主要部分。这部分以查找、插入、删除运算为主线全面而系统地介绍表、树、图等基本数据结构的特点、存储方法、完成各运算的算法设计方法和实现程序、时空效率。因为，查找、插入、删除不仅是最基本的、最常用的，而且往往也是不可分的（通常联合使用，极少单独使用），其它某些运算还可以转化为这三种运算。将这三种运算构成的运算集作为一个整体，可以得出结构的整体时空效率。

    最后一部分，以问题为导向（这里选用排序问题），介绍求解同一个问题的多种不同处理算法，通过对算法的评价，分析各算法的特点、效率、适用情况。

    图2展示了这些课堂教学内容之间的关联关系。

图2  数据结构教学内容之间的概念图

5.  实践教学设计

    本课程设计的实践教学（即上机实验）题分为基础性、综合性和设计性三大类。

    基础性（即知识验证性）类实验题主要用于巩固课堂知识，其难度不大，实现程序不长（小程序），通常只需要将教材中的程序进行简单拼装，简单改造，简单模仿，简单细化。

   综合性和设计性实验题属于大作业，实现程序较长，难度较大。顾名思义，完成综合性实验题需要将多个知识点进行综合，而完成设计性实验题则要实现从建模到解模的全过程，即实验者要独立完成：问题的抽象，数据的提取，数据的组织，数据结构的确定（逻辑结构），算法设计，数据的存储形式（物理结构），编程实现，程序的调试和测试等步骤。

6.  教学模式设计

    对于基本概念，在讲清基本概念条文的同时，尽可能多地举例阐述概念的内涵，并强调规范术语用词，培养严谨的科学作风。

    对于算法设计，遵循“少而精”的原则，突出重点，以点带面，通过对比，使学习者逐步建立设计“好”算法的意识。

    对于表、树、图三大基本结构，依照“逻辑结构→物理结构→基本运算→基本算法→算法评价”这个脉络，研究每种结构的特点，给学习者一个清晰的研究主线，使学习者能够根据问题的特点选择合适的数据结构，进一步理解研究数据结构的意义。

    对于学习者，可以按照“读、仿、改、究”的学习模式逐步提升自己的程序（算法）设计能力，并以此衡量自己当前达到的水平。具体地说，“读”就是研读（本课程中给出的）经典算法及其实现代码，领会算法设计思路、描述方式和实现代码的程序结构；“仿”是指对现有的求解原问题的算法进行简单搭建和修改，写出用来求解与原问题相近的新问题的模仿算法；而“改”则是，当应用场景或用户需求发生较大改变时，能够对现有算法进行改进，写出改进算法，这一阶段至关重要，不仅起到了深化理解知识的作用，而且对算法设计能力、分析能力，改进点的定位，改进措施的选定都是极大考验和锻炼；“究”指的是研究和探索给定问题的性质、特征，确定求解策略，设计出性能良好的求解算法。

通过本课程的教学，使学习者懂得数据结构的一般原理，掌握表、树、图等基本结构的特点，学会对算法的评估方法。培养学习者的算法设计能力、程序设计能力，以及用软件方法处理问题的能力，培养学习者的分析、对比、归纳、综合和创新能力，为后续学习专业课程，设计系统程序打下坚实的理论基础。

学习者应具备以下几个方面的基础知识：

 l 熟练掌握C/C++（传引用）语言；

 l 掌握基本图论知识，初步概率知识；

 l 掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念；

 l 熟练运用一种编程环境（例如，VC编译环境）。

（1）教材

     陈卫卫,王庆瑞编著．数据结构与算法（第二版）．北京：高等教育出版社, 2015.07

               （“十二五”普通高等教育本科国家级规划教材）

     部分参考答案下载地址：http://pan.baidu.com/s/1o83yAi2 （pdf文件，若下载后后缀消失，请手工添加文件后缀）

（2）参考书

l  张铭等编著. 数据结构与算法．北京:高等教育出版社, 2008

l  陈越主编. 数据结构. 北京:高等教育出版社, 2012

l  Robert Sedgewick著，周良忠  译．C算法（第一卷，基础、数据结构、排序和搜索）（第三版）．北京：人民邮电出版社 POSTS & TELECOM  PRESS,2004

l  Robert Sedgewick著，周良忠  译．C算法（第二卷 图算法）．北京：人民邮电出版社 POSTS & TELECOM  PRESS,2004

l  计算机程序设计艺术（第3版）．Donald E.Knuth  著，苏运霖  译．北京：国防工业出版社 Addison Wesley,2002

第1卷  基本算法

第2卷  半数值算法

第3卷  排序与查找

本课程的学习者，要注意以下事项，确保教学活动能够深入、有效地进行。

l要事先具备基本的C语言基础知识，避免降低听课效果。

l视频授课的内容是基础的核心内容，要认真学习，细心领会。

l要按时完成教师指定的作业，尤其是上机实践作业。

l要积极参与师生互动，主动获得教师的指导。