江苏自动化研究所硕士研究生入学考试

《数据结构与程序设计》考试大纲

一、命题范围及考查的知识点

（一）、数据结构部分

1、概述

（1）数据的逻辑结构与存储结构的基本概念；

（2）算法的定义、基本性质以及算法分析的基本概念，包括采用大O形式表示时间或空间复杂度。

2、线性表

（1）线性关系、线性表的定义，线性表的基本操作；

（2）线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理；

(3)在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计(含递归算法的设计)。

3、堆栈与队列

(1)堆栈与队列(含循环队列)的基本概念、基本操作；

(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理；

(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。

4、树与二叉树

(1)树与二叉树的基本概念，基本特征、名词术语；

(2)完全二叉树、满二叉树的概念、二叉树的基本性质；

(3)二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作；

(4)线索二叉树的基本概念以及构造原理；

(5)二叉排序树的基本概念、建立(插入)和查找，在二叉排序树中查找结点的平均查找长度ASL。

5、图

(1)图的基本概念、名词术语；

(2)邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点；

(3)图的深度优先搜索和广度优先搜索的过程，图的遍历的基本作用；

(4)最小生成树及最短路径的特点、求解过程，拓扑排序及其目的。

6、文件及查找

(1)顺序查找法、折半查找法以及查找过程对应的“判定树”的构造；

(2)索引文件的基本概念；

(3)B-树与B+树的构造以及构造上异同，B-树的插入和查找；

(4)散列文件的特点，散列函数和散列冲突的概念，处理散列冲突的方法以及散列文件的查找。

7、内排序

插入排序、选择排序、泡排序、快速排序、堆积排序(大顶堆积)和二路归并排序法等排序方法的排序原理、规律和特点。

（二）、C语言程序设计部分

1、C语言基本知识

（1）C语言的特点以及C语言程序的组成；

（2）数据类型，包括整型、实型、字符型等常量与变量和变量的赋值；用typedef定义类型；

（3）各种类型数据之间的混合运算；

（4）各类运算符的运算规则和优先级；条件运算符；

（5）算术表达式、关系表达式和逻辑表达式，逗号运算符和逗号表达式，表达式sizeof的含义。

2、语句

（1）赋值语句(含条件赋值语句)、条件语句(含if、if-else、switch)、循环语句(含while、do-while、for语句，包括循环嵌套和break语句)；

（2）输入/输出语句，包括整型、实型、字符型(含字符串)等类型数据的格式输入函数scanf和格式输出函数printf。

3、数组

（1）一维数组与二维数组的定义，数组元素的引用，数组的初始化；

（2）字符数组的定义，字符数组的初始化，字符数组的引用，字符数组的输入与输出，字符串和字符串处理函数。

4、函数

（1）函数的定义，函数参数(形参和实参)与函数的返回值；

（2）函数的调用，包括函数的嵌套调用和递归函数的递归调用；

（3）命令行参数的概念（带参数的主函数）。

5、宏定义

（1）带参数的宏定义；

（2）包含文件的处理。

6、指针

（1）指针的概念，变量的指针与指向变量的指针变量，包括定义、引用以及指针变量作为函数参数；

（2）数组的指针，包括指向数组的指针变量的定义与赋值、通过指针引用数组元素、数组名作为函数参数；

（3）字符串的指针与指向字符串的指针变量。

7、结构体

（1）结构体的基本概念和特点，结构体的初始化与引用；

（2）结构体数组。

8、文件

（1）文本文件的基本概念，文本文件的类型指针FILE以及文本文件的使用方式；

（2）文本文件的打开(fopen函数)、文本文件的关闭(fclose函数)；

（3）文本文件的状态，包括feof函数和ferror函数；

（4）文本文件的读写，包括fputc函数和fgetc函数、fgets函数和fputs函数等；

（5）文本文件的输入函数fscanf和输出函数fprintf。

二、考试说明

1、总分满分：150分

2、考试时间：3小时

3、考试方式：笔试

4、考试题型：

填空题（20分）

选择题（20分）

分析计算题（30分）

简答题（30分）

综合应用编程题（50分）

5、数据结构和C语言程序设计分别占75分。

三、主要参考书

1、《数据结构》C语言版） 严蔚敏，清华大学出版社，2007年；

2、《C程序设计》（第四版） 谭浩强，清华大学出版社2010年；