南开《程序设计基础（下）》课程期末复习资料

添加微信apfd6688查看答案,了解更多学习技巧,平 台作业、毕业论文完成时间友情提醒。。

 《程序设计基础（下）》课程期末复习资料

一、客观部分：（单项选择、多项选择、不定项选择、判断）
（一）、选择部分
1．下面关于对象概念的描述中，（     ）是错误的。
A. 对象就是C语言中的结构变量
B. 对象代表着正在创建的系统中的一个实体
C. 对象是一个状态和操作（或方法）的封装体
D. 对象之间的信息传递是通过消息进行的
★考核知识点: 对象
参见讲稿章节：7-1
附1.1.1（考核知识点解释）：
对象是构成世界的一个独立单位（实体），每一个对象具有自己的静态特征和动态特征。静态特征描述了对象的状态；动态特征描述了对象改变状态或提供服务的行为。
2、下面关于类概念的描述中，（     ）是错误的。。
A. 类是抽象数据类型的实现
B. 类是具有共同行为的若干对象的统一描述体
C. 类是创建对象的样板
D. 类就是C语言中的结构体类型
★考核知识点: 类
参见讲稿章节：7-1
附1.1.2（考核知识点解释）：
分类是人类认识客观世界的基本方法，人类认识客观世界是把具有相同性质的对象抽象成类，例如动物、植物、人类、鸟类等。
面向对象方法中的类描述了问题空间中一组有相同的属性（attribute）和方法（method）的对象，即将对象的静态特征抽象成属性，将对象的动态特征抽象成方法。例如，把所有教师抽象成教师类，把所有学生抽象成学生类等。
3、1．关于类和对象不正确的说法是（     ）。
A. 类是一种类型，它封装了数据和操作
B. 对象是类的实例
C. 一个类的对象只有一个
D. 一个对象必属于某个类
★考核知识点: 类和对象之间的关系
参见讲稿章节：7-1
附1.1.3（考核知识点解释）：
对象是构成世界的一个独立单位（实体），每一个对象具有自己的静态特征和动态特征。静态特征描述了对象的状态；动态特征描述了对象改变状态或提供服务的行为。分类是人类认识客观世界的基本方法，人类认识客观世界是把具有相同性质的对象抽象成类，例如动物、植物、人类、鸟类等。
面向对象方法中的类描述了问题空间中一组有相同的属性（attribute）和方法（method）的对象，即将对象的静态特征抽象成属性，将对象的动态特征抽象成方法。例如，把所有教师抽象成教师类，把所有学生抽象成学生类等。
实例就是由某个特定的类所描述的一个具体的对象。
4、面向对象程序设计思想的主要特征中不包括（     ）。
A. 封装性
B. 多态性
C. 继承性
D. 功能分解，逐步求精
★考核知识点: 面向对象程序设计思想
参见讲稿章节：7-1
附1.1.4（考核知识点解释）
封装性、多态性和继承性是面向面向对象程序设计思想的主要特征，而“功能分解，逐步求精”是结构化程序设计的主要特征。
5、下面对构造函数的不正确描述是（     ）。
A. 系统可以提供默认的构造函数
B. 构造函数可以有参数，所以可以有返回值
C. 构造函数可以重载
D. 构造函数可以设置默认参数
★考核知识点: 构造函数
参见讲稿章节：7-2
附1.1.5（考核知识点解释）
对象就是类的一个变量，和其他变量一样，也可以在创建对象时为对象的数据成员赋初值。在C++中，对象的初始化工作是由一个特殊的成员函数——构造函数来完成的，该函数在创建一个对象时被自动调用。设置构造函数的目的主要是用来初始化对象的数据成员。构造函数可以重载，以满足对象多样性的初始化需要。
构造函数是一类特殊函数，其特点如下：
①构造函数名必须与类名相同。
②构造函数没有任何函数返回类型，void也不行。
③任意一个新的对象被创建时，编译系统都会自动调用构造函数，完成对该对象数据成员的初始化工作。
④如果在类定义时没有给出构造函数，系统会自动提供一个默认的无参构造函数：
    <类名>( ) {   }
6、下列（     ）是构造函数的特征。
A. 构造函数在创建对象时自动调用
B. 构造函数不可以重载
C. 构造函数不可以设置默认参数
D. 构造函数必须指定函数类型
★考核知识点: 构造函数
参见讲稿章节：7-2
附1.1.6（考核知识点解释）
对象就是类的一个变量，和其他变量一样，也可以在创建对象时为对象的数据成员赋初值。在C++中，对象的初始化工作是由一个特殊的成员函数——构造函数来完成的，该函数在创建一个对象时被自动调用。设置构造函数的目的主要是用来初始化对象的数据成员。构造函数可以重载，以满足对象多样性的初始化需要。
构造函数是一类特殊函数，其特点如下：
①构造函数名必须与类名相同。
②构造函数没有任何函数返回类型，void也不行。
③任意一个新的对象被创建时，编译系统都会自动调用构造函数，完成对该对象数据成员的初始化工作。
④如果在类定义时没有给出构造函数，系统会自动提供一个默认的无参构造函数：
    <类名>( ) {   }
7、有关构造函数说法不正确的是（     ）。
A. 构造函数的名字和类的名字一样
B. 在创建对象时，系统自动调用构造函数
C. 构造函数无任何函数类型
D. 构造函数有且只有一个
★考核知识点: 构造函数
参见讲稿章节：7-2
附1.1.7（考核知识点解释）
对象就是类的一个变量，和其他变量一样，也可以在创建对象时为对象的数据成员赋初值。在C++中，对象的初始化工作是由一个特殊的成员函数——构造函数来完成的，该函数在创建一个对象时被自动调用。设置构造函数的目的主要是用来初始化对象的数据成员。构造函数可以重载，以满足对象多样性的初始化需要。
构造函数是一类特殊函数，其特点如下：
①构造函数名必须与类名相同。
②构造函数没有任何函数返回类型，void也不行。
③任意一个新的对象被创建时，编译系统都会自动调用构造函数，完成对该对象数据成员的初始化工作。
④如果在类定义时没有给出构造函数，系统会自动提供一个默认的无参构造函数：
    <类名>( ) {   }
8、（   ）的功能是对对象进行初始化。。
A. 析构函数
B. 数据成员
C. 构造函数
D. 静态数据成员
★考核知识点: 构造函数
参见讲稿章节：7-2
附1.1.8（考核知识点解释）
C++中是通过构造函数对对象进行初始化的。
9、3. 下面对友元的描述错误的是（     ）。
A. 关键字friend用于声明友元
B. 一个类的成员函数可以是另一个类的友元
C. 友元函数访问对象的成员不受访问特性影响
D. 友元函数通过this指针访问对象成员
★考核知识点: 类的友员
参见讲稿章节：7-10
附1.1.9（考核知识点解释）
在程序中，如果普通函数或另一个类中的函数需要经常通过类提供的公有接口来间接地访问类的私有成员或保护成员，为了提高程序运行的效率，可以将普通函数声明为类的朋友——友元，它们就可以直接访问类的任何成员了。友元提供了一个一般函数与类的成员之间、不同类的成员之间进行数据共享的机制。
10、3. 一个类的友元函数能够访问该类的（     ）。
A. 私有成员
B. 保护成员
C. 公有成员
D. 所有成员
★考核知识点: 类的友员
参见讲稿章节：7-10
附1.1.10（考核知识点解释）
在程序中，如果普通函数或另一个类中的函数需要经常通过类提供的公有接口来间接地访问类的私有成员或保护成员，为了提高程序运行的效率，可以将普通函数声明为类的朋友——友元，它们就可以直接访问类的任何成员了。
11、友元访问类对象的成员时使用（     ）。
A. 类的成员名
B. “this->成员名”的形式
C. “类名：：成员名”的形式
D. “类名：：成员名”的形式##“对象名.成员名”的形式
★考核知识点: 类成员的访问及类的友员
参见讲稿章节：7-2和7-10
附1.1.11（考核知识点解释）
一个对象创建以后，访问它的数据成员和调用它的成员函数，可通过对象名和对象成员访问运算符“.”，或对象指针和箭头成员访问运算符“->”两种方式完成。
访问对象数据成员的一般形式为：
<对象名>.数据成员名
或
<指向对象的指针名>->数据成员名
调用对象成员函数的一般形式为：
<对象名>.成员函数名([实参])
或
<指向对象的指针名>->成员函数名([实参])
在程序中，如果普通函数或另一个类中的函数需要经常通过类提供的公有接口来间接地访问类的私有成员或保护成员，为了提高程序运行的效率，可以将普通函数声明为类的朋友——友元，它们就可以直接访问类的任何成员了。
 
12、下面选项中，是类的成员函数为（     ）
A. 构造函数
B. 析构函数
C. 友元函数
D. 缺省参数的构造函数
★考核知识点: 构造函数、析构函数、友元函数
参见讲稿章节：7-2、7-4和7-10
附1.1.12（考核知识点解释）
友元函数虽然可以访问类的任何成员，但不是类的成员函数。
13、对基类和派生类的描述中错误的是（     ）。
A. 派生类是基类的具体化
B. 基类继承了派生类的属性
C. 派生类是基类定义的延续
D. 派生类是基类的特殊化
★考核知识点: 继承
参见讲稿章节：8-1
附1.1.13（考核知识点解释）
派生类所表示的事物是基类所表示事物的子集（即派生类所表示的事物比基类更具体）。因此，在一个继承关系中，“派生类事物是基类事物”这句话肯定成立，但反过来却不行。例如，对于Teacher类和Person类的继承关系来说，Teacher类是派生类，Person类是基类，显然“Teacher是Person”这句话是正确的，而反过来说“Person是Teacher”则不行。我们在定义继承关系时可以参照上述方法来检验所定义的继承关系是否合理。
14、继承具有（     ），即当基类本身也是某一个类的派生类时，底层的派生类也会自动继承间接基类的成员。
A. 规律性
B. 传递性
C. 重复性
D. 多样性
★考核知识点: 继承
参见讲稿章节：8-1
附1.1.14（考核知识点解释）
继承具有传递性，即当基类本身也是某一个类的派生类时，底层的派生类也会自动继承间接基类的成员。
15、在C++中，能被派生类继承的函数是（     ）。
A. 成员函数
B. 构造函数
C. 析构函数
D. 拷贝构造函数
★考核知识点: 继承
参见讲稿章节：8-1
附1.1.15（考核知识点解释）
在C++中，成员函数能够被派生类继承。
16、通过类型兼容，对于基类及其公有派生类的对象，可以使用相同的函数统一进行处理。比如，函数参数是基类类型，而实际调用该函数时既可以传入基类对象，也可以传入派生类对象，这就是（     ）。
A. 继承
B. 多态
C. 派生
D. 基类
★考核知识点: 多态
参见讲稿章节：8-2
附1.1.16（考核知识点解释）
通过类型兼容，对于基类及其公有派生类的对象，可以使用相同的函数统一进行处理。比如，函数参数是基类类型，而实际调用该函数时既可以传入基类对象，也可以传入派生类对象，这就是多态。
17、 C++中的多态调用是指（     ）。
A. 以任何方式调用一个虚函数
B. 以任何方式调用一个纯虚函数
C. 借助于指向对象的基类指针或引用调用一个虚函数
D. 借助于指向对象的基类指针或引用调用一个纯虚函数
 [答案]:C
★考核知识点:多态
参见讲稿章节：8-2
附1.1.17（考核知识点解释）
C++中的多态调用是指借助于指向对象的基类指针或引用调用一个虚函数，根据实际对象所属的派生类，调用派生类相应的虚函数。
18、在C++中，要实现动态联编，可以使用（     ）调用虚函数。
A. 类名
B. 派生类指针
C. 基类引用
D. 对象名
★考核知识点:多态
参见讲稿章节：8-2
附1.1.18（考核知识点解释）
在C++中，要实现动态联编，可以使用基类的指针或引用调用虚函数。
19、下列类中（     ）是输入/输出流类iostream的派生类。
A. fstream
B. ofstream
C. ifstream
D. ostream
★考核知识点: 标准输入输出流
参见讲稿章节：9-1
附1.1.19（考核知识点解释）

图 I/O流的类层次关系
 
20、进行文件操作时需要包含（     ）头文件。
A. iostream
B. fstream
C. stdio
D. stdlib
★考核知识点: 标准输入输出流
参见讲稿章节：9-1
附1.1.20（考核知识点解释）
编写程序时，如果使用输入/输出操作，则需要包含头文件iostream；如果使用文件输入/输出操作，则需要包含头文件fstream。
21、在下列选项中（     ）不是ostream类的对象。
A. cin
B. cout
C. clog
D. cerr
★考核知识点: cout和cin对象及插入和提取运算符
参见讲稿章节：9-2
附1.1.21（考核知识点解释）
C++预定义了4个标准流对象：cin、cout、cerr、clog，它们均包含于头文件iostream中。
cin是istream类的对象，用于处理标准输入（即从键盘输入数据到内存中）；
cout是ostream类的对象，用于处理标准输出（即将内存中的数据输出到屏幕上）；
cerr和clog都是ostream类的对象，均用于处理错误信息标准输出。
22、下列的函数模板声明中，正确的是（     ）。
A. template <typename T1, T2>
B. template < template T1, T2>
C. template < template T1, template T2>
D. template <typename T1; typename T2>
★考核知识点: 函数模板
参见讲稿章节：10-1
定义函数模板的一般格式为：
    template <<模板形参表>> <函数类型> <函数名>(<函数形参表>)
    {
    函数体
    }
其中:

• template：定义模板的关键字，指明是函数或类模板。
• 模板形参表：用尖括号括起来，可以是一个或多个模板参数，多个模板参数用“，”分隔。
• 模板参数：由关键字typename及其后面的标识符构成。该标识符对应的实参可以是系统的基本数据类型，也可以是用户自定义的数据类型。

23、下列关于函数模板的描述中，正确的是（     ）。
A. 函数模板和普通函数重载时，函数调用会优先调用符合要求的普通函数
B. 函数模板和普通函数重载时，函数调用会优先调用符合要求的函数模板
C. 函数模板的主要作用是减少可执行程序文件的尺寸
D. 函数模板能够使程序规范
★考核知识点: 函数模板
参见讲稿章节：10-1
附1.1.23（考核知识点解释）
当函数模板与一般函数同名时，遵行下面的调用顺序：
一个函数调用首先寻找参数完全匹配的一般函数，如果找到就调用它；
寻找一个函数模板，使其实例化，生成一个匹配的模板函数，然后调用该模板函数。
24、关于函数模板，描述正确的是（     ）。
A. 函数模板必须由程序员实例化为可执行的函数模板
B. 函数模板的实例化由编译器实现
C. 函数模板和模板函数是一个概念
D. 模板函数就是普通函数
★考核知识点: 函数模板
参见讲稿章节：10-1
附1.1.24（考核知识点解释）
函数模板只是一个模板，需要实例化为具体的函数后才能使用，即需要将模板中数据类型形参实例化为确定的数据类型，这个过程是由编译器完成的。实例化的函数模板称为模板函数。
25、建立类模板对象的实例化过程为（     ）。
A. 基类->派生类
B. 构造函数->对象
C. 模板类->对象
D. 模板类->模板函数
★考核知识点: 类模板
参见讲稿章节：10-2
附1.1.25（考核知识点解释）
类模板与函数模板一样也不能直接使用，必须先实例化为相应的模板类，创建该模板类的对象后才能使用。类模板实例化后称为模板类，模板类具有和普通类相同的行为。
26、类模板的使用实际上是类模板实例化成一个具体的（     ）。
A.  类
B.  对象
C.  函数
D.  变量
★考核知识点: 类模板
参见讲稿章节：10-2
附1.1.26（考核知识点解释）
类模板与函数模板一样也不能直接使用，必须先实例化为相应的模板类，创建该模板类的对象后才能使用。类模板实例化后称为模板类，模板类具有和普通类相同的行为。
27、一个（     ）允许用户为类定义一种模式，使得类中的某些数据成员、某些成员函数的参数和返回值可以取任意数据类型。
A. 函数模板
B. 模板函数
C. 类模板
D. 模板类
★考核知识点: 类模板
参见讲稿章节：10-2
附1.1.27（考核知识点解释）
类模板可以用来描述一个与数据类型无关的类。类模板中类的数据成员和函数成员的参数和返回值可以是任意的数据类型，它描述了一族类的属性和行为，是一族类的统一描述，可以避免类的重复定义。
28、类模板的静态数据成员由（     ）共享。
A. 一个类模板的所有模板类
B. 一个模板类的所有对象
C. 一个模板类的一个对象
D. 一个类模板的所有对象
★考核知识点: 类模板
参见讲稿章节：10-2
附1.1.28（考核知识点解释）
类模板的静态数据成员由一个模板类的所有对象共享。
29、在数据结构中，从逻辑上可以把数据结构分成（     ）。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
★考核知识点: 数据结构的基本概念
参见讲稿章节：11-1
附1.1.29（考核知识点解释）
根据数据结构中各数据元素之间前驱与后继关系的复杂程度，数据的逻辑结构可分为线性结构与非线性结构两大类。
30、下列不属于常用的存储结构的是（     ）。
A. 顺序存储结构
B. 链式存储结构
C. 非线性存储结构
D. 索引存储结构
★考核知识点: 数据结构的基本概念
参见讲稿章节：11-1
附1.1.30（考核知识点解释）
根据数据结构中各数据元素之间前驱与后继关系的复杂程度，数据的逻辑结构可分为线性结构与非线性结构两大类。数据的存储结构也称数据的物理结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。数据的存储结构主要包括顺序存储结构、链式存储结构、索引存储结构和散列存储结构
31、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（     ）。
A. 数据的处理方法
B. 数据元素之间的关系
C. 数据元素的类型
D. 数据的存储方法
★考核知识点: 数据结构的基本概念
参见讲稿章节：11-1
附1.1.31（考核知识点解释）
在计算机机中存储数据时，通常不仅要存储各数据元素的值，而且还要存储数据元素之间的关系。
32、顺序存储结构中数据元素之间的逻辑关系是由（     ）表示的。
A. 线性结构          
B. 非线性结构
C. 指针     
D. 存储位置
★考核知识点: 数据结构的基本概念
参见讲稿章节：11-1
附1.1.32（考核知识点解释）
把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元里，数据元素之间的逻辑关系由存储单元的邻接关系来体现。这样的存储结构称为顺序存储结构。
33、线性表最多有（     ）个结点没有前驱。
A. 1          
B. 2
C. 3   
D. 0
★考核知识点: 数据结构的基本概念
参见讲稿章节：12-1
附1.1.33（考核知识点解释）
对于非空线性表，数据元素之间存在一对一的关系，具体特性如下：
（1）第一个数据元素没有前驱。
（2）最后一个数据元素没有后继。
（3）其他数据元素都是首尾相接、有且只有一个前驱和后继。
34、设线性表有n个元素，以下算法中，(   )在顺序表上实现比在链表上实现效率更高。
A. 输出第i(0≤i≤n—1)个元素值            
B. 交换第0个元素与第1个元素的值
C. 顺序输出这n个元素的值
D. 输出与给定值x相等的元素在线性表中的序号
★考核知识点: 顺序表
参见讲稿章节：12-2
附1.1.34（考核知识点解释）
顺序表具有简单、存储密度大、空间利用率高、存储效率高等优点。但在顺序表中进行插入与删除操作时，往往需要移动大量的数据元素（浪费时间）。
35、设线性表中有n个元素，（     ）操作，在单链表上实现要比在顺序表上实现效率更高。
A. 删除所有值为x的元素
B. 在最后一个元素的后面插入一个新元素
C. 顺序输出前k个元素
D. 交换第i个元素和第n-i-1个元素的值(i=1,1,…,n)
★考核知识点: 链表
参见讲稿章节：12-3
附1.1.35（考核知识点解释）
线性表的链式存储结构是用一组任意的存储单元存储线性表中的数据元素，称为线性链表。线性链表中的结点可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。在插入和删除操作中，不需要移动大量数据。
36、下列关于栈的叙述中正确的是（     ）。
A. 在栈中只能插入数据         
B. 在栈中只能删除数据
C. 栈是先进先出的线性表   
D. 栈是先进后出的线性表
★考核知识点: 栈
参见讲稿章节：13-1
附1.1.36（考核知识点解释）
栈是一种插入和删除操作都只能在表的同一端进行的线性表。栈中元素是以e1，e2，…，en的顺序进栈，而出栈的顺序却是en，…，e2，e1。也就是说，栈是按照“先进后出”（first in last out，FILO）或“后进先出”（last in first out，LIFO）的原则组织数据的。所以，栈也被称为后进先出LIFO、先进后出FILO线性表或下推表。
37、判定一个顺序表示的栈S(最大元素数量为m)为空的条件是（     ）。
A. S->top==0
B. S->top==-1
C.S->top!=m
D.S->top==m
★考核知识点: 栈的表示
参见讲稿章节：13-2
附1.1.37（考核知识点解释）
假设一个空的顺序栈，元素A、B、C、D、E、F依次进栈，然后元素再出栈，则该顺序栈的进栈和出栈动态变化下图所示。

        (a)空栈     (b)插入元素A后 (c)插入元素B、C、  (d)两个元素出      (e)所有元素出
D、E、F后     栈后            栈后    
38、判定一个栈S(最大元素数量为m)为栈满的条件是（     ）。
A. S->top!=0
B. S->top==m
C. S->top==m-1
D. S->top!=m-1
★考核知识点: 栈的表示
参见讲稿章节：13-2
附1.1.38（考核知识点解释）
int MaxSize;        //栈中最大元素个数
当栈中已有MaxSize个元素时，如果再进行进栈操作，则会产生溢出，此时称为上溢（overflow）；而对空栈进行出栈操作时也会产生溢出，此时称为下溢（underflow）。因此，在进行进栈或出栈操作时，应首先检查栈是否为满（IsFull）或是否为空（IsEmpty）。

• IsEmpty()的算法：

    return top==-1;

• IsFull()的算法：

    return top==MaxSize;
39. 队列出队操作时，(    )。
A. 必须判别队列是否满
B. 判别队列元素的类型
C. 必须判别队列是否空
D. 对队列不作任何判别
★考核知识点: 队列的实现
参见讲稿章节：13-4
附1.1.39（考核知识点解释）
队列是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。队列的插入操作也成为入队，允许入队的一端称为队尾（rear）；队列的删除操作也称为出队，允许出队的一端称为队头（front）。不含元素的队列称为空队列。因此，队列又称为“先进先出”（first in first out，FIFO）或“后进后出”（last in last out，LILO）线性表。
只有队列中有元素时，才可以出队。
40. 在一个顺序队列中，队尾指针指向队尾元素的（     ）位置。
A. 当前
B. 下一个
C. 前一个
D. 最后
★考核知识点: 队列的实现
参见讲稿章节：13-4
附1.1.40（考核知识点解释）
采用顺序存储结构的队列称为顺序队列。顺序队列通常用一个一维数组来存放队列中的数据元素。此外，还需设置两个整型变量front和rear，分别指示队头和队尾，称为头指针和尾指针。为了运算的方便，在此约定，在非空队列里，front始终指向队头元素，而rear始终指向队尾元素的下一位置。
 
41. 树最适合用来表示（     ）。
A. 有序数据元素          
B. 无序数据元素
C. 元素之间无联系的数据
D.元素之间具有分支层次关系的数据
★考核知识点:树的基本概念
参见讲稿章节：14-1
附1.1.40（考核知识点解释）
用树型结构表示实体之间联系的层次模型。
 
41.二叉树就是每个结点的度（     ）2的有序树。
A. 大于
B. 小于
C. 等于
D. 小于等于
★考核知识点:二叉树的基本概念
参见讲稿章节：14-3
附1.1.41（考核知识点解释）
二叉树是由n（n≥0）个结点组成的有限集T。当n=0时，称为空二叉树；当n>0时，**T须满足如下条件：
（1）有且仅有一个没有前驱的结点，该结点称为二叉树的根结点。
（2）将根节点去除后，其余结点可分为两个互不相交的子集T1、T2，其中每个子集Ti（i=1, 2）又是一棵二叉树，并分别称为根结点的左子树和右子树。
可见，二叉树就是每个结点的度小于等于2的有序树。
 
42.深度为5的二叉树至多有（     ）个叶子结点。
A. 15
B. 16
C.31
D.10
★考核知识点:二叉树的性质
参见讲稿章节：14-3
附1.1.42（考核知识点解释）
二叉树具有以下几个基本性质。
性质1：在二叉树的第i层上至多有2^i-1个结点（i≥1）。
性质2：深度为k的二叉树至多有2^k-1个结点。
性质3：在二叉树中，若度为0的结点（即叶子结点）数为n₀，度为2的结点数为n₂，则n₀=n₂+1。
性质4：具有n个结点的完全二叉树其深度为ëlog₂nû+1（其中ëlog₂nû表示不大于log₂n的最大整数）。
性质5：采用顺序编号的完全二叉树具有如下性质：
（1）若一个分支结点的编号为i，则其左子树的根结点（即左孩子结点）编号为2*i，右子树的根结点（即右孩子结点）编号为2*i+1；
（2）反之，若一个非根结点的编号为i，则其双亲结点的编号为ëi/2û（其中ëi/2û表示不大于i/2的最大整数）。
43.下列（     ）是图型结构。
A.操作系统中的文件目录结构
B.城市交通网络
C.实数**
D.n维向量
★考核知识点:图的基本概念
参见讲稿章节：15-1
附1.1.43（考核知识点解释）
树型结构主要是用来表示数据元素之间一对多的关系。而在图结构中，结点之间的关系可以是任意的，图中任意两个结点都可能相关，图结构可以用来表示数据元素之间多对多的关系。

（二）、判断部分
1、在面向对象程序设计中，每个对象可以单独设置属性值。（     ）
★考核知识点:面向对象方法的基本概念
参见讲稿章节：7-1
附1.2.1（考核知识点解释）
在面向对象方法中，类是一类相同对象的抽象，一个对象是类的一个实例，可以具有单独的属性值。
2、在一个类中最多只能定义1个构造函数和1个析构函数。（     ）
★考核知识点:C++中的类和对象
参见讲稿章节：7-2
附1.2.2（考核知识点解释）
C++中的构造函数可以有多个，析构函数由于没有参数，因此只能有一个。
3、当建立一个新对象时，程序不会自动调用任何函数。（     ）
★考核知识点:C++中的类和对象
参见讲稿章节：7-2
附1.2.3（考核知识点解释）
C++中，当建立一个新对象时，程序会自动调用构造函数为期成员进行初始化。
4、在类内部定义的public数据可以在类外进行存取。（     ）
★考核知识点:C++中的类的访问控制
参见讲稿章节：7-3
附1.2.4（考核知识点解释）
C++是通过三个关键字public（公有）、private（私有）以及protected（保护）来指定类成员的访问限制的。关键字public、private和protected被称为访问限定符。类成员的访问控制实现了类的封装性。
（1）公有成员：在public（公有） 区域内声明的成员是公有成员。公有成员在程序的任何地方都可以被访问。一般将公有成员限制在成员函数上，使其作为类与外界的接口，程序通过这种函数来操作该类的对象。
（2）私有成员：在private（私有）区域内声明的成员是私有成员。私有成员只能被该类的成员函数或该类的友元访问。一般将类的数据成员和不希望外界知道其实现细节的成员函数声明为private，程序必须通过类的公有成员函数才能间接地访问类的私有成员，从而实现了对类成员的封装。
（3）保护成员：在protected（保护）区域内声明的成员是被保护的成员。被声明为protected（保护）访问级别的数据成员或成员函数只能在该类的内部或其派生类类体中使用，这部分内容将在继承与派生部分中详细讲解。
5、使用关键字class定义的类中默认的访问权限是公有(public)的。（     ）
★考核知识点:C++中的类的访问控制
参见讲稿章节：7-3
附1.2.5（考核知识点解释）
使用关键字class定义的类中默认的访问权限是私有(private)的。
6、说明或定义对象时，类名前面不需要加class关键字。（     ）
★考核知识点:C++中的类和对象
参见讲稿章节：7-2
附1.2.6（考核知识点解释）
定义对象的过程叫做类的实例化，即由类产生一个具体的对象。在C++中，类是一种用户自定义的数据类型，与基本数据类型一样，通过定义类的变量（即对象），才能通过对象来解决实际问题。
对象的定义
定义对象的一般形式为：
        类名 对象名表;
7、拷贝构造函数通常使用已有对象的引用来初始化创建中的对象。（     ）
★考核知识点:C++中的拷贝构造函数
参见讲稿章节：7-5
附1.2.7（考核知识点解释）
C++中除普通的构造函数外，还有一类特殊的构造函数——拷贝构造函数。拷贝构造函数的作用是用一个已经存在的对象来初始化一个正在创建的新对象。拷贝构造函数有如下特征：
（1）拷贝构造函数名与类名相同，形参只有一个，是对象的引用，所以，不能重载拷贝构造函数。拷贝构造函数的原形为：
    <类名>(<类名> &对象名);
（2）拷贝构造函数无任何函数返回类型说明。
（3）如果在类声明中没有给出拷贝构造函数，系统会自动给出一个默认的拷贝构造函数，该拷贝构造函数只进行对象数据成员间的对位拷贝，即所谓的“浅拷贝”。
（4）在某些情况下，用户必须在类定义中给出一个显式的拷贝构造函数，以实现用户指定的用一个对象初始化另一个对象的功能，即所谓的“深拷贝”。
（5）在以下3种情况下，系统会自动调用拷贝构造函数：
①当使用下面的声明语句用一个已存在的对象初始化一个新对象时，系统会自动调用拷贝构造函数：
    <类名><新对象名>(<已存在对象名>);
或
    <类名><新对象名>=<已存在对象名>;
②对象作为实参，在函数调用开始进行实参和形参结合时，会自动调用拷贝构造函数，完成由已知的实参对象初始化形参新对象的功能。
③如果函数的返回值是类的对象，在函数调用完成返回时，系统自动调用拷贝构造函数，用return后面的已知对象来初始化一个临时新对象（所创建的临时对象只在外部表达式范围内有效，表达式结束时，系统将自动调用析构函数撤销该临时对象）。
8、在多文件结构汇总，一般将C++中的类声明和类实现分别放到两个文件中。（     ）
★考核知识点:C++中类声明与实现的分离
参见讲稿章节：7-6
附1.2.8（考核知识点解释）
为了实现类的复用，一般将类声明在一个独立的头文件中。C++允许将类的声明和实现分离。类的声明描述了类的结构，包括类的所有数据成员、函数成员和友元。类的实现定义了成员函数的具体功能。类的声明和实现放在两个不同的文件中，这两个文件具有相同的文件名、不同的扩展名。类声明文件的扩展名为“.h”，类实现文件的扩展名为“.cpp”。
 
9、类的静态成员函数中不能访问非静态成员。（     ）
★考核知识点:C++中类的静态成员
参见讲稿章节：7-7
附1.2.9（考核知识点解释）
在类的成员前如果加上关键字static修饰的成员就是类的静态成员。类的静态成员包括静态数据成员和静态成员函数。类的静态成员的特点是：

• 静态成员属于类，不属于任何对象。
• 静态成员函数没有this指针。因此，静态成员函数不能访问一般的数据成员，它只能访问静态数据成员，也只能调用其他的静态成员函数。
• 无论对象是否存在，类的一个静态数据成员都只有一个，存于公用内存中，可被该类的所有对象共享。

10、C++语言中,既允许单继承,又允许多继承。（     ）
★考核知识点:继承
参见讲稿章节：8-1
附1.2.10（考核知识点解释）
如果一个派生类是基于一个基类创建的，则该继承关系称为单继承；如果一个派生类是基于多个基类创建的，则该继承关系称为多继承。
11、派生类的继承方式中有两种:公有继承和私有继承（     ）
★考核知识点:继承
参见讲稿章节：8-1
附1.2.11（考核知识点解释）
派生类的继承方式中有三种:公有继承、私有继承和受保护继承。
12、在私有继承中,基类中只有公有成员对派生类是可见的。（     ）
★考核知识点:继承
参见讲稿章节：8-1
附1.2.12（考核知识点解释）
 三种继承方式的对基类成员的访问控制

13、当类的继承方式为公有继承时，基类的私有成员在派生类中不可直接访问。（     ）
★考核知识点:继承
参见讲稿章节：8-1
附1.2.13（考核知识点解释）
三种继承方式的对基类成员的访问控制

14、通过指针或引用可以调用不同对象相同名称的函数，但可导致完全不同的行为的现象称为二义性。（     ）
★考核知识点:多态
参见讲稿章节：8-2
附1.2.14（考核知识点解释）
通过指针或引用可以调用不同对象相同名称的函数，但可导致完全不同的行为的现象称为多态。
15、在C++中，虚函数帮助实现了类的封装性。（     ）
★考核知识点:多态
参见讲稿章节：8-2
附1.2.15（考核知识点解释）
C++通过虚函数实现“动态绑定”技术。虚函数的声明方法是在基类的函数声明前或函数定义的函数头前（无函数声明时）加上virtual关键字
16、定义虚函数所用的关键字是class。（     ）
★考核知识点:多态
参见讲稿章节：8-2
附1.2.16（考核知识点解释）
定义虚函数所用的关键字是virtual。C++通过虚函数实现“动态绑定”技术。虚函数的声明方法是在基类的函数声明前或函数定义的函数头前（无函数声明时）加上virtual关键字
17、多态性是指同样的消息被不同对象接收时可产生不同的行为。（     ）
★考核知识点:多态
参见讲稿章节：8-2
附1.2.17（考核知识点解释）
多态性是指同样的消息被不同对象接收时可产生不同的行为。
18、具有纯虚函数的类是抽象类,它的特点是不可以定义对象。（     ）
★考核知识点:抽象类
参见讲稿章节：8-3
附1.2.18（考核知识点解释）
C++还提供了一种“抽象类”。抽象类不能实例化对象，它的唯一用途是为其他类提供合适的基类，其他类可从它这里继承和（或）实现接口。
一个类是抽象类还是具体类，主要看其是否包含纯虚函数，包含纯虚函数的类就是抽象类。纯虚函数就是在声明时初始化为0、没有函数体的虚函数，其声明形式为：
    virtual <函数类型> 纯虚函数名(<形参类型表>) = 0;
19、含有虚函数的类是抽象类。（     ）
★考核知识点:抽象类
参见讲稿章节：8-3
附1.2.19（考核知识点解释）
含有纯虚函数的类是抽象类，而不是虚函数。
20、定义纯虚函数所用的关键字是purevirtual。（     ）
★考核知识点:抽象类
参见讲稿章节：8-3
附1.2.20（考核知识点解释）
C++还提供了一种“抽象类”。抽象类不能实例化对象，它的唯一用途是为其他类提供合适的基类，其他类可从它这里继承和（或）实现接口。
一个类是抽象类还是具体类，主要看其是否包含纯虚函数，包含纯虚函数的类就是抽象类。纯虚函数就是在声明时初始化为0、没有函数体的虚函数，其声明形式为：
    virtual <函数类型> 纯虚函数名(<形参类型表>) = 0;
21、C++中ostream类的直接基类是ios。（     ）
★考核知识点:输入输出流基本概念
参见讲稿章节：9-1
附1.2.21（考核知识点解释）
计算机所做的任何数据处理工作都是在内存中进行。一般来说，待处理的数据是从输入设备获取，而处理结果则会输出到输出设备上。输入/输出（Input/Output，简称为I/O）是数据传送的过程，其中，输入是指将数据从输入设备传送到内存的过程，而输出则是指将数据从内存传送到输出设备的过程。C++将数据的输入/输出过程形象地称为流，并定义了相应的输入/输出流类和一些代表标准输入/输出设备的流对象，以方便数据的输入/输出操作。C++用继承方法建立了I/O流类库，其类层次关系如下图所示。
 

图 I/O流的类层次关系
其中，streambuf类和ios类是两个平行的基类，其他类都是它们的直接或间接派生类。streambuf类为输入/输出操作提供内存缓冲区支持；filebuf类从streambuf派生，为文件输入/输出操作提供内存缓冲区支持。在进行输入/输出操作时，数据会先放在缓冲区中，待缓冲区满或遇到结束符时，才真正进行数据读写操作。ios类是一个抽象基类，提供一些对流状态、工作方式等设置的功能。通过对ios类进行虚拟继承得到istream类和ostream类两个派生类。输入流类istream提供输入操作功能，输出流类ostream提供输出操作功能。输入/输出流类iostream是对istream类和ostream类进行多重继承得到的派生类，同时具有输入、输出功能。ifstream类是istream类的派生类，用于支持从磁盘文件的输入操作（即从文件中读取数据到内存中）；ofstream类是ostream类的派生类，用于支持向磁盘文件的输出操作（即将内存中的数据写入到文件中）；fstream类是iostream类的派生类，支持磁盘文件的输入/输出操作。编写程序时，如果使用输入/输出操作，则需要包含头文件iostream；如果使用文件输入/输出操作，则需要包含头文件fstream。
22、C++中，预定义的提取符>>和插入符<<是不可以重载的。（     ）
★考核知识点: cout和cin对象及插入和提取运算符
参见讲稿章节：9-2
附1.2.22（考核知识点解释）
输入/输出操作时经常使用的“<<”和“>>”分别是ostream类和istream类中重载的运算符。
系统提供的istream类也已经对“>>”进行了多次重载，能够用于处理对多种内部类型数据的输入操作。重载的形式如下：
    istream& operator>>(int);       // 从输入设备提取一个int型数据到内存中
    istream& operator>>(double);// 从输入设备提取一个double型数据到内存中
    istream& operator>>(char*); // 从输入设备提取一个字符串数据到内存中
    ……                            // 对其他类型数据的“>>”运算符重载
系统提供的ostream类已经对“<<”进行了多次重载，能够实现对不同类型数据的输出操作。重载的形式如下：
ostream& operator<<(int);   // 将内存中的一个int型数据输出到输出设备
ostream& operator<<(double);   // 将内存中的一个double型数据输出到输出设备
ostream& operator<<(char*); //将内存中的一个字符串数据输出到输出设备
    ……                        // 对其他类型数据的“<<”运算符重载
23、cin是输出流的一个对象，处理标准输出。（     ）
★考核知识点: cout和cin对象及插入和提取运算符
参见讲稿章节：9-2
附1.2.23（考核知识点解释）
cout是输出流的一个对象，处理标准输出。
24、使用打开文件函数open()之前，需要定义一个流类对象，使用open()函数来操作该对象。（     ）
★考核知识点: 文件流对象
参见讲稿章节：9-4
附1.2.24（考核知识点解释）
对文件进行输入/输出即读/写操作，必须先定义文件流对象并打开某个文件（即将流对象与文件建立关联）；然后，就可以使用流对象进行文件的读/写操作；操作完毕后关闭文件（即将流对象与文件的关联断开）。
定义文件流对象实际上就是使用文件流类定义类对象，与前面学习的定义类对象的方法完全相同。打开文件使用文件流类的成员函数open()，其函数原型为：
    void open(const char* filename, int mode);
filename是要打开的文件名，
mode是文件的打开方式
25、以app方式打开文件时，当前的读指针和写指针都定位于文件头。（     ）
★考核知识点: 文件流对象
参见讲稿章节：9-4
附1.2.25（考核知识点解释）
以app方式打开文件时，当前的读指针和写指针都定位于文件尾。
26、getline()函数从流中提取终止字符，但终止字符被丢弃。（     ）
★考核知识点: 使用成员函数进行标准输出和输入
参见讲稿章节：9-3
附1.2.26（考核知识点解释）
输入流类提供了用于输入字符串的成员函数getline()，输入流对象可以调用这个函数实现从输入设备读取一个字符串的操作。
getline()有3个参数，输入流对象调用getline()的格式为：
    in.getline(字符数组名或字符型指针, 字符个数n, 终止标识符)
其中，in为输入流对象，既可以是cin对象，也可以是自定义的文件流对象。
函数调用时，从输入设备读取n-1个字符，并在其后加上字符串结束符'\0'，构成一个字符串存入第1个参数所指向的内存空间中。若在读取够n-1个字符前遇到由第3个参数指定的终止标识符，则提前结束读取。终止标识符参数的默认值是'\n'，也可以通过传递实参指定为其他字符。若读取成功，函数返回值为真（非0）值，若读取失败（遇到文件结束符EOF），函数返回值为假（0）值。
27、使用模板可以减少重复劳动,提高代码重用率。（     ）
★考核知识点:模板
参见讲稿章节：10
附1.2.27（考核知识点解释）
泛化编程是对抽象的算法的编程，泛化是指可以广泛的适用于不同的数据类型。模板是泛化编程的主要方法之一。模板的特点在于它的参数不仅是我们传统函数中所说的数值形式的参数，还可以是一种类型。
28、一个函数模板只生成一个模板函数。（     ）
★考核知识点:函数模板
参见讲稿章节：10-1
附1.2.28（考核知识点解释）
函数模板只是一个模板，需要实例化为具体的函数后才能使用，即需要将模板中数据类型形参实例化为确定的数据类型。实例化的函数模板称为模板函数。根据数据类型的不同，可以生成多个模板函数。
29、类模板可以生成若干个模板类,每个模板类又可定义若干个对象。（     ）
★考核知识点:类模板
参见讲稿章节：10-2
附1.2.29（考核知识点解释）
类模板与函数模板一样也不能直接使用，必须先实例化为相应的模板类，创建该模板类的对象后才能使用。类模板实例化后称为模板类，模板类具有和普通类相同的行为。类模板可以生成若干个模板类,每个模板类又可定义若干个对象。
30、数据结构中的数据元素是数据的不可分割的最小单位。（     ）
★考核知识点:数据结构的基本概念
参见讲稿章节：11-1
附1.2.30（考核知识点解释）
数据项是数据的不可分割的最小单位，又称数据域。数据项是数据结构中讨论的最小单位，数据元素是数据项的**。
31、数据的存储结构是指对数据进行存储时，各数据元素在计算机中的存储关系。（     ）
★考核知识点:数据结构的基本概念
参见讲稿章节：11-1
附1.2.31（考核知识点解释）
数据结构是研究计算机的操作对象（数据）以及它们之间的关系和操作等的学科，目的是提高计算机的数据处理效率并节省存储空间。数据结构主要研究下面3个方面的问题：
（1）数据的逻辑结构：在数据**中，各种数据元素之间固有的逻辑关系。
（2）数据的存储结构：在对数据进行存储时，各数据元素在计算机中的存储关系。
（3）数据结构的操作：各种数据结构要进行的操作，以及基于计算机中的存储方式如何实现这些操作。各种数据结构的操作有所不同，但一般都包含插入、删除、查找、更新、排序等常用的基本操作。
32、线性结构只能用顺序存储结构表示。（     ）
★考核知识点:数据结构的基本概念
参见讲稿章节：11-1
附1.2.32（考核知识点解释）
线性结构既可以用顺序存储结构表示、也可以用链式结构表示。
33、线性表的逻辑顺序与物理顺序总是一致的。（     ）
★考核知识点:线性表的基本概念
参见讲稿章节：12-1
附1.2.33（考核知识点解释）
线性表的链式存储中，逻辑顺序与物理顺序往往是不一致的。
34、在需要经常做元素随机访问操作的情况下，线性表的顺序存储结构比链式存储结构更好。（     ）
★考核知识点:线性表的顺序存储结构
参见讲稿章节：12-1
附1.2.34（考核知识点解释）
在需要经常做元素随机访问操作的情况下，线性表的顺序存储结构比链式存储结构更好。在经常进行插入和删除操作的情况下，线性表的链式存储结构比顺序存储结构更好。
35、对链表进行插入和删除操作时，需要移动链表中的结点。（     ）
★考核知识点:线性表的链式存储结构
参见讲稿章节：12-2
附1.2.35（考核知识点解释）
对链表进行插入和删除操作时，不需要移动链表中的结点，只需要修改指针的指向即可。
36、栈是操作受限的线性表，只允许在表的一端进行元素插入操作、在另一端进行元素删除操作。（     ）
★考核知识点:栈的基本概念
参见讲稿章节：13-1
附1.2.36（考核知识点解释）
栈是操作受限的线性表，只允许在表的一端进行元素插入和删除操作。
37、进栈操作，在顺序存储结构上需要考虑“溢出”情况。（     ）
★考核知识点:栈的实现
参见讲稿章节：13-2
附1.2.37（考核知识点解释）
进栈操作，在顺序存储结构上因为要提前确定栈的最大规模，因此需要考虑“溢出”情况，链式存储结构则通常认为内存足够大，不需要考虑溢出。
38、对同一输入序列进行两次不同的合法的入栈和出栈操作，所得的输出序列不一定相同。（     ）
★考核知识点:栈的基本概念
参见讲稿章节：13-1
附1.2.38（考核知识点解释）
对同一输入序列进行两次不同的合法的入栈和出栈操作，由于其先进后出的性质，所得的输出序列不一定相同。
39、在用顺序表表示的循环队列中，可用表示队列元素数量的成员变量作为区分队空或队满的条件。（     ）
★考核知识点:队列的基本概念
参见讲稿章节：13-3
附1.2.39（考核知识点解释）
要解决判断循环队列是“空”还是“满”的问题，可以采用以下两种方法：
（1）约定少用一个元素空间。入队前，如果关系“(rear+1)%MaxSize==front”存在，就认为队列已满，再要插入就会发生溢出。可见，这种方法rear始终指向那个空闲的元素空间。
（2）使用一个计数器size记录当前队列的实际长度。如果size=0，则当“front==rear”时，当前队列是空队列，可以进行入队操作；否则，当前队列满，不能进行入队操作。
40、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（     ）
★考核知识点:队列的基本概念
参见讲稿章节：13-3
附1.2.40（考核知识点解释）
队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进先出型结构。
41、在通信、数据压缩等领域被广泛应用的哈夫曼树采用的是二叉树结构。（     ）
★考核知识点:哈夫曼树和哈夫曼编码
参见讲稿章节：14-7
附1.2.41（考核知识点解释）
在通信、数据压缩等领域被广泛应用的哈夫曼树采用的是二叉树结构。
42、由于顺序表示完全二叉树时空间利用率较低，因此，二叉树的顺序表示在实际中应用很多。（     ）
★考核知识点:二叉树的表示
参见讲稿章节：14-3
附1.2.42（考核知识点解释）
由于顺序表示非完全二叉树时空间利用率较低，因此，二叉树的顺序表示在实际中应用不多。
43、满二叉树是完全二叉树。（     ）
★考核知识点:二叉树的概念及性质
参见讲稿章节：14-2
附1.2.43（考核知识点解释）
满二叉树和完全二叉树是两种特殊形态的二叉树。
满二叉树是指除了最后一层的结点为叶子结点外其它结点都有左、右两棵子树的二叉树。完全二叉树是指其结点与相同深度的满二叉树中的结点编号完全一致的二叉树。
44、无向图的邻接矩阵是对称的。（     ）
★考核知识点:图的表示方法
参见讲稿章节：15-2
附1.2.44（考核知识点解释）
无向图的邻接矩阵是对称的，有向图的邻接矩阵不是对称的。
45、在图的一条路径中，若一个顶点至多只经过一次，则该路径称为简单路径。（     ）
★考核知识点:图的基本概念
参见讲稿章节：15-1
附1.2.45（考核知识点解释）
在一条路径中，若一个顶点至多只经过一次，则该路径称为简单路径；若组成路径的顶点序列中第一个顶点与最后一个顶点相同，则该路径称为回路（或环）；在一个回路中，若除第一个顶点与最后一个顶点外，其他顶点只出现一次，则该回路称为简单回路（或简单环）。46、在有n个顶点的有向图中，每个顶点的度最大可达n-1。（     ）
★考核知识点:图的基本概念
参见讲稿章节：15-1
附1.2.46（考核知识点解释）
在有向图G中，若存在<vi, vj>∈E(G)，则称顶点vi邻接到顶点vj，或顶点vj邻接自顶点vi。以顶点vi为弧头的弧的数目称为顶点vi的入度；以顶点vi为弧尾的弧的数目称为vi的出度；顶点vi的入度和出度之和称为vi的度。因此，在有n个顶点的有向图中，每个顶点的度最大可达2n-2。
47、广度优先遍历类似于树的逐层遍历。（     ）
★考核知识点:图的遍历
参见讲稿章节：15-3
附1.2.47（考核知识点解释）
图的遍历是指从某一顶点出发按照某种规则依次访问图中的所有顶点，且每个顶点只被访问一次。根据搜索路径的不同，图的遍历通常采有两种方法：广度优先遍历和深度优先遍历。
广度优先遍历类似于树的逐层遍历，即先从某一个顶点开始访问，然后访问与该顶点相邻接且未被访问过的顶点集V1(G)，再访问与V1(G)中顶点相邻接且未被访问过的顶点集V2(G)，重复该过程直至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通图，还要从某一个未被访问的顶点开始重复上一过程，直至所有顶点访问完毕。
深度优先遍历类似于树的先序遍历，即从某一个顶点开始访问，访问后将该顶点去除得到若干子图，对每个子图再依次进行深度优先遍历。

二、主观部分：
（一）、程序填空部分
1、下面程序中用来求数组元素的和。请将程序补充完整，使程序的输出为:s＝150。
#include <iostream>
using namespace std;
class IntArray
{
private:
    int Size;
    int *p;
public:
    IntArray()
    {
        Size=0;
        p=NULL;
    }
    IntArray(int *aa, int n)
    {
        Size=n;
        p=new int[n]; 
        for(int i=0;i<n;i++)
            *(p+i)=*(aa+i);
    }
    ~IntArray()
    {
        delete []p;
    }
    int GetValue(int i)
    {
        return *(p+i);
    }
};
int main()
{
    int b[5]={5,20,15,35,25};
    IntArray a(b,5);
    int i=0,s=0;
    for(;i<5;i++)
        s+=a.GetValue(i);
    cout<<"s="<<s<<endl;
    return 0;
}
★考核知识点：C++中的类和对象
参见讲稿章节：7-2——7-4
附2.1.1：（考核知识点解释）
详见教材7-2——7-4。
2、下面的程序是在ARRAY类中重载运算符[],程序的运行结果为“A[3]=4”,请将程序补充完整。
#include <iostream>
using namespace std;
class ARRAY
{  
private:
    int *v;
    int s;
public:
    ARRAY( int a[], int n );
    ~ARRAY( )
    {   
        delete []v; 
    }                                 
    int size()
    { 
        return s; 
    }
    int& operator[](int i);
};
ARRAY::ARRAY(int a[], int n)      
{ 
    if( n<=0 )
    { 
        v=NULL;
        s=0;
        return; 
    }
    s=n;
    v= new int[s] ;
    for(int i=0; i<n; i++)
        v[i]=a[i];
}
int& ARRAY::operator[](int i)
{
    return v[i];
}
 
int main()
{
    int a[5]={1,2,3,4,5};
    ARRAY A(a,5);
    cout<<"A[3]="<< A[3];
    return 0;
}
★考核知识点：自定义类的运算符重载
参见讲稿章节：7-12
附2.1.2：（考核知识点解释）
详见教材7-12
3、下面程序中用来求数组元素的最大值。请将程序补充完整，使程序的输出为:max＝30。
#include <iostream>
using namespace std;
class SHUZU
{
private:
    int Size;
    int *p;
public:
    SHUZU()
    {
        Size=0;
        p=NULL;
    }
    SHUZU(int *aa, int n)
    {
        Size=n;
        p=new int[n]; 
        for(int i=0;i<n;i++)
            *(p+i)=*(aa+i);
    }
    ~SHUZU()
    {
        delete []p;
    }
    int GetValue(int i)
    {
        return *(p+i);
    }
};
int main()
{
    int a[7]={25,15,10,30,20,3,7};
    SHUZU A(a,7);
    int max;
    max=A.GetValue(1);
    ,for(int i=1;i<7;i++)
    {
        if (max<A.GetValue(i))
            max=A.GetValue(i);
    }
    cout<<"max="<<max<<endl;
    return 0;
}
 ★考核知识点：C++中的类和对象
参见讲稿章节：7-2——7-4
附2.1.3：（考核知识点解释）
详见教材7-2——7-4
4、下面的程序是在str类中重载运算符=，请将程序补充完整，使程序的输出结果为：
he
she
he
he
#include <iostream>
using namespace std;
class str
{
private:
 char *st;
public:
 str(char *a)
 {
     set(a);
 }
 str & operator=(  str& a   )
 {
     delete []st;
     set(a.st);
     return *this;
 }
 void show()
 {
     cout<<st<<endl;
 }
 ~str()
 {
     delete []st;
 }
 void set(char *s)
 { 
     st=new char[strlen(s)+1];
     strcpy(st,s);
 }
};
int main()
{
    str s1("he"),s2("she");
    s1.show();
    s2.show();
    s2=s1
    s1.show();
    s2.show();
}
★考核知识点：自定义类的运算符重载,构造函数，析构函数
参见讲稿章节：7-12，7-2,7-4
附2.1.4：（考核知识点解释）
详见教材7-12,7-2,7-4
 
 
（二）、读程序写结果题
1、 已知结点类和二叉链表表示二叉树类的声明如下：
#include<iostream>
using namespace std;
//节点类
class Node
{
    friend class LinkedBinTree;
public:
    Node(const int &x)
{
        m_pLeftChild = m_pRightChild = NULL;
        m_data = x;
}
private:
    int m_data;
    Node *m_pLeftChild, *m_pRightChild;
};
//二叉链表表示二叉树类
class LinkedBinTree
{
public:
    LinkedBinTree();    // 创建空二叉树
    Node* CreateRoot(const int &x);     // 以指定元素值创建根结点
    // 将一个结点作为指定结点的左孩子插入
    Node* InsertLeftChild(Node *pNode, const int &x);
    // 将一个结点作为指定结点的右孩子插入
    Node* InsertRightChild(Node *pNode, const int &x);
    // 获取指定结点的元素值
    bool GetNodeValue(Node *pNode, int &x);
    // 获取指定结点的左孩子结点
    Node* GetLeftChild(Node *pNode);
    // 获取指定结点的右孩子结点
    Node* GetRightChild(Node *pNode);
private:
    Node *m_pRoot;  //指向根结点的指针
};
void BinTreeTraverse(LinkedBinTree &btree, Node *pNode)
{
    int x;
    if (pNode == NULL) return;
    btree.GetNodeValue(pNode, x);
    cout << x;
    BinTreeTraverse(btree, btree.GetLeftChild(pNode));
    BinTreeTraverse(btree, btree.GetRightChild(pNode));
}
……// LinkedBinTree的其他成员函数的实现略
 
int main()
{
    LinkedBinTree btree;
    Node *pNode1, *pNode2, *pNode3, *pNode4, *pNode5, *pNode6, *pNode7, *pNode8, *pNode9;
    pNode1 = btree.CreateRoot(1);
    pNode2 = btree.InsertLeftChild(pNode1, 2);
    pNode3 = btree.InsertRightChild(pNode1, 3);
    pNode4 = btree.InsertLeftChild(pNode2, 4);
    pNode5 = btree.InsertLeftChild(pNode3, 5);
    pNode6 = btree.InsertRightChild(pNode3, 6);
    pNode7 = btree.InsertLeftChild(pNode4, 7);
    pNode8 = btree.InsertRightChild(pNode4, 8);
    pNode9 = btree.InsertLeftChild(pNode6, 9);
    BinTreeTraverse(btree, pNode2);
    cout << endl;
    BinTreeTraverse(btree, pNode3);
    cout << endl;
    return 0;
}
请写出执行主函数后在屏幕上的输出结果。
 
★考核知识点：二叉树的遍历及常用操作
参见讲稿章节：14-4
[答案]:
2478
3569
2、已知结点类模板和链接队列类模板的声明如下:
//存储结点类
template<class T>
class LinkNode    //结点类
{
   template<class T>
   friend class LinkQueue;//将链接队列类声明为友类
public:
   LinkNode();//构造函数
private:
   T data;          //结点元素
   LinkNode<T> *next;  //指向下一个结点的指针
};
//链接队列类
template<class T>
class LinkQueue
{
public:
   LinkQueue();                 //创建空队列
   ~LinkQueue();                    //删除队列
   bool IsEmpty();  //判断队列是否为空，空返回true，非空返回false
   bool Insert(const T& x);     //入队，在队列尾部插入元素x
   bool GetElement(T& x);       //求队头元素的值放入x中
   bool Delete(T& x);   //出队，从队头删除一个元素，并将该元素的值放入x中
   void OutPut(ostream& out)const;  //输出队列
private:
   int size;                //队列实际元素个数
   LinkNode<T>* front,*rear;    //队列的队头和队尾指针
};
int main()
{
   int x1, x2, x3;
   LinkQueue<int> q;
   q.Insert(1);
   q.Insert(1);
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   q.Insert(x3);
   cout<<x3<<endl;
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   cout<<x3<<endl;
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
★考核知识点：队列的表示与实现
参见讲稿章节：13-4
[答案]：
2
3
3、已知顺序表类模板的C++描述如下：
template<class T>
class LinearList
{
public:
   LinearList(int LLMaxSize);   //构造函数，创建空表
   ~LinearList();           //析构函数，删除表
   LinearList<T>& Insert(int k,const T& x);
                    //在第k个位置插入元素x，返回插入后的线性表
   bool IsEmpty() const;       
                    //判断表是否为空，表空返回true，表非空返回false
   int GetLength() const;       //返回表中数据元素的个数
   bool GetData(int k,T& x);       
                    //将表中第k个元素保存到x中，不存在则返回false
   bool ModifyData(int k,const T& x);
                    //将表中第k个元素修改为x，不存在则返回false
   int Find(const T& x);    //返回x在表中的位置，如果x不在表中返回0
   LinearList<T>& DeleteByIndex(const int k, T& x);
            //删除表中第k个元素，并把它保存到x中，返回删除后的线性表
   LinearList<T>& DeleteByKey(const T& x,T& y);
            //删除表中关键字为x元素，返回删除后的线性表
   void OutPut(ostream& out) const;
            //将线性表放到输出流out中输出
private:
   int length;          //当前数组元素个数
   int MaxSize;         //线性表中最大元素个数
   T *element;          //一维动态数组
};
int main()
{
   LinearList<int> IntegerLList(10);
   int x;
   IntegerLList.Insert(1,50);
   IntegerLList.Insert(1,100);
   IntegerLList.Insert(1,150);
   IntegerLList.Insert(1,250);
   cout<<IntegerLList.GetLength()<<endl;
   IntegerLList.GetData(3,x);
   cout<<x<<endl;
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
★考核知识点：线性表的顺序存储结构与实现
参见讲稿章节：12-2
[答案]:
 4
100
 
4、已知结点类模板和链接队列类模板的声明如下:
//存储结点类
template<class T>
class LinkNode    //结点类
{
   template<class T>
   friend class LinkQueue;//将链接队列类声明为友类
public:
   LinkNode();//构造函数
private:
   T data;          //结点元素
   LinkNode<T> *next;  //指向下一个结点的指针
};
//链接队列类
template<class T>
class LinkQueue
{
public:
   LinkQueue();                 //创建空队列
   ~LinkQueue();                    //删除队列
   bool IsEmpty();  //判断队列是否为空，空返回true，非空返回false
   bool Insert(const T& x);     //入队，在队列尾部插入元素x
   bool GetElement(T& x);       //求队头元素的值放入x中
   bool Delete(T& x);   //出队，从队头删除一个元素，并将该元素的值放入x中
   void OutPut(ostream& out)const;  //输出队列
private:
   int size;                //队列实际元素个数
   LinkNode<T>* front,*rear;    //队列的队头和队尾指针
};
int main()
{
   int x1, x2, x3;
   LinkQueue<int> q;
   q.Insert(5);
   q.Insert(8);
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   q.Insert(x3);
   cout<<x3<<endl;
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   cout<<x3<<endl;
   return 0;
}
写出主函数main执行后在屏幕上的输出结果。
★考核知识点：队列的实现
参见讲稿章节：13-4
[答案]：
13
21
5、已知顺序表类模板的C++描述如下：
template<class T>
class LinearList
{
public:
   LinearList(int LLMaxSize);   //构造函数，创建空表
   ~LinearList();           //析构函数，删除表
   LinearList<T>& Insert(int k,const T& x);
                    //在第k个位置插入元素x，返回插入后的线性表
   bool IsEmpty() const;       
                    //判断表是否为空，表空返回true，表非空返回false
   int GetLength() const;       //返回表中数据元素的个数
   bool GetData(int k,T& x);       
                    //将表中第k个元素保存到x中，不存在则返回false
   bool ModifyData(int k,const T& x);
                    //将表中第k个元素修改为x，不存在则返回false
   int Find(const T& x);    //返回x在表中的位置，如果x不在表中返回0
   LinearList<T>& DeleteByIndex(const int k, T& x);
            //删除表中第k个元素，并把它保存到x中，返回删除后的线性表
   LinearList<T>& DeleteByKey(const T& x,T& y);
            //删除表中关键字为x元素，返回删除后的线性表
   void OutPut(ostream& out) const;
            //将线性表放到输出流out中输出
private:
   int length;          //当前数组元素个数
   int MaxSize;         //线性表中最大元素个数
   T *element;          //一维动态数组
};
int main()
{
   LinearList<int> IntegerLList(10);
   int i,x;
   for(i=1;i<11;i++)
       IntegerLList.Insert(i,i*5);
   for(i=2;i<=3;i++)
   {
      IntegerLList.DeleteByIndex(i,x);
      cout<<x<<endl;
   }
   cout<<endl;
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
★考核知识点：线性表的顺序存储结构与实现
参见讲稿章节：12-2
[答案]：
10
20
 
6、已知结点类模板和二叉树二叉链表表示类模板的声明如下:
// 结点类模板
template<class T>
class LinkedNode
{
   template<class T>
   friend class LinkedBinTree;
public:
   LinkedNode();    //构造函数
   LinkedNode(const T &x);  //构造函数
private:
    T m_data;
    LinkedNode<T> *m_pLeftChild, *m_pRightChild;
};
……// LinkedNode成员函数的实现略
 
// 二叉树二叉链表表示类模板
template<class T>
class LinkedBinTree
{
public:
   LinkedBinTree(); // 创建空二叉树
   ~LinkedBinTree();    // 删除二叉树
   bool IsEmpty();                  // 判断二叉树是否为空
   LinkedNode<T>* CreateRoot(const T &x);   // 以指定元素值创建根结点
   void Clear();        // 清空二叉树
   LinkedNode<T>* GetRoot();    // 获取根结点
   // 将一个结点作为指定结点的左孩子插入
   LinkedNode<T>* InsertLeftChild(LinkedNode<T> *pNode, const T &x);
   // 将一个结点作为指定结点的右孩子插入
   LinkedNode<T>* InsertRightChild(LinkedNode<T> *pNode, const T &x);
   // 修改指定结点的元素值
   bool ModifyNodeValue(LinkedNode<T> *pNode, const T &x);
   // 获取指定结点的元素值
   bool GetNodeValue(LinkedNode<T> *pNode, T &x);
   // 获取指定结点的左孩子结点
   LinkedNode<T>* GetLeftChild(LinkedNode<T> *pNode);
   // 获取指定结点的右孩子结点
   LinkedNode<T>* GetRightChild(LinkedNode<T> *pNode);
   // 删除以指定结点为根的子树
   void DeleteSubTree(LinkedNode<T> *pNode);
private:
    LinkedNode<T> *m_pRoot;  //指向根结点的指针
};
template <class T>
void BinTreeTraverse(LinkedBinTree<T> &btree, LinkedNode<T> *pNode)
{
   T x;
   if (pNode==NULL) return;
   BinTreeTraverse(btree, btree.GetLeftChild(pNode));
   BinTreeTraverse(btree, btree.GetRightChild(pNode));
btree.GetNodeValue(pNode, x);
   cout<<x;
  
}
……// LinkedBinTree的其他成员函数的实现略
 
int main()
{
   LinkedBinTree<char> btree;
   LinkedNode<char> *pNodeA, *pNodeB, *pNodeC, *pNodeD, *pNodeE, *pNodeF, *pNodeG, *pNodeH, *pNodeI;
   // 创建一棵二叉树
   pNodeI = btree.CreateRoot('I');
   pNodeH = btree.InsertLeftChild(pNodeI, 'H');
   pNodeG = btree.InsertRightChild(pNodeI, 'G');
   pNodeF = btree.InsertRightChild(pNodeH, 'F');
   pNodeE = btree.InsertLeftChild(pNodeG, 'E');
   pNodeD = btree.InsertRightChild(pNodeG, 'D');
   pNodeC = btree.InsertLeftChild(pNodeF, 'C');
   pNodeB = btree.InsertLeftChild(pNodeE, 'B');
   pNodeA = btree.InsertRightChild(pNodeE, 'A');
   DeleteSubTree(pNodeE);
   BinTreeTraverse(btree, pNodeA);
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
★考核知识点：二叉树的遍历及常用操作
参见讲稿章节：14-4
[答案]：CFHDGI
7、已知顺序表类模板的C++描述如下：
template<class T>
class LinearList
{
public:
   LinearList(int LLMaxSize);   //构造函数，创建空表
   ~LinearList();           //析构函数，删除表
   LinearList<T>& Insert(int k,const T& x);
                    //在第k个位置插入元素x，返回插入后的线性表
   bool IsEmpty() const;       
                    //判断表是否为空，表空返回true，表非空返回false
   int GetLength() const;       //返回表中数据元素的个数
   bool GetData(int k,T& x);       
                    //将表中第k个元素保存到x中，不存在则返回false
   bool ModifyData(int k,const T& x);
                    //将表中第k个元素修改为x，不存在则返回false
   int Find(const T& x);    //返回x在表中的位置，如果x不在表中返回0
   LinearList<T>& DeleteByIndex(const int k, T& x);
            //删除表中第k个元素，并把它保存到x中，返回删除后的线性表
   LinearList<T>& DeleteByKey(const T& x,T& y);
            //删除表中关键字为x元素，返回删除后的线性表
   void OutPut(ostream& out) const;
            //将线性表放到输出流out中输出
private:
   int length;          //当前数组元素个数
   int MaxSize;         //线性表中最大元素个数
   T *element;          //一维动态数组
};
int main()
{
   LinearList<int> IntegerLList(10);
   int i,x;
   for(i=1;i<11;i++)
       IntegerLList.Insert(i,i*5);
   for(i=3;i<5;i++)
   {
      IntegerLList.DeleteByIndex(i,x);
      cout<<x<<endl;
   }
   cout<<endl;
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
 
[答案]：
15
25
★考核知识点：线性表的顺序存储结构与实现
参见讲稿章节：12-2
8、已知结点类模板和二叉树二叉链表表示类模板的声明如下:
// 结点类模板
template<class T>
class LinkedNode
{
   template<class T>
   friend class LinkedBinTree;
public:
   LinkedNode();    //构造函数
   LinkedNode(const T &x);  //构造函数
private:
    T m_data;
    LinkedNode<T> *m_pLeftChild, *m_pRightChild;
};
……// LinkedNode成员函数的实现略
 
// 二叉树二叉链表表示类模板
template<class T>
class LinkedBinTree
{
public:
   LinkedBinTree(); // 创建空二叉树
   ~LinkedBinTree();    // 删除二叉树
   bool IsEmpty();                  // 判断二叉树是否为空
   LinkedNode<T>* CreateRoot(const T &x);   // 以指定元素值创建根结点
   void Clear();        // 清空二叉树
   LinkedNode<T>* GetRoot();    // 获取根结点
   // 将一个结点作为指定结点的左孩子插入
   LinkedNode<T>* InsertLeftChild(LinkedNode<T> *pNode, const T &x);
   // 将一个结点作为指定结点的右孩子插入
   LinkedNode<T>* InsertRightChild(LinkedNode<T> *pNode, const T &x);
   // 修改指定结点的元素值
   bool ModifyNodeValue(LinkedNode<T> *pNode, const T &x);
   // 获取指定结点的元素值
   bool GetNodeValue(LinkedNode<T> *pNode, T &x);
   // 获取指定结点的左孩子结点
   LinkedNode<T>* GetLeftChild(LinkedNode<T> *pNode);
   // 获取指定结点的右孩子结点
   LinkedNode<T>* GetRightChild(LinkedNode<T> *pNode);
   // 删除以指定结点为根的子树
   void DeleteSubTree(LinkedNode<T> *pNode);
private:
    LinkedNode<T> *m_pRoot;  //指向根结点的指针
};
template <class T>
void BinTreeTraverse(LinkedBinTree<T> &btree, LinkedNode<T> *pNode)
{
   T x;
   if (pNode==NULL) return;
   btree.GetNodeValue(pNode, x);
   cout<<x;
   BinTreeTraverse(btree, btree.GetLeftChild(pNode));
   BinTreeTraverse(btree, btree.GetRightChild(pNode));
}
……// LinkedBinTree的其他成员函数的实现略
 
int main()
{
   LinkedBinTree<char> btree;
   LinkedNode<char> *pNodeA, *pNodeB, *pNodeC, *pNodeD, *pNodeE, *pNodeF, *pNodeG, *pNodeH, *pNodeI;
   // 创建一棵二叉树
   pNodeI = btree.CreateRoot('I');
   pNodeH = btree.InsertLeftChild(pNodeI, 'H');
   pNodeG = btree.InsertRightChild(pNodeI, 'G');
   pNodeF = btree.InsertRightChild(pNodeH, 'F');
   pNodeE = btree.InsertLeftChild(pNodeG, 'E');
   pNodeD = btree.InsertRightChild(pNodeG, 'D');
   pNodeC = btree.InsertLeftChild(pNodeF, 'C');
   pNodeB = btree.InsertLeftChild(pNodeE, 'B');
   pNodeA = btree.InsertRightChild(pNodeE, 'A');
   DeleteSubTree(pNodeE);
   BinTreeTraverse(btree, pNodeA);
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
[答案]：IHFCGD
★考核知识点：二叉树的遍历及常用操作
参见讲稿章节：14-4
9、已知结点类模板和链接队列类模板的声明如下：
//存储结点类
template<class T>
class LinkNode    //结点类
{
   template<class T>
   friend class LinkQueue;//将链接队列类声明为友类
public:
   LinkNode();//构造函数
private:
   T data;          //结点元素
   LinkNode<T> *next;  //指向下一个结点的指针
};
//链接队列类
template<class T>
class LinkQueue
{
public:
   LinkQueue();                 //创建空队列
   ~LinkQueue();                    //删除队列
   bool IsEmpty();  //判断队列是否为空，空返回true，非空返回false
   bool Insert(const T& x);     //入队，在队列尾部插入元素x
   bool GetElement(T& x);       //求队头元素的值放入x中
   bool Delete(T& x);   //出队，从队头删除一个元素，并将该元素的值放入x中
   void OutPut(ostream& out)const;  //输出队列
private:
   int size;                //队列实际元素个数
   LinkNode<T>* front,*rear;    //队列的队头和队尾指针
};
int main()
{
   int x1, x2, x3;
   LinkQueue<int> q;
   q.Insert(2);
   q.Insert(3);
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   q.Insert(x3);
   cout<<x3<<endl;
   q.Delete(x1);
   q.GetElement(x2);
   x3 = x1+x2;
   cout<<x3<<endl;
   return 0;
}
请写出主函数main执行后在屏幕上的输出结果。
[答案]：
5
8
★考核知识点：队列的实现
参见讲稿章节：13-4