上海海事大学

上海海事大学研究生入学考试考试大纲

考试科目：828数据结构及程序设计

参考书

《数据结构(C语言版)》严蔚敏，清华大学出版社;

《C程序设计(第四版)》谭浩强，清华大学出版社

题型及分数比例

150分

判断题、填空题、选择题共60分;应用题60分;编程题30分

考试大纲：

考试基本要求：

熟练掌握结构化程序设计的方法，具有良好的程序设计风格;系统地理解数据结构的基本概念、基本原理和基本方法;熟练掌握线性表、树、图、查找表等数据结构的逻辑结构、存储结构及基本操作(包括查找和排序等基本算法)的实现，能对算法进行时间复杂度与空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言实现基本数据结构及算法的能力。

考试大纲：

一、程序设计

1、C语言基本数据类型及定义、数据运算及表达式

2、算法流程图表示

3、程序基本结构(顺序、分支、循环)、基本输入输出

4、函数、参数、返回值及其定义与使用

5、复杂数据类型(数组、指针、结构体、共用体等及其复合)的定义与使用

二、数据结构与算法概述

1、数据结构的基本概念和术语 2、算法的描述和算法分析

三、线性表

1、线性表的定义 2、线性表的存储结构及基本操作 3、线性表的应用

四、栈和队列

1、栈和队列的定义 2、栈和队列的存储结构及基本操作 3、栈和队列的应用

五、串

1、串的定义 2、串的存储结构及基本操作 3、串的应用

六、数组和广义表

1、数组和广义表的定义 2、数组和广义表的存储结构及基本操作 3、矩阵的压缩存储 4、数组和广义表的应用

七、树和二叉树

1、树的定义和基本操作 2、二叉树的定义、性质和存储结构及基本操作 3、遍历二叉树和线索二叉树

4、树和森林(存储结构、遍历、与二叉树的互相转换) 5、哈夫曼树及其应用

八、图

1、图的定义 2、图的存储结构 3、图的遍历 4、图的连通性(连通分量、最小生成树) 5、图的拓扑排序、关键路径、最短路径

九、查找

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

3、散列(Hash)表的定义、Hash函数的构造方式、冲突处理和Hash表的查找及其分析

十、内部排序

1、内部排序的基本概念 2、各种(插入类、交换类、选择类、归并类、基数排序)内部排序方法及其分析比较

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

十一、文件

1、有关文件的基本概念 2、顺序文件、索引文件、索引顺序文件、直接存取文件、多重链表文件、倒排文件等的基本存取方法。

[注]：参考书中上述章节的带**部分不作要求