901數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計
一、考試的總體要求
本考試內(nèi)容由兩部分組成，數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計，各占總分的50％。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)基礎(chǔ)課,要求學(xué)生掌握基本的數(shù)據(jù)結(jié)構(gòu)及相關(guān)的存儲方式、基本運算、算法和應(yīng)用,并能運用盒圖、結(jié)構(gòu)化語言、類C、高級語言（C或C++）等方法之一編寫算法。程序設(shè)計指采用C++語言，應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識進行面向?qū)ο蟪绦蛟O(shè)計。要求學(xué)生掌握面向?qū)ο蟮某绦蛟O(shè)計方法，掌握C＋＋語言的基本概念，語法及編程方法。
二、考試的內(nèi)容及比例
數(shù)據(jù)結(jié)構(gòu)考試的內(nèi)容包括：（占總分50%）
1、線性表、順序表、鏈表的定義、特點、存儲結(jié)構(gòu)及相關(guān)的基本算法
2、棧的定義、特點、順序與鏈式存儲表示、基本算法；棧的應(yīng)用；隊列的定義、特點；鏈隊列、循環(huán)隊列相關(guān)的定義、特點、基本算法；棧與遞歸的實現(xiàn)
3、廣義表的定義及存儲結(jié)構(gòu)
4、二叉樹的定義、性質(zhì)及存儲結(jié)構(gòu)；遍歷二叉樹定義、過程及其算法；二叉樹的應(yīng)用；樹、森林與二叉數(shù)之間的轉(zhuǎn)換；哈夫曼樹及其應(yīng)用；與二叉樹應(yīng)用相關(guān)的遞歸算法
5、圖的定義、存儲結(jié)構(gòu)；圖的遍歷過程及算法；小生成樹構(gòu)造過程及算法；拓撲排序過程及算法；關(guān)鍵路徑相關(guān)內(nèi)容；短路徑相關(guān)內(nèi)容；與圖的應(yīng)用相關(guān)的遞歸算法
6、靜態(tài)表查找過程及算法、動態(tài)表查找過程及算法；哈希表的構(gòu)造及處理沖突方法
7、插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序等內(nèi)部排序的特點、過程及算法
程序設(shè)計考試的內(nèi)容包括：（占總分50％）
1、基本語法與常用語句，面向?qū)ο蟮幕靖拍?BR> 2、函數(shù)的調(diào)用，函數(shù)參數(shù)，函數(shù)的重載及函數(shù)作用域
3、類的概念，類的定義與說明，類的成員函數(shù)，作用域
4、對象的概念，對象的初始化，對象的特殊生成方法，對象的生存期
5、對象指針和對象引用，對象數(shù)組
6、類的繼承性和派生類
7、虛基類與虛函數(shù)
8、重載及其應(yīng)用
9、模版及其應(yīng)用
10、基本數(shù)據(jù)結(jié)構(gòu)和算法的程序設(shè)計
三、試卷類型及比例
考試題型：
數(shù)據(jù)結(jié)構(gòu)部分：
包括實做題與算法設(shè)計題兩大類：其中實做題有簡述題、舉例說明題、圖示題、圖表題、過程描述題、論述題等。算法設(shè)計題應(yīng)當根據(jù)要求，運用允許使用的適當?shù)姆椒ň帉懰惴ā?BR> 比例：實做題（60%）
算法設(shè)計題（40%）
程序設(shè)計部分：
包括3類題型：程序填空，寫程序結(jié)果和程序設(shè)計。
程序填空題：本題型給出程序的功能描述與少量提示，考生填寫缺少的程序部分，使得程序完整，并且實現(xiàn)描述的功能。
本題型為20分，2---4個題。
寫程序結(jié)果題：本題型給出C++程序，并已經(jīng)調(diào)試通過，考生需要根據(jù)C++的語法與語義給出正常運行后應(yīng)該輸出的結(jié)果。需要按照程序運行的順序給出正確結(jié)果，不需要對程序的正確性進行判斷。本題型為30分，4---6個題。
程序設(shè)計：按照題中的要求，寫出完整的C++程序，并符合程序設(shè)計規(guī)范。
本題型為25分，2個題。
四、考試形式及時間
考試形式均為筆試，考試時間為三小時（滿分150分）。
五、參考書目
數(shù)據(jù)結(jié)構(gòu)：
1、《數(shù)據(jù)結(jié)構(gòu)》C語言版，嚴為敏吳偉民編，清華大學(xué)出版社，2009.
2、《數(shù)據(jù)結(jié)構(gòu)》(用面向?qū)ο蠓椒ㄅcC++描述)，殷人昆等，清華大學(xué)出版社，2007.
程序設(shè)計：
1、《C++程序設(shè)計》，Y.DanielLiang著，王剛劉曉光劉璟譯，機械工業(yè)出版社
2、《C++編程思想(兩卷合訂本)》?？藸?BruceEckel)、ChuckAllison、劉宗田、袁兆山機械工業(yè)出版社
3、《C++程序設(shè)計語言(特別版o十周年中文紀念版)》斯特朗斯特魯普(BjarneStroustrup)、裘宗燕機械工業(yè)出版社
一、考試的總體要求
本考試內(nèi)容由兩部分組成，數(shù)據(jù)結(jié)構(gòu)和程序設(shè)計，各占總分的50％。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)基礎(chǔ)課,要求學(xué)生掌握基本的數(shù)據(jù)結(jié)構(gòu)及相關(guān)的存儲方式、基本運算、算法和應(yīng)用,并能運用盒圖、結(jié)構(gòu)化語言、類C、高級語言（C或C++）等方法之一編寫算法。程序設(shè)計指采用C++語言，應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識進行面向?qū)ο蟪绦蛟O(shè)計。要求學(xué)生掌握面向?qū)ο蟮某绦蛟O(shè)計方法，掌握C＋＋語言的基本概念，語法及編程方法。
二、考試的內(nèi)容及比例
數(shù)據(jù)結(jié)構(gòu)考試的內(nèi)容包括：（占總分50%）
1、線性表、順序表、鏈表的定義、特點、存儲結(jié)構(gòu)及相關(guān)的基本算法
2、棧的定義、特點、順序與鏈式存儲表示、基本算法；棧的應(yīng)用；隊列的定義、特點；鏈隊列、循環(huán)隊列相關(guān)的定義、特點、基本算法；棧與遞歸的實現(xiàn)
3、廣義表的定義及存儲結(jié)構(gòu)
4、二叉樹的定義、性質(zhì)及存儲結(jié)構(gòu)；遍歷二叉樹定義、過程及其算法；二叉樹的應(yīng)用；樹、森林與二叉數(shù)之間的轉(zhuǎn)換；哈夫曼樹及其應(yīng)用；與二叉樹應(yīng)用相關(guān)的遞歸算法
5、圖的定義、存儲結(jié)構(gòu)；圖的遍歷過程及算法；小生成樹構(gòu)造過程及算法；拓撲排序過程及算法；關(guān)鍵路徑相關(guān)內(nèi)容；短路徑相關(guān)內(nèi)容；與圖的應(yīng)用相關(guān)的遞歸算法
6、靜態(tài)表查找過程及算法、動態(tài)表查找過程及算法；哈希表的構(gòu)造及處理沖突方法
7、插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序等內(nèi)部排序的特點、過程及算法
程序設(shè)計考試的內(nèi)容包括：（占總分50％）
1、基本語法與常用語句，面向?qū)ο蟮幕靖拍?BR> 2、函數(shù)的調(diào)用，函數(shù)參數(shù)，函數(shù)的重載及函數(shù)作用域
3、類的概念，類的定義與說明，類的成員函數(shù)，作用域
4、對象的概念，對象的初始化，對象的特殊生成方法，對象的生存期
5、對象指針和對象引用，對象數(shù)組
6、類的繼承性和派生類
7、虛基類與虛函數(shù)
8、重載及其應(yīng)用
9、模版及其應(yīng)用
10、基本數(shù)據(jù)結(jié)構(gòu)和算法的程序設(shè)計
三、試卷類型及比例
考試題型：
數(shù)據(jù)結(jié)構(gòu)部分：
包括實做題與算法設(shè)計題兩大類：其中實做題有簡述題、舉例說明題、圖示題、圖表題、過程描述題、論述題等。算法設(shè)計題應(yīng)當根據(jù)要求，運用允許使用的適當?shù)姆椒ň帉懰惴ā?BR> 比例：實做題（60%）
算法設(shè)計題（40%）
程序設(shè)計部分：
包括3類題型：程序填空，寫程序結(jié)果和程序設(shè)計。
程序填空題：本題型給出程序的功能描述與少量提示，考生填寫缺少的程序部分，使得程序完整，并且實現(xiàn)描述的功能。
本題型為20分，2---4個題。
寫程序結(jié)果題：本題型給出C++程序，并已經(jīng)調(diào)試通過，考生需要根據(jù)C++的語法與語義給出正常運行后應(yīng)該輸出的結(jié)果。需要按照程序運行的順序給出正確結(jié)果，不需要對程序的正確性進行判斷。本題型為30分，4---6個題。
程序設(shè)計：按照題中的要求，寫出完整的C++程序，并符合程序設(shè)計規(guī)范。
本題型為25分，2個題。
四、考試形式及時間
考試形式均為筆試，考試時間為三小時（滿分150分）。
五、參考書目
數(shù)據(jù)結(jié)構(gòu)：
1、《數(shù)據(jù)結(jié)構(gòu)》C語言版，嚴為敏吳偉民編，清華大學(xué)出版社，2009.
2、《數(shù)據(jù)結(jié)構(gòu)》(用面向?qū)ο蠓椒ㄅcC++描述)，殷人昆等，清華大學(xué)出版社，2007.
程序設(shè)計：
1、《C++程序設(shè)計》，Y.DanielLiang著，王剛劉曉光劉璟譯，機械工業(yè)出版社
2、《C++編程思想(兩卷合訂本)》?？藸?BruceEckel)、ChuckAllison、劉宗田、袁兆山機械工業(yè)出版社
3、《C++程序設(shè)計語言(特別版o十周年中文紀念版)》斯特朗斯特魯普(BjarneStroustrup)、裘宗燕機械工業(yè)出版社