《數(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ù)語(yǔ)。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ù)語(yǔ)二叉樹的定義和基本操作二叉樹的性質(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-路插入排序表插入排序希爾排序快速排序簡(jiǎn)單選擇排序樹形選擇排序堆排序歸并排序基數(shù)排序考試要求1．掌握各種插入排序算法及性能。2．掌握快速排序算法及性能。3