《數(shù)據(jù)結(jié)構(gòu)B》教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)B》教學(xué)大綱適用范圍：202X版本科人才培養(yǎng)方案課程代碼：08150371課程性質(zhì)：專業(yè)選修課學(xué)分：3學(xué)分學(xué)時(shí)：48學(xué)時(shí)（理論32學(xué)時(shí)，實(shí)驗(yàn)16學(xué)時(shí)）先修課程：C語言程序設(shè)計(jì)B等后續(xù)課程：智能機(jī)器人等適用專業(yè)：機(jī)器人工程專業(yè)開課單位：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院一、課程說明《數(shù)據(jù)結(jié)構(gòu)B》是機(jī)器人工程專業(yè)的專業(yè)選修課。本課程主要使學(xué)生體會(huì)“算法的設(shè)計(jì)建立于邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)依賴于物理（存儲(chǔ)）結(jié)構(gòu)”，并能根據(jù)實(shí)際情況選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法，學(xué)習(xí)如何合理地組織數(shù)據(jù)、有效地存儲(chǔ)和處理數(shù)據(jù)，正確地設(shè)計(jì)算法以及對(duì)算法的分析和評(píng)價(jià)，為以后在本專業(yè)方面的優(yōu)質(zhì)程序設(shè)計(jì)打下基礎(chǔ)。二、課程目標(biāo)通過本課程的學(xué)習(xí)，使學(xué)生達(dá)到如下目標(biāo)：課程目標(biāo)1：掌握和理解線性結(jié)構(gòu)與非線性結(jié)構(gòu)數(shù)據(jù)組織形式及基本算法。課程目標(biāo)2：具有簡(jiǎn)單運(yùn)用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法合理組織數(shù)據(jù)、處理數(shù)據(jù)的能力。課程目標(biāo)3：在課程教學(xué)中把理想信念教育與科學(xué)精神的培養(yǎng)結(jié)合起來，提高學(xué)生用馬克思主義的世界觀和方法論認(rèn)識(shí)、分析和解決問題的能力；讓學(xué)生在學(xué)好專業(yè)知識(shí)的同時(shí)堅(jiān)定理想信念，不斷增強(qiáng)科技強(qiáng)國(guó)的使命感和責(zé)任感；培養(yǎng)學(xué)生精益求精的工匠精神和創(chuàng)新精神。三、課程目標(biāo)與畢業(yè)要求《數(shù)據(jù)結(jié)構(gòu)B》課程教學(xué)目標(biāo)對(duì)機(jī)器人工程專業(yè)畢業(yè)要求的支撐見表1。表1課程教學(xué)目標(biāo)與畢業(yè)要求關(guān)系畢業(yè)要求指標(biāo)點(diǎn)課程目標(biāo)支撐強(qiáng)度2.問題分析：能夠應(yīng)用數(shù)學(xué)、自然科學(xué)和工程基礎(chǔ)的基本原理，識(shí)別、表達(dá)、并通過文獻(xiàn)研究分析機(jī)器人工程領(lǐng)域的復(fù)雜工程問題，掌握對(duì)象特性，以獲得有效結(jié)論。2.2應(yīng)用數(shù)學(xué)、物理等方法和專業(yè)知識(shí)，能夠?qū)C(jī)器人工程領(lǐng)域復(fù)雜工程問題進(jìn)行建模。課程目標(biāo)1：掌握和理解線性結(jié)構(gòu)與非線性結(jié)構(gòu)數(shù)據(jù)組織形式及基本算法。課程目標(biāo)2：具有簡(jiǎn)單運(yùn)用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法合理組織數(shù)據(jù)、處理數(shù)據(jù)的能力。M4.研究：能夠基于機(jī)器人機(jī)械、電子電路、計(jì)算機(jī)、控制等科學(xué)原理，并采用數(shù)學(xué)建模、系統(tǒng)仿真等科學(xué)方法，對(duì)機(jī)器人工程領(lǐng)域的復(fù)雜工程問題進(jìn)行研究，包括設(shè)計(jì)實(shí)驗(yàn)、建模、分析與解釋數(shù)據(jù)、并通過信息綜合得到合理有效的結(jié)論。4.3能夠采用計(jì)算機(jī)仿真、實(shí)物或半實(shí)物仿真等方法，設(shè)計(jì)實(shí)驗(yàn)方案，搭建實(shí)驗(yàn)系統(tǒng)，進(jìn)行實(shí)驗(yàn)。課程目標(biāo)3：在課程教學(xué)中把理想信念教育與科學(xué)精神的培養(yǎng)結(jié)合起來，提高學(xué)生用馬克思主義的世界觀和方法論認(rèn)識(shí)、分析和解決問題的能力；讓學(xué)生在學(xué)好專業(yè)知識(shí)的同時(shí)堅(jiān)定理想信念，不斷增強(qiáng)科技強(qiáng)國(guó)的使命感和責(zé)任感；培養(yǎng)學(xué)生精益求精的工匠精神和創(chuàng)新精神。M注：表中“H（高）、M（中）”表示課程與相關(guān)畢業(yè)要求的關(guān)聯(lián)度。四、教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配1.理論部分理論部分的教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配見表2。表2教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配教學(xué)內(nèi)容教學(xué)要求，教學(xué)重點(diǎn)難點(diǎn)理論學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)對(duì)應(yīng)的課程目標(biāo)1.緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)；1.2基本概念和術(shù)語；1.3算法和算法分析。教學(xué)要求：使學(xué)生能夠知道為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課，這門課的主要內(nèi)容是什么；知道本門課的基本學(xué)習(xí)方法；能準(zhǔn)確理解各種基本概念和術(shù)語；會(huì)估算算法的時(shí)間復(fù)雜度。重點(diǎn):了解數(shù)據(jù)結(jié)構(gòu)這門課的主要研究?jī)?nèi)容及學(xué)習(xí)方法；熟悉基本概念和術(shù)語；算法時(shí)間復(fù)雜度的計(jì)算；難點(diǎn):算法時(shí)間復(fù)雜度的計(jì)算。41、2、32.線性表2.1線性表的類型定義；2.2線性表的順序表示和實(shí)現(xiàn)；2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；2.4循環(huán)鏈表和雙向鏈表。教學(xué)要求：使學(xué)生理解線性表的定義和特點(diǎn)；理解線性表的順序表示和實(shí)現(xiàn)；理解線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)；掌握線性表的基本操作和應(yīng)用。重點(diǎn):單鏈表的插入、刪除和查詢；難點(diǎn):通過單鏈表舉一反三對(duì)循環(huán)鏈表和雙向鏈表進(jìn)行操作。4213.棧和隊(duì)列3.1棧的定義、特點(diǎn)、表示和操作、應(yīng)用；3.2隊(duì)列的定義、特點(diǎn)、表示和操作、應(yīng)用教學(xué)要求：使學(xué)生掌握棧和隊(duì)列的定義、特點(diǎn)、邏輯結(jié)構(gòu)及其基本運(yùn)算；了解棧和隊(duì)列在實(shí)際編程中的基本應(yīng)用。重點(diǎn):棧和隊(duì)列的定義、特點(diǎn)、基本操作；難點(diǎn):循環(huán)隊(duì)列的表示和實(shí)現(xiàn)。321、24.串、數(shù)組和廣義表4.1串的定義、存儲(chǔ)、運(yùn)算；4.2數(shù)組的定義、順序存儲(chǔ)、壓縮存儲(chǔ)；4.3廣義表的定義和存儲(chǔ)。教學(xué)要求：使學(xué)生了解串和廣義表的定義和基本特點(diǎn)；明白串、廣義表的編程適用場(chǎng)合；能對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)。重點(diǎn):串的定義和運(yùn)算、廣義表的定義和存儲(chǔ)；難點(diǎn):串的運(yùn)算。341、35.樹與二叉樹5.1樹和二叉樹的定義；5.2二叉樹的性質(zhì)和存儲(chǔ)；5.3遍歷二叉樹；5.4樹和森林；5.5哈夫曼樹及其應(yīng)用教學(xué)要求：使學(xué)生理解樹和二叉樹的定義和特點(diǎn)；熟練掌握二叉樹的存儲(chǔ)方法和遍歷方法；）能完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，能用哈夫曼樹解決實(shí)際問題。重點(diǎn):二叉樹的定義、性質(zhì)、存儲(chǔ)、遍歷、應(yīng)用；難點(diǎn):哈夫曼樹及其應(yīng)用。622、36.圖6.1圖的定義和術(shù)語；6.2圖的存儲(chǔ)結(jié)構(gòu)；6.3圖的遍歷；6.4圖的應(yīng)用。教學(xué)要求：使學(xué)生理解圖的基本概念及術(shù)語；掌握?qǐng)D的存儲(chǔ)方式和遍歷方法；能用圖解決實(shí)際問題。重點(diǎn):圖的存儲(chǔ)、遍歷和應(yīng)用；難點(diǎn):圖的應(yīng)用。422、37.查找7.1查找的基本概念；7.2線性表的查找；7.3樹表的查找；7.4散列表的查找。教學(xué)要求：使學(xué)生了解查找的基本思想；掌握查找的基本方法；了解查找的實(shí)際應(yīng)用。重點(diǎn):線性表、樹表的查找；難點(diǎn):散列表的查找。421、2、38.排序8.1排序的基本概念；8.2內(nèi)部排序的基本方法——插入、交換、選擇、歸并、基數(shù)；8.3外部排序與內(nèi)部排序的不同之處、外部排序的基本方法。教學(xué)要求：使學(xué)生了解排序的基本思想；掌握插入類、交換類、選擇類排序的基本思想和方法；了解各種排序算法的優(yōu)缺點(diǎn)，在現(xiàn)實(shí)問題解決中能選用合適的排序算法。重點(diǎn):插入、交換、選擇排序的基本思想；難點(diǎn):希爾排序、快速排序、堆排序。421、2、3合計(jì)32162.實(shí)驗(yàn)部分實(shí)驗(yàn)部分的教學(xué)內(nèi)容、基本要求與學(xué)時(shí)分配見表3。表3實(shí)驗(yàn)項(xiàng)目、實(shí)驗(yàn)內(nèi)容與學(xué)時(shí)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)內(nèi)容和要求實(shí)驗(yàn)學(xué)時(shí)對(duì)應(yīng)的課程目標(biāo)1.線性表（棧和隊(duì)列）實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)一個(gè)線性表，分別采用順序存儲(chǔ)結(jié)構(gòu)插入一個(gè)元素；和采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)刪除一個(gè)結(jié)點(diǎn)。棧和隊(duì)列兩種類型二選一，完成創(chuàng)建、入棧或出棧（入隊(duì)或出隊(duì)）。實(shí)驗(yàn)要求：掌握線性表的插入、刪除和查詢；了解棧的先進(jìn)先出及隊(duì)列的基本操作。41、22.單鏈表和串實(shí)驗(yàn)內(nèi)容：從鍵盤輸入一串，求串長(zhǎng)度；從鍵盤輸入兩串，實(shí)現(xiàn)串的連接；從鍵盤輸入一串，求從該串第i個(gè)字符開始的j個(gè)子串；選作：從鍵盤輸入兩個(gè)串，實(shí)現(xiàn)兩個(gè)串的比較；從鍵盤輸入一個(gè)串，刪除該串中指定字符。實(shí)驗(yàn)要求：熟悉單鏈表的創(chuàng)建、插入、刪除、查詢、輸出；掌握串的基本操作和應(yīng)用。41、23.二叉樹和圖實(shí)驗(yàn)內(nèi)容：創(chuàng)建二叉樹；遍歷二叉樹或求二叉樹葉子節(jié)點(diǎn)數(shù)或求二叉樹深度（選一）；圖：圖的遍歷、最小生成樹、關(guān)鍵路徑、最短路徑等操作（選一）。實(shí)驗(yàn)要求：掌握二叉樹的基本操作和應(yīng)用；掌握?qǐng)D的基本操作和應(yīng)用。42、34.查找與排序?qū)嶒?yàn)內(nèi)容：二分法查找、二叉排序樹的查找、哈希表的創(chuàng)建與查找選一；冒泡排序、插入排序選一。實(shí)驗(yàn)要求：熟悉查找和排序的經(jīng)典算法。42、3合計(jì)16五、教學(xué)方法及手段本課程以課堂講授為主，結(jié)合討論、案例、網(wǎng)絡(luò)資源共享、實(shí)驗(yàn)等教學(xué)手段完成課程教學(xué)任務(wù)和相關(guān)能力的培養(yǎng)。學(xué)生比較全面地體會(huì)“算法的設(shè)計(jì)建立于邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)依賴于物理（存儲(chǔ)）結(jié)構(gòu)”，并能根據(jù)實(shí)際情況選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法，所以本課程教學(xué)強(qiáng)調(diào)思維訓(xùn)練，為隨后的程序設(shè)計(jì)和技能訓(xùn)練打好基礎(chǔ)。在實(shí)驗(yàn)教學(xué)環(huán)節(jié)中，通過啟發(fā)式教學(xué)、討論式教學(xué)培養(yǎng)學(xué)生的對(duì)問題的分析、數(shù)據(jù)結(jié)構(gòu)的基本理論、基本知識(shí)和基本技能。培養(yǎng)學(xué)生自主學(xué)習(xí)能力、實(shí)際動(dòng)手能力，激發(fā)學(xué)生的創(chuàng)新思維。每完成一項(xiàng)實(shí)驗(yàn)，要認(rèn)真完成一份實(shí)驗(yàn)報(bào)告。六、課程資源1.推薦教材：（1）《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，嚴(yán)蔚敏，吳偉民著[M].北京：清華大學(xué)出版社，2021.102.參考書：（1）嚴(yán)蔚敏，李冬梅，吳偉民等著《數(shù)據(jù)結(jié)構(gòu)（C語言第2版）》[M].北京：人民郵電出版社，2021.10（2）劉暢著，《數(shù)據(jù)結(jié)構(gòu)》[M].北京：上海交通大學(xué)出版社，2016.08（3）程杰，《大話數(shù)據(jù)結(jié)構(gòu)》[M].北京：清華大學(xué)出版社，2020.123.期刊：（1）EllisHorowitzSartajSahniSusanAnderson-Freed(李建中、張巖、李治軍譯).數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：機(jī)械工業(yè)出版社.2012.3（2）MarkAllenWeiss(馮舜璽譯).數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述[M].北京：機(jī)械工業(yè)出版社.2012.11（3）BentleyJL.Multidimensionalbinarysearchtreesusedforassociativesearching[J].CommunicationsoftheAcm.（4）LiuL,YuM,ShaoL.LatentStructurePreservingHashing[J].InternationalJournalofComputerVision,2017.（5）于智娟,姜珊.DNA計(jì)算機(jī)中隊(duì)列數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)及實(shí)現(xiàn)[J].計(jì)算機(jī)學(xué)報(bào),2014.4.網(wǎng)絡(luò)資源：（1）Poll的筆記.[DataStructure]數(shù)據(jù)結(jié)構(gòu)中各種樹.2015-08-15./maybe2030/p/4732377.html（2）小草莓lllll.數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)概念篇.2017-11-14./qq_31196849/article/details/78529724（3）靜默虛空.程序員的內(nèi)功——數(shù)據(jù)結(jié)構(gòu)和算法系列.2015-03-11./jingmoxukong/p/4329079.html七、課程考核對(duì)課程目標(biāo)的支撐課程成績(jī)由過程性考核成績(jī)和期末考核成績(jī)兩部分構(gòu)成，具體考核/評(píng)價(jià)細(xì)則及對(duì)課程目標(biāo)的支撐關(guān)系見表4。表4課程考核對(duì)課程目標(biāo)的支撐考核環(huán)節(jié)占比考核/評(píng)價(jià)細(xì)則課程目標(biāo)123過程性考核課堂表現(xiàn)30（1）根據(jù)課堂出勤情況和課堂回答問題情況進(jìn)行考核，滿分100分。（2）以平時(shí)考核成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)?！獭獭?2135實(shí)驗(yàn)10（1）根據(jù)每個(gè)實(shí)驗(yàn)的實(shí)驗(yàn)操作完成情況和實(shí)驗(yàn)報(bào)告質(zhì)量單獨(dú)評(píng)分，滿分100分；（2）每次實(shí)驗(yàn)單獨(dú)評(píng)分，取各次實(shí)驗(yàn)成績(jī)的平均值作為此環(huán)節(jié)的最終成績(jī)。（3）以實(shí)驗(yàn)成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)?！?0作業(yè)10（1）主要考核學(xué)生對(duì)各章節(jié)知識(shí)點(diǎn)的復(fù)習(xí)、理解和掌握程度，滿分100分；（2）每次作業(yè)單獨(dú)評(píng)分，取各次成績(jī)的平均值作為此環(huán)節(jié)的最終成績(jī)。（3）以作業(yè)成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)。√√√442期末考核50（1）卷面成績(jī)100分，以卷面成績(jī)乘以其在總評(píng)成績(jī)中所占的比例計(jì)入課程總評(píng)成績(jī)。（2）主要考核軟件工程的基礎(chǔ)概念，3個(gè)時(shí)期8各階段的相應(yīng)目的、過程、原理和方法等；以及相應(yīng)過程中的各種圖形描述工具和技術(shù)等內(nèi)容。（3）考試題型為：選擇、填空題、判斷題、綜合應(yīng)用題等。√√√202010合計(jì)：100分364717八、考核與成績(jī)?cè)u(píng)定1.考核方式及成績(jī)?cè)u(píng)定考核方式：本課程主要以課堂表現(xiàn)、實(shí)驗(yàn)、作業(yè)、期末考試等方式對(duì)學(xué)生進(jìn)行考核評(píng)價(jià)?？己嘶疽螅嚎己丝偝煽?jī)由期末試卷成績(jī)和過程性考核成績(jī)組成。其中：期末試卷成績(jī)?yōu)?00分（權(quán)重50%），試題類型為選擇題、判斷題等類型，試卷中基本知識(shí)、基本理論、基本技能的試題分值不超過50%，綜合應(yīng)用題、分析題不低于50%；課堂表現(xiàn)、實(shí)驗(yàn)、作業(yè)等過程性考核成績(jī)?yōu)?00分（權(quán)重50%）；過程性考核和考試試題分值分配應(yīng)與教學(xué)大綱各章節(jié)的學(xué)時(shí)基本成比例。2.過程性考核成績(jī)的標(biāo)準(zhǔn)過程性考核方式重點(diǎn)考核內(nèi)容、評(píng)價(jià)標(biāo)準(zhǔn)、所占比重見表5。表5過程性考核方式評(píng)價(jià)標(biāo)準(zhǔn)考核方式所占比重(%)100>x≥9090>x≥8080>x≥7070>x≥60x<60課堂表現(xiàn)60積極參與教學(xué)活動(dòng)，踴躍回答問題，準(zhǔn)確率大于90%。認(rèn)真參與教學(xué)活動(dòng)，回答問題準(zhǔn)確率大于80%。偶爾參與教學(xué)活動(dòng)，回答問題準(zhǔn)確率大于70%。上課不認(rèn)真，上課不記筆記，偶爾參與教學(xué)活動(dòng)。上課不認(rèn)真，上課不記筆記，不參與教學(xué)活動(dòng)。作業(yè)20作業(yè)完整，思路清晰，準(zhǔn)確率大于90%，字跡工整。作業(yè)完整，準(zhǔn)確率大于80%，字跡工整。不交作業(yè)2次以內(nèi)，準(zhǔn)確率大于70%.不交作業(yè)4