题号901

　　《计算机专业综合》考试大纲

　　C语言上机（内容包含数据结构和算法设计与分析）

　　一、数据结构和算法设计与分析考试内容

　　1.了解数据、数据结构、抽象数据类型以及算法等概念的确切含义，熟悉数据结构的逻辑结构和物理结构，熟练运用C语言描述和使用各类数据结构。

　　2.掌握线性数据结构（包括普通线性表、栈、队列）的逻辑结构和物理存储结构（顺序映像和随机映像）的描述方法，掌握这些线性数据结构上的基本运算操作及其实现方法。了解串、数组、和广义表的逻辑结构和存储方式。知晓线性数据结构各自的特点，并使用线性数据结构解决实际应用问题。

　　3.熟悉树、二叉树的定义、性质及存储方式，重点掌握二叉树的遍历和线性搜索化过程。掌握树与二叉树之间的转换关系和转换算法，二叉树的其它应用问题。掌握二叉排序树的概念，并能用于解决实际问题。

　　4.熟悉图的定义和存储方式，掌握图的广度优先和深度优先遍历算法及其应用，掌握无向图的连通性、连通分量、生成树及最小生成树的算法，掌握有向图的拓扑排序算法和关键路径以及最短路径的求解算法。

　　5.掌握静态查找表、动态查找表的各种查找方法，掌握哈希表的基本概念，哈希表的建立和查找方法，以及相关的冲突问题及其解决方法。能够分析各种查找算法的效率（空间复杂度和时间复杂度）。

　　6.熟练掌握各种内部排序算法（包括简单选择排序、插入排序、快速排序、归并排序、基数排序）的基本思想，能够分析这些排序算法的时间复杂度、空间复杂度和优缺点，并能综合应用这些算法解决实际应用问题。

　　7.结合基本数据结构，了解动态存储管理的基本思想和方法，能够使用边界标识法实现分配和回收策略。

　　8.了解文件的基本概念，掌握基本的文件结构以及文件管理方法。

　　二、参考书目

　　1、《数据结构》（C语言版）严蔚敏、吴伟民等编，清华大学出版社，1997年4月。

　　2、《数据结构习题集（C语言版）》 严蔚敏，吴伟民，清华大学出版社，1998年。

　　3、《数据结构与算法基础》王晓冬编，电子工业出版社，2000年。

　　4、《C语言程序设计》（第二版） 谭浩强编  清华大学出版社

　　5、《算法设计与分析》王晓东  清华大学出版社  2003年1月

　　6、《计算机算法导引》 卢开澄  清华大学出版社  2001年8月