基于工程認證的數據結構實踐逆向教學設計

徐燕妮，林曉霞，李環宇

（山東科技大學（泰安校區）信息工程系，泰安271000）

0 引言

作為國際通行的工程教育質量保障制度，工程教育專業認證是大勢所趨，國家已經全面建立工程專業認證體系[1-2]，各大院校正積極地投入大量精力進行工程專業認證的審核。在此大背景下，本文從學生發展和社會需求為出發點，專業培養目標為導向，對《數據結構》實驗課程教學環節進行逆向設計，助于提升學生實踐創新能力，全面提高工程教育人才培養質量。

1 數據結構課程的培養目標

《數據結構》課程是計算機專業及相關專業的核心課程，在整個課程體系中起了承上啟下的作用，在系統應用軟件開發、無線傳感器網絡、入侵檢測等領域均有廣泛的應用。它全面而又系統地講解了數據的組織形式、在計算機內部的存儲形式以及數據相關運算的實現。著重培養學生軟件設計、算法應用、編程調試和計算思維的綜合素質，提高學生運用所學專業知識解決實際信息技術問題和自主創新的能力。在工程專業認證的大背景下，《數據結構》作為信息專業的主干課程，其課程目標必然與社會需求相適應，與培養具有創新思維的高水平IT 工程師的需求相一致。所以，該課程不僅在于讓學生熟練掌握專業理論知識，更重要的是培養學生軟件設計能力和創新思維，為其后續完成的畢業設計和走向工作崗位服務國家科技行業奠定良好的基礎。

2 逆向實踐教學設計案例

逆向設計的課程教學，不僅打通了實踐環節與理論課堂教學環節的關系，更加關注學生的應用素質能力的培養[3]。因為篇幅有限，現以最短路徑為例介紹實踐課程的逆向設計過程。

2.1 問題提出：幫“美團騎手”找最快路線

當我們在美團網上點了一份外賣，美團的快遞師傅接到訂單之后，就會借助百度地圖等工具找到最快的線路，爭取最快的速度送達到客戶手中，那百度地圖是怎樣找到最短路線的呢？

2.2 實驗數據

選取濟南市山東大學周邊區域地圖，如圖1 所示。以千佛山風景區為快遞出發點，以山東大學、濟南大學、濟南技師學院、濟南護理職業學院和濟南城市建設職業學院為運送目的地。

圖1 濟南市部分地圖

2.3 數學模型

將圖中地點看做圖的頂點，把兩個地點的道路看做圖中的弧，把道路的長度看做弧上的權值，就為這個問題建立了一個數據模型——有向圖，如圖2 所示。美團騎手找最短路線問題就轉換為在這個有向圖中從源點S 到其余各目標點的單源點最短路徑問題。

圖2 有向圖

2.4 算法設計及關鍵問題

求單源點最短路徑問題采用著名的Dijkstra 算法[4-5]，算法思想為：

（1）初始化：將源點v0加到S 集合中；將v0到各個終點的最短路徑長度初始化為權值，即D[i]=G.arcs[v0][vi]；如果v0和頂點vi有弧，則將vi的前驅置為v0。在這一步中需要解決三個關鍵問題。

關鍵問題1：如何來表示S 集合？可以采用一維數組S[]，若置為true，表示該頂點屬于S 集合，false 屬于V-S 集合。

關鍵問題2：如何存放最短路徑的長度？可以采用一維數組dist[]來保存。其初值為：如果源點v0到vi有弧，則D[i]為弧上的權值，否則為∞。

關鍵問題3：如何存放最短路徑？可以采用一維數組path[]來保存前驅頂點。其初值為：如果源點v0到vi有弧，則path[i]為v0，否則為-1。

有向圖圖2 的輔助數組初始化情況，如表1 所示。

表1 輔助數組初始化

（2）在D[]中選擇最短路徑的終點vk，使得D[k]=Min{D[i]|vi∈V-S}。

（3）將vk加入到S 中，并置S[vk]=true。

（4）更新從v0出發到集合V-S 上任一頂點的最短路徑的長度，同時更改vi的前驅為vk。

若S[i]=false 且D[k]+G.arcs[k][i]

（5）重復（2）～（4）n-1 次，即可按照路徑長度的遞增順序，逐個求得從v0到其余各頂點的最短路徑。

有向圖圖2 在求解過程中各參量的變化如表2所示。

表2 求解過程中各參量的變化

2.5 Dijkstra算法的實現

程序分為三個模塊：一是輸入模塊，二是處理模塊，三是輸出模塊。下面給出Dijkstra 算法的實現部分。

2.6 實驗的實際應用和延伸

（1）一方面在物流運輸中的應用，隨著網絡購物的普及，物流逐漸興起，如何選擇距離最短或者時間最短的路徑成了物流關注的主要問題。因此，最短路徑算法的應用與改進是物流企業經濟效益來源的主要因素之一。另一方面在日常出行中的應用，在我們日常出行中已經習慣應用百度地圖或者汽車GPS 為我們選擇一條最優路線，而最優路線的選擇就是采用的最短路徑算法。另外，在房地產選址、城市公交系統、城市資源配置都有最短路徑算法的應用。

（2）Dijkstra 算法是求靜態的單源點到各個頂點的最短路徑。而在一些對抗游戲如敵人或障礙物不斷移動的情況下，動態路徑的最短路徑是隨著外界環境不斷發生變化的，此時應采用的D*算法，美國火星探測器采用的核心尋路算法就是采用的D*算法。

3 實踐內容設計

為了提高學生的學習興趣增強社會實踐能力，設計了坡度型進階實驗。結合工程認證要求構建7 個知識點的實踐教學案例。主要分為基礎型實驗和設計型實驗。基礎型實驗主要包括基本數據結構以及基本算法的實現，屬于驗證性實驗，是學生必做實驗。設計型實驗是在基礎掌握之后，教師為了延伸實踐內容，增加學習興趣，讓學生自行完成一個獨立的實際問題的實驗。設計型實驗難度較大，學生可以選擇性進行分組設計。這種從易到難的實驗設計，不僅鞏固了基礎知識，更讓學生看到了理論知識的實際應用，培養了他們獨立分析問題解決問題的能力和嚴謹的工作作風，為將來走向IT 工作崗位奠定良好的基礎。

為了更好地實施實驗教學，我們編寫了數據結構實驗大綱、實驗教材，定制了實驗報告格式，充分利用浙江大學PTA 平臺。以社會實際問題和培養目標為導向，從數據的邏輯結構設計、物理結構設計到算法的分析與實現，全面提升學生解決實際問題的能力。實驗設計內容如表3 所示。

表3 坡度型實驗表

4 教學效果分析

以計算機科學與技術專業17-1 班和18-1 班為分析數據，17 級為實驗教學改進前的班級，18 級為改進后的班級。他們的卷面成績和實驗成績分析如圖3、圖4 所示。從圖中可以看出，卷面成績和實驗成績80 分以上均由42%提高到57%，成績大幅度提高。從實驗課堂來看，低頭族越來越少，學生提問發言的次數增多，課堂比較活躍，學生學習興趣度大大提高。

圖3 卷面成績分析

圖4 實驗成績分析

5 結語

在工程教育專業認證的大背景下，如何設計教學環節以適應社會發展的需要是每個教師必須要考慮的重要問題。本文以社會需求和培養目標為導向，逆向設計了數據結構實驗課程的教學環節，給出了完整的實踐教學案例，取得良好的實踐效果，當然也存在很多不足之處，例如案例的選擇是否典型、欠缺課程的監管機制等，在以后的教學過程中將進一步加以完善，使得教學成效螺旋上升。