翻轉(zhuǎn)課堂在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用

摘要：分析現(xiàn)行教學(xué)模式下數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)現(xiàn)狀，探討翻轉(zhuǎn)課堂在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用，以數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)內(nèi)容“最小生成樹”為例，提出翻轉(zhuǎn)課堂教學(xué)實(shí)例。

關(guān)鍵詞：翻轉(zhuǎn)課堂；數(shù)據(jù)結(jié)構(gòu)；教學(xué)實(shí)例；自主學(xué)習(xí)

1 數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)現(xiàn)狀

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的課程，在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)類主干課程。該課程的教學(xué)要求是：學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析技術(shù)。

數(shù)據(jù)結(jié)構(gòu)課程的現(xiàn)行教學(xué)模式以教師講授為主，即在課堂內(nèi)通過教師講課進(jìn)行知識(shí)的傳授，在課堂外則通過學(xué)生完成作業(yè)進(jìn)行知識(shí)的內(nèi)化。這種教學(xué)模式在實(shí)施過程中存在以下3個(gè)方面的不足：漠視學(xué)生的差異化需求，影響學(xué)生的學(xué)習(xí)興趣和積極性；學(xué)生是知識(shí)的被動(dòng)接受者，抑制學(xué)生獨(dú)立思考和探索創(chuàng)新能力的發(fā)展；講授時(shí)間偏長(zhǎng)，易造成學(xué)生注意力分散，影響學(xué)習(xí)效果。

探索新的教學(xué)模式，提高數(shù)據(jù)結(jié)構(gòu)課程的教

2 翻轉(zhuǎn)課堂概述

翻轉(zhuǎn)課堂是在信息化環(huán)境中，教師提供以教學(xué)視頻為主要形式的學(xué)習(xí)資源，學(xué)生在上課前完成對(duì)教學(xué)視頻等學(xué)習(xí)資源的觀看和學(xué)習(xí)，師生在課堂上一起完成作業(yè)答疑、協(xié)作探究和互動(dòng)交流等活動(dòng)的一種新型教學(xué)模式，簡(jiǎn)而言之即“課前傳授+課上內(nèi)化”。

翻轉(zhuǎn)課堂彌補(bǔ)了現(xiàn)行教學(xué)模式的不足：①滿足學(xué)生的差異化需求，激發(fā)學(xué)生的學(xué)習(xí)興趣和積極性。②促進(jìn)學(xué)生自主學(xué)習(xí)、探索創(chuàng)新和協(xié)作溝通能力的發(fā)展，學(xué)生不再是知識(shí)的被動(dòng)接受者，而是知識(shí)的主動(dòng)學(xué)習(xí)者；教師不再是知識(shí)的傳授者，而是學(xué)生自主學(xué)習(xí)的“引路人”和“指導(dǎo)者”。③能使學(xué)生自主掌握學(xué)習(xí)節(jié)奏，有利于教學(xué)效果的提高。

隨著互聯(lián)網(wǎng)的發(fā)展和普及，翻轉(zhuǎn)課堂已經(jīng)逐漸成為教育教學(xué)改革的一波新浪潮。加拿大的《環(huán)球郵報(bào)》將翻轉(zhuǎn)課堂評(píng)為2011年影響課堂教學(xué)的重大技術(shù)變革。

3 翻轉(zhuǎn)課堂在數(shù)據(jù)結(jié)構(gòu)課程中的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)課程具有知識(shí)點(diǎn)繁多、知識(shí)抽象性高、對(duì)學(xué)生的編程實(shí)踐能力要求高的特點(diǎn)。將翻轉(zhuǎn)課堂應(yīng)用于數(shù)據(jù)結(jié)構(gòu)課程，教學(xué)視頻覆蓋知識(shí)點(diǎn)面，但在知識(shí)深度和編程實(shí)踐兩個(gè)方面，還需要課堂教學(xué)和上機(jī)實(shí)驗(yàn)的配合。

3.1 課前活動(dòng)安排

從教師的角度出發(fā)，在課前，教師對(duì)教學(xué)內(nèi)容進(jìn)行梳理，劃分出若干相對(duì)獨(dú)立的小知識(shí)點(diǎn)，針對(duì)每一個(gè)小知識(shí)點(diǎn)錄制10分鐘的教學(xué)視頻。除此以外，教師整理出每一個(gè)小知識(shí)點(diǎn)的在線測(cè)試題目；在學(xué)生觀看教學(xué)視頻時(shí)，參與在線討論，了解學(xué)生的差異化需求。

從學(xué)生的角度出發(fā)，在課前，學(xué)生觀看教學(xué)視頻，完成在線測(cè)試。進(jìn)度快、基礎(chǔ)好的學(xué)生可以直接進(jìn)行在線測(cè)試，然后帶著問題有針對(duì)性地學(xué)習(xí)；進(jìn)度慢、基礎(chǔ)薄弱的學(xué)生可以重復(fù)觀看教學(xué)視頻，也可以與同學(xué)、老師進(jìn)行在線討論等。

3.2 課中活動(dòng)安排

從教師的角度出發(fā)，在課中，教師首先根據(jù)學(xué)生課前在線討論和在線測(cè)試的情況，進(jìn)行有針對(duì)性的講解；然后組織學(xué)生完成作業(yè)或進(jìn)行小組討論。對(duì)于簡(jiǎn)單的、概念性的知識(shí)點(diǎn)，教師直接組織學(xué)生完成作業(yè)，對(duì)學(xué)習(xí)有困難的學(xué)生進(jìn)行一對(duì)一輔導(dǎo)。對(duì)于復(fù)雜的、設(shè)計(jì)實(shí)現(xiàn)性的知識(shí)點(diǎn)，教師歸納總結(jié)出幾個(gè)關(guān)鍵性問題，組織學(xué)生小組討論，教師旁聽學(xué)生的討論情況，適當(dāng)進(jìn)行引導(dǎo)和建議。小組討論結(jié)束后，教師聽取代表學(xué)生的發(fā)言，對(duì)小組討論過程中出現(xiàn)的問題進(jìn)行講解。

從學(xué)生的角度出發(fā)，在課中，學(xué)生完成作業(yè)或進(jìn)行小組討論。數(shù)據(jù)結(jié)構(gòu)一般為小班教學(xué)，學(xué)生人數(shù)不超過20人，學(xué)生由3-5人組成一個(gè)討論小組，每個(gè)小組選出一名小組長(zhǎng)。小組長(zhǎng)負(fù)責(zé)組織協(xié)調(diào)小組成員的討論和發(fā)言，并在小組討論結(jié)束后進(jìn)行代表發(fā)言。小組成員應(yīng)積極交流對(duì)問題的認(rèn)識(shí)和想法，達(dá)成組內(nèi)共識(shí)。

4 翻轉(zhuǎn)課堂應(yīng)用于數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)實(shí)例

以數(shù)據(jù)結(jié)構(gòu)第7章“圖”中的教學(xué)內(nèi)容“圖的最小生成樹”為例，介紹翻轉(zhuǎn)課堂應(yīng)用于數(shù)據(jù)結(jié)構(gòu)課程的實(shí)施過程。這一教學(xué)內(nèi)容的教學(xué)要求如下：

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

其中，教學(xué)重點(diǎn)是理解普里姆算法和克魯斯卡爾算法的算法思想，教學(xué)難點(diǎn)是掌握普里姆算法和克魯斯卡爾算法的編程實(shí)現(xiàn)。

根據(jù)教學(xué)要求，這一教學(xué)內(nèi)容可以劃分成3個(gè)相對(duì)獨(dú)立的小知識(shí)點(diǎn)：圖的最小生成樹的概念；普里姆算法；克魯斯卡爾算法；其中，普里姆算法和克魯斯卡爾算法的教學(xué)安排類似，在接下來的討論中均以普里姆算法為例。

4.1 課前活動(dòng)設(shè)計(jì)

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

4.1.1 圖的最小生成樹的概念

（1）教學(xué)視頻設(shè)計(jì)。圖的最小生成樹指的是帶權(quán)無向連通圖中各邊權(quán)值之和最小的生成樹，常常應(yīng)用于構(gòu)造具有最小代價(jià)的通信線路等實(shí)際問題中。教學(xué)視頻如果只是理論性地介紹什么是圖的最小生成樹的概念，學(xué)生難以將這一概念與實(shí)際應(yīng)用聯(lián)系起來，因此，教師由一個(gè)實(shí)際問題出發(fā)，通過分析，引出圖的最小生成樹的概念，使得學(xué)生在學(xué)習(xí)這一概念的同時(shí)，能了解它的實(shí)際應(yīng)用。

問題設(shè)計(jì)：

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

問題分析：

這個(gè)實(shí)際問題可以抽象成一個(gè)無向完全網(wǎng)G。網(wǎng)G包含6個(gè)頂點(diǎn)，15條邊。其中頂點(diǎn)表示城市，邊表示兩城市之間的通訊線路，邊的權(quán)值表示相應(yīng)的建設(shè)成本。

這個(gè)實(shí)際問題轉(zhuǎn)換成：構(gòu)造網(wǎng)G的各邊權(quán)值之和最小的生成樹（最小生成樹）。

（2）在線測(cè)試設(shè)計(jì)。什么是圖的最小生成樹？圖的最小生成樹一般應(yīng)用于哪些實(shí)際問題中？

4.1.2 普里姆算法

（1）教學(xué)視頻設(shè)計(jì)。對(duì)普里姆算法的學(xué)習(xí)包括理解算法思想，掌握編程實(shí)現(xiàn)。教學(xué)視頻只介紹普里姆算法的算法思想。

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

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

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

（2）在線測(cè)試設(shè)計(jì)。給出具有典型特征的圖，要求學(xué)生利用普里姆算法構(gòu)造其最小生成樹，畫出構(gòu)造過程。

4.2 課中活動(dòng)設(shè)計(jì)

在課中，教師首先根據(jù)學(xué)生課前在線討論和在線測(cè)試的情況，進(jìn)行有針對(duì)性的講解，然后組織學(xué)生完成作業(yè)或進(jìn)行小組討論。

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

圖的最小生成樹是一個(gè)簡(jiǎn)單的概念性的知識(shí)點(diǎn)，教師直接組織學(xué)生完成作業(yè)。在學(xué)生完成作業(yè)的過程中，教師對(duì)學(xué)習(xí)有困難的學(xué)生進(jìn)行一對(duì)一輔導(dǎo)。

2）普里姆算法。

普里姆算法是一個(gè)復(fù)雜的設(shè)計(jì)性的知識(shí)點(diǎn)，在教學(xué)視頻中只介紹了普里姆算法的算法思想。在課中，教師歸納總結(jié)出普里姆算法在編程實(shí)現(xiàn)時(shí)需要解決的幾個(gè)關(guān)鍵性問題，依次組織學(xué)生進(jìn)行小組討論。歸納總結(jié)出的問題如下：

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

（2）待選邊集合如何表示？待選邊集合已經(jīng)存儲(chǔ)在鄰接矩陣或鄰接表中，但由于鄰接矩陣或鄰接表中存儲(chǔ)了網(wǎng)中所有的邊，要在待選邊集合中選擇權(quán)值最小的邊，需要遍歷整個(gè)鄰接矩陣或鄰接表，每次遍歷的時(shí)間復(fù)雜度為O（n2）。為了降低時(shí)間復(fù)雜度，附設(shè)一個(gè)輔助數(shù)組，用于存儲(chǔ)待選邊集合。

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

（4）-個(gè)頂點(diǎn)并入集合U如何表示？當(dāng)挑選出權(quán)值最小的邊后，需要將該邊依附的屬于集合V-U的頂點(diǎn)并入集合U，此時(shí)，將輔助數(shù)組中該頂點(diǎn)對(duì)應(yīng)分量的權(quán)值域置為0。

針對(duì)這4個(gè)問題，教師在每次提問后，給學(xué)生10分鐘左右的時(shí)間進(jìn)行小組討論，由小組長(zhǎng)負(fù)責(zé)協(xié)調(diào)小組成員的討論和發(fā)言，達(dá)成組內(nèi)共識(shí)。在學(xué)生進(jìn)行小組討論的過程中，教師旁聽學(xué)生的討論情況，適當(dāng)進(jìn)行引導(dǎo)和建議。小組討論結(jié)束后，教師聽取小組長(zhǎng)的匯報(bào)，對(duì)小組討論過程中出現(xiàn)的典型問題進(jìn)行講解。

經(jīng)過小組討論后，學(xué)生對(duì)普里姆算法在編程實(shí)現(xiàn)過程中需要解決的4個(gè)關(guān)鍵性問題已經(jīng)有了自己的認(rèn)識(shí)和想法，接下來組織學(xué)生上機(jī)實(shí)驗(yàn)，利用C語言編程實(shí)現(xiàn)普里姆算法。在上機(jī)實(shí)驗(yàn)過程中，教師對(duì)編程有困難的學(xué)生進(jìn)行一對(duì)一輔導(dǎo)。

5 結(jié)語

數(shù)據(jù)結(jié)構(gòu)課程具有知識(shí)點(diǎn)繁多，知識(shí)抽象性高，對(duì)學(xué)生的編程實(shí)踐能力要求高的特點(diǎn)。在現(xiàn)行教學(xué)模式下，學(xué)生習(xí)慣于被動(dòng)地接受知識(shí)，而不是主動(dòng)地思考和探究，以至于最后對(duì)知識(shí)的理解比較膚淺，編程實(shí)踐能力也比較薄弱。將翻轉(zhuǎn)課堂應(yīng)用于數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中，學(xué)生成為知識(shí)的主動(dòng)學(xué)習(xí)者，培養(yǎng)了學(xué)生獨(dú)立思考和探索創(chuàng)新的能力；學(xué)生在小組討論的過程中，鍛煉了組織協(xié)調(diào)和團(tuán)隊(duì)合作能力；教師能夠關(guān)注學(xué)生的個(gè)體化差異，滿足學(xué)生的差異化需求，有利于教學(xué)效果的提高。