柳 欣 李保田 薛玉利 唐 艷

1.山東青年政治學(xué)院信息工程學(xué)院，山東 濟(jì)南 250103

2.山東省高校信息安全與智能控制重點(diǎn)實(shí)驗(yàn)室（山東青年政治學(xué)院），山東 濟(jì)南 250103

數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程是我校計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的專(zhuān)業(yè)選修課。該課程對(duì)先修課程數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)與分析的教學(xué)內(nèi)容進(jìn)行了補(bǔ)充，同時(shí)對(duì)這兩門(mén)課程的重點(diǎn)內(nèi)容進(jìn)行了知識(shí)歸納和算法設(shè)計(jì)的思維拓展，形成了完整的數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)鏈。通過(guò)本課程的學(xué)習(xí)，學(xué)生能深入理解典型數(shù)據(jù)結(jié)構(gòu)的重要性質(zhì)、存儲(chǔ)結(jié)構(gòu)以及具體實(shí)現(xiàn)，掌握重點(diǎn)算法，并能運(yùn)用數(shù)據(jù)結(jié)構(gòu)技術(shù)和算法設(shè)計(jì)策略分析、解決現(xiàn)實(shí)應(yīng)用中的問(wèn)題，培養(yǎng)軟件開(kāi)發(fā)素質(zhì)、工程意識(shí)和職業(yè)道德規(guī)范。數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程的教學(xué)內(nèi)容中包含大量復(fù)雜算法，這些算法具有存儲(chǔ)結(jié)構(gòu)定義復(fù)雜、算法執(zhí)行過(guò)程抽象、實(shí)驗(yàn)難度大等特點(diǎn)，在傳統(tǒng)教學(xué)模式下，教師往往會(huì)面臨“教師講不動(dòng)、學(xué)生沒(méi)興趣”的雙重困境。

一、支撐的教學(xué)理論

問(wèn)題驅(qū)動(dòng)教學(xué)是一種“以學(xué)生為主體、以問(wèn)題為核心”的教學(xué)方法，其特點(diǎn)如下：（1）教師將教學(xué)內(nèi)容嵌入精心創(chuàng)設(shè)的問(wèn)題情境中，將課堂教學(xué)轉(zhuǎn)換為不斷地提出問(wèn)題和解決問(wèn)題的迭代過(guò)程。（2）強(qiáng)調(diào)學(xué)生是學(xué)習(xí)主體，是知識(shí)的主動(dòng)探究者。教師的角色是組織和引導(dǎo)對(duì)問(wèn)題的討論，并且為學(xué)生提供必要的幫助。（3）教學(xué)目標(biāo)不是靠教師講授直接達(dá)成的，而是在教師與學(xué)生的共同努力下以遞進(jìn)方式達(dá)成的，具體表現(xiàn)為認(rèn)識(shí)問(wèn)題，探索解決關(guān)鍵問(wèn)題的途徑，逐步求精地解決問(wèn)題，對(duì)不同的問(wèn)題解決方法進(jìn)行比較以及通過(guò)思考發(fā)散性問(wèn)題實(shí)現(xiàn)知識(shí)拓展。成果導(dǎo)向教育（OBE,Outcomes-based Edu‐cation）是工程教育專(zhuān)業(yè)認(rèn)證的核心理念，它強(qiáng)調(diào)首先明確學(xué)生的學(xué)習(xí)成果（即畢業(yè)要求），然后根據(jù)畢業(yè)要求對(duì)課程的教學(xué)目標(biāo)和教學(xué)內(nèi)容進(jìn)行反向設(shè)計(jì)。思維可視化是一種利用圖像、媒介、言語(yǔ)和肢體表征對(duì)不可見(jiàn)的思維進(jìn)行直觀展示的技術(shù)。該技術(shù)的成功運(yùn)用可以加強(qiáng)學(xué)生的思維訓(xùn)練，提升他們的創(chuàng)新思維層次。

二、問(wèn)題驅(qū)動(dòng)教學(xué)改革總體思路

（一）OBE理念下的教學(xué)目標(biāo)制訂

根據(jù)工程教育認(rèn)證標(biāo)準(zhǔn)，我們將人才培養(yǎng)方案中的畢業(yè)要求細(xì)化為33 個(gè)二級(jí)指標(biāo)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程對(duì)其中的4 個(gè)指標(biāo)點(diǎn)形成支撐（如表1 所示），分別側(cè)重對(duì)學(xué)生的應(yīng)用能力、分析能力、設(shè)計(jì)能力和職業(yè)規(guī)范進(jìn)行培養(yǎng)。

在確定這些指標(biāo)點(diǎn)之后，我們?cè)O(shè)置了4 個(gè)與之相應(yīng)的教學(xué)目標(biāo)（如表2所示）。

（二）案例算法選取

在教學(xué)目標(biāo)確定之后，我們遴選了一部分有代表性的復(fù)雜算法作為實(shí)施問(wèn)題驅(qū)動(dòng)教學(xué)的內(nèi)容。具體遴選原則如下：1.算法的底層存儲(chǔ)結(jié)構(gòu)具有代表性，學(xué)習(xí)該算法有助于學(xué)生加深對(duì)順序/鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的理解。2.算法的設(shè)計(jì)思想體現(xiàn)了典型的算法設(shè)計(jì)策略，能較好地對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程和先修課程算法設(shè)計(jì)與分析的教學(xué)內(nèi)容進(jìn)行銜接。3.算法有著較為廣泛的現(xiàn)實(shí)應(yīng)用，有利于與思政元素進(jìn)行結(jié)合。

（三）教學(xué)難點(diǎn)分析以及應(yīng)對(duì)策略

在選定教學(xué)內(nèi)容之后，我們結(jié)合教材中的算法描述，對(duì)有可能給學(xué)生理解造成障礙的關(guān)鍵點(diǎn)進(jìn)行分析。以模式匹配算法為例，教材中介紹了兩個(gè)算法，即BF（Brute Force）的模式匹配算法和KMP（Kruth-Morris-Pratt）模式匹配算法。這兩個(gè)算法都采用了順序存儲(chǔ)結(jié)構(gòu)，其核心思想是借助游標(biāo)i 和j 對(duì)主串S 和模式T 中參與匹配的當(dāng)前字符進(jìn)行比較。通過(guò)分析發(fā)現(xiàn)，在教學(xué)過(guò)程中存在以下的難點(diǎn)：（1）當(dāng)發(fā)生“失配”時(shí)，如何對(duì)游標(biāo)i進(jìn)行回溯。（2）在BF模式匹配算法中，利用語(yǔ)句“i=i-j+2;”實(shí)現(xiàn)對(duì)游標(biāo)i的回溯，但是這條語(yǔ)句的可讀性欠佳。（3）教材的KMP算法描述中對(duì)“S[i]=T[j]”和“j=0”兩種情況下的游標(biāo)設(shè)置進(jìn)行了合并，致使理解算法的難度增大。

針對(duì)教學(xué)難點(diǎn)，我們采取了以下的應(yīng)對(duì)策略：（1）在許多復(fù)雜算法中，都是先對(duì)特定條件做出判斷，然后分情況進(jìn)行處理。對(duì)這些情況進(jìn)行圖解，可以為學(xué)生自主探究提供最有效的學(xué)習(xí)“支架”。（2）教材中的算法描述往往是最精簡(jiǎn)的形式，缺點(diǎn)是容易造成閱讀和理解的困難。對(duì)此，可以采用問(wèn)題驅(qū)動(dòng)教學(xué)方法，先引導(dǎo)學(xué)生將精力放在如何解決問(wèn)題上，在歸納得出算法描述之后，再對(duì)算法描述進(jìn)行化簡(jiǎn)，最終得出與教材相同的算法描述。

（四）OBE 理念指導(dǎo)下的問(wèn)題設(shè)計(jì)與問(wèn)題驅(qū)動(dòng)教學(xué)詳細(xì)設(shè)計(jì)

針對(duì)教學(xué)難點(diǎn)，我們?cè)贠BE理念指導(dǎo)下進(jìn)行問(wèn)題設(shè)計(jì)。教師將在問(wèn)題驅(qū)動(dòng)教學(xué)過(guò)程的不同階段提出這些問(wèn)題，既能實(shí)現(xiàn)問(wèn)題的抽絲剝繭、逐步求精，又能對(duì)人才培養(yǎng)方案中有關(guān)能力培養(yǎng)和職業(yè)規(guī)范的指標(biāo)點(diǎn)進(jìn)行支撐。以模式匹配算法為例，我們針對(duì)教學(xué)內(nèi)容設(shè)置了10個(gè)具體問(wèn)題（如表3所示）。

在完成問(wèn)題設(shè)計(jì)之后，需要圍繞這些問(wèn)題開(kāi)展問(wèn)題驅(qū)動(dòng)教學(xué)的詳細(xì)設(shè)計(jì)。在該過(guò)程中，我們采用文獻(xiàn)［3］的做法，將每個(gè)階段的教學(xué)過(guò)程劃分為多個(gè)循序漸進(jìn)的板塊，即問(wèn)題情境、自主探究、合作交流、總結(jié)提升和遷移拓展。

三、問(wèn)題驅(qū)動(dòng)教學(xué)設(shè)計(jì)舉例

我們以模式匹配算法為例，給出一個(gè)具體的問(wèn)題驅(qū)動(dòng)教學(xué)的教學(xué)設(shè)計(jì)案例（教師提出的問(wèn)題均來(lái)自表3）。本次課的教學(xué)目標(biāo)如下：（1）理解字符串的順序存儲(chǔ)結(jié)構(gòu)、掌握BF 模式匹配算法和KMP 模式匹配算法。（2）通過(guò)課程思政使學(xué)生了解社會(huì)主義核心價(jià)值觀倡導(dǎo)的誠(chéng)信理念，保持科研誠(chéng)信、杜絕抄襲行為?？紤]到KMP 算法是在BF 算法基礎(chǔ)上改進(jìn)得到的，我們將整個(gè)教學(xué)過(guò)程分為以下兩個(gè)階段。

（一）第一階段——樸素模式匹配算法的問(wèn)題驅(qū)動(dòng)教學(xué)

問(wèn)題情境板塊：教師介紹教材中的病毒感染檢測(cè)案例，并且提出問(wèn)題1。

自主探究板塊：首先，教師簡(jiǎn)要回顧字符串順序存儲(chǔ)結(jié)構(gòu)，并且提出問(wèn)題2。接下來(lái)，教師提供對(duì)模式匹配問(wèn)題的完整描述以及重要的符號(hào)定義。最后，教師向?qū)W生提供有關(guān)算法匹配過(guò)程中“成功”和“失配”兩種情況下的圖示（如圖1所示，匹配成功的區(qū)域用灰色填充），并且提出問(wèn)題3。該板塊結(jié)束后，學(xué)生會(huì)在教師提示下自行寫(xiě)出算法描述。

合作交流板塊：教師要求學(xué)生以小組為單位將寫(xiě)出的算法描述與教材中的算法描述進(jìn)行對(duì)照。容易發(fā)現(xiàn)，兩者并不一致。這主要體現(xiàn)在，當(dāng)發(fā)生失配時(shí)，教材并未使用語(yǔ)句“i=pos+1;”對(duì)游標(biāo)i進(jìn)行回溯，而是使用了令人費(fèi)解的語(yǔ)句“i=i-j+2;”。對(duì)此，教師提出問(wèn)題4，并且為學(xué)生提供一個(gè)具體的例子作為學(xué)習(xí)支架（見(jiàn)圖2）。通過(guò)討論，學(xué)生終于理解如果將回溯位置pos+1 視為未知數(shù)，同時(shí)將i 和j 的當(dāng)前位置視為已知數(shù)，則可以通過(guò)解方程而求出pos+1的值，即i-j+2。

總結(jié)提升板塊：為了鞏固學(xué)習(xí)成果，教師向?qū)W生提供文獻(xiàn)［8］中的模式匹配問(wèn)題實(shí)例S="ababcabcacbab"，T="abcac"，并且要求學(xué)生利用圖解方法進(jìn)行模式匹配，且主串S的匹配開(kāi)始位置為i=3。這是一個(gè)精心設(shè)計(jì)的“陷阱”，學(xué)生需要總共執(zhí)行4 輪模式匹配（即當(dāng)主串的匹配起始位置為i=6時(shí)）才能最終取得匹配成功。此時(shí)，學(xué)生發(fā)覺(jué)算法的回溯策略并非總是有效的，存在即使執(zhí)行回溯也會(huì)“做無(wú)用功”的現(xiàn)象。此時(shí)，教師可以提出問(wèn)題5。

（二）第二階段——KMP 模式匹配算法的問(wèn)題驅(qū)動(dòng)教學(xué)

問(wèn)題情境板塊：教師介紹KMP 算法，并且指出該算法可以有效地避免上述“做無(wú)用功”的現(xiàn)象。同時(shí)，強(qiáng)調(diào)該算法假設(shè)存在一個(gè)“神奇”的next表格。

自主探究板塊：教師將KMP算法每輪的匹配過(guò)程分為“本輪匹配成功”“本輪發(fā)生失配”和“上一輪發(fā)生失配導(dǎo)致j 回退到0”三種情況，并且利用思維可視化技術(shù)為學(xué)生提供圖形化的學(xué)習(xí)支架，如圖3所示，匹配成功的區(qū)域用灰色填充。最后，教師提出問(wèn)題6。

合作交流板塊：教師強(qiáng)調(diào)，盡管已經(jīng)理解了KMP 算法的核心技術(shù)，但是必須將next 表格構(gòu)造出來(lái)，否則KMP算法就是“無(wú)源之水，無(wú)本之木”。在具體教學(xué)過(guò)程中，教師首先介紹用于構(gòu)造next表格的手工算法，然后提出問(wèn)題7。

總結(jié)提升板塊：在該板塊，教師提出問(wèn)題8，并且以討論的形式對(duì)兩個(gè)算法進(jìn)行優(yōu)缺點(diǎn)比較。教師負(fù)責(zé)引導(dǎo)討論的走向，最終得出以下結(jié)論：（1）KMP算法適合于從外存中讀取主串的情況。（2）KMP 算法并非總是優(yōu)于BF算法。

遷移拓展板塊：教師強(qiáng)調(diào)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)最大的困難在于理解和設(shè)計(jì)算法。選取適當(dāng)?shù)睦舆M(jìn)行圖解分析，不但可以降低問(wèn)題難度，而且有助于歸納得出算法描述中的關(guān)鍵語(yǔ)句。此時(shí)，教師提出問(wèn)題9，鼓勵(lì)學(xué)生將圖解作為攻克復(fù)雜算法的“利器”。事實(shí)上，模式匹配算法是設(shè)計(jì)論文抄襲檢測(cè)算法的重要基礎(chǔ)。我們認(rèn)為，這個(gè)思政元素與教學(xué)內(nèi)容緊密結(jié)合，容易為學(xué)生所接受。因此，教師可以不失時(shí)機(jī)地介紹這個(gè)應(yīng)用，并且提出問(wèn)題10，使學(xué)生明確恪守職業(yè)道德、堅(jiān)守學(xué)術(shù)誠(chéng)信與社會(huì)主義核心價(jià)值觀倡導(dǎo)的誠(chéng)信理念在本質(zhì)上是一致的。

四、滿意度調(diào)查

為了了解問(wèn)題驅(qū)動(dòng)教學(xué)改革的實(shí)際效果，我們?cè)诮Y(jié)課后利用“問(wèn)卷星”向?qū)W生發(fā)布了匿名調(diào)查問(wèn)卷。問(wèn)卷內(nèi)容主要涉及課程教學(xué)滿意度、問(wèn)題驅(qū)動(dòng)教學(xué)法對(duì)學(xué)習(xí)積極性的促進(jìn)作用、對(duì)問(wèn)題的難度評(píng)價(jià)、圖解是否有助于對(duì)算法關(guān)鍵執(zhí)行過(guò)程的理解、是否希望教師提供有針對(duì)性的圖解作為學(xué)習(xí)支架等內(nèi)容。

結(jié)果顯示，有68.64%的學(xué)生認(rèn)為問(wèn)題驅(qū)動(dòng)教學(xué)有助于提高學(xué)習(xí)積極性，有85.59%的學(xué)生贊同教師提供圖解作為學(xué)習(xí)支架的做法。這說(shuō)明該嘗試取得了較好的效果。

五、結(jié)束語(yǔ)

為了改善數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程的教學(xué)效果，本文提出了基于OBE 理念的問(wèn)題驅(qū)動(dòng)教學(xué)改革思路。通過(guò)引入OBE 理念，使得課程教學(xué)目標(biāo)聚焦于對(duì)學(xué)生的應(yīng)用能力、分析能力、設(shè)計(jì)能力和職業(yè)規(guī)范的培養(yǎng)。同時(shí)，教師必須在問(wèn)題設(shè)計(jì)階段充分考慮教學(xué)內(nèi)容對(duì)指標(biāo)點(diǎn)的有效支撐。此外，以模式匹配算法為例，提出詳細(xì)的問(wèn)題驅(qū)動(dòng)教學(xué)設(shè)計(jì)案例。今后，我們將在以下方面繼續(xù)深化現(xiàn)有研究：（1）建立面向數(shù)據(jù)結(jié)構(gòu)進(jìn)階課程的問(wèn)題驅(qū)動(dòng)教學(xué)案例庫(kù)。（2）在OBE理念指導(dǎo)下，開(kāi)展針對(duì)問(wèn)題驅(qū)動(dòng)教學(xué)內(nèi)容的知識(shí)點(diǎn)考核達(dá)成度評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果改善教學(xué)方法和內(nèi)容，形成“問(wèn)題驅(qū)動(dòng)教學(xué)—達(dá)成度評(píng)價(jià)—改進(jìn)教學(xué)”的完整閉環(huán)結(jié)構(gòu)。