基于考研真题分析的数据结构教学改革

李 征，杨 伟，袁 科

（河南大学 计算机与信息工程学院，河南 开封475004）

基于考研真题分析的数据结构教学改革

李 征，杨 伟，袁 科

（河南大学 计算机与信息工程学院，河南 开封475004）

针对数据结构课程教学中存在的问题，分析历年考研真题及该课程自身的知识体系，提出从理论教学方面，将教学内容划分为不同的知识单元，采用启发式和课堂练习相结合的教学方式；从实践教学方面，调整实验分类及实验的考核方式，并设置竞赛环节。

真题分析；课堂练习；教学改革

0 引 言

数据结构课程是计算机相关专业承上启下的核心基础课，课程内容以软件开发过程中的数据元素关系为研究对象，研究不同数据元素关系的组织方法、操作方法以及常用算法，旨在使学生学会分析数据的结构特性，为软件开发过程中涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间和空间分析的技术[1]。

1 数据结构知识体系

大多数数据结构教材一般都是先介绍基础数据结构，即以数据的结构特征为主线，顺序介绍线性结构、非线性结构（树、图等），然后介绍应用数据结构，比如查找和排序。在介绍每种基础数据结构时，围绕其逻辑结构、存储结构、运算特性（在其上的操作）展开，同时辅以一定的应用;介绍应用数据结构时，以基本概念、基本方法、性能分析的顺序进行。我们实施教学改革时采用的教材是严蔚敏和吴伟民主编的、清华大学出版社出版的数据结构（C语言版）[2]，结合该课程教学大纲及近几年的全国硕士研究生计算机考研课程数据结构考研大纲，将课程内容分为5个知识单元，分别为基本概念单元、线性结构单元、树结构单元、图结构单元和知识综合应用单元。

其中，基本概念单元为第1章，主要介绍数据结构的基本概念，各种逻辑结构和存储结构、算法特点及算法复杂度分析;线性结构单元包括第2～5章共4章，其中，第2章线性表是普通的线性结构，属于一般线性表，是线性结构的基础，也是重点内容;第3章栈和队列属于操作受限的线性表;第4章串属于特殊线性表;第5章数组和广义表是线性表的推广。非线性结构是线性结构的扩展，包括树结构单元（第6章）和图结构单元（第7章），同样是讲述重点内容，在很多领域都有广泛的应用。知识综合应用单元包括第9～11章，其中第9章查找、第10章排序是重点，不仅是研究生考试的重点考查内容，其应用也很广泛，比如搜索引擎中涉及的图搜索、排序等;第11章外部排序是研究生考研大纲变化后新增加的需要教授的内容。

2 历年考研真题分析

首先对2012—2015年的考研大纲进行分析，其中2012年计算机统考中数据结构部分大纲变动主要体现在第6部分排序方面，将内部排序范围扩展为排序（增加了外部排序）。2013年相比2012年大纲没有变化，2014年大纲变化包括以下3个方面[3]：①考查目标：能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力，删去了“Java”;②考查知识点图的存储及基本操作部分中新增：邻接多重表、十字链表;③查找部分新增：分块查找法、字符串模式匹配。2015年考研大纲没有变化。

然后分析2012—2015年数据结构考研真题考查知识点及分值分布情况。数据结构总分45分，其中选择题11小题，共22分;综合应用题2题，共23分;主要从线性表，栈、队列和数组，树与二叉树，图，查找，排序6个部分进行考查，每年考查的知识点及分值分布情况见表1。

从考研真题考查的知识点及相应分值分布情况可以看出：算法的时间、空间复杂度分析为必考题，2012—2014年通过选择题考查，2015年在综合应用题中考查。线性表部分除了2014年，几乎每年都会出综合应用题，2014年综合应用是变化较大的地方，一方面改变了以往从线性表出大题的规律，从次重点的树进行大题设计;另一方面，开始重视学科之间的联系，重视知识的实际应用，将数据结构中图的应用与计算机网络的路由算法相结合，考查图的存储结构和最短路径。栈、队列和数组部分，每年通过1～2个选择题考查栈和队列的特性。树与二叉树部分，重点考查二叉树基本概念、遍历、线索化、平衡二叉树、二叉排序树、森林和二叉树的转换、哈夫曼树等。图部分重点考查图的存储结构、遍历算法、拓扑排序、最小生成树、关键路径、最短路径等。查找部分重点考查B树定义及其插人、删除，折半查找条件、不同存储结构查找方法的选择及平均查找长度的计算、kmp算法、哈希方法冲突处理等。排序部分重点考查各种内部排序算法思想、折半、直接插人排序区别，最小堆的概念及其重建、最佳归并树应用等。

表1 2012—2015年数据结构考研真题考查知识点及分值分布情况

3 基于考研真题分析的教学改革

数据结构课程教学中理论与实践并重，但仍存在以下问题：①目前学生在以教师传授为主的接受型学习方法的环境下学习，不能对所学知识有一个深刻的认识，或在实际软件开发过程中不知道如何运用数据结构的知识;②实践效果不理想：数据结构在全国硕士研究生计算机考研课程中占45分(总分150分)，其中针对特定问题的算法的设计与分析每年都占20分左右，而这种算法设计与分析题一般也是学生失分比较严重的题目。针对上述课程教学中存在的问题, 结合课程教学大纲及2012—2015年考研大纲和考研真题分析，从理论教学和实践教学两个方面对数据结构课程进行改革。

3.1 理论教学改革

在教学内容方面，如前所述，根据课程教学大纲，按照知识单元对课程内容进行组织，将课程内容分为5个知识单元：基本概念单元、线性结构单元、树结构单元、图结构单元和知识综合应用单元。结合2012—2015年考研真题分析，筛选出每个单元的重点、难点及需要补充的知识点，比如，针对2012—2015年考研大纲变化部分，增加外部排序讲解内容，同时强调邻接多重表、十字链表、分块查找法、字符串模式匹配等内容的讲解。对于基本概念单元，根据考研真题分析结果，将重点讲述算法的时间/空间复杂度分析，培养学生的算法(时间/空间)分析能力。

在教学方法方面，传统的数据结构课程理论教学基本上以教师根据教材内容讲授为主，满堂灌，学生被动地接受知识，导致学生的学习兴趣不高，应用知识的实践能力较差。因此，我们采用启发式和课堂练习相结合的教学方法，同时讲解相关知识点的实际应用，并建立有效的课堂激励机制，引导学生主动学习与探索知识，培养、锻炼学生的自主学习能力，充分调动学生学习积极性，进而提升学生对知识的吸收能力及应用能力。

3.2 实践教学改革

目前，数据结构课程的实验设置分为验证性和设计性两类，实验考核方式多以实验报告为主，导致学生精力主要集中在实验报告的撰写上，而忽略了实验的实际操作及实验中遇到的一些问题。因此，为了改善实验效果，提高学生的操作能力，在保留验证性和设计性实验基础上，增加了综合性实验，以培养学生对知识的综合应用能力。同时，对实验考核方式也进行相应调整，实验报告成绩只占40%，将考核重心放在程序检查上，重点抽查实验中的核心代码，考查学生对代码的理解与掌握情况。

另外，组织学生参加学院的数据结构课程竞赛。我们密切结合教学大纲、考研大纲及考研真题分析，从中筛选出适合竞赛的知识点，进行竞赛试卷命题并组织学生参加，以提高学生的实践能力及算法设计与分析能力，为后续课程的学习及考研课程成绩的提高打下坚实的基础。

4 改革方法实施及效果

4.1 理论改革方法实施

在教学内容上，将课程内容组织为不同的知识单元，围绕知识单元展开讲解。结合教学大纲及2012—2015年考研真题分析，对每个知识单元的内容进行梳理，突出重点与难点，并强调考研新增的知识点。比如，考研大纲没发生变化前，只讲各种内部排序方法，2012年考研大纲调整后，补充了外部排序相关内容。另外，之前讲述图的存储结构时，重点讲邻接矩阵及邻接表，2014年考研大纲变化后，强调邻接多重表及十字链表的讲解;字符串的模式匹配算法以前重点讲BF算法，略讲或不讲KMP算法，大纲变化后，新增KMP算法的具体讲解。

在教学方法上，学生以小组为单位，教师采用启发式与课堂练习相结合的方法进行授课。比如，讲到图结构单元时，先讲图的一些实际应用，比如图搜索、图的最短路径问题，启发、引导学生，调动学习的主动性。另外，课堂练习多来源于历年考研真题及一些数据结构的实际应用，学生按组竞答，一定程度上激发了学生的学习兴趣，变被动学习为主动学习，逐步实现以“教”为中心到以“学”为中心的转变，以提高课堂教学效果，培养学生发现问题、解决问题的实践能力。

4.2 实践改革方法实施

根据数据结构课程教学大纲、实验教学大纲、考研真题分析并结合学生实际情况，将原有验证性和设计性实验扩充为3类，即验证性、设计性和综合性实验，实验内容分别为：顺序表的操作（设计性）、单链表的操作（设计性）、栈和队列的操作（验证性）、二叉树的操作（综合性）、图的操作（综合性）、查找和排序的实现（验证性）。同时，制定新的实验考核方式，即实验成绩从上机检查情况（占总成绩的50%，教师可随机抽查每个学生的设计性实验或综合性实验至少3次）、实验报告（占总成绩的40%）、出勤情况（占总成绩的10%）3个方面进行综合评判。通过这些方式培养学生分析问题、解决问题的创造性思维能力，进而提高学生对知识的综合应用实践能力及算法的设计、分析能力。

在竞赛方面，分析考研大纲及考研真题，结合教学大纲，从中筛选竞赛知识点，制定竞赛规则并组织学生积极参加竞赛。从学生的反馈情况来看效果明显，一定程度上激发了学生的学习兴趣，促进了学生自主学习能力的培养。

4.3 方法实施效果

数据结构课程改革措施已经在6个本科班中实施。通过采用基于考研真题分析与启发式的数据结构理论与实践教学改革，一定程度上激发了学生的学习兴趣，调动了学生学习的积极性。理论课堂讲授时辅以相应的课堂练习，有助于加深学生对相关知识的理解，进而提高学生对知识的吸收及应用能力。通过数据结构实践教学改革，切实提高了学生综合运用知识的实践能力及算法设计与分析能力，这些在理论课程考核和实验课程的检查中都有所反映。

5 结 语

在数据结构课程中采用启发式与课堂练习相结合的教学模式，一定程度上调动了学生的学习积极性，促进了学生对相关知识的理解，培养了学生自主学习能力。同时，通过数据结构实践教学改革，提高了学生分析问题、解决问题的能力以及算法设计与分析能力。从学生反馈情况及考核情况看，我们提出的改革方法一定程度上有效改进了数据结构理论教学与实践教学效果。

[1] 崔彩霞, 菅小艳, 庞天杰. 地方高校计算机类专业“算法与数据结构”实践教学改革[J]. 计算机教育, 2016(7): 52-54.

[2] 严蔚敏, 吴伟民. 数据结构(C语言版) [M]. 北京: 清华大学出版社, 2011: I.

[3] 新东方在线. 计算机: 2014年考研大纲解析之数据结构[EB/OL]. [2016-10-11]. http://yz.chsi.com.cn/kyzx/zyk/201310/20131011/520716177. html.

（编辑：郭田珍）

1672-5913(2017)01-0076-04

G642

李征，女，副教授，研究方向为服务计算、软件工程，lizheng@henu．edu．cn。