《计算机软件基础》（C程序设计+数据结构）考试大纲

一、考试内容

《数据结构》部分：

1、了解数据、数据结构、抽象数据类型以及算法等概念的确切含义，熟悉数据结构的逻辑结构和物理结构，能够以完整的理论模型定义各种数据结构。

2、熟练掌握线性数据结构（包括普通线性表、栈、队列）的逻辑结构和物理存储结构的描述方法，熟练掌握及这些线性数据结构上的基本运算操作及其实现方法。并能够解决应用问题，了解串、数组、和广义表的逻辑结构和存储方式，能够综合分析线性数据结构各自的特点，并使用线性数据结构解决实际应用问题。

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

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

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

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

7、了解和掌握数据压缩的基本思想和方法，包括运用哈夫曼编码方法实现数据压缩。

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

9、了解文件的基本概念，掌握几种类型的文件结构以及文件和管理的基本方法。

《C程序设计》部分：

要求能熟悉运用C语言的开发环境，如 Visual C++ 6.0 集成开发环境。能够熟练编写C程序，具有纠错和调试程序的能力。掌握程序设计中简单的数据结构和算法如排序。

一、C语言程序的基本结构

理解C程序的组成结构，main函数和其他函数、头文件、函数的开始和结束标志以及注释。

二、数据类型及表达式

掌握数据类型（基本类型，构造类型，指针类型，void类型）的定义和使用。掌握运算符的运算优先级和结合性；不同类型数据间的转换与运算；表达式的定义和使用。

三、基本语句

掌握变量的定义说明，表达式语句，空语句和复合语句。掌握输入输出函数的调用，正确输入和输出数据并能按格式操作。

四、选择结构程序设计

掌握if语句和switch语句，理解和掌握break在switch中的使用。掌握选择结构的嵌套使用。

五、循环结构程序设计

掌握循环结构的编程如for循环结构、while和do-while循环结构。掌握循环体中的continue语句和break语句的使用。掌握循环的嵌套使用。

六、数组的定义和引用

掌握一维数组和二维数组的定义、初始化和数组元素的引用。掌握字符串与字符数组以及相关函数。

七、函数

掌握常用的库函数的使用。掌握函数的定义、参数和返回值的定义、函数原型声明。掌握形参和实参的定义和传递。掌握递归函数的使用。理解和使用局部变量、静态变量、全局变量。掌握变量的存储类别和使用，变量的作用域和生存期。

八、编译预处理

掌握宏定义、文件包含、typedef的定义和使用。

九、指针

理解地址与指针变量的概念，掌握指针的定义、使用和相关运算符。掌握数组指针和字符串的指针操作、能用指针作为函数参数和返回值。理解和掌握指针数组，指向指针的指针。

十、结构体与共同体

掌握结构体和共用体类型数据的定义使用，掌握结构体相关的运算符的使用。能熟练使用结构体构成链表，掌握链表的建立、删除、插入与查找，掌握内存的动态分配和释放。

十一、位运算

掌握位运算符的含义、使用以及简单的位运算操作。

十二、文件操作

掌握文件类型指针（FILE类型指针）的定义和使用。掌握文件的打开与关闭（fopen，fclose）、文件的读写及文件的定位、文件操作的错误判别与处理。

二、试卷结构

1、题分及考试时间

试卷满分为150分，考试时间为180分钟。

2、内容比例

数据结构　 约50%

C程序设计　约50%

3、题型比例

填空题与选择题　约35%

简答题与算法题　约65%