一、考試基本要求
《數據結構與高級程序設計》(科目代碼：804)是我校電子信息專(zhuān)業(yè)碩士生入學(xué)考試的專(zhuān)業(yè)基礎課之一?？荚嚹繕耸且罂忌莆崭呒壋绦蛟O計的基本概念、各種數據類(lèi)型及基本程序設計方法，掌握各種數據結構的特點(diǎn)、存儲表示、運算方法以及在計算機科學(xué)中最基本的應用，并具備選用合適的數據結構，利用高級編程語(yǔ)言(C 語(yǔ)言)編寫(xiě)質(zhì)量高、風(fēng)格好的應用程序的能力。合格考生應當達到全國普通高等院校計算機專(zhuān)業(yè)優(yōu)秀本科畢業(yè)生的水平，具有較好的計算機理論基礎。
考試對象為報考我校專(zhuān)業(yè)碩士研究生入學(xué)考試的準考考生。
二、試題類(lèi)型及分值
1. 答卷方式：閉卷、筆試
2. 試卷總分：150 分(其中高級程序設計占 70 分，數據結構部分占 80 分)
3. 題型比例：
第一部分：高級程序設計(共 70 分)
選擇題、填空題、程序閱讀題、編程題。
第二部分：數據結構部分(共 80 分)
選擇題、簡(jiǎn)答題、分析題、計算題、編程題。
三、考試時(shí)間：3 小時(shí)
四、考試內容
1. 第一部分：高級程序設計
(1)掌握程序的基本結構;變量與數據類(lèi)型;變量聲明與賦值。熟練掌握 C 語(yǔ)言程序的基本結構;掌握基本變量的聲明與訪(fǎng)問(wèn)。
(2)掌握關(guān)系運算符與關(guān)系表達式;枚舉法的思路;循環(huán)結構;分支結構。理解 C 語(yǔ)言最基本的運算符與關(guān)系表達式的概念;熟練掌握運算符與關(guān)系表達式的最基本使用;理解枚舉法的基本思想;熟練掌握枚舉法的最基本使用;理解循環(huán)結構;熟練掌握循環(huán)結構的最基本使用(for 語(yǔ)句與 while 語(yǔ)句);理解分支結構;熟練掌握分支結構的最基本使用。
(3)掌握數組與一維數組的基本使用;篩法與排序法;結構與結構數組;二維數組。理解數組的基本概念;熟練掌握一維數組的基本使用;掌握二維數組的基本使用;理解篩法與排序法;掌握篩選法與排序法的最基本的使用。理解結構的基本概念;熟練掌握結構的基本使用;掌握結構數組的基本使用。
(4)掌握函數的基本概念、使用與應用;遞推;遞歸。理解函數的基本概念;熟練掌握函數的定義、聲明、調用、返回的基本操作;了解遞推數列的定義與算法的程序實(shí)現;了解遞歸及其實(shí)現的基本思路與方法。
(5)掌握指針的基本概念與基本使用;指針與數組;字符串及其處理;指針與結構;指針與結構數組;引用的概念與應用;利用引用來(lái)傳遞參數;幾種參數傳遞方式的比較。理解指針的基本概念;掌握指針的基本使用;掌握指針與數組(一維)的基本使用;掌握字符串的基本使用;了解指針與結構;了解指針與結構數組;理解引用概念;掌握引用基本使用;了解利用引用傳遞參數;掌握幾種參數傳遞方式的比較。
(6)掌握流的基本概念與常用輸入輸出流格式控制;文件流;理解 I/O 流、文件流的基本概念;熟練掌握 I/O 流與文件流的基本使用;了解 I/O 流與文件流的格式控制。
2. 第二部分：數據結構
(1)了解數據結構和算法的形成和發(fā)展及在計算學(xué)科中所處的地位，并掌握數據結構和算法的基本概念和術(shù)語(yǔ)、算法描述及算法分析的基本方法。
(2)熟練掌握順序線(xiàn)性表和鏈式線(xiàn)性表(重點(diǎn)單鏈表)及其基本操作，以及簡(jiǎn)單應用;順序存儲和鏈式存儲的優(yōu)缺點(diǎn)。
(3)掌握棧和隊列的結構特征、順序存儲結構、基本操作及其簡(jiǎn)單應用;講述棧與遞歸的關(guān)系，掌握核心概念——遞歸。
(4)掌握數組的定義及地址公式、特殊矩陣的存儲方式及地址公式、稀疏矩陣的三元組存儲方式及基本運算;了解廣義表的基本概念。
(5)掌握樹(shù)及二叉樹(shù)的基本概念、基本性質(zhì)和存儲結構;熟練掌握二叉樹(shù)的各種遍歷(前序、中序、后序、層次)和恢復;掌握樹(shù)、森林與二叉樹(shù)的關(guān)系，及其相互轉換方法;熟練掌握哈夫曼樹(shù)及其編碼的算法。
(6)掌握圖的基本概念和存儲結構(鄰接矩陣、鄰接表)，掌握圖的基本類(lèi)型與運算(連通圖、有向無(wú)環(huán)圖、圖的遍歷)及各類(lèi)典型應用(最小生成樹(shù)、拓撲排序、關(guān)鍵路徑、最短路徑)。
(7)掌握各類(lèi)存儲結構的查找算法(順序查找、折半查找、分塊查找、二叉排序樹(shù)查找)，理解靜態(tài)查找與動(dòng)態(tài)查找的區別，掌握哈希表的基本思想、函數構造、沖突處理方法及查找)。
(8)掌握內部排序的基本概念及其常用排序方法(插入排序、二分插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數排序)，掌握各種不同排序方法的適用場(chǎng)合。
五、參考書(shū)目
1.《數據結構》嚴蔚敏，清華大學(xué)出版社
2.《C 程序設計》譚浩強，清華大學(xué)出版社，2010 年
