翻轉課堂在數據結構課程中的應用

摘要：分析現行教學模式下數據結構課程的教學現狀，探討翻轉課堂在數據結構課程中的應用，以數據結構課程的教學內容“最小生成樹”為例，提出翻轉課堂教學實例。

關鍵詞：翻轉課堂；數據結構；教學實例；自主學習

1 數據結構課程的教學現狀

數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等的課程，在計算機科學中是一門綜合性的專業基礎類主干課程。該課程的教學要求是：學會分析研究計算機加工的數據結構特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析技術。

數據結構課程的現行教學模式以教師講授為主，即在課堂內通過教師講課進行知識的傳授，在課堂外則通過學生完成作業進行知識的內化。這種教學模式在實施過程中存在以下3個方面的不足：漠視學生的差異化需求，影響學生的學習興趣和積極性；學生是知識的被動接受者，抑制學生獨立思考和探索創新能力的發展；講授時間偏長，易造成學生注意力分散，影響學習效果。

探索新的教學模式，提高數據結構課程的教

2 翻轉課堂概述

翻轉課堂是在信息化環境中，教師提供以教學視頻為主要形式的學習資源，學生在上課前完成對教學視頻等學習資源的觀看和學習，師生在課堂上一起完成作業答疑、協作探究和互動交流等活動的一種新型教學模式，簡而言之即“課前傳授+課上內化”。

翻轉課堂彌補了現行教學模式的不足：①滿足學生的差異化需求，激發學生的學習興趣和積極性。②促進學生自主學習、探索創新和協作溝通能力的發展，學生不再是知識的被動接受者，而是知識的主動學習者；教師不再是知識的傳授者，而是學生自主學習的“引路人”和“指導者”。③能使學生自主掌握學習節奏，有利于教學效果的提高。

隨著互聯網的發展和普及，翻轉課堂已經逐漸成為教育教學改革的一波新浪潮。加拿大的《環球郵報》將翻轉課堂評為2011年影響課堂教學的重大技術變革。

3 翻轉課堂在數據結構課程中的應用

數據結構課程具有知識點繁多、知識抽象性高、對學生的編程實踐能力要求高的特點。將翻轉課堂應用于數據結構課程，教學視頻覆蓋知識點面，但在知識深度和編程實踐兩個方面，還需要課堂教學和上機實驗的配合。

3.1 課前活動安排

從教師的角度出發，在課前，教師對教學內容進行梳理，劃分出若干相對獨立的小知識點，針對每一個小知識點錄制10分鐘的教學視頻。除此以外，教師整理出每一個小知識點的在線測試題目；在學生觀看教學視頻時，參與在線討論，了解學生的差異化需求。

從學生的角度出發，在課前，學生觀看教學視頻，完成在線測試。進度快、基礎好的學生可以直接進行在線測試，然后帶著問題有針對性地學習；進度慢、基礎薄弱的學生可以重復觀看教學視頻，也可以與同學、老師進行在線討論等。

3.2 課中活動安排

從教師的角度出發，在課中，教師首先根據學生課前在線討論和在線測試的情況，進行有針對性的講解；然后組織學生完成作業或進行小組討論。對于簡單的、概念性的知識點，教師直接組織學生完成作業，對學習有困難的學生進行一對一輔導。對于復雜的、設計實現性的知識點，教師歸納總結出幾個關鍵性問題，組織學生小組討論，教師旁聽學生的討論情況，適當進行引導和建議。小組討論結束后，教師聽取代表學生的發言，對小組討論過程中出現的問題進行講解。

從學生的角度出發，在課中，學生完成作業或進行小組討論。數據結構一般為小班教學，學生人數不超過20人，學生由3-5人組成一個討論小組，每個小組選出一名小組長。小組長負責組織協調小組成員的討論和發言，并在小組討論結束后進行代表發言。小組成員應積極交流對問題的認識和想法，達成組內共識。

4 翻轉課堂應用于數據結構課程的教學實例

以數據結構第7章“圖”中的教學內容“圖的最小生成樹”為例，介紹翻轉課堂應用于數據結構課程的實施過程。這一教學內容的教學要求如下：

①了解圖的最小生成樹的概念；②理解構造圖的最小生成樹的兩種算法：普里姆（Prim）算法和克魯斯卡爾（Kruscal）算法的算法思想；③掌握普里姆算法和克魯斯卡爾算法的編程實現。

其中，教學重點是理解普里姆算法和克魯斯卡爾算法的算法思想，教學難點是掌握普里姆算法和克魯斯卡爾算法的編程實現。

根據教學要求，這一教學內容可以劃分成3個相對獨立的小知識點：圖的最小生成樹的概念；普里姆算法；克魯斯卡爾算法；其中，普里姆算法和克魯斯卡爾算法的教學安排類似，在接下來的討論中均以普里姆算法為例。

4.1 課前活動設計

根據對教學內容的劃分，教師在課前可以錄制3個教學視頻，分別介紹圖的最小生成樹的概念、普里姆算法和克魯斯卡爾算法。然而，要在短短10分鐘的教學視頻中完整介紹普里姆算法或克魯斯卡爾算法的算法思想和編程實現是不可能的，因此，在學習普里姆算法和克魯斯卡爾算法時，需要教學視頻、課堂討論、上機實驗的相互配合。

4.1.1 圖的最小生成樹的概念

（1）教學視頻設計。圖的最小生成樹指的是帶權無向連通圖中各邊權值之和最小的生成樹，常常應用于構造具有最小代價的通信線路等實際問題中。教學視頻如果只是理論性地介紹什么是圖的最小生成樹的概念，學生難以將這一概念與實際應用聯系起來，因此，教師由一個實際問題出發，通過分析，引出圖的最小生成樹的概念，使得學生在學習這一概念的同時，能了解它的實際應用。

問題設計：

已知6座城市：合肥（H）、蕪湖（W）、六安（L）、亳州（B）、滁州（C）、馬鞍山（M）。要在這6座城市之間建設通訊網絡，要求所有城市能相互通訊，且總的建設成本最小。

問題分析：

這個實際問題可以抽象成一個無向完全網G。網G包含6個頂點，15條邊。其中頂點表示城市，邊表示兩城市之間的通訊線路，邊的權值表示相應的建設成本。

這個實際問題轉換成：構造網G的各邊權值之和最小的生成樹（最小生成樹）。

（2）在線測試設計。什么是圖的最小生成樹？圖的最小生成樹一般應用于哪些實際問題中？

4.1.2 普里姆算法

（1）教學視頻設計。對普里姆算法的學習包括理解算法思想，掌握編程實現。教學視頻只介紹普里姆算法的算法思想。

普里姆算法是一種構造圖的最小生成樹的算法，算法思想如下：

假設N=（V，{E}）是連通網，TE是N上最小生成樹中邊的集合。算法從U={uo}（uo∈V），TE={）開始，重復執行下述操作：在所有u∈U.v∈V-U的邊（u，v）∈E（待選邊）中找一條權值最小的邊（uo，vo）并人集合TE，同時v。并入u，直至U=V為止。此時TE中必有n-l條邊，則T=（V，{TE}）為N的最小生成樹。

教學視頻如果只是理論性地介紹普里姆算法的算法思想，不僅枯燥無味，而且難以表達清楚，因此，教師配合動畫演示，講解利用普里姆算法構造圖的最小生成樹的具體過程。在講解過程中，需要注意以下兩點：①集合V中的每一個頂點都可以作為初始的u。點；②當待選邊集合中出現多條權值相等且最小的邊時，任意選擇其中一條即可。

（2）在線測試設計。給出具有典型特征的圖，要求學生利用普里姆算法構造其最小生成樹，畫出構造過程。

4.2 課中活動設計

在課中，教師首先根據學生課前在線討論和在線測試的情況，進行有針對性的講解，然后組織學生完成作業或進行小組討論。

1）圖的最小生成樹的概念。

圖的最小生成樹是一個簡單的概念性的知識點，教師直接組織學生完成作業。在學生完成作業的過程中，教師對學習有困難的學生進行一對一輔導。

2）普里姆算法。

普里姆算法是一個復雜的設計性的知識點，在教學視頻中只介紹了普里姆算法的算法思想。在課中，教師歸納總結出普里姆算法在編程實現時需要解決的幾個關鍵性問題，依次組織學生進行小組討論。歸納總結出的問題如下：

（1）無向連通網如何存儲？在普里姆算法中，可以采用鄰接矩陣或鄰接表存儲無向連通網。

（2）待選邊集合如何表示？待選邊集合已經存儲在鄰接矩陣或鄰接表中，但由于鄰接矩陣或鄰接表中存儲了網中所有的邊，要在待選邊集合中選擇權值最小的邊，需要遍歷整個鄰接矩陣或鄰接表，每次遍歷的時間復雜度為O（n2）。為了降低時間復雜度，附設一個輔助數組，用于存儲待選邊集合。

（3）權值最小的邊如何選擇？在輔助數組中選擇權值最小的邊，可以采用樸素的最小值求解算法，時間復雜度降低為O（n）。

（4）-個頂點并入集合U如何表示？當挑選出權值最小的邊后，需要將該邊依附的屬于集合V-U的頂點并入集合U，此時，將輔助數組中該頂點對應分量的權值域置為0。

針對這4個問題，教師在每次提問后，給學生10分鐘左右的時間進行小組討論，由小組長負責協調小組成員的討論和發言，達成組內共識。在學生進行小組討論的過程中，教師旁聽學生的討論情況，適當進行引導和建議。小組討論結束后，教師聽取小組長的匯報，對小組討論過程中出現的典型問題進行講解。

經過小組討論后，學生對普里姆算法在編程實現過程中需要解決的4個關鍵性問題已經有了自己的認識和想法，接下來組織學生上機實驗，利用C語言編程實現普里姆算法。在上機實驗過程中，教師對編程有困難的學生進行一對一輔導。

5 結語

數據結構課程具有知識點繁多，知識抽象性高，對學生的編程實踐能力要求高的特點。在現行教學模式下，學生習慣于被動地接受知識，而不是主動地思考和探究，以至于最后對知識的理解比較膚淺，編程實踐能力也比較薄弱。將翻轉課堂應用于數據結構課程的教學中，學生成為知識的主動學習者，培養了學生獨立思考和探索創新的能力；學生在小組討論的過程中，鍛煉了組織協調和團隊合作能力；教師能夠關注學生的個體化差異，滿足學生的差異化需求，有利于教學效果的提高。