上海海事大學(xué)研究生入學(xué)考試考試大綱

考試科目：828數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計

參考書

《數(shù)據(jù)結(jié)構(gòu)(C語言版)》嚴(yán)蔚敏，清華大學(xué)出版社;

《C程序設(shè)計(第四版)》譚浩強，清華大學(xué)出版社

題型及分?jǐn)?shù)比例

150分

判斷題、填空題、選擇題共60分;應(yīng)用題60分;編程題30分

考試大綱：

考試基本要求：

熟練掌握結(jié)構(gòu)化程序設(shè)計的方法，具有良好的程序設(shè)計風(fēng)格;系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法;熟練掌握線性表、樹、圖、查找表等數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作(包括查找和排序等基本算法)的實現(xiàn)，能對算法進行時間復(fù)雜度與空間復(fù)雜度的分析;能夠運用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進行問題的分析與求解，具備采用C語言實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu)及算法的能力。

考試大綱：

一、程序設(shè)計

1、C語言基本數(shù)據(jù)類型及定義、數(shù)據(jù)運算及表達式

2、算法流程圖表示

3、程序基本結(jié)構(gòu)(順序、分支、循環(huán))、基本輸入輸出

4、函數(shù)、參數(shù)、返回值及其定義與使用

5、復(fù)雜數(shù)據(jù)類型(數(shù)組、指針、結(jié)構(gòu)體、共用體等及其復(fù)合)的定義與使用

二、數(shù)據(jù)結(jié)構(gòu)與算法概述

1、數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語 2、算法的描述和算法分析

三、線性表

1、線性表的定義 2、線性表的存儲結(jié)構(gòu)及基本操作 3、線性表的應(yīng)用

四、棧和隊列

1、棧和隊列的定義 2、棧和隊列的存儲結(jié)構(gòu)及基本操作 3、棧和隊列的應(yīng)用

五、串

1、串的定義 2、串的存儲結(jié)構(gòu)及基本操作 3、串的應(yīng)用

六、數(shù)組和廣義表

1、數(shù)組和廣義表的定義 2、數(shù)組和廣義表的存儲結(jié)構(gòu)及基本操作 3、矩陣的壓縮存儲 4、數(shù)組和廣義表的應(yīng)用

七、樹和二叉樹

1、樹的定義和基本操作 2、二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)及基本操作 3、遍歷二叉樹和線索二叉樹

4、樹和森林(存儲結(jié)構(gòu)、遍歷、與二叉樹的互相轉(zhuǎn)換) 5、哈夫曼樹及其應(yīng)用

八、圖

1、圖的定義 2、圖的存儲結(jié)構(gòu) 3、圖的遍歷 4、圖的連通性(連通分量、最小生成樹) 5、圖的拓?fù)渑判�、關(guān)鍵路徑、最短路徑

九、查找

1、順序表、有序表的查找及其分析 2、二叉排序樹和平衡二叉樹、B樹

3、散列(Hash)表的定義、Hash函數(shù)的構(gòu)造方式、沖突處理和Hash表的查找及其分析

十、內(nèi)部排序

1、內(nèi)部排序的基本概念 2、各種(插入類、交換類、選擇類、歸并類、基數(shù)排序)內(nèi)部排序方法及其分析比較

3、外部排序的基本概念與方法

十一、文件

1、有關(guān)文件的基本概念 2、順序文件、索引文件、索引順序文件、直接存取文件、多重鏈表文件、倒排文件等的基本存取方法。

[注]：參考書中上述章節(jié)的帶**部分不作要求