一、单选题（每题 2 分，共 30 分）

1. 关于 $\tt C$++ 类和对象的说法，错误的是（ ）。

{{ select(1) }}

• 在 $\tt C$++ 中，一切皆对象，即便是字面量如整数 $5$ 等也是对象
• 在 $\tt C$++ 中，可以自定义新的类，并实例化为新的对象
• 在 $\tt C$++ 中，内置函数和自定义函数，都是类或者对象
• 在 $\tt C$++ 中，可以在自定义函数中嵌套定义新的函数

2. 有关下面 $\tt C$++ 代码的说法，错误的是（ ）。

   class Rectangle {
   private:
   	class Point {
   	public:
   		double x;
   		double y;
   	};
   
   	Point a, b, c, d;
   	double length;
   	double width;
   };
   

{{ select(2) }}

• $\tt C$++ 中类内部可以嵌套定义类
• 在类中定义的类被称为内部类，定义类的类被称为外部类
• 内部类可以随便访问，不需要通过外部类来访问
• 代码中 $\tt Point$ 被称为内部类，可以通过外部类 $\tt Rectangle$ 来访问 $\tt Rectangle::Point$

3. 有关下面 $\tt C$++ 代码的说法，正确的是（ ）。

   class newClass {
   public:
   	static int objCounter;
   };
   
   int newClass::objCounter = 2;
   
   int main() {
   	newClass classA;
   	newClass classB;
   
   	cout << newClass::objCounter << endl;
   	cout << classB.objCounter << endl;
   }
   

{{ select(3) }}

• 第 $14$ 行代码错误，第 $15$ 行正确
• 第 $15$ 行代码错误，第 $14$ 行代码正确
• 第 $14$、$15$ 两行代码都正确
• 第 $6$ 行代码可修改为 objCounter += 1

4. 有关下面 $\tt C$++ 代码的说法，错误的是（ ）。

   struct BiNode {
   	char data;
   	BiNode* lchild, *rchild;
   };
   
   class BiTree {
   private:
   	BiNode* Creat();
   	void Release(BiNode* bt);
   	BiNode* root;
   public:
   	BiTree() {
   		root = Creat();
   	}
   	~BiTree() {
   		Release(root);
   	}
   }
   

{{ select(4) }}

• 上述 $\tt C$++ 代码适用于构造各种二叉树
• 代码 struct BiNode ⽤于构造二叉树的节点
• 代码 BiTree() { root = Creat(); } ⽤于构造二叉树
• 析构函数不可以省略

5. 基于第 $4$ 题的定义，有关下面 $\tt C$++ 代码的说法正确的是（ ）。

   void Order(BiNode* bt) {
   	if (bt == nullptr)
   		return ;
   	else {
   		cout << bt->data;
   		Order(bt->lchild);
   		Order(bt->rchild);
   	}
   }
   

{{ select(5) }}

• 代码中 $\tt Order()$ 函数是中序遍历二叉树的方法
• 代码中 $\tt Order()$ 先访问根节点，然后对左子树进行前序遍历，再对右子树前序遍历
• 代码中 $\tt Order()$ 先访问中序遍历左子树，然后访问根节点，最后则是中序遍历右子树
• 代码中 $\tt Order()$ 先后序遍历左子树，然后后序遍历右子树，最后访问根节点

6. 有关下面 $\tt C$++ 代码的说法正确的是（ ）。

   typedef struct LinkList {
   	int data;
   	LinkList* next;
   	LinkList* prev;
   }LinkList, LinkNode;
   
   bool ListInit(LinkList* &L) {
   	L = new LinkNode;
   	if (!L) return false;
   
   	L->next = NULL;
   	L->prev = NULL;
   	L->data = -1;
   
   	return true;
   }
   

{{ select(6) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

7. 对 $\tt hello\ world$ 使用霍夫曼编码（$\tt Huffman\ Coding$），最少 $\tt bit$（比特）为（ ）。

{{ select(7) }}

• $4$
• $32$
• $64$
• $88$

8. 下面的 $\tt fiboA()$ 和 $\tt fiboB()$ 两个函数分别实现斐波那契数列，该数列第 $1$、第 $2$ 项值为 $1$，其余各项分别为前两项之和。下面有关说法错误的是（ ）。

   注：此题原代码有误，此处已修正。

   int FiboA(int n) {
   	if (n == 0)
   		return 1;
   	if (n == 1)
   		return 1;
   	else {
   		return FiboA(n - 1) + FiboA(n - 2);
   	}
   }
   
   int FiboB(int n) {
   	if ((n == 0) || (n == 1)) {
   		fiboB[n] = n;
   		return n;
   	}
   	else {
   		if (fiboB[n] == 0) {
   			fiboB[n] = FiboB(n - 1) + FiboB(n - 2);
   		}
   
   		return fiboB[n];
   	}
   }
   

{{ select(8) }}

• $\tt fiboA()$ 采用递归方式实现斐波那契数列
• $\tt fiboB()$ 采用动态规划算法实现斐波那契数列
• 当 $N$ 值较大时，$\tt fiboA()$ 存在大量重复计算
• 由于 $\tt fiboA()$ 代码较短，其执行效率较高

9. 有关下面 $\tt C$++ 代码不正确的说法是（ ）。

   int Depth(BiTree T) {
   	if (T == NULL) {
   		return 0;
   	}
   	else {
   		int m = Depth(T->lchild);
   		int n = Depth(T->rchild);
   
   		if (m > n) {
   			return m + 1;
   		}
   		else {
   			return n + 1;
   		}
   	}
   }
   

{{ select(9) }}

• 该代码可用于求解二叉树的深度
• 代码中函数 $\tt Depth()$ 的参数 $T$ 表示根节点，非根节点不可以作为参数
• 代码中函数 $\tt Depth()$ 采用了递归方法
• 代码中函数 $\tt Depth()$ 可用于求解各种形式的二叉树深度，要求该二叉树节点至少有 $\tt left$ 和 $\tt right$ 属性

10. 下面有关树的存储，错误的是（ ）。

{{ select(10) }}

• 完全二叉树可以用 $\tt list$ 存储
• 一般二叉树都可以用 $\tt list$ 存储，空子树位置可以用 $\tt None$ 表示
• 满二叉树可以用 $\tt list$ 存储
• 树数据结构，都可以用 $\tt list$ 存储

11. 用括号表示法构造二叉树 $\tt [1,2,3,null,4]$ 的结果是（ ）。

{{ select(11) }}

• 1(2()(4))(3)
• 1(2(3)())(4)
• (1,2(3),(4))
• (1,(2)(3),(4))

12. 下面有关布尔类型的函数的说法，正确的是（ ）。

{{ select(12) }}

• $\tt bool$ 类型函数只能返回 $0$ 或者 $1$ 两种值
• $\tt bool$ 类型函数可以返回任何整数值
• $\tt bool$ 类型函数必须有参数传递
• $\tt bool$ 类型函数没有返回值

13. 通讯卫星在通信网络系统中主要起到（ ）的作用。

{{ select(13) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

14. 小杨想编写一个判断任意输入的整数 $N$ 是否为素数的程序，下面哪个方法不合适？（ ）

{{ select(14) }}

• 埃氏筛法
• 线性筛法
• 二分答案
• 枚举法

15. 内排序有不同的类别，下面哪种排序算法和冒泡排序是同一类？（ ）

{{ select(15) }}

• 希尔排序
• 快速排序
• 堆排序
• 插入排序

二、判断题（每题 2 分，共 20 分）

1. 在面向对象中，方法在 $\tt C$++ 的 $\tt class$ 中表现为 $\tt class$ 内定义的函数。（ ）

{{ select(16) }}

• 正确
• 错误

2. $\tt C$++ 类的定义中，可以没有构造函数，会给出默认的构造函数。（ ）

{{ select(17) }}

• 正确
• 错误

3. 如果某个 $\tt C$++ 对象（$\tt object$）支持下标运算符（方括号运算符），则该对象在所对应 $\tt class$ 中以成员函数的形式进行了重载。（ ）

{{ select(18) }}

• 正确
• 错误

4. 深度优先搜索（$\tt DFS$，$\tt Depth\ First\ Search$ 的简写）属于图算法，其过程是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。（ ）

{{ select(19) }}

• 正确
• 错误

5. 哈夫曼编码（$\tt Huffman\ Coding$）具有唯一性，因此有确定的压缩率。（ ）

{{ select(20) }}

• 正确
• 错误

6. 在下面 $\tt C$++ 代码中，由于删除了变量 $\tt ptr$，因此 $\tt ptr$ 所对应的数据也随之删除，故第 $8$ 行代码被执行时，将报错。（ ）

   int * ptr = new int(10);
   cout << *ptr << endl;
   delete ptr;
   cout << *ptr << endl;
   

{{ select(21) }}

• 正确
• 错误

7. 二叉搜索树查找的平均时间复杂度为 $O(\log N)$。（ ）

{{ select(22) }}

• 正确
• 错误

8. 二叉搜索树可以是空树（没有任何节点）或者单节点树（只有一个节点），或者多节点。如果是多节点，则左节点的值小于父节点的值，右节点的值大于父节点的值，由此推理，右节点树的值都大于根节点的值，左节点树的值都小于根节点的值。（ ）

{{ select(23) }}

• 正确
• 错误

9. 小杨想写一个程序来算出正整数 $N$ 有多少个因数，经过思考他写出了一个重复没有超过 $N/2$ 次的循环就能够算出来了。（ ）

{{ select(24) }}

• 正确
• 错误

10. 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）

{{ select(25) }}

• 正确
• 错误