991数据结构与C语言程序设计考试大纲(2008版).doc

1 江苏自动化研究所硕士研究生入学考试《数据结构与程序设计》考试大纲一、命题范围及考查的知识点(一) 、数据结构部分 1、概述(1)数据的逻辑结构与存储结构的基本概念; (2) 算法的定义、基本性质以及算法分析的基本概念,包括采用大?形式表示时间或空间复杂度。 2、线性表(1)线性关系、线性表的定义,线性表的基本操作; (2) 线性表的顺序存储结构与链式存储结构( 包括单链表、循环链表和双向链表) 的构造原理; (3) 在以上两种存储结构的基础上对线性表实施的基本操作,包括顺序表的插入和删除、链表的建立、插入和删除、检索等操作对应的算法设计( 含递归算法的设计)。 3 、堆栈与队列(1) 堆栈与队列(含循环队列)的基本概念、基本操作; (2) 堆栈与队列的顺序存储结构与链式存储结构的构造原理; (3) 在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作。 4 、树与二叉树(1) 树与二叉树的基本概念,基本特征、名词术语; (2) 完全二叉树、满二叉树的概念、二叉树的基本性质; (3) 二叉树的顺序存储结构与二叉链表存储结构的构造原理、二叉树的前序遍历、中序遍历、后序遍历和按层次遍历算法(重点为非递归算法)以及利用遍历解决有关二叉树的其它操作; (4) 线索二叉树的基本概念以及构造原理; (5) 二叉排序树的基本概念、建立( 插入) 和查找,在二叉排序树中查找结点的平均查找长度 ASL 。 5、图(1) 图的基本概念、名词术语; (2) 邻接矩阵存储方法和邻接表存储方法的基本构造原理与特点; (3) 图的深度优先搜索和广度优先搜索的过程,图的遍历的基本作用; (4) 最小生成树及最短路径的特点、求解过程,拓扑排序及其目的。 6 、文件及查找(1) 顺序查找法、折半查找法以及查找过程对应的“判定树”的构造; 2 (2) 索引文件的基本概念; (3) B-树与 B+ 树的构造以及构造上异同, B-树的插入和查找; (4) 散列文件的特点,散列函数和散列冲突的概念,处理散列冲突的方法以及散列文件的查找。?、?排序插入排序、??排序、?排序、??排序、堆?排序(大?堆?)和二路归?排序法等排序方法的排序原理、??和特点。(二)、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)函数的定义,函数?数(形?和实?)与函数的???