基于工程認(rèn)證的數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)研究

1、基于工程認(rèn)證的數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)研究基于工程認(rèn)證的數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)研究打開文本圖片集摘 要：數(shù)據(jù)結(jié)構(gòu)與算法課程作為計(jì)算機(jī)與信息類專業(yè)的基礎(chǔ)課程，傳統(tǒng)教學(xué)過程中存在重視理論教學(xué)，忽視實(shí)踐教學(xué)的問題。為適應(yīng)工程認(rèn)證要求，對(duì)數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)踐教學(xué)環(huán)節(jié)進(jìn)行研究與改革。將原有以理論教學(xué)為主的教學(xué)方式，轉(zhuǎn)換為以理論教學(xué)為基礎(chǔ)、實(shí)踐教學(xué)為核心的教學(xué)體系，從而鍛煉和培養(yǎng)學(xué)生的工程實(shí)踐能力。圍繞實(shí)踐教學(xué)環(huán)節(jié)，以蘭州交通大學(xué)服務(wù)大交通行業(yè)的特色為切入點(diǎn)，結(jié)合數(shù)據(jù)結(jié)構(gòu)與算法課程特點(diǎn)，構(gòu)建 68 個(gè)科學(xué)可行的實(shí)踐教學(xué)案例，填補(bǔ)現(xiàn)階段數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)踐教學(xué)環(huán)節(jié)無標(biāo)準(zhǔn)化、科學(xué)化、系統(tǒng)化教學(xué)案例的空白。關(guān)

2、鍵詞：課程教學(xué);工程教育;實(shí)踐教學(xué);教學(xué)案例doi：10. 11907/rjdk. 181674中圖分類號(hào)：g434 文獻(xiàn)標(biāo)識(shí)碼：a 文章編號(hào)：1672-7800（2019）001-0201-04abstract： the course of data structure and algorithm is a basic coursefor computer and information majors. there is the problem of focusing ontheory teaching and neglecting practice teaching in traditio

3、nal teachingprocess. in order to meet the requirements of engineering certification， thepractice and teaching part of this course are studied and reformed. theoriginal teaching method， which is based on theory teaching， is convertedinto a teaching system based on theoretical teaching as a？foundation

4、？andpractice teaching as the core to train and temperi students engineeringpractical ability. in practical teaching， we take the characteristics oflanzhou jiaotong universitys major transportation trade as the breakthroughpoint combined with the characteristics of data structure and algorithm course

5、to construct 6 to 8 scientific and feasible practice teaching cases which fillthe blank of standardized， scientific and systematized teaching cases for thepractice teaching part.key words： curriculum instruction; engineering certification; practiceteaching; teaching cases0 引言工程教育專業(yè)認(rèn)證作為工程師資格國(guó)際互認(rèn)的標(biāo)準(zhǔn)，以

6、由美、英等 6 國(guó)在 1989 年發(fā)起并簽署的華盛頓協(xié)議1為基礎(chǔ)。以 2006 年中華人民共和國(guó)教育部發(fā)布的關(guān)于成立教育部工程教育認(rèn)證專家委員會(huì)的通知為起點(diǎn)，我國(guó)開展工程教育認(rèn)證2工作已有十余年時(shí)間。2013 年我國(guó)成為華盛頓協(xié)議預(yù)備成員國(guó)。2016 年 6 月，我國(guó)正式加入華盛頓協(xié)議3，成為該協(xié)議第十八個(gè)正式成員國(guó)，標(biāo)志著我國(guó)工程教育專業(yè)認(rèn)證工作獲得了里程碑式的突破。由于工程教學(xué)認(rèn)證在國(guó)際人才市場(chǎng)上具有很高的含金量，并且為工科院校學(xué)生培養(yǎng)提供了依據(jù)，目前我國(guó)多數(shù)工科院校都在積極開展工程專業(yè)認(rèn)證工作。數(shù)據(jù)結(jié)構(gòu)與算法課程4-6是程序設(shè)計(jì)的基礎(chǔ)，在計(jì)算機(jī)、軟件工程、物聯(lián)網(wǎng)等專業(yè)的學(xué)習(xí)中占有重要地位

7、。完成程序設(shè)計(jì)不僅需要掌握編程語言 （如 c 語言7、c+8、c#9、java10等），還需了解數(shù)據(jù)間的組織關(guān)系、數(shù)據(jù)物理結(jié)構(gòu)等。通過對(duì)數(shù)據(jù)結(jié)構(gòu)與算法課程的學(xué)習(xí)，可以培養(yǎng)學(xué)生利用計(jì)算機(jī)處理數(shù)據(jù)的能力。此外，數(shù)據(jù)結(jié)構(gòu)與算法課程作為后續(xù)編譯原理11、操作系統(tǒng)12、數(shù)據(jù)庫系統(tǒng)13等課程的前修課程，對(duì)知識(shí)的貫穿起到承前啟后的作用。為了適應(yīng)工程教育認(rèn)證的要求，蘭州交通大學(xué)對(duì)該課程教學(xué)環(huán)節(jié)進(jìn)行改革。數(shù)據(jù)結(jié)構(gòu)與算法課程常被作為報(bào)考計(jì)算機(jī)相關(guān)專業(yè)碩士研究生或者博士研究生的初試專業(yè)課程14。為了契合應(yīng)試教育需要，傳統(tǒng)教學(xué)過程中存在重視理論環(huán)節(jié)、忽視實(shí)踐環(huán)節(jié)的問題，然而課程相關(guān)知識(shí)被廣泛應(yīng)用于不同的研究和實(shí)踐領(lǐng)域

8、，如無線傳感器網(wǎng)絡(luò)15-18、入侵檢測(cè)19-20等，因此課程改革存在必要性和緊迫性。在當(dāng)前工程教育專業(yè)認(rèn)證體系背景下，工程教育通用認(rèn)證標(biāo)準(zhǔn)要求計(jì)算機(jī)專業(yè)學(xué)生能夠運(yùn)用所學(xué)專業(yè)知識(shí)建立抽象模型以解決復(fù)雜工程問題，并持續(xù)改進(jìn)、優(yōu)化解決方案。為更好地滿足工程教育、課程體系與學(xué)生畢業(yè)要求，本文對(duì)本課程改革進(jìn)行探索，首先以堅(jiān)實(shí)理論為基礎(chǔ)，充分發(fā)掘本課程涉及的 4 方面基本內(nèi)容：純集合數(shù)據(jù)結(jié)構(gòu)、線性數(shù)據(jù)結(jié)構(gòu)、樹形數(shù)據(jù)結(jié)構(gòu)、圖形（網(wǎng)狀）數(shù)據(jù)結(jié)構(gòu)。結(jié)合工程認(rèn)證要求構(gòu)建 68 個(gè)實(shí)踐教學(xué)案例，應(yīng)用于實(shí)踐教學(xué)以達(dá)到鍛煉學(xué)生工程實(shí)踐能力的目的，從而培養(yǎng)學(xué)生在實(shí)踐過程中解決復(fù)雜工程問題的能力，最終為工業(yè)界培養(yǎng)出符合工程

9、認(rèn)證要求的合格人才。1 課程與工程認(rèn)證標(biāo)準(zhǔn)的差距由工程教育認(rèn)證通用標(biāo)準(zhǔn)和補(bǔ)充標(biāo)準(zhǔn)可知，工程教育認(rèn)證以社會(huì)需求為導(dǎo)向，以學(xué)生為核心，其實(shí)質(zhì)是以社會(huì)需求為基礎(chǔ)，倒推畢業(yè)要求，以達(dá)到培養(yǎng)合格工程人才的目標(biāo)。通用標(biāo)準(zhǔn)各部分之間的關(guān)系如圖 1 所示。然而，目前我國(guó)高校本科教學(xué)往往以應(yīng)試教育為導(dǎo)向，以專業(yè)骨干教師為核心開展教學(xué)工作，與工程教育以社會(huì)需求為導(dǎo)向、以學(xué)生為核心的理念相背離，導(dǎo)致工程人才培養(yǎng)與社會(huì)需求脫節(jié)。對(duì)于數(shù)據(jù)結(jié)構(gòu)與算法課程而言，傳統(tǒng)上按照線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)為順序主線，逐章進(jìn)行理論知識(shí)講解，雖然滿足了應(yīng)試教育的要求，取得了一定效果，但與工程教育專業(yè)認(rèn)證導(dǎo)向和核心要求還存在一定差距。

10、其主要問題表現(xiàn)在：教學(xué)方法方面，以理論教學(xué)為重點(diǎn)，忽視實(shí)踐教學(xué)環(huán)節(jié)，甚至缺失實(shí)踐教學(xué)環(huán)節(jié)，從而嚴(yán)重限制了學(xué)生工程實(shí)踐能力的培養(yǎng)，以至于學(xué)生在畢業(yè)時(shí)很難達(dá)到工程教育認(rèn)證要求的畢業(yè)條件，不能滿足社會(huì)需求;考核評(píng)價(jià)方面，以期末考試分?jǐn)?shù)為主，平時(shí)表現(xiàn)為輔，雖然能在一定程度上衡量學(xué)生對(duì)知識(shí)的掌握程度，但是該考核評(píng)價(jià)體系存在局限性，不能有效評(píng)價(jià)學(xué)生實(shí)際工程應(yīng)用能力，從而無法滿足社會(huì)對(duì)工程人才的實(shí)際需求。2 基于工程認(rèn)證的數(shù)據(jù)結(jié)構(gòu)與算法課程改革針對(duì)目前數(shù)據(jù)結(jié)構(gòu)與算法課程存在的問題，本文提出以實(shí)踐教學(xué)案例為支撐，滿足社會(huì)需求為導(dǎo)向，基于反向課程設(shè)計(jì)為基本原理，面向社會(huì)需求為起點(diǎn)，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)踐教學(xué)

11、案例，完善課程體系，支撐學(xué)生畢業(yè)指標(biāo)點(diǎn)。畢業(yè)指標(biāo)點(diǎn)主要包括：針對(duì)計(jì)算機(jī)專業(yè)中存在的復(fù)雜工程問題，進(jìn)行抽象分析，建立或選擇合適的數(shù)學(xué)模型;運(yùn)用計(jì)算機(jī)技術(shù)相關(guān)理論對(duì)復(fù)雜工程問題的解決方案進(jìn)行研究分析并改進(jìn);能夠運(yùn)用專業(yè)理論和知識(shí)正確分析、評(píng)價(jià)工程中存在的復(fù)雜工程問題，提出相應(yīng)的預(yù)防措施或解決方案，并制定合理課程評(píng)價(jià)體系。由于篇幅限制，本文僅列出具有代表性的實(shí)踐教學(xué)案例：課程計(jì)劃輔助制定實(shí)踐教學(xué)案例和汽車牌照快速查找實(shí)踐教學(xué)案例，并介紹課程評(píng)價(jià)體系。2.1 課程計(jì)劃輔助制定實(shí)踐教學(xué)案例2.1.1 問題描述每學(xué)期一個(gè)學(xué)生允許同時(shí)學(xué)習(xí)多門課程，同一學(xué)期各課程之間不存在次序關(guān)系，使用拓?fù)渑判蛑R(shí)制定課程計(jì)

12、劃使學(xué)生可在最短時(shí)間內(nèi)完成所有課程。2.1.2 實(shí)驗(yàn)數(shù)據(jù)（待完成的全部課程）課程包括計(jì)算機(jī)導(dǎo)論、線性代數(shù)、離散數(shù)學(xué)、passcal 語言、匯編語言、c 語言、數(shù)據(jù)庫、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理及微機(jī)原理。此外，課程之間的先后關(guān)系可描述為如圖 2 所示的活動(dòng)頂點(diǎn)網(wǎng)絡(luò)（aov 網(wǎng)絡(luò)）。2.1.3 案例構(gòu)建核心思想課程計(jì)劃制定是將 aov 網(wǎng)絡(luò)中的頂點(diǎn)集合劃分成互不相交的頂點(diǎn)子集s1，s2，sn，并且獲得的子集數(shù)量最少。對(duì)于任意通過弧相連的頂點(diǎn)應(yīng)該屬于不同的頂點(diǎn)子集。此外，假如代表一條從頂點(diǎn) i 到頂點(diǎn) j 的有向弧，isk，jsl，則存在 kl。每個(gè)頂點(diǎn)子集代表同一學(xué)期開設(shè)的課程?；谏鲜鲇懻?，

13、該實(shí)踐教學(xué)案例可以歸結(jié)為對(duì)拓?fù)渑判蛑R(shí)改進(jìn)，利用拓?fù)渑判蛩枷雽?duì)頂點(diǎn)集合進(jìn)行劃分，將其劃分為不同的子集，實(shí)現(xiàn)步驟如下：step 1：在 aov 網(wǎng)絡(luò)中尋找當(dāng)前全部入度為 0 的頂點(diǎn)，構(gòu)成一個(gè)新的頂點(diǎn)子集 s;step 2： 刪除 aov 網(wǎng)絡(luò)中子集 s 中全部頂點(diǎn)以及從這些頂點(diǎn)出發(fā)的弧。重復(fù)上述兩步，直到 aov 網(wǎng)絡(luò)為空。具體實(shí)現(xiàn)采用棧進(jìn)行處理。當(dāng)前棧為存儲(chǔ)當(dāng)前入度為 0 的頂點(diǎn)，備用棧為存儲(chǔ)新生成入度為 0 的頂點(diǎn)。通過兩個(gè)棧間相互交替，最終完成課程計(jì)劃的制定。2.1.4 程序設(shè)計(jì)過程輸入課程名稱作為頂點(diǎn)，以及頂點(diǎn)之間先后關(guān)系，建立有向圖 g;對(duì)有向圖 g 集合劃分，輸出各學(xué)期課程計(jì)劃。（2

14、） 棧程序模塊：設(shè)計(jì)棧的抽象數(shù)據(jù)類型。（3） 有向圖 g 模塊：構(gòu)建有向圖，實(shí)現(xiàn)拓?fù)浼蟿澐帧＃?） 程序的偽代碼實(shí)現(xiàn)：2.1.5 課程計(jì)劃輔助制定結(jié)果課程計(jì)劃輔助制定結(jié)果如圖 3 所示。從圖 3 可以看出所獲得的 4 個(gè)課程子集，即某位學(xué)生 4 個(gè)學(xué)期課程計(jì)劃安排。s1=計(jì)算機(jī)導(dǎo)論、線性代數(shù)，s2=passcal 語言，微機(jī)原理、離散數(shù)學(xué)，s3=數(shù)據(jù)結(jié)構(gòu)、c 語言、匯編語言，s4=操作系統(tǒng)、編譯原理、數(shù)據(jù)庫。2.2 汽車牌照快速查找實(shí)踐教學(xué)案例2.2.1 問題描述對(duì)一批汽車牌照進(jìn)行排序查找，利用基數(shù)排序和二分查找的思想完成程序設(shè)計(jì)任務(wù)。2.2.2 實(shí)驗(yàn)（測(cè)試）數(shù)據(jù)人工錄入，或者自動(dòng)隨機(jī)生成一批以車牌號(hào)為關(guān)鍵的記錄集合。2.2.3 需求分析（1） 利用基數(shù)排序的思想對(duì)一批具有結(jié)構(gòu)特征的汽車牌照進(jìn)行排序，并且利用二分查找的思想對(duì)排好序的汽車牌照記錄實(shí)現(xiàn)查找。（2） 測(cè)試數(shù)據(jù)的每個(gè)記錄包括 5 項(xiàng)，分別為牌照號(hào)碼、汽車商標(biāo)、顏色、注冊(cè)日期和車主的姓名，其中牌照號(hào)碼一項(xiàng)的輸入形式如圖 4 所示。其中 k0 和 k1 輸入值為 0131（代表地區(qū)），k2 輸入值為 az（代表車的使用