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

《數(shù)據(jù)結(jié)構(gòu)》課程考試大綱（一）適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)（二）考試的基本要求：要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，掌握數(shù)據(jù)結(jié)構(gòu)的基本算法。要求考生具有抽象思維能力，邏輯推理能力和綜合運(yùn)用所學(xué)的知識(shí)分析和解決問題的能力。（三）教材及主要參考書

清華大學(xué)出版社王紅梅、胡明、王濤等主編

《數(shù)據(jù)結(jié)構(gòu)（C++版）》第2版（四）課程主要內(nèi)容一、緒論

考試內(nèi)容

數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型算法算法的特性算法設(shè)計(jì)的要求時(shí)間復(fù)雜度空間復(fù)雜度

考試要求1．了解數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的地位和在程序設(shè)計(jì)中的重要作用。2．了解數(shù)據(jù)結(jié)構(gòu)的基本概念術(shù)語。3．掌握算法的描述和分析算法。二、線性表

考試內(nèi)容

線性表線性表的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)的特點(diǎn)線性表的基本操作（初始化，插入，刪除等）

考試要求1．

了解線性表的基本特點(diǎn)和邏輯結(jié)構(gòu)。2．

掌握線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3．

掌握線性表的基本操作。三、棧和隊(duì)列

考試內(nèi)容

棧棧的特點(diǎn)棧的表示和實(shí)現(xiàn)棧的基本應(yīng)用隊(duì)列隊(duì)列的特點(diǎn)隊(duì)列的表示和實(shí)現(xiàn)隊(duì)列的應(yīng)用

考試要求1．了解棧和隊(duì)列的特點(diǎn)。2．了解棧和隊(duì)列的應(yīng)用。3．掌握棧和隊(duì)列的各種表示和實(shí)現(xiàn)方式。4．掌握棧和隊(duì)列的基本操作。四、樹和二叉樹

考試內(nèi)容

樹的結(jié)構(gòu)定義和存儲(chǔ)結(jié)構(gòu)樹的基本術(shù)語二叉樹的定義和基本操作二叉樹的性質(zhì)二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的遍歷線索二叉樹

哈夫曼樹及應(yīng)用

考試要求1．了解樹和森林的定義和基本概念。2．掌握二叉樹的各種存儲(chǔ)結(jié)構(gòu)及基本操作。3．掌握二叉樹的線索化。4．掌握哈夫曼樹的構(gòu)造方法和應(yīng)用。五、圖考試內(nèi)容圖的定義圖的基本概念圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷圖的最小生成樹拓?fù)渑判蜿P(guān)鍵路徑最短路徑考試要求1．了解圖的特點(diǎn)和圖的基本概念。2．了解圖的基本應(yīng)用。3．掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)。4．掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索遍歷算法。5．掌握?qǐng)D的最小生成樹算法。6．學(xué)會(huì)利用拓?fù)渑判蚪鉀Q問題。7．掌握關(guān)鍵路徑和最短路徑算法及應(yīng)用。六、查找考試內(nèi)容查找表關(guān)鍵字查找順序表的查找有序表的查找哈希表哈希函數(shù)的構(gòu)造方法處理沖突的方法查找性能的分析考試要求1．

了解各種查找表和查找樹的特點(diǎn)和查找性能。2．

掌握查找表和查找樹的查找方法。3．

掌握哈希表的構(gòu)造方法、查找過程、處理沖突的方法。4．

能熟練分析各種查找算法的特點(diǎn)。七、內(nèi)部排序考試內(nèi)容排序直接插入排序折半插入排序

2-路插入排序表插入排序希爾排序快速排序簡單選擇排序樹形選擇排序堆排序歸并排序基數(shù)排序考試要求1．掌握各種插入排序算法及性能。2．掌握快速排序算法及性能。3