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

《數(shù)據(jù)結(jié)構(gòu)A》教學大綱適適用范圍：2020本科人才培養(yǎng)方案課程代碼：08130291課程性質(zhì)：學科基礎(chǔ)必修課學分：4.5學分學時：72學時（其中：理論56學時，實驗16學時）先修課程：C程序設(shè)計后續(xù)課程：數(shù)據(jù)庫原理及應(yīng)用適用專業(yè)：物聯(lián)網(wǎng)工程、軟件工程、數(shù)據(jù)科學與大數(shù)據(jù)技術(shù)、數(shù)字媒體技術(shù)教材：《數(shù)據(jù)結(jié)構(gòu)》（C語言版），劉暢姚學峰編著，上海交通大學出版社，2016.09開課單位：計算機科學與技術(shù)學院一、課程的性質(zhì)與任務(wù)課程性質(zhì)：本課程是物聯(lián)網(wǎng)工程、軟件工程、數(shù)據(jù)科學與大數(shù)據(jù)技術(shù)及數(shù)字媒體技術(shù)專業(yè)的學科基礎(chǔ)必修課。課程任務(wù)：其任務(wù)主要是使學生體會“算法的設(shè)計建立于邏輯結(jié)構(gòu)，算法的實現(xiàn)依賴于物理（存儲）結(jié)構(gòu)”，并能根據(jù)實際情況選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法，學習如何合理地組織數(shù)據(jù)、有效地存儲和處理數(shù)據(jù)，正確地設(shè)計算法以及對算法的分析和評價，為以后在本專業(yè)方面的優(yōu)質(zhì)程序設(shè)計打下基礎(chǔ)。二、課程教學目標1.知識目標掌握和理解線性結(jié)構(gòu)與非線性結(jié)構(gòu)數(shù)據(jù)組織形式及基本算法；2.能力目標簡單運用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法合理組織數(shù)據(jù)、處理數(shù)據(jù)；3.素質(zhì)目標樹立正確的政治理想和政治道德，培養(yǎng)對黨和國家，社會主義事業(yè)忠誠可靠的建設(shè)者和接班人；三、課程的基本內(nèi)容及要求（一）緒論1．課程教學內(nèi)容（1）什么是數(shù)據(jù)結(jié)構(gòu)；（2）基本概念和術(shù)語；（3）算法和算法分析。2．課程重點難點重點:了解數(shù)據(jù)結(jié)構(gòu)這門課的主要研究內(nèi)容及學習方法；熟悉基本概念和術(shù)語；算法時間復雜度的計算；難點:算法時間復雜度的計算。3．課程教學要求（1）能夠知道為什么學習數(shù)據(jù)結(jié)構(gòu)這門課，這門課的主要內(nèi)容是什么；（2）知道本門課的基本學習方法；（3）能準確理解各種基本概念和術(shù)語；會估算算法的時間復雜度。（二）線性表1．課程教學內(nèi)容（1）線性表的類型定義；（2）線性表的順序表示和實現(xiàn)；（3）線性表的鏈式表示和實現(xiàn)；（4）循環(huán)鏈表和雙向鏈表。2．課程重點難點重點:單鏈表的插入、刪除和查詢；難點:通過單鏈表舉一反三對循環(huán)鏈表和雙向鏈表進行操作。3．課程教學要求（1）理解線性表的定義和特點；（2）理解線性表的順序表示和實現(xiàn)；（3）理解線性表的鏈式表示和實現(xiàn)；（4）掌握線性表的基本操作和應(yīng)用。（三）棧和隊列1．課程教學內(nèi)容（1）棧的定義、特點、表示和操作、應(yīng)用；（2）隊列的定義、特點、表示和操作、應(yīng)用。2．課程重點難點重點:棧和隊列的定義、特點、基本操作；難點:循環(huán)隊列的表示和實現(xiàn)。3．課程教學要求（1）掌握棧和隊列的定義、特點、邏輯結(jié)構(gòu)及其基本運算；（2）了解棧和隊列在實際編程中的基本應(yīng)用。（四）串、數(shù)組和廣義表1．課程教學內(nèi)容（1）串的定義、存儲、運算；（2）數(shù)組的定義、順序存儲、壓縮存儲；（3）廣義表的定義和存儲。2．課程重點難點重點:串的定義和運算、廣義表的定義和存儲；難點:串的運算。3．課程教學要求（1）了解串和廣義表的定義和基本特點；（2）明白串、廣義表的編程適用場合；（3）能對稀疏矩陣進行壓縮存儲。（五）樹與二叉樹1．課程教學內(nèi)容（1）樹和二叉樹的定義；（2）二叉樹的性質(zhì)和存儲；（3）遍歷二叉樹；（4）樹和森林；（5）哈夫曼樹及其應(yīng)用。2．課程重點難點重點:二叉樹的定義、性質(zhì)、存儲、遍歷、應(yīng)用；難點:哈夫曼樹及其應(yīng)用。3．課程教學要求（1）理解樹和二叉樹的定義和特點；（2）熟練掌握二叉樹的存儲方法和遍歷方法；（3）能完成樹、森林與二叉樹間的相互轉(zhuǎn)換；（3）理解哈夫曼樹的構(gòu)造方法，能用哈夫曼樹解決實際問題。（六）圖1．課程教學內(nèi)容（1）圖的定義和術(shù)語；（2）圖的存儲結(jié)構(gòu)；（3）圖的遍歷；（4）圖的應(yīng)用。2．課程重點難點重點:圖的存儲、遍歷和應(yīng)用；難點:圖的應(yīng)用。3．課程教學要求（1）理解圖的基本概念及術(shù)語；（2）掌握圖的存儲方式和遍歷方法；（3）能用圖解決實際問題。（七）查找1．課程教學內(nèi)容（1）查找的基本概念；（2）線性表的查找；（3）樹表的查找；（4）散列表的查找。2．課程重點難點重點:線性表、樹表、散列表的查找；難點:散列表的查找。3．課程教學要求（1）了解查找的基本思想；（2）掌握查找的基本方法；（3）了解查找的實際應(yīng)用。（八）排序1．課程教學內(nèi)容（1）排序的基本概念；（2）內(nèi)部排序的基本方法——插入、交換、選擇、歸并、基數(shù)；（3）外部排序與內(nèi)部排序的不同之處、外部排序的基本方法。2．課程重點難點重點:插入、交換、選擇、歸并排序的基本思想；難點:希爾排序、快速排序、堆排序。3．課程教學要求（1）了解排序的基本思想；（2）掌握插入類、交換類、選擇類、歸并類排序的基本思想和方法；（3）了解各種排序算法的優(yōu)缺點，在現(xiàn)實問題解決中能選用合適的排序算法。四、課程學時分配教學章節(jié)理論實踐（驗）討論、習題一、緒論4二、線性表82三、棧和隊列64四、串、數(shù)組和廣義表62五、樹和二叉樹82六、圖82七、查找82八、排序82總計5616五、課程考核方式與要求考核方式：本課程主要以課堂表現(xiàn)、作業(yè)評價、平時測試、期末筆試等考核方式對學生進行考核評價?？己嘶疽螅嚎己丝偝煽冇善谀┰嚲沓煽兒瓦^程性評價成績組成。其中：期末筆試考核成績?yōu)?00分（權(quán)重為60%），試題類型為填空題、選擇題、計算題、編程題和綜合分析題等類型；試卷中基本知識、基本理論、基本技能的試題分值不超過50%，綜合應(yīng)用題、分析題不低于50%；過程性評價成績?yōu)?00分（權(quán)重40%）,由課堂表現(xiàn)、作業(yè)評價、平時測試等組成。過程性評價和考試試題分值分配應(yīng)與教學大綱各章節(jié)的學時基本成比例。五、課程資源庫1.程杰.大話數(shù)據(jù)結(jié)構(gòu).清華大學出版社.2020.122.嚴蔚敏李冬梅吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言）.清華大學出版社2015.22.EllisHorowitzSartajSahniSusanAnderson-Freed(李建中、張巖、李治軍譯).數(shù)據(jù)結(jié)構(gòu)(C語言版).機械工業(yè)出版社.2012.33.MarkAllenWeiss(馮舜璽譯).數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述.機械工業(yè)出版社.2012.114.BentleyJL.Multidimensionalbinarysearchtreesusedforassociativesearching[J].CommunicationsoftheAcm.5.LiuL,YuM,ShaoL.LatentStructurePreservingHashing[J].InternationalJournalofComputerVision,2017.6.于智娟,姜珊.DNA計算機中隊列數(shù)據(jù)結(jié)構(gòu)的設(shè)計及實現(xiàn)[J].計算機學報,2014.7.魏玲,魏永江,高長元.基于Bigtable與MapReduce的Apriori算法改進[J].計算機科學,2015.8.王尚平,張亞玲,王育民.