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

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

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

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