南开大学C++与数据结构2018年大纲

南开大学C++与数据结构2019年大纲

《C++与数据结构》之C++部分考试大纲

一、考试目的

    本考试是全日制软件工程硕士学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围

以下是本科目的考试范围。

    1. 数据封装

1.1 对象占用内存大小；

1.2 类的嵌套定义。

    2. 存取控制

2.1 public，private，friend关键字的含义及使用；

2.2 将一个嵌套的类定义为友元；

2.3 存取控制的应用。

3. 初始化和清理

3.1 构造函数（及何时被调用）；

3.2析构函数（及何时被调用）；

3.3对象数组中对象的构造；
3.4 默认构造函数。

4. 函数重载与默认参数

4.1 函数名的重用；

4.2 默认参数；

4.3 类中的常量；

4.4 初始化列表；

4.5常量对象；

4.6常量成员函数。

5. 内联函数以及名字控制

5.1 内联函数；

5.2 函数中的静态变量与对象；

5.3构造与析构顺序；

5.4名字空间。

6. 引用、复制构造函数以及运算符重载

6.1 复制构造函数；

6.2 默认复制构造函数；

6.3 指向数据成员的指针；

6.4 指向成员函数的指针；

6.5 自动类型转换。

7. 继承与复合

  7.1 继承中的存取控制；

7.2 构造、析构的调用顺序；

7.3 私有继承；

7.4 运算符重载与继承；

7.5 upcasting。

8. 多态性与虚函数

8.1 早/晚绑定；

8.2 虚函数；

8.3 多态性。

9. 模板

9.1 类模板；

9.2 函数模板；

9.3 自动类型推断；

9.4 模板特化；

9.5 容器与迭代器。

三、考试基本要求

1. 掌握C++的基本语法知识。

2. 综合运用C++解决一些基本问题的能力。

四、考试形式

本考试包括两个部分：单项选择题、编程题。

I. 单项选择

考试要求

该部分考察考生对C++基本语法知识的掌握程度。其中大部分选择题要求考生阅读一段程序，理解程序的执行过程，预测程序的输出结果。

II. 编程题 

考试要求

该部分包含两个编程题，每个编程题要求考生综合使用基本的C++知识解决一个基本的问题。每个编程题不涉及复杂的数据结构、算法，代码行数在100行左右。只涉及C++标准库中最常用的类模板、类、函数的使用。涉及的C++知识参“考试的性质与范围”部分。

      答题和计分

要求考生用钢笔或圆珠笔做在答题卷上。

《C++与数据结构》之数据结构部分考试大纲

一、考试目的

    本考试是全日制软件工程硕士学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围

以下是本科目的基础考试范围。

    1.  程序性能

1.1 程序的时间复杂性、空间复杂性及实际复杂性的分析和计算

       1.2 使用渐进符号表示程序的复杂性

    2．线性表

   2.1 线性表的基本概念和基本操作

   2.2 线性表的公式化描述、基本操作及应用

   2.3 线性表的链表描述、基本操作及应用

3．数组和矩阵

3.1 数组的基本概念、存储结构及应用

3.2 矩阵、特殊矩阵、稀疏矩阵的定义、基本操作及应用

4. 栈、队列

   4.1 栈和队列的基本概念及存储结构

   4.2 栈和队列的公式化描述、基本操作及应用

   4.3 栈和队列的链表描述、基本操作及应用

5. 跳表和散列

5.1 跳表的描述、基本操作及应用

5.2 散列的描述、基本操作及应用

6．树与二叉树

   6.1 树和森林的基本概念、性质

   6.2 二叉树的基本概念、描述、性质和基本操作

   6.3 二叉树的遍历

   6.4 树和二叉树的应用

6.5 树、二叉树和森林的相互转化

7. 优先队列

7.1 堆和最大堆的基本概念、基本操作及应用

7.2 最大高度优先左高树的基本概念、基本操作及应用

8. 搜索树

8.1 二叉搜索树的基本概念及基本操作

8.2 AVL树、AVL搜索树的基本概念及基本操作

8.3 B-树的基本概念及基本操作

9．图

   9.1 图的基本概念、性质

   9.2 图的存储与基本操作

   9.3 有向图和无向图的描述

   9.4 图的搜索算法

   9.5 图的应用

10．查找和排序

   10.1 查找的基本概念

   10.2 常用查找算法及复杂性分析

   10.3 排序的基本概念

   10.4常用排序方法及复杂性分析

三、考试基本要求

1. 掌握各种数据结构的基本概念、性质、操作及相关应用。

2. 掌握基础算法的设计思想，并能够综合运用数据结构的知识，设计算法并解决各种问题。

四、考试形式

本考试包括三个部分：填空题、简答题、算法程序题。

I. 填空题

考试要求

该部分考察考生对数据结构基本知识的掌握程度。

II. 简答题

考试要求

该部分考察考生应用常用数据结构以及基础算法的解决问题的能力。

III. 算法程序题

考试要求

该部分考察考生应用常用数据结构进行算法设计、分析和编程的能力。

答题和计分

要求考生用钢笔或圆珠笔做在答题卷上。

   《C++与数据结构》C++部分与数据结构部分合计150分，180分钟。

814  《C++与数据结构》考试大纲

《C++与数据结构》之C++部分考试大纲

一、考试目的

    本考试是全日制软件工程硕士学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围

以下是本科目的考试范围。

    1. 数据封装

1.1 对象占用内存大小；

1.2 类的嵌套定义。

    2. 存取控制

2.1 public，private，friend关键字的含义及使用；

2.2 将一个嵌套的类定义为友元；

2.3 存取控制的应用。

3. 初始化和清理

3.1 构造函数（及何时被调用）；

3.2析构函数（及何时被调用）；

3.3对象数组中对象的构造；
3.4 默认构造函数。

4. 函数重载与默认参数

4.1 函数名的重用；

4.2 默认参数；

4.3 类中的常量；

4.4 初始化列表；

4.5常量对象；

4.6常量成员函数。

5. 内联函数以及名字控制

5.1 内联函数；

5.2 函数中的静态变量与对象；

5.3构造与析构顺序；

5.4名字空间。

6. 引用、复制构造函数以及运算符重载

6.1 复制构造函数；

6.2 默认复制构造函数；

6.3 指向数据成员的指针；

6.4 指向成员函数的指针；

6.5 自动类型转换。

7. 继承与复合

  7.1 继承中的存取控制；

7.2 构造、析构的调用顺序；

7.3 私有继承；

7.4 运算符重载与继承；

7.5 upcasting。

8. 多态性与虚函数

8.1 早/晚绑定；

8.2 虚函数；

8.3 多态性。

9. 模板

9.1 类模板；

9.2 函数模板；

9.3 自动类型推断；

9.4 模板特化；

9.5 容器与迭代器。

三、考试基本要求

1. 掌握C++的基本语法知识。

2. 综合运用C++解决一些基本问题的能力。

四、考试形式

本考试包括两个部分：单项选择题、编程题。

I. 单项选择

考试要求

该部分考察考生对C++基本语法知识的掌握程度。其中大部分选择题要求考生阅读一段程序，理解程序的执行过程，预测程序的输出结果。

II. 编程题 

考试要求

该部分包含两个编程题，每个编程题要求考生综合使用基本的C++知识解决一个基本的问题。每个编程题不涉及复杂的数据结构、算法，代码行数在100行左右。只涉及C++标准库中最常用的类模板、类、函数的使用。涉及的C++知识参“考试的性质与范围”部分。

                     答题和计分

要求考生用钢笔或圆珠笔做在答题卷上。

《C++与数据结构》之数据结构部分考试大纲

一、考试目的

    本考试是全日制软件工程硕士学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围

以下是本科目的基础考试范围。

    1.  程序性能

1.1 程序的时间复杂性、空间复杂性及实际复杂性的分析和计算

       1.2 使用渐进符号表示程序的复杂性

    2．线性表

   2.1 线性表的基本概念和基本操作

   2.2 线性表的公式化描述、基本操作及应用

   2.3 线性表的链表描述、基本操作及应用

3．数组和矩阵

3.1 数组的基本概念、存储结构及应用

3.2 矩阵、特殊矩阵、稀疏矩阵的定义、基本操作及应用

4. 栈、队列

   4.1 栈和队列的基本概念及存储结构

   4.2 栈和队列的公式化描述、基本操作及应用

   4.3 栈和队列的链表描述、基本操作及应用

5. 跳表和散列

5.1 跳表的描述、基本操作及应用

5.2 散列的描述、基本操作及应用

6．树与二叉树

   6.1 树和森林的基本概念、性质

   6.2 二叉树的基本概念、描述、性质和基本操作

   6.3 二叉树的遍历

   6.4 树和二叉树的应用

6.5 树、二叉树和森林的相互转化

7. 优先队列

7.1 堆和最大堆的基本概念、基本操作及应用

7.2 最大高度优先左高树的基本概念、基本操作及应用

8. 搜索树

8.1 二叉搜索树的基本概念及基本操作

8.2 AVL树、AVL搜索树的基本概念及基本操作

8.3 红黑树的基本概念及基本操作

8.3 B-树的基本概念及基本操作

9．图

   9.1 图的基本概念、性质

   9.2 图的存储与基本操作

   9.3 有向图和无向图的描述

   9.4 图的搜索算法

   9.5 图的应用

10．查找和排序

   10.1 查找的基本概念

   10.2 常用查找算法及复杂性分析

   10.3 排序的基本概念

   10.4常用排序方法及复杂性分析

三、考试基本要求

1. 掌握各种数据结构的基本概念、性质、操作及相关应用。

2. 掌握基础算法的设计思想，并能够综合运用数据结构的知识，设计算法并解决各种问题。

四、考试形式

本考试包括三个部分：填空题、简答题、算法程序题。

I. 填空题

考试要求

该部分考察考生对数据结构基本知识的掌握程度。

II. 简答题

考试要求

该部分考察考生应用常用数据结构以及基础算法的解决问题的能力。

III. 算法程序题

考试要求

该部分考察考生应用常用数据结构进行算法设计、分析和编程的能力。

答题和计分

要求考生用钢笔或圆珠笔做在答题卷上。

   《C++与数据结构》C++部分与数据结构部分合计150分，180分钟。

变化情况：

1、新加了“8.3 红黑树的基本概念及基本操作”知识点，其余没变；