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

$1、$​​ 关于C++类和对象的说法，错误的是( )。

{{ select(1) }}

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

$2、$ 有关下面C++代码的说法，错误的是( )

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

{{ select(2) }}

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

$3、$ 有关下面C++代码的说法，正确的是( )。

using namespace std;
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、$ 有关下面C++代码的说法，错误的是( )。

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

{{ select(4) }}

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

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

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

{{ select(5) }}

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

$6、$ 有关下面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、$ 对 hello world 使用霍夫曼编码（Huffman Coding），最少bit（比特）为（ ）。

{{ select(7) }}

• 4
• 32
• 64
• 88

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

int fiboA(int n) {
	if (n == 8)
		return 1;
	if (n == 1)
		return 1;
	else
		return fiboA(n - 1) + fiboA(n - 2);
}

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

{{ select(8) }}

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

$9、$ 有关下面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) }}

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

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

{{ select(10) }}

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

$11、$ 构造二叉树 [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) }}

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

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

{{ select(13) }}

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

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

{{ select(14) }}

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

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

{{ select(15) }}

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

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

$16、$ 在面向对象中，方法在C++的class中表现为class内定义的函数。( )

{{ select(16) }}

• 正确
• 错误

$17、$ C++类的定义中，可以没有构造函数，会给出默认的构造函数（ ）

{{ select(17) }}

• 正确
• 错误

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

{{ select(18) }}

• 正确
• 错误

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

{{ select(19) }}

• 正确
• 错误

$20、$ 哈夫曼编码（Huffman Coding）具有唯一性，因此有确定的压缩率。 ( )

{{ select(20) }}

• 正确
• 错误

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

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

{{ select(21) }}

• 正确
• 错误

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

{{ select(22) }}

• 正确
• 错误

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

{{ select(23) }}

• 正确
• 错误

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

{{ select(24) }}

• 正确
• 错误

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

{{ select(25) }}

• 正确
• 错误