《软件综合》考试大纲
（考试时间为3小时，总分为100分）
一、考试大纲的编制依据和适用范围
本考试大纲主要根据陈志泊主编、人民邮电出版社的《面向对象的程序设计语言——C++(第二版)》和严蔚敏主编、清华大学出版社的《数据结构 (C语言)》编制而成。
二、考试内容
《面向对象程序设计语言》部分
1、C++语言概述
（1）C++的产生、发展及特点。
（2）C++程序的基本框架：结构程序设计框架、面向对象程序设计框架等。
（3）C++的词汇：基本符号、保留字、标识符、常量、变量、运算符、标点符号等。
（4）C++程序的开发过程。
2、数据类型、运算符和表达式
（1）C++基本数据类型及其定义方法。
（2）C++的常量定义：逻辑常量、整型常量、实型常量、字符常量、字符串常量、符号常量、枚举常量。
（3）变量的定义与使用方法。
（4）C++运算符的种类、运算优先级和结合性。
（5）C++表达式类型及求值规则：赋值运算、算术运算、关系运算、逻辑运算、条件运算、逗号运算、位运算等。
3、基本控制结构
（1）C++的基本语句：赋值语句、表达式语句、复合语句、输入输出语句、空格语句等。
（2）用if语句实现分支结构。
（3）用switch语句实现多分支选择结构。
（4）用for语句实现循环结构。
（5）用while语句实现循环结构。
（6）用do…while语句实现循环结构。
（7）跳转语句：goto、break、continue、return。
（8）分支语句和循环语句的各种嵌套使用。
4、函数
（1）函数的定义方法和调用方法。
（2）函数的类型和返回值。
（3）形式参数与实际参数，参数值的传递。
（4）变量的作用域、生存周期和存储类别：自动、静态、寄存器、外部。
（5）函数的递归调用。
（6）函数重载。
（7）内联函数。
（8）带有默认参数值的函数。
5、构造数据类型
（1）一维数组、二维数组的定义、初始化和访问。
（2）字符串与字符数组。
（3）常用字符串函数：strcat、strcpy、strcmp、strlen等。
（4）指针和指针变量的概念，指针与地址运算符，指针与数组，指针与字符串。
（5）引用的基本概念、定义和使用。
（6）结构体和共用体的定义，结构体和共用体变量的初始化和引用。
（7）堆内存的分配和释放。
6、类与对象
（1）类的定义方式，数据成员、成员函数及访问权限public、private、protected。
（2）对象和对象指针的定义与使用。
（3）构造函数与析构函数。
（4）静态数据成员与静态成员函数的定义与使用。
（5）常数据成员与常成员函数。
（6）this指针的使用。
（7）友元函数和友元类。
（8）对象数组与成员对象。
7、继承和派生
（1）继承的概念。
（2）派生类的定义和派生类对基类成员的访问权限。
（3）派生类的构造函数和析构函数。
（4）基类指针与派生类指针的使用。
（5）多继承的二义性和虚基类。
（6）多态性的类型和实现。
（7）虚函数机制的要点。
（8）纯虚函数与抽象类。
8、运算符重载
（1）运算符函数。
（2）运算符重载的形式：重载为成员函数、重载为友元函数，运算符重载的限制。
（3）几种典型的运算符的重载。
9、模板
（1）函数模板的定义和使用。
（2）类模板的定义和使用。
10、文件
（1）C++流的概念。
（2）通过FILE结构进行文件操作（打开文件、关闭文件、文件的读写）。
（3）通过文件流进行文件操作（打开文件、关闭文件、文件的读写）。
《数据结构》部分
1、绪论
(1) 数据结构的一些基本概念：逻辑结构、物理结构、算法等。
(2) 算法时间复杂度和空间复杂度的分析。
2、线性表
(1) 线性表的顺序表示和实现。
(2) 线性表的链式表示和实现。
3、栈和队列
(1) 栈的顺序存储和链接存储的表示和实现。
(2) 队列的类型，队列的顺序存储(循环队)和链接存储的表示和实现。
4、数组
一维、二维数组的地址计算方法。
5、树和二叉树
(1) 二叉树的定义、性质和存储结构。
(2) 二叉树的遍历。
(3) 树的应用，哈夫曼树及哈夫曼编码。
6、图
(1) 图的定义和术语。
(2) 图的存储结构两种存储结构：邻接矩阵表示法、邻接表表示法。
(3) 图的两种遍历策略：深度优先搜索和广度优先搜索。
(4) 构造最小生成树的两种算法：普里姆算法和克鲁斯卡尔算法。
(5) 求最短路径问题的算法：迪杰斯特拉算法。
(6) 拓扑排序算法。
7、查找
(1) 静态查找：顺序查找、折半查找。
(2) 动态查找：二叉排序树
(3) 哈希表：哈希函数的构造方法、处理冲突的方法、哈希表的查找。
8、排序
(1) 插入排序：直接插入排序。
(2) 交换排序：冒泡排序和快速排序。
(3) 选择排序：简单选择排序。
(4) 归并排序：2-路归并排序。
三、考试要求
《面向对象程序设计语言》部分
1、理解和掌握面向对象的程序设计方法中的有关概念，如类、对象、封装、继承、消息和多态性等；熟练掌握面向对象程序设计方法与结构化程序设计方法之间的区别和联系；掌握C++程序开发的过程及各环节的主要工作。
2、熟悉和掌握C++中数据类型的分类及使用；熟练掌握C++中各种运算符的使用；熟练掌握C++中表达式的描述和计算；理解和掌握C++中数据的输入和输出。
3、理解和领会C++程序的三种基本结构：顺序、选择和循环结构；熟练掌握两种选择语句：if语句和switch语句；熟练掌握三种循环语句：while循环语句、do-while循环语句和for循环语句；熟练掌握跳转语句break和继续语句continue。
4、了解函数的功能；熟练掌握函数定义及其调用的方法和形式；理解和领会函数重载的意义。
5、理解和掌握数组的定义和使用；理解和掌握指针的定义和使用；熟练掌握C++中结构体的定义和使用。
6、掌握类与对象的概念、定义方法及二者的区别；掌握类的成员函数的定义及调用方法；掌握类中成员的访问机制和方法；理解并掌握构造函数、析构函数的含义、定义方法以及它们在对象的构造和撤消中的作用。
7、理解继承的概念和意义；理解单一继承、多重继承中基类与派生类之间的关系；掌握虚函数和多态性的概念；掌握虚函数的定义方法、调用方法及其在实现多态性方面所起到的作用。
8、了解运算符重载的概念及意义；掌握运算符重载的方法。
9、理解模板的概念。
10、掌握文件的基本概念；掌握文件流进行文件的打开、读写和关闭的方法。
《数据结构》部分
1、掌握数据结构的基本概念，了解抽象数据类型，了解算法的描述方法，掌握算法时间复杂度分析的简易方法。
2、熟练掌握顺序表和链表这两类存储结构的描述方法，掌握循环链表、双向链表的特点等。掌握顺序表、链表的查找、插入和删除算法。能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。
3、掌握栈和队列的特点，并能在相应的应用问题中正确选用。掌握栈的顺序栈和链栈的进栈出栈算法。掌握循环队列和链队列的进队出队算法。
4、掌握一维、二维数组的地址计算方法。
5、掌握二叉树的概念、性质及二叉树的表示。熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作。掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。
6、掌握图的基本概念及相关术语和性质。掌握图的邻接矩阵和邻接表表示法。熟练掌握图的深度优先搜索和广度优先搜索算法思想。掌握构造最小生成树的两种算法的思想，掌握求最短路径问题的迪杰斯特拉算法思想，掌握拓扑排序的思想。
7、熟练掌握顺序表和有序表的查找方法及其实现，掌握二叉排序树的插入和查找算法思想。熟练掌握哈希表的构造方法、处理冲突的方法，深刻理解哈希表与其他结构的表的实质性的差别，了解各种哈希函数的特点。
8、熟练掌握各种排序方法的排序过程，深刻理解各种排序方法的特点及其适用情况。
四、试卷结构
单项选择题
简答题
应用题
编程题
五、考试方式
闭卷笔试。
六、主要参考书
[1] 面向对象的程序设计语言——C++(第二版)，陈志泊主编，人民邮电出版社，2007。
[2] 数据结构(C语言)，严蔚敏编著，清华大学出版社，2008。
