江苏自动化研究所

院校隶属:工业与信息化部    所在地:江苏省
院校类型:  在线咨询

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

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

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

 

 

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

(一)、数据结构部分

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)赋值语句(含条件赋值语句)、条件语句(ifif-elseswitch)、循环语句(whiledo-whilefor语句,包括循环嵌套和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年;