李 征，楊 偉，袁 科

（河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封475004）

基于考研真題分析的數(shù)據(jù)結(jié)構(gòu)教學(xué)改革

李 征，楊 偉，袁 科

（河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開封475004）

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

真題分析；課堂練習(xí)；教學(xué)改革

0 引 言

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

1 數(shù)據(jù)結(jié)構(gòu)知識體系

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

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

2 歷年考研真題分析

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

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

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

表1 2012—2015年數(shù)據(jù)結(jié)構(gòu)考研真題考查知識點(diǎn)及分值分布情況

3 基于考研真題分析的教學(xué)改革

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

3.1 理論教學(xué)改革

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

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

3.2 實(shí)踐教學(xué)改革

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

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

4 改革方法實(shí)施及效果

4.1 理論改革方法實(shí)施

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

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

4.2 實(shí)踐改革方法實(shí)施

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

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

4.3 方法實(shí)施效果

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

5 結(jié) 語

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

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

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

[3] 新東方在線. 計(jì)算機(jī): 2014年考研大綱解析之?dāng)?shù)據(jù)結(jié)構(gòu)[EB/OL]. [2016-10-11]. http://yz.chsi.com.cn/kyzx/zyk/201310/20131011/520716177. html.

（編輯：郭田珍）

1672-5913(2017)01-0076-04

G642

李征，女，副教授，研究方向?yàn)榉?wù)計(jì)算、軟件工程，lizheng@henu．edu．cn。