數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案福州大學2012年碩士研究生入學考試自命題科目考試大綱考試科目名稱:《數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計》數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案全文共3頁，當前為第1頁。招生學院和專業(yè)：數(shù)學與計算機科學學院數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案全文共3頁，當前為第1頁?；緝?nèi)容(可續(xù)頁):數(shù)據(jù)結(jié)構(gòu)與算法概論：算法的基本概念、表達算法的抽象機制以及算法的計算復(fù)雜性概念和分析方法。數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的基本概念以及這3個重要概念的區(qū)別和內(nèi)在聯(lián)系。采用C/C++與自然語言相結(jié)合的方式描述算法的方法。線性表：抽象數(shù)據(jù)類型表的基本概念及其邏輯特征。實現(xiàn)抽象數(shù)據(jù)類型的一般步驟。按照抽象數(shù)據(jù)類型設(shè)計和實現(xiàn)的一般性原則，常用的實現(xiàn)表的方法，如用數(shù)組實現(xiàn)表的方法、用指針實現(xiàn)表的方法、用間接尋址技術(shù)實現(xiàn)表的方法、用游標實現(xiàn)表的方法、單循環(huán)鏈表和雙鏈表以及表的搜索游標的實現(xiàn)方法和步驟。棧：抽象數(shù)據(jù)類型棧的基本概念及其邏輯特征。按照抽象數(shù)據(jù)類型設(shè)計和實現(xiàn)的一般性原則，常用的用數(shù)組實現(xiàn)棧的方法和用指針實現(xiàn)棧的方法。以集合的等價類劃分等問題為例討論棧的應(yīng)用方法。隊列：抽象數(shù)據(jù)類型隊列的基本概念及其邏輯特征。按照抽象數(shù)據(jù)類型設(shè)計和實現(xiàn)的一般性原則，常用的用指針實現(xiàn)隊列的方法和用循環(huán)數(shù)組實現(xiàn)隊列的方法。以電路布線等問題為例討論隊列的應(yīng)用方法。集合：集合和以集合為基礎(chǔ)的抽象數(shù)據(jù)類型的基本概念及其邏輯特征。如何用位向量和鏈表兩種方式實現(xiàn)集合。排序與選擇：排序問題的提法及其實質(zhì)，常用的簡單排序算法，如冒泡排序算法、插入排序算法和選擇排序算法的設(shè)計思想與分析方法?？焖倥判蛩惴ǖ幕驹O(shè)計思想及其多方面的改進。合并排序算法的基本設(shè)計思想與分析方法。計數(shù)排序算法和桶排序算法等典型的線性時間排序算法的設(shè)計思想與分析方法，線性時間排序算法與基于比較的排序算法的主要差別和適用范圍。與排序問題類似的選擇問題及相應(yīng)的算法。從平均情況和最壞情況2個不同側(cè)面研究算法的設(shè)計思想及實現(xiàn)方法。樹：常用的非線性層次結(jié)構(gòu)樹以及作為抽象數(shù)據(jù)類型的樹的一般操作和一些常用的表示樹的數(shù)據(jù)結(jié)構(gòu)。樹的定義，樹的前序遍歷、中序遍歷和后序遍歷方法。常用的樹的父結(jié)點數(shù)組表示法、樹的兒子鏈表表示法和樹的左兒子右兄弟表示法。二叉樹和ADT二叉樹的概念。二叉樹的順序存儲結(jié)構(gòu)、二叉樹的結(jié)點度表示法和用指針實現(xiàn)二叉樹的方法。線索二叉樹結(jié)構(gòu)。以信號傳輸網(wǎng)絡(luò)中最優(yōu)信號增強裝置布局等問題為例討論樹結(jié)構(gòu)在實際問題中的應(yīng)用方法。二叉搜索樹：字典的概念，用數(shù)組和二叉搜索樹實現(xiàn)字典的方法，AVL樹的概念及相關(guān)運算。堆與優(yōu)先隊列：以集合為基礎(chǔ)的抽象數(shù)據(jù)類型優(yōu)先隊列，以及優(yōu)先級樹、堆、左偏樹和可并優(yōu)先隊列等概念。堆排序算法。散列：符號表的概念以及用數(shù)組、開散列、閉散列三種實現(xiàn)符號表的方法。常用的散列函數(shù)構(gòu)造方法，如：除余法、數(shù)乘法、平方取中法等以及主要的幾種解決沖突的方法，如：線性探測法、二次探測法等。并查集：以不相交的集合為基礎(chǔ)的抽象數(shù)據(jù)類型并查集概念，并查集的實現(xiàn)方法及其合并策略。路徑壓縮技術(shù)及其實現(xiàn)方法。圖：常用的表示復(fù)雜非線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)圖，以及作為抽象數(shù)據(jù)類型的圖的一般操作和表示圖的數(shù)據(jù)結(jié)構(gòu)。圖的鄰接矩陣表示及其實現(xiàn)方法、圖的鄰接表表示及其實現(xiàn)方法以及圖的緊縮鄰接表表示方法。遍歷一個圖的2個重要方法，即圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法。單源最短路徑問題的Dijkstra算法和Bellman-Ford算法以及所有頂點對之間最短路徑問題的Floyd算法。構(gòu)造最小支撐樹的Prim算法和Kruskal算法。無圈有向圖DAG的拓撲排序及其最短路徑和最長路徑的求法。二分圖的概念及其相關(guān)的圖匹配問題，最大匹配問題的增廣路徑算法。用C++語言實現(xiàn)算法與數(shù)據(jù)結(jié)構(gòu)：C++語言基本成分、數(shù)據(jù)描述與基本操作；C++語言流程設(shè)計和模塊化設(shè)計；算法的基本控制結(jié)構(gòu)（順序、選擇、循環(huán)結(jié)構(gòu)設(shè)計）；函數(shù)的定義與使用；數(shù)組、指針與字符串的綜合使用；結(jié)構(gòu)體的定義和使用；面向?qū)ο蟪绦蛟O(shè)計中的類與對象、繼承與派生、多態(tài)性等基本概念和基本方法。熟練掌握面向?qū)ο蟪绦蛟O(shè)計方法，利用線性表、棧、隊列、集合、排序算法、樹及二叉樹、二叉搜索樹、優(yōu)先隊列、散列、并查集、圖解決實際問題。數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案全文共數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計方案全文共3頁，當前為第2頁。參考書目(須與專業(yè)目錄一致)(包括作者、書目、出版社、出版時間、版次)：教材：

《數(shù)據(jù)結(jié)構(gòu)（STL框架）》，王曉東編，清華大學出版社《C++程序設(shè)計教程》，錢能編，清華大學出版社教學參考書：《數(shù)據(jù)結(jié)構(gòu)（C++版）》，王曉東編著，科學出版社

《數(shù)據(jù)結(jié)構(gòu)》嚴蔚敏編著清華大學出版社。說明：1、考試基本內(nèi)容：一般包括基礎(chǔ)理論、實際知識、綜合分析和論證等幾個方面的內(nèi)容。有些課程還應(yīng)有基本運算和實驗方法等方面的內(nèi)容。2、難易程度：根據(jù)