基于考研真題分析的數(shù)據(jù)結構教學改革

李 征，楊 偉，袁 科

（河南大學 計算機與信息工程學院，河南 開封475004）

基于考研真題分析的數(shù)據(jù)結構教學改革

李 征，楊 偉，袁 科

（河南大學 計算機與信息工程學院，河南 開封475004）

針對數(shù)據(jù)結構課程教學中存在的問題，分析歷年考研真題及該課程自身的知識體系，提出從理論教學方面，將教學內容劃分為不同的知識單元，采用啟發(fā)式和課堂練習相結合的教學方式；從實踐教學方面，調整實驗分類及實驗的考核方式，并設置競賽環(huán)節(jié)。

真題分析；課堂練習；教學改革

0 引 言

數(shù)據(jù)結構課程是計算機相關專業(yè)承上啟下的核心基礎課，課程內容以軟件開發(fā)過程中的數(shù)據(jù)元素關系為研究對象，研究不同數(shù)據(jù)元素關系的組織方法、操作方法以及常用算法，旨在使學生學會分析數(shù)據(jù)的結構特性，為軟件開發(fā)過程中涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及相應的算法，并初步掌握算法的時間和空間分析的技術[1]。

1 數(shù)據(jù)結構知識體系

大多數(shù)數(shù)據(jù)結構教材一般都是先介紹基礎數(shù)據(jù)結構，即以數(shù)據(jù)的結構特征為主線，順序介紹線性結構、非線性結構（樹、圖等），然后介紹應用數(shù)據(jù)結構，比如查找和排序。在介紹每種基礎數(shù)據(jù)結構時，圍繞其邏輯結構、存儲結構、運算特性（在其上的操作）展開，同時輔以一定的應用;介紹應用數(shù)據(jù)結構時，以基本概念、基本方法、性能分析的順序進行。我們實施教學改革時采用的教材是嚴蔚敏和吳偉民主編的、清華大學出版社出版的數(shù)據(jù)結構（C語言版）[2]，結合該課程教學大綱及近幾年的全國碩士研究生計算機考研課程數(shù)據(jù)結構考研大綱，將課程內容分為5個知識單元，分別為基本概念單元、線性結構單元、樹結構單元、圖結構單元和知識綜合應用單元。

其中，基本概念單元為第1章，主要介紹數(shù)據(jù)結構的基本概念，各種邏輯結構和存儲結構、算法特點及算法復雜度分析;線性結構單元包括第2～5章共4章，其中，第2章線性表是普通的線性結構，屬于一般線性表，是線性結構的基礎，也是重點內容;第3章棧和隊列屬于操作受限的線性表;第4章串屬于特殊線性表;第5章數(shù)組和廣義表是線性表的推廣。非線性結構是線性結構的擴展，包括樹結構單元（第6章）和圖結構單元（第7章），同樣是講述重點內容，在很多領域都有廣泛的應用。知識綜合應用單元包括第9～11章，其中第9章查找、第10章排序是重點，不僅是研究生考試的重點考查內容，其應用也很廣泛，比如搜索引擎中涉及的圖搜索、排序等;第11章外部排序是研究生考研大綱變化后新增加的需要教授的內容。

2 歷年考研真題分析

首先對2012—2015年的考研大綱進行分析，其中2012年計算機統(tǒng)考中數(shù)據(jù)結構部分大綱變動主要體現(xiàn)在第6部分排序方面，將內部排序范圍擴展為排序（增加了外部排序）。2013年相比2012年大綱沒有變化，2014年大綱變化包括以下3個方面[3]：①考查目標：能夠運用數(shù)據(jù)結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現(xiàn)算法的能力，刪去了“Java”;②考查知識點圖的存儲及基本操作部分中新增：鄰接多重表、十字鏈表;③查找部分新增：分塊查找法、字符串模式匹配。2015年考研大綱沒有變化。

然后分析2012—2015年數(shù)據(jù)結構考研真題考查知識點及分值分布情況。數(shù)據(jù)結構總分45分，其中選擇題11小題，共22分;綜合應用題2題，共23分;主要從線性表，棧、隊列和數(shù)組，樹與二叉樹，圖，查找，排序6個部分進行考查，每年考查的知識點及分值分布情況見表1。

從考研真題考查的知識點及相應分值分布情況可以看出：算法的時間、空間復雜度分析為必考題，2012—2014年通過選擇題考查，2015年在綜合應用題中考查。線性表部分除了2014年，幾乎每年都會出綜合應用題，2014年綜合應用是變化較大的地方，一方面改變了以往從線性表出大題的規(guī)律，從次重點的樹進行大題設計;另一方面，開始重視學科之間的聯(lián)系，重視知識的實際應用，將數(shù)據(jù)結構中圖的應用與計算機網(wǎng)絡的路由算法相結合，考查圖的存儲結構和最短路徑。棧、隊列和數(shù)組部分，每年通過1～2個選擇題考查棧和隊列的特性。樹與二叉樹部分，重點考查二叉樹基本概念、遍歷、線索化、平衡二叉樹、二叉排序樹、森林和二叉樹的轉換、哈夫曼樹等。圖部分重點考查圖的存儲結構、遍歷算法、拓撲排序、最小生成樹、關鍵路徑、最短路徑等。查找部分重點考查B樹定義及其插人、刪除，折半查找條件、不同存儲結構查找方法的選擇及平均查找長度的計算、kmp算法、哈希方法沖突處理等。排序部分重點考查各種內部排序算法思想、折半、直接插人排序區(qū)別，最小堆的概念及其重建、最佳歸并樹應用等。

表1 2012—2015年數(shù)據(jù)結構考研真題考查知識點及分值分布情況

3 基于考研真題分析的教學改革

數(shù)據(jù)結構課程教學中理論與實踐并重，但仍存在以下問題：①目前學生在以教師傳授為主的接受型學習方法的環(huán)境下學習，不能對所學知識有一個深刻的認識，或在實際軟件開發(fā)過程中不知道如何運用數(shù)據(jù)結構的知識;②實踐效果不理想：數(shù)據(jù)結構在全國碩士研究生計算機考研課程中占45分(總分150分)，其中針對特定問題的算法的設計與分析每年都占20分左右，而這種算法設計與分析題一般也是學生失分比較嚴重的題目。針對上述課程教學中存在的問題, 結合課程教學大綱及2012—2015年考研大綱和考研真題分析，從理論教學和實踐教學兩個方面對數(shù)據(jù)結構課程進行改革。

3.1 理論教學改革

在教學內容方面，如前所述，根據(jù)課程教學大綱，按照知識單元對課程內容進行組織，將課程內容分為5個知識單元：基本概念單元、線性結構單元、樹結構單元、圖結構單元和知識綜合應用單元。結合2012—2015年考研真題分析，篩選出每個單元的重點、難點及需要補充的知識點，比如，針對2012—2015年考研大綱變化部分，增加外部排序講解內容，同時強調鄰接多重表、十字鏈表、分塊查找法、字符串模式匹配等內容的講解。對于基本概念單元，根據(jù)考研真題分析結果，將重點講述算法的時間/空間復雜度分析，培養(yǎng)學生的算法(時間/空間)分析能力。

在教學方法方面，傳統(tǒng)的數(shù)據(jù)結構課程理論教學基本上以教師根據(jù)教材內容講授為主，滿堂灌，學生被動地接受知識，導致學生的學習興趣不高，應用知識的實踐能力較差。因此，我們采用啟發(fā)式和課堂練習相結合的教學方法，同時講解相關知識點的實際應用，并建立有效的課堂激勵機制，引導學生主動學習與探索知識，培養(yǎng)、鍛煉學生的自主學習能力，充分調動學生學習積極性，進而提升學生對知識的吸收能力及應用能力。

3.2 實踐教學改革

目前，數(shù)據(jù)結構課程的實驗設置分為驗證性和設計性兩類，實驗考核方式多以實驗報告為主，導致學生精力主要集中在實驗報告的撰寫上，而忽略了實驗的實際操作及實驗中遇到的一些問題。因此，為了改善實驗效果，提高學生的操作能力，在保留驗證性和設計性實驗基礎上，增加了綜合性實驗，以培養(yǎng)學生對知識的綜合應用能力。同時，對實驗考核方式也進行相應調整，實驗報告成績只占40%，將考核重心放在程序檢查上，重點抽查實驗中的核心代碼，考查學生對代碼的理解與掌握情況。

另外，組織學生參加學院的數(shù)據(jù)結構課程競賽。我們密切結合教學大綱、考研大綱及考研真題分析，從中篩選出適合競賽的知識點，進行競賽試卷命題并組織學生參加，以提高學生的實踐能力及算法設計與分析能力，為后續(xù)課程的學習及考研課程成績的提高打下堅實的基礎。

4 改革方法實施及效果

4.1 理論改革方法實施

在教學內容上，將課程內容組織為不同的知識單元，圍繞知識單元展開講解。結合教學大綱及2012—2015年考研真題分析，對每個知識單元的內容進行梳理，突出重點與難點，并強調考研新增的知識點。比如，考研大綱沒發(fā)生變化前，只講各種內部排序方法，2012年考研大綱調整后，補充了外部排序相關內容。另外，之前講述圖的存儲結構時，重點講鄰接矩陣及鄰接表，2014年考研大綱變化后，強調鄰接多重表及十字鏈表的講解;字符串的模式匹配算法以前重點講BF算法，略講或不講KMP算法，大綱變化后，新增KMP算法的具體講解。

在教學方法上，學生以小組為單位，教師采用啟發(fā)式與課堂練習相結合的方法進行授課。比如，講到圖結構單元時，先講圖的一些實際應用，比如圖搜索、圖的最短路徑問題，啟發(fā)、引導學生，調動學習的主動性。另外，課堂練習多來源于歷年考研真題及一些數(shù)據(jù)結構的實際應用，學生按組競答，一定程度上激發(fā)了學生的學習興趣，變被動學習為主動學習，逐步實現(xiàn)以“教”為中心到以“學”為中心的轉變，以提高課堂教學效果，培養(yǎng)學生發(fā)現(xiàn)問題、解決問題的實踐能力。

4.2 實踐改革方法實施

根據(jù)數(shù)據(jù)結構課程教學大綱、實驗教學大綱、考研真題分析并結合學生實際情況，將原有驗證性和設計性實驗擴充為3類，即驗證性、設計性和綜合性實驗，實驗內容分別為：順序表的操作（設計性）、單鏈表的操作（設計性）、棧和隊列的操作（驗證性）、二叉樹的操作（綜合性）、圖的操作（綜合性）、查找和排序的實現(xiàn)（驗證性）。同時，制定新的實驗考核方式，即實驗成績從上機檢查情況（占總成績的50%，教師可隨機抽查每個學生的設計性實驗或綜合性實驗至少3次）、實驗報告（占總成績的40%）、出勤情況（占總成績的10%）3個方面進行綜合評判。通過這些方式培養(yǎng)學生分析問題、解決問題的創(chuàng)造性思維能力，進而提高學生對知識的綜合應用實踐能力及算法的設計、分析能力。

在競賽方面，分析考研大綱及考研真題，結合教學大綱，從中篩選競賽知識點，制定競賽規(guī)則并組織學生積極參加競賽。從學生的反饋情況來看效果明顯，一定程度上激發(fā)了學生的學習興趣，促進了學生自主學習能力的培養(yǎng)。

4.3 方法實施效果

數(shù)據(jù)結構課程改革措施已經(jīng)在6個本科班中實施。通過采用基于考研真題分析與啟發(fā)式的數(shù)據(jù)結構理論與實踐教學改革，一定程度上激發(fā)了學生的學習興趣，調動了學生學習的積極性。理論課堂講授時輔以相應的課堂練習，有助于加深學生對相關知識的理解，進而提高學生對知識的吸收及應用能力。通過數(shù)據(jù)結構實踐教學改革，切實提高了學生綜合運用知識的實踐能力及算法設計與分析能力，這些在理論課程考核和實驗課程的檢查中都有所反映。

5 結 語

在數(shù)據(jù)結構課程中采用啟發(fā)式與課堂練習相結合的教學模式，一定程度上調動了學生的學習積極性，促進了學生對相關知識的理解，培養(yǎng)了學生自主學習能力。同時，通過數(shù)據(jù)結構實踐教學改革，提高了學生分析問題、解決問題的能力以及算法設計與分析能力。從學生反饋情況及考核情況看，我們提出的改革方法一定程度上有效改進了數(shù)據(jù)結構理論教學與實踐教學效果。

[1] 崔彩霞, 菅小艷, 龐天杰. 地方高校計算機類專業(yè)“算法與數(shù)據(jù)結構”實踐教學改革[J]. 計算機教育, 2016(7): 52-54.

[2] 嚴蔚敏, 吳偉民. 數(shù)據(jù)結構(C語言版) [M]. 北京: 清華大學出版社, 2011: I.

[3] 新東方在線. 計算機: 2014年考研大綱解析之數(shù)據(jù)結構[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。