《數據結構》課程標準

《數據結構》課程標準課程名稱：數據結構課程代碼：3250619適用專業(yè)：軟件技術專業(yè)（軟件開發(fā)方向）課程性質：專業(yè)必修課學時：48學時（理論：24實踐：24）學分：3學分一、課程概述（一）課程的地位和作用《數據結構》是軟件技術專業(yè)（軟件開發(fā)方向）的一門專業(yè)必修課。課程的前導課程是《Java面向對象編程》，本課程在后續(xù)軟件開發(fā)類課程中起著非常重要的作用，其知識的應用將貫穿于本專業(yè)的所有課程。在程序設計中，一個好的程序無非是選擇一個合適的數據結構和好的算法，而好的算法的選擇很大程度上取決于描述實際問題的數據結構的選取。所以，學好數據結構，將是進一步提高學生程序設計水平的關鍵之一。數據結構的應用水平是區(qū)分軟件開發(fā)、設計人員水平高低的重要標志之一，缺乏數據結構和算法的深厚功底，很難設計出高水平的具有專業(yè)水準的應用程序。本課程的改革理念是，堅持工程化、實用化教學，密切適應計算機技術的發(fā)展趨勢，堅持學以致用；解決抽象理論與實踐相脫節(jié)現(xiàn)象，讓絕大多數學生在有限的時間內迅速掌握課程的基本理論知識，并把理論知識應用到軟件開發(fā)的實際工作中，開發(fā)出高質是的應用軟件。（二）課程設計思路課程資源建設遵循三個原則、一個過程、四個應用層次。課程內容的選取遵循科學性原則，課程內容的選取依據數據結構課程在學科體系的理論體系，結合其在實際開發(fā)中的使用頻度及難易程度，選取適合高職學生的學習內容；課程內容的組織遵循情境性原則，所有模塊的內容按一個過程進行組織。課程內容置于由實踐情境建構的以軟件開發(fā)過程主要邏輯為主線的行動體系之中，采用打碎、集成的思想，將學科體系中所涉及的概念、方法、原理打碎，然后按照軟件開發(fā)過程邏輯重新集成。課程資源的建設充分體現(xiàn)人本性原則，按人類掌握知識的基本規(guī)律“獲取—>內化—>實踐—>反思—>新的獲取”，開發(fā)四個實踐層次“驗證性應用、訓練性應用、設計性應用、創(chuàng)造性應用”的訓練題庫。二、培養(yǎng)目標（一）總體目標《數據結構》課程以培養(yǎng)學生的數據抽像能力和復雜程序設計的能力為總目標。通過本課程的學習，學生可以學會分析研究計算機加工數據結構的特性，以便為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的運算，并初步掌握算法的時間分析和空間分析技術；另一方面，本課程的學習過程也是工程化能力培養(yǎng)的過程，要求學生按軟件開發(fā)過程分析問題，設計算法，并編寫結構清楚、正確易讀，符合軟件工程規(guī)范的程序。（二）具體目標①知識目標從數據結構的類定義和對象的使用，以及存儲表示和操作的實現(xiàn)兩個層次，系統(tǒng)地學習和掌握常用的基本數據結構（包括數組、順序表、多項式、字符串、鏈表、棧與隊列、廣義表、樹與森林、二叉樹、圖、搜索結構、索引結構、散列結構等）及其不同的實現(xiàn)，了解并掌握分析、比較和選擇不同數據結構、不同存儲結構、不同算法的原則和方法，為后續(xù)課程的學習打好基礎。②能力目標具軟件開發(fā)常規(guī)設計方法和技巧，養(yǎng)成良好的程序設計風格。具備用面向對象的思想進行數據結構和算法設計的能力。基本具備選擇合適的數據結構和方法進行問題求解，開發(fā)高質量軟件的能力。③素質目標按時、按質的軟件交付觀念。思維清晰、過程嚴謹、耐心細致編程習慣。自主、開放的學習能力。良好的自我表現(xiàn)、與人溝通能力。三、教學內容（1）課程內容選擇依據針對每種常用的數據結構，以項目為載體，以軟件開發(fā)過程為主線，按照問題提出→需求分析（分析邏輯結構和算法）→軟件設計（設計存儲結構和算法）→代碼實現(xiàn)（用C#實現(xiàn)數據結構和算法）→代碼測試這樣一個過程組織教學內容。（2）課程內容的標準本課程的知識與技能要求分為知道、理解、掌握、學會四個層次。這四個層次的一般涵義表述如下：熟悉——是指知道基本理論、基本概念和基本方法。理解——是指在熟悉本課程涉及到的主要結構類型和算法的基礎上進一步明白其因果關系。掌握——是指運用已理解的概念和算法解決實際問題的一般方法。學會——是指能模仿或在教師指導下獨立地完成較復雜程序設計。教學內容和要求表中的“√”號表示教學知識和技能的教學要求層次。注：其中知道和理解為知識要求的水平，掌握和學會是在理解知識的基礎上達到的技能水平。任務學習任務教學內容教學要求建議學時熟悉理解掌握學會任務一了解數據結構1.數據結構的基本概念和術語2.抽象數據類型的表示與實現(xiàn)3.算法和算法分析⑴算法⑵算法設計的要求⑶算法效率的度量⑷算法存儲空間的度量√√√√√√2任務二解決線性表的編程問題1.組件圖的定義、構成及其關系2.線性表的順序存儲和實現(xiàn)3.線性表的鏈式存儲和實現(xiàn)⑴線性鏈表⑵循環(huán)鏈表⑶雙向鏈表4.一元多項式的表示及相加√√√√√√6任務三解決堆棧的編程問題1堆棧的類型定義2.堆棧的表示和實現(xiàn)⑴順序棧⑵鏈棧3.棧與遞歸的實現(xiàn)√√√√4任務四解決隊列編程問題1.隊列的類型定義2.隊列的表示和實現(xiàn)⑴順序隊列⑵循環(huán)隊列⑶鏈隊列√√√√4任務五解決串的編程問題1.串的類型定義2.串的表示和實現(xiàn)3.串的模式匹配算法√√√4任務六解決樹的編程問題1.樹的定義和基本術語2.二叉樹的定義、性質3.二叉樹的表示和實現(xiàn)4.遍歷二叉樹和線索二叉樹⑴遍歷二叉樹⑵線索二叉樹5.樹和森林⑴樹的表示和實現(xiàn)⑵森林與二叉樹的轉換⑶樹和森林的遍歷6.哈夫曼樹及其應用⑴最優(yōu)二叉樹（哈夫曼樹）⑵哈夫曼編碼√√√√√√√√√√√8任務七解決圖的編程問題1.圖的定義和術語2.圖的存儲結構⑴數組表示法⑵鄰接表⑶十字鏈表3.圖的遍歷⑴深度優(yōu)先搜索⑵廣度優(yōu)先搜索√√√√√√6任務八實現(xiàn)排序算法1.排序的概念及分類2.插入排序⑴直接插入排序⑵希爾排序3.選擇排序⑴簡單選擇排序⑵堆排序4.交換排序⑴冒泡排序⑵快速排序5.歸并排序6.基數排序√√√√√√√√√4任務九執(zhí)行查詢算法1.查找的基本概念2.靜態(tài)查找表⑴順序表的查找⑵有序表的查找⑶靜態(tài)樹的查找⑷索引順序表的查找3.動態(tài)查找表⑴二叉排序樹和平衡二叉樹⑵B_樹和B+樹4.哈希表⑴哈希表的概念⑵哈希函數的構造方法⑶處理沖突的方法⑷哈希表的查找及其分析√√√√√√√√√√√4十綜合實訓全面掌握數據結構的知識點6合計48四、課程實施建議（一）教材的選用及編寫建議①本課程實踐性較強，為了實現(xiàn)教、學、做一體化的教學目標，在講義或教材的編寫上要首先突出項目實施的方法和步驟，按照軟件開發(fā)過程基本流程組織教材內容。②必要的基本概念貫穿在教師和學生共同分析程序功能的過程中，內容循序漸進，程序從簡單到復雜，學生從實踐到理論，再到實踐不斷循環(huán)，使學生對技術的應用能力不斷提升。③有關專業(yè)本身發(fā)展的歷史、本課程知識的延伸以及在完成項目過程中對其它課程知識和技術的應用，作為輔助閱讀內容體現(xiàn)在教材中。④提供可查閱的資料，并且指明出處，體現(xiàn)教學載體的實際應用。⑤預測學生完成實做的過程中容易出現(xiàn)的錯誤，在講義或教材中必須予以特別強調，說明區(qū)別并介紹避免錯誤的方法。（二）教學參考資料推薦建議①充分利用軟件技術實訓室的實訓設備，結合實際應用中的具體程序，設計開發(fā)教學項目，以安裝vs2010開發(fā)環(huán)境的計算機為主要教學載體，配置投影儀、大屏幕以及相應的屏蔽廣播軟件，作為教學實施的主要場景。②結合本課程的教學目標，借鑒和使用國家級精品課程的有關課件、錄像等網上教學資源。③使用ACM自動評判系統(tǒng)，實時檢驗學生實踐效果。ACM程序設計大賽的很多題目都涉及到數據結構的知識，為了激發(fā)學生的編程興趣，為學生提供了很多歷界ACM大賽的有趣的題目，鼓勵學生用C#語言實現(xiàn)，激發(fā)學生的學習興趣。（三）主要教學方法建議①主要采用“工學結合，項目載體、任務驅動”的教學模式。②通過與企業(yè)深度合作引入企業(yè)真實項目，課程教師對企業(yè)項目進行轉換與提煉，設計開發(fā)教學項目為載體。③以基于工作過程的典型工作任務為主線，解構和重構課程知識結構。④通過對具體項目的任務分析，引入課程知識，以任務驅動的方式推動課程進程。⑤教學過程中充分利用MCLA教學法、WORKSHOP教學法、ISAS教學法、情景教學法和案例教學法等多種教學方法，激發(fā)學生的學習興趣，引導學生自覺自主學習、引導學生獨立思考、提升學生分析問題和解決問題的能力。⑥利用大學城等開放的自由的網絡教學環(huán)境，開發(fā)更多網絡多媒體教學資源，為學生的學習提供更多的幫助。五、考核評價標準①考核評價方法本課程的學習，按照理論和實踐標準進行評價，學習效果需要從知識點、能力點和素質點來評價，主要分為理論考核、項目實踐動手能力和平時表現(xiàn)三個方面考核。②考核評價標準平時成績（50%）+基本理論（30%）+項目考核（20%）課程的采用多種形式相結合的考核方式。整個課程考核由平時成績、理論考核、項目考核三部分組成。各占50%、30%、20%。平時成績中，空間課業(yè)占30%，空間課業(yè)以完成項目任務為主，對形成性證據進行監(jiān)控，教師應制定課業(yè)的評價標準，指導學生有目的性的為任務成果積累評價的證據。根據課程特點，采用了老師、學生、自動評判系統(tǒng)評價相結合的評價方式，并有明確合理的比例分配。其中教師評價占65%，學生自評和互評占20%，自動評判系統(tǒng)占15%。各種評價主體合理分配評分比例，保證考核的公正合理，全面有效的考核學生的綜合素質。序號考核內容考核方式考核主體權重1平時成績考核平時出勤教師10%課堂表現(xiàn)教師5%互評5%空間課業(yè)教師15%互評15%小計50%基本理論筆試期終考試教師30%小計30%2實踐部分考核項目實踐項目上機實踐自動評判系統(tǒng)15%解題報告教師5%小計40%總計100%其中項目考核（卷面分數100分，占期評的20％），出4道實際