第 1 题 以下不属于计算机输出设备的有（ ）。

第 2 题 小明想了一个 1 到 100 之间的整数。你可以做多次猜测，每次猜测之后，如果你没有猜中，小明会告诉你，你猜的数比他想的数大还是小。你希望你在运气最坏的情况下花费最少的次数猜中，请问你运气最坏的情况下会猜几次？（包括最后猜中的那次）

第 3 题 关于分治算法，下列说法错误的是（ ）。

第 4 题 下面关于 C++类的说法中，正确的是（ ）。

第 5 题 关于下面 C++代码说法错误的是（ ）。

#include<iostream>
#include <string>
using namespace std;

class Pet{
public:
    string kind;
    int age;
    Pet(string _kind, int _age):kind(_kind),age(_age) {}
}

class Dog : public Pet {
public:
    string color;
    Dog(string _kind, int _age, string _color):Pet(_kind,_age)，color(_color) {}
}

int main( ) {
    auto dog = Dog("dog",3,"white");
    cout << "kind:" << dog,kind << endl;
    cout << "age:" << dog.age << endl;
    cout << "color:"<< dog.color << endl; // 输出行A
    return 0;
}

第 6 题 以下几个类定义中不能顺利通过编译的是（ ）。

class A {
public:
    void func(int a, int b, int c) {};
};

class B{
public:
    void func(int a, int b=1, int cm1){}
};

class c{
public:
    void func(int a=3, int b, int c){}
};

class D {
public:
    void func(int a=3, int b=1, int c*o){}
};

第 7 题 关于运算符重载，下列说法正确的是（ ）。

第 8 题 关于 C++程序的异常处理，以下选项中描述错误的是（ ）。

第 9 题 有关下面 C++代码的说法，正确的是（ ）。

#include <iostream>
#include <cassert>

using namespace std;

class MoreData {
	int* __data;
	int head, tail, capacity;
public:
	MoreData(int cap) {
		capacity = cap;
		__data = new int[capacity];
		head = tail = 0;
	}
	MoreData& push(int val) {
		assert(tail < capacity);
		__data[tail++] = val;
		return *this;
	}
	int pop() {
		assert(head < tail);
		return __data[--tail];
	}
	int size() {
		return tail - head;
	}
};

int main() {
	auto myData = MoreData(100) ;
	myData. push(4). push(5);
	cout << myData.pop() << endl;
	cout << myData.pop() << endl;
	cout << myData.pop() << endl;
	return 0;
}

第 10 题 如下图所示的哈夫曼树，按照哈夫曼编码规则，假设图中字符 C 的编码为 0，则 E 的编码为（ ）。

第 11 题 下面有关格雷码的说法，错误的是（ ）。

第 12 题 在具有2N个结点的完全二叉树中，叶子结点个数为（ ）。

第 13 题 有关下图的二叉树，说法正确的有（ ）个。 - 是完全二叉树 - 是二叉搜索树 - 是平衡二叉树

第 14 题 现希望存储整数??的所有质因子，请问其空间复杂度上界为是（ ）。

第 15 题 下面 C++代码实现了某种排序算法，其中代码片段 my_sort(arr, begin, i); my_sort(arr, i + 1, end); 采用的算法思想是（ ）。

void my_sort(int arr[], int begin, int end) {
	if (begin >= end-1) return;
	int i=begin, j=end-1, x=arr[begin];
	while (i < j)
	{
		while(i < j & arr[j] >= x)
			j-- ;
		if(i < j)
			arr[i++] = arr[j];
			
		while(i < j && arr[i] < x)
			i++;
		if(i < j)
			arr[j--] = arr[i];
	}
	arr[i] = x;
	my_sort(arr, begin, i);
	my_sort(arr, i + 1, end);
}

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

第 1 题 质数的判定和筛法的目的并不相同，质数判定旨在判断特定的正整数是否为质数，而质数筛法意在筛选出范围内的所有质数。

第 2 题 唯一分解定理指的是分解质因数只有唯一的一种算法。

第 3 题 一般情况下，在 C++中定义一个类时，构造函数和析构函数都不是必须手动定义的。

第 4 题 如果一个对象具有另一个对象的性质，那么它们之间就是继承关系。

第 5 题 哈夫曼编码树中，两个频率相同的字符一定具有相同的哈夫曼编码。

第 6 题 宽度优先搜索算法的英文简写是 BFS。

第 7 题 深度优先遍历算法的时间复杂度为 $(NlogN)$ ，其中$N$为树的节点数。

第 8 题 任意二叉树都至少有一个结点的度是 2。

第 9 题 将$N$个数据按照从小到大顺序存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是$O(log N)$。

第 10 题 深度优先遍历一般需要借助数据结构栈来实现，广度优先遍历一般需要借助数据结构队列来实现。

三、编程题（每题 25 分，共 50 分）

第 1 题 下楼梯

题面描述

顽皮的小明发现，下楼梯时每步可以走 1 个台阶、2 个台阶或 3 个台阶。现在一共有$N$个台阶，你能帮小明算算有多少种方案吗？

输入格式

输入一行，包含一个整数$N$。约定$ 1 ≤ N ≤ 60 $。

输出格式

输出一行，包含一个整数$C$，表示方案数。

4

7

10

274

数据要求

第 2 题 亲朋数

题面描述

给定一串长度为$L$、由数字 0-9 组成的数字串$S$。容易知道，它的连续子串共

有$\frac{N(N+1)}{2}$个。如果某个子串对应的数（允许有前导零）是$p$的倍数，则称该子串为数字串$S$对于$p$的亲朋数。

例如，数字串$S$为“12342”、$p$为 2，则在 15 个连续子串中，亲朋数有“12”、

“1234”、“12342”、“2”、“234”、“2342”、“34”、“342”、“4”、

“42”、“2”等共 11 个。注意其中“2”出现了 2 次，但由于其在$S$中的位置不

同，记为不同的亲朋数。

现在，告诉你数字串$S$和正整数$p$，你能计算出有多少个亲朋数吗？

输入格式

输入的第一行，包含一个正整数 $p$。约定$ 2 ≤ p ≤ 128 $。

输入的第二行，包含一个长为$L$的数字串$S$。约定 $1 ≤ L ≤ 10^6$。

输出格式

输出一行，包含一个正整数$C$，表示亲朋数的个数。

2
102

5

2
12342

11

数据要求

【样例解释 1】

5 个亲朋数，分别为“10”、“102”、“0”、“02”、“2”。