數(shù)據(jù)結(jié)構(gòu)與算法課程標(biāo)準(zhǔn)

1、數(shù)據(jù)結(jié)構(gòu)與算法課程標(biāo)準(zhǔn)主編： 張揚 主審： 梁平 職業(yè)教育及專業(yè)拓展平臺: 職業(yè)技術(shù)課 課程編碼: 1102203 是否專業(yè)核心課程: 是 總學(xué)時: 64 適用專業(yè): 計算機應(yīng)用技術(shù) 實踐比例(%): 15.6% 課程類型:（理論+實踐）課 學(xué)分: 4 精品課程: 有 考核方式: 考試 開設(shè)學(xué)期: 第二學(xué)期 制(修)訂日期: 2010年6月 一、課程描述隨著計算機軟件和硬件的發(fā)展，計算機的應(yīng)用已經(jīng)深入到社會的各個領(lǐng)域，各行各業(yè)都需要對大量的非數(shù)值數(shù)據(jù)進(jìn)行存儲、加工和管理。如何根據(jù)實際應(yīng)用研究的要求，對這些大量的表面上雜亂無章的數(shù)據(jù)進(jìn)行有效地組織、存儲和處理，編制出相應(yīng)的高效算法，這就是數(shù)據(jù)結(jié)構(gòu)

2、與算法這門課程所要研究并加以解決的問題。數(shù)據(jù)結(jié)構(gòu)與算法是計算機科學(xué)中一門綜合性的專業(yè)技術(shù)基礎(chǔ)課，也是計算機科學(xué)技術(shù)應(yīng)用專業(yè)的必修課程，為計算機專業(yè)技術(shù)人員提供必要的專業(yè)基礎(chǔ)知識和技能訓(xùn)練，同時也是計算機應(yīng)用相關(guān)學(xué)科所必須掌握的課程。通過本課程的學(xué)習(xí)，使學(xué)生熟練掌握計算機程序設(shè)計中常見的各種數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的運算，初步掌握算法的時間分析和空間分析的技術(shù)，并能根據(jù)計算機加工的數(shù)據(jù)特性運用數(shù)據(jù)結(jié)構(gòu)的知識和技巧設(shè)計出更好的算法和程序，并進(jìn)一步培養(yǎng)基本的良好的程序設(shè)計能力。數(shù)據(jù)結(jié)構(gòu)與算法課程適用于三年制計算機應(yīng)用技術(shù)專業(yè)，在第二學(xué)期開設(shè)。二、課程培養(yǎng)目標(biāo)本課程以培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和復(fù)雜

3、程序設(shè)計的能力為總目標(biāo)。通過本課程的學(xué)習(xí)，學(xué)生可以學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的運算，并初步掌握算法的時間分析和空間分析的技術(shù)；另一方面，本課程的學(xué)習(xí)過程也是復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范。1專業(yè)能力目標(biāo)（1）掌握各種主要數(shù)據(jù)結(jié)構(gòu)的特點、計算機內(nèi)的表示方法，以及處理數(shù)據(jù)的算法實現(xiàn)。（2）使學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時間分析和空間分析技術(shù)。（3）通過對本課程算法設(shè)計和上機實踐的訓(xùn)練，

4、培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和復(fù)雜程序設(shè)計的能力。2方法能力目標(biāo)（1）有初步的算法分析和設(shè)計能力。（2）能夠有效地獲取、利用、傳遞信息。（3）通過獨立學(xué)習(xí)，不斷獲取新的知識和技能，能夠在工作中尋求發(fā)現(xiàn)問題、解決問題的途徑。3社會能力目標(biāo)（1）培養(yǎng)學(xué)生“愛崗、敬業(yè)、細(xì)致、求精”的職業(yè)道德與情感。（2）培養(yǎng)學(xué)生良好的動手實踐習(xí)慣，尤其注重挖掘?qū)W生的潛質(zhì)。（3）注重培養(yǎng)學(xué)生與社會接軌。（4）培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)男惺嘛L(fēng)格。三、與前后課程的聯(lián)系數(shù)據(jù)結(jié)構(gòu)與算法課程為計算機應(yīng)用技術(shù)專業(yè)的基礎(chǔ)課，前修課程為計算機應(yīng)用基礎(chǔ)、高級語言程序設(shè)計，后續(xù)課程為：C+程序設(shè)計、C#程序設(shè)計等。 四、學(xué)習(xí)內(nèi)容與學(xué)時分配本課程標(biāo)準(zhǔn)從計算

5、機軟件技術(shù)及應(yīng)用技術(shù)專業(yè)的視角出發(fā)，以滿足本專業(yè)就業(yè)崗位所必須具備的計算機軟件技術(shù)基礎(chǔ)知識為基礎(chǔ)，教學(xué)內(nèi)容設(shè)計通過崗位工作目標(biāo)與任務(wù)分析，分解完成工作任務(wù)所必備的知識和能力，采用并列和流程相結(jié)合的教學(xué)結(jié)構(gòu)，構(gòu)建教學(xué)內(nèi)容的任務(wù)和達(dá)到工作任務(wù)要求而組建的各項目，以及教學(xué)要求和參考教學(xué)課時數(shù)。通過實踐操作、案例分析，培養(yǎng)學(xué)生的綜合職業(yè)能力，基本達(dá)到程序員級職業(yè)技能鑒定標(biāo)準(zhǔn)。主要內(nèi)容如下：（1）緒論內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，算法的概念、特點。（2）線性表內(nèi)容：線性表的定義及運算，線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)鏈表和雙向鏈表，鏈表的應(yīng)用和算法舉例。（3）棧和隊列內(nèi)容：棧的定義及運算，棧的

6、順序結(jié)構(gòu)與鏈表結(jié)構(gòu)，棧的應(yīng)用，隊列的定義及運算，隊列的順序結(jié)構(gòu)與鏈表結(jié)構(gòu)，棧和隊列的算法實現(xiàn)。（4）字符串與數(shù)組內(nèi)容：串的概念，存儲結(jié)構(gòu)和運算，數(shù)組的基本概念，稀疏矩陣。（5）樹內(nèi)容：樹的基本概念，二叉樹的遍歷，線索二叉樹，森林，樹的應(yīng)用。（6）圖內(nèi)容：圖的基本概念和術(shù)語，圖的存儲結(jié)構(gòu)，圖的遍歷，生成樹的概念，最短路徑，拓?fù)渑判?。?）查找內(nèi)容：靜態(tài)和動態(tài)查找表，哈希表及其查找。（8）排序內(nèi)容：插入排序、交換排序、選擇排序法。學(xué)時分配學(xué)習(xí)單元編號學(xué)習(xí)任務(wù)學(xué)習(xí)要求學(xué)時分配備注一體化學(xué)時實踐比例(%)1緒論掌握數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、物理結(jié)構(gòu)和邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)的概念。2152線性表掌握線性表的

7、定義，向量的基本運算，單鏈表與指針的關(guān)系和基本運算，循環(huán)鏈表與雙向鏈表，多項式相加問題的求解。10153棧和隊列掌握棧和隊列的定義、順序結(jié)構(gòu)與鏈表結(jié)構(gòu)及相應(yīng)的算法8154字符串與數(shù)組掌握串的概念，順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)和基本運算。掌握數(shù)組的概念，稀疏矩陣的存儲。8155樹掌握樹和二叉樹的定義，二叉樹的性質(zhì)、存儲結(jié)構(gòu)、遍歷算法，線索二叉樹的概念與存儲，樹與二叉樹森林的轉(zhuǎn)換，二叉排序樹和哈夫曼樹。12156圖掌握圖的基本概念和術(shù)語，鄰接表，圖的建立與遍歷，最小生成樹的求法，最短路徑的求法。12157查找掌握順序表、有序表、索引順序表的查找，二叉排序樹和二叉平衡樹，哈希函數(shù)與哈希表，解決沖突的方法。81

8、58排序掌握幾種基本的排序方法415總計6415五、考核方式與標(biāo)準(zhǔn)本課程教學(xué)評價采用過程性評價與結(jié)果性評價相結(jié)合完成。注重對學(xué)生動手能力和實踐分析問題、解決問題能力的考核，對學(xué)習(xí)和實踐環(huán)節(jié)上有創(chuàng)新的學(xué)生應(yīng)特別給予鼓勵，綜合評價學(xué)生能力。本課程的過程性評價建議包括學(xué)生平時課堂表現(xiàn)、作業(yè)完成情況、考勤情況、單元測試成績、實訓(xùn)成績等，約占總評成績的40%。 本課程結(jié)果性評價是指期末筆試。筆試全面考核本課程所學(xué)知識與技能，重點考核與實踐能力緊密相關(guān)的知識，并與全國計算機二級考試緊密結(jié)合，約占總評成績的60%。六、教學(xué)與實踐環(huán)境要求教學(xué)環(huán)境：具備多媒體教學(xué)系統(tǒng)，能實現(xiàn)邊講邊練。設(shè)備條件：教師操作演示用機

9、和學(xué)生操作用機須安裝VC+。七、課程實施建議1教材選用建議（1）教材：高職、高專規(guī)劃教材數(shù)據(jù)結(jié)構(gòu)，鄧文華編著，清華大學(xué)出版社（2）教學(xué)參考書：數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏 吳偉民編著，清華大學(xué)出版社，2007.3數(shù)據(jù)結(jié)構(gòu)（C語言版），胡學(xué)鋼主編，高等教育出版社，2008.12教學(xué)建議（1）在教學(xué)過程中應(yīng)結(jié)合現(xiàn)實生活中的具體實際應(yīng)用實例，通過實驗、實訓(xùn)應(yīng)用與理論的結(jié)合以激發(fā)學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的興趣。 （2）教學(xué)可在多媒體教室進(jìn)行，借助于多媒體課件組織教學(xué)。（3）教學(xué)過程中可參考計算機軟件資格考試（初級、中級、高級）或全國計算機等級考試（二級）規(guī)定的有關(guān)程序設(shè)計和數(shù)據(jù)結(jié)構(gòu)的知識要求和技能等級職業(yè)標(biāo)準(zhǔn)

10、。3教師要求（1）擔(dān)任本課程主講教師應(yīng)該熟悉各種算法的思想及軟件開發(fā)流程，具有豐富的軟件開發(fā)經(jīng)驗，熟練掌握VC+，能夠應(yīng)用這些技術(shù)開發(fā)一個完整的應(yīng)用軟件系統(tǒng)，同時，還要求主講教師具備較豐富的教學(xué)經(jīng)驗及課題組織能力。（2）擔(dān)任本課程實踐教學(xué)指導(dǎo)教師應(yīng)具有豐富的軟件企業(yè)開發(fā)工作經(jīng)驗，具有一定的教學(xué)經(jīng)驗并且需要有較強的責(zé)任心。 八、課程資源的利用推薦如下學(xué)習(xí)網(wǎng)站：（1）（2）（3）（4）九、學(xué)習(xí)情境設(shè)計根據(jù)本課程的培養(yǎng)目標(biāo)，以項目開發(fā)活動為載體確定6個學(xué)習(xí)情境，其具體內(nèi)容如下：學(xué)習(xí)情境1： 線性表及其應(yīng)用學(xué)習(xí)情境線性表及其應(yīng)用學(xué)時2能力目標(biāo)Ø 熟悉C語言的上機環(huán)境，進(jìn)一步掌握C語

11、言的結(jié)構(gòu)特點。Ø 掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言實現(xiàn)。 Ø 掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表的定義及C語言實現(xiàn)。Ø 掌握線性表在順序存儲結(jié)構(gòu)即順序表中的各種基本操作。Ø 掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表中的各種基本操作。主要內(nèi)容1 線性表的建立、插入及刪除。2 鏈?zhǔn)骄€性表的建立、插入及刪除。工作任務(wù)1. 建立含n個數(shù)據(jù)元素的順序表并輸出該表中各元素的值及順序表的長度。2. 利用前面的實驗先建立一個順序表L=21，23，14，5，56，17，31，然后在第i個位置插入元素68。3. 建立一個帶頭結(jié)點的單鏈表，結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按

12、尾插入法來建立相應(yīng)單鏈表。實訓(xùn)環(huán)境為每位學(xué)生配置的計算機具備如下的軟件環(huán)境：1. Windows XP/ Windows 2003或以上版本2. vc+6.0環(huán)境教學(xué)資源1. 電子課件2. 任務(wù)樣例教學(xué)方法建議1“教、學(xué)、做”三位一體教學(xué)法。2. 案例分析法。3. 訓(xùn)練學(xué)習(xí)法。教學(xué)組織形式1以班為單位的一體化教學(xué)2個人獨立完成任務(wù)教師能力要求1. 精通vc+6.0的使用。2. 熟悉各種數(shù)據(jù)的類型及算法。3. 具有一定的和好的教學(xué)能力，語言溝通能力?？己朔绞缴蠙C調(diào)試備注學(xué)習(xí)情境2： 棧和隊列學(xué)習(xí)情境棧和隊列學(xué)時2能力目標(biāo)Ø 掌握棧的順序表示和實現(xiàn)。Ø 掌握隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

13、。主要內(nèi)容1. 編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算。2. 實現(xiàn)隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)。工作任務(wù)1 初始化順序棧2 插入元素3 刪除棧頂元素4 遍歷順序棧5 置空順序棧6 初始化并建立鏈隊列7 入鏈隊列8 出鏈隊列實訓(xùn)環(huán)境為每位學(xué)生配置的計算機具備如下的軟件環(huán)境：1. Windows XP/ Windows 2003或以上版本2. vc+6.0環(huán)境教學(xué)資源1. 電子課件2. 任務(wù)樣例教學(xué)方法建議1“教、學(xué)、做”三位一體教學(xué)法。2. 案例分析法。3. 訓(xùn)練學(xué)習(xí)法。教學(xué)組織形式1以班為單位的一體化教學(xué)2個人獨立完成任務(wù)教師能力要求1. 精通vc+6.0的使用。2. 熟悉各種數(shù)據(jù)的類型及算法。3. 具

14、有一定的和好的教學(xué)能力，語言溝通能力?？己朔绞缴蠙C調(diào)試備注學(xué)習(xí)情境3： 樹及二叉樹學(xué)習(xí)情境樹及二叉樹學(xué)時2能力目標(biāo)Ø 掌握二叉樹的建立與存儲。Ø 掌握二叉樹的遍歷方法。主要內(nèi)容1. 練習(xí)二叉樹的建立與存儲。2. 練習(xí)二叉樹的遍歷。工作任務(wù)1 建立自己的頭文件BT.H，內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹的建立、二叉樹的先序、中序與后序遍歷算法。2 建立二叉樹,并通過調(diào)用函數(shù),，輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。刪除棧頂元素。實訓(xùn)環(huán)境為每位學(xué)生配置的計算機具備如下的軟件環(huán)境：1. Windows XP/ Windows 2003或以上版本2. vc+6.0環(huán)境教學(xué)資源1.

15、 電子課件2. 任務(wù)樣例教學(xué)方法建議1“教、學(xué)、做”三位一體教學(xué)法。2. 案例分析法。3. 訓(xùn)練學(xué)習(xí)法。教學(xué)組織形式1以班為單位的一體化教學(xué)2個人獨立完成任務(wù)教師能力要求1. 精通vc+6.0的使用。2. 熟悉各種數(shù)據(jù)的類型及算法。3. 具有一定的和好的教學(xué)能力，語言溝通能力。考核方式上機調(diào)試備注學(xué)習(xí)情境4： 圖學(xué)習(xí)情境圖學(xué)時2能力目標(biāo)Ø 掌握圖的基本存儲方法。Ø 掌握有關(guān)圖的操作算法并用高級語言實現(xiàn)。Ø 熟練掌握圖的兩種搜索路徑的遍歷方法。主要內(nèi)容假設(shè)以一個帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該

16、線路上的票價（或搭乘所需時間），試設(shè)計一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達(dá)另一場所。工作任務(wù)1 定義結(jié)點結(jié)構(gòu)，定義圖結(jié)構(gòu)。2 存儲圖信息。3 定義求任意兩點最短路徑函數(shù)。4 寫出主函數(shù)。實訓(xùn)環(huán)境為每位學(xué)生配置的計算機具備如下的軟件環(huán)境：1. Windows XP/ Windows 2003或以上版本2. vc+6.0環(huán)境教學(xué)資源1. 電子課件2. 任務(wù)樣例教學(xué)方法建議1“教、學(xué)、做”三位一體教學(xué)法。2. 案例分析法。3. 訓(xùn)練學(xué)習(xí)法。教學(xué)組織形式1以班為單位的一體化教學(xué)2個人獨立完成任務(wù)教師能力要求1. 精通vc+6.0的使用。2. 熟悉各種數(shù)據(jù)的類型

17、及算法。3. 具有一定的和好的教學(xué)能力，語言溝通能力?？己朔绞缴蠙C調(diào)試備注學(xué)習(xí)情境5： 查找學(xué)習(xí)情境查找學(xué)時2能力目標(biāo)Ø 掌握查找的不同方法，并能用高級語言實現(xiàn)查找算法。Ø 熟練掌握二叉樹的構(gòu)造和查找方法。主要內(nèi)容設(shè)計一個讀入一串整數(shù)，然后進(jìn)行排序（二叉排序樹法）的算法。工作任務(wù)1 從空的二叉樹開始，每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)點插入到當(dāng)前已生成的二叉排序樹中。2 在二叉排序樹中插入新結(jié)點。3 建立一個帶頭結(jié)點的單鏈表，結(jié)點的值域為整型數(shù)據(jù)。要求將用戶輸入的數(shù)據(jù)按尾插入法來建立相應(yīng)單鏈表。實訓(xùn)環(huán)境為每位學(xué)生配置的計算機具備如下的軟件環(huán)境：1. Windows XP/

18、Windows 2003或以上版本2. vc+6.0環(huán)境教學(xué)資源1. 電子課件2. 任務(wù)樣例教學(xué)方法建議1“教、學(xué)、做”三位一體教學(xué)法。2. 案例分析法。3. 訓(xùn)練學(xué)習(xí)法。教學(xué)組織形式1以班為單位的一體化教學(xué)2個人獨立完成任務(wù)教師能力要求1. 精通vc+6.0的使用。2. 熟悉各種數(shù)據(jù)的類型及算法。3. 具有一定的和好的教學(xué)能力，語言溝通能力?？己朔绞缴蠙C調(diào)試備注學(xué)習(xí)情境6： 排序?qū)W習(xí)情境排序?qū)W時2能力目標(biāo)Ø 掌握常用的排序方法，并掌握用高級語言實現(xiàn)排序算法的方法。Ø 深刻理解排序的定義和各種排序方法的特點，并能加以靈活應(yīng)用。Ø 了解各種方法的排序過程及其時間復(fù)雜度的分析方法。主要內(nèi)容統(tǒng)計成績 給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法。1. 按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)