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

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

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

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

#include <iostream>
using namespace std;

int factA(int n) {
    if (n <= 1)
        return 1;
    int ret = 1;
    for (int i = 2; i <= n; ++i)
        ret *= i;
    return ret;
}

int factB(int n) {
    return n ==1?1:n*factB(n -1);
}

int main(){
    int n;
    cin >> n;
    cout << factA(n) << ' ' << factB(n) << endl;
    return 0;

第 5 题 下面 C++代码意在实现字符串反序的功能。关于这段代码，以下说法正确的是（ ）

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

void printSReverse(char* sIn, int len) {
    if (len <= 1) {
        cout << sIn[0];
    } else {
        cout << sIn[0];
        printSReverse(sIn + 1,len -1);
    }
}

int main(){
    char sIn[100]= "Hello";
    printSReverse(sIn, strlen(sIn));
    return 0;
}

第 6 题 阅读下面 C++实现的二分查找代码，下列说法中错误的是（ ）。

int binarySearch(int * arr, int l, int r, int x){
    if (r >= l) {
        int mid = l+(r-l)/2;
        if (arr[mid] == x)
            return mid;
        else if (arr[mid]>x)
            return binarySearch(arr, l,mid - 1,x);
        else
        return binarySearch(arr, mid + 1, r,x);
    }else
        return -1;
}

第 7 题 使用如下代码片段定义四个字符串（假设头文件已正确定义），以下说法错误的是（ ）。

string str1 = "abc";
string str2 = str1;
char str3[ ] = "abc";
char * str4 =str3;

第 8 题 有关下面 C++代码正确的是（ ）。

#include <iostream>
using namespace std;

void f1(){
    cout << "f1()" << endl;
}

void f1(int x){
    cout << "f1(" << x << ")" << endl;
}

int main() {
    f1();
    f1(0);
    f1('0');
    return 0;
}

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

第 10 题 下面代码执行后的输出是（ ）。

#include <iostream>
using namespace std;

int fibonacci(int N) {
    cout << N << ",";
    if (N== 1||N==2){
        return 1;
    } else {
        return fibonacci(N- 1)+fibonacci(N - 2);
    }
}

int main(){
    cout << fibonacci(5)<< endl;
    return 0;
}

第 11 题 下列代码中，函数 f 的作用是（ ）。

void f(int a, int b) {
    return b == 0?a: f(b,a % b);
}

第 12 题 下面 C++代码用于排序，下列说法中错误的是（ ）。

void sortA(int * arr, int n) {
    for (int i = 0; i < n;++i)
        for (int j= 0;j<n- i- 1;++j)
            if (arr[j]> arr[j + 1]){
                int tmp = arr[j];
                arr[j] = arr[j+ 1];
                arr[j + 1]= tmp;
            }
}

void sortB(int * arr, int start, int end){
    if (start >= end)
        return;
    int middle = (start + end) / 2;
    sortB(arr,start,middle);
    sortB(arr,middle + 1, end);

    int leftsize = middle - start +1;
    int rightsize = end - middle;

    int * left = new int[leftsize];
    int * right - new int[rightsize];

    for (int i = 0; i < leftSize; i++)
        left[i]= arr[start + i];
    for (int j = 0; j< rightsize; j++)
        right[j]= arr[middle + 1+ j];

    inti= 0;
    int j = 0;
    int k = start;
    while (i < leftsize && j < rightSize) {
        if (left[i] <= right[j]){
            arr[k]= left[i];
            i++;
        } else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < leftsize){
        arr[k] = left[i];
        i++;
        k++;
    }
    while (j < rightsize){
        arr[k] = right[j];
        j++;
        k++;
    }
    delete[] left;
    delete[] right;
}

第 13 题 上一题中的`sortB`函数，明显体现出的算法思想和编程方法包括（）。

第 14 题 下列哪个算法并没有体现分治思想？（ ）。

第 15 题 下列关于链表说法，正确的是（ ）。

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

第 1 题 计算机硬件主要包括运算器、控制器、存储器、输入设备和输出设备。

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

第 3 题 埃氏筛法用于找出自然数 N 以内的所有质数，其时间复杂度为 $O(N \sqrt{N})$，因为判定一个数是否为质数的时间复杂度为 O(N)。

第 4 题 贪心法的每一步都采取局部最优策略，因此必然能实现全局最优。

第 5 题 在 C++语言中，函数的参数也可以是另一个函数。

第 6 题 在 C++语言中，内置的排序算法（algorithm 库中的 sort 函数）只能对 C++的基础类型（如 int、double 等）做排序，而不能对自定义类型做排序。

第 7 题 在任何场景下，链表都是比数组更优秀的数据结构。

第 8 题 在 C++语言中，可以使用 delete 来释放指针指向的内存空间。

第 9 题 选择排序和快速排序都是不稳定的。

第 10 题 二分查找法可以应用于有序序列（如升序排序的整数数组），也可以应用于无序序列（如乱序的整数数组）。

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

第 1 题 小杨的锻炼

题面描述

小杨的班级里共有 $N$ 名同学，每位同学都有各自的锻炼习惯。具体来说，第 $i$ 位同学每隔 $a_i$ 天就会进行一次锻炼（也就是说，每次锻炼会在上一次锻炼的 $a_i$ 天后进行）。

某一天，班上的 $N$ 名同学恰好都来进行了锻炼。他们对此兴奋不已，想要计算出下一次所有同学都来锻炼，至少要过多少天。但他们不会计算，你能帮帮他们吗？

输入格式

第一行一个整数 $N$，表示同学的数量。

第二行 $N$ 个用空格隔开的正整数，依次为 $a_0, a_1, …, a_{n-1}$。

输出格式

输出一个整数，表示下一次所有同学都来锻炼，至少要过多少天。

3
1 2 3

6

4
2 4 8 16 

16

4
2 4 6 8

24

数据要求

【样例解释 1】

第一位同学每天都锻炼；第二位同学每 2 天锻炼一次；第三位同学每 3 天锻炼一次。因此，6 天之后，三位同学都会进行锻炼。在此之前，第二位同学只会在第 2, 4 天进行锻炼，第三位同学只会在第 3 天进行锻炼，他们都无法相遇。

【样例解释 2】

第四位同学每 16 天锻炼一次，而第 16 天后也恰好是前三位同学锻炼的日子。

【数据规模】

对于 $20\%$ 的测试点，保证 $N = 2$。

对于 $50\% $的测试点，保证 $N \le 4$。

对于所有测试点，保证 $2 \le N \le 10,1 \le a_i \le 50$。

第 2 题 小杨的队列

题面描述

小杨的班级里共有 $N$ 名同学，学号从 $0$ 至 $N-1$。

某节课上，老师要求同学们进行列队。具体来说，老师会依次点名 $M$ 名同学，让他们加入队伍。每名新入队的同学需要先站到队伍末尾（刚开始队伍里一个人都没有，所以第一个入队的同学只需要站好即可），随后，整个队伍中的所有同学需要按身高从低到高重新排序（身高相同的同学之间的顺序任意）。

排队很容易，但重新排序难倒了同学们。稍加讨论后，他们发现可以通过交换位置的方法来实现排序。具体来说，他们可以让队伍中的两名同学交换位置，这样整个队伍的顺序就会发生变化，多经过这样的几次交换后，队伍的顺序就可以排好。

例如：队伍中有 4 名同学，学号依次为 10, 17, 3, 25，我们可以令 3 号同学和 10 号同学交换位置，则交换后的队伍顺序变为 3, 17, 10, 25，这就是一次交换位置。

聪明的小杨想要知道：在老师每次点名一位新同学加入队伍后，在原有队伍的基础上，同学们最少要进行几次$\textbf{交换位置}$，才能完成老师按身高排序的要求。

输入格式

第一行一个整数 $N$，表示同学的数量。

第二行 $N$ 个用空格隔开的正整数，依次表示学号为 $0, 1, …, N-1$ 的同学的身高（不超过 2,147,483,647）。

第三行一个整数 $M$，表示老师点名的数量。

接下来 $M$ 行，依次描述 $M$ 次点名：每行一个整数 $x(0 \le x \lt N)$，表示要求学号为 $x$ 的同学加入队伍。保证该名同学此前不在队伍中。

对于所有的测试点，保证 $1 \le M \le N \le 2000$。对于 $50\%$ 的测试点，保证所有同学的身高互不相同。

输出格式

输出 $M$ 行，依次表示对于每次点名，同学们最少要进行几次$\textbf{交换位置}$，才能完成按身高排序的要求。

5
170 165 168 160 175
4
0
3
2
1

0
1
1
2

4
20 20 20 10
4
0
1
2
3

0
0
0
1

数据要求

【样例解释 1】

初始时队伍为空，身高为 170 的 0 号同学加入队伍，不需要任何交换位置。

接着，身高为 160 的 3 号同学加入队伍的末尾，此时两位同学需要进行依次交换位置，才能保证身高更矮的 3 号同学排在身高更高的 0 号同学前面。

接着，身高为 168 的 2 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为 3(160), 0(170), 2(168)，此时 2 号同学可以和 0 号同学进行一次交换位置，即可完成排序要求。

接着，身高为 165 的 1 号同学加入队伍的末尾，此时队伍中的同学学号（身高）依次为 3(160), 2(168), 0(170), 1(165)，此时可以令 1 号同学和 2号同学进行一次交换位置，使队伍变为 3(160), 1(165), 0(170), 2(168)；随后再令 0 号同学和 2 号同学进行一次交换位置，使队伍变为 3(160), 1(165), 2(168), 0(170)，即可完成排序要求。

【样例解释 2】

前三位加入队伍的同学（0, 1, 2 号同学）身高都相同，不需要进行任何交换位置。最后加入队伍的 3 号同学身高最矮，需要和队头的 0 号同学交换位置，方可完成排序要求。