2018年上海海事大学828数据结构及程序设计考研大纲

上海海事大学
2018 年研究生入学考试考试大纲
考
试
科
目
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、顺序文件、索引文件、索
引顺序文件、直接存取文件、多重链表文件、倒排文件等的
基本存取方法。
[注]：参考书中上述章节的带**部分不作要求