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

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

參考書(shū)

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

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

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

150分

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

考試大綱：

考試基本要求：

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

考試大綱：

一、程序設(shè)計(jì)

1、C語(yǔ)言基本數(shù)據(jù)類(lèi)型及定義、數(shù)據(jù)運(yùn)算及表達(dá)式

2、算法流程圖表示

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

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

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

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

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

三、線(xiàn)性表

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

四、棧和隊(duì)列

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

五、串

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

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

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

七、樹(shù)和二叉樹(shù)

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

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

八、圖

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

九、查找

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

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

十、內(nèi)部排序

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

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

十一、文件

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

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