已知小写字母 b 的ASCII码为98，下列C++代码的输出结果是？（ ）

#include <iostream>
using namespace std;
int main() {
    char a = 'b' ^ 4;
    cout << a;
    return 0;
}

已知 a 为 int 类型变量， p 为 int * 类型变量，下列赋值语句不符合语法的是？（ ）

下列C++代码的输出是？（ ）

#include <iostream>
using namespace std;
int main() {
    int arr[5] = {2, 4, 6, 8, 10};
    int * p = arr + 2;
    cout << p[3] << endl;
    return 0;
}

以下关于动态规划的说法中，【错误】的是？（ ）

以下哪个方案不能合理解决或缓解哈希表冲突？（ ）

下面程序的时间复杂度为？（ ）

int rec_fib[MAX_N];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}

图的存储和遍历算法，下面说法【错误】的是？（ ）

对于如下图的二叉树，说法正确的是？（ ）

下列关于C++类的说法，【错误】的是？（ ）

假定只有一个根节点的树的深度为 ，则一棵有 个节点的完全二叉树，则树的深度为？（ ）

下列选项中，哪个【不可能】是下图的广度优先遍历序列？（ ）

下面程序的输出为？（ ）

#include <iostream>
using namespace std;
int rec_fib[100];
int fib(int n) {
    if (n <= 1)
        return n;
    if (rec_fib[n] == 0)
        rec_fib[n] = fib(n - 1) + fib(n - 2);
    return rec_fib[n];
}
int main() {
    cout << fib(6) << endl;
    return 0;
}

一个连通的简单有向图，共有28条边，则该图至少有（ ）个顶点？

下面 search 函数的平均时间复杂度为？（ ）

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low < high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    return -1;
}

下面程序的时间复杂度为？（ ）

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve() {
    for (int n = 2; n <= MAXN; n++) {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

使用 math.h 或 cmath 头文件中的函数，表达式 pow(10, 3) 的结果的值为 1000 、类型为 int 。（ ）

动态规划方法将原问题分解为一个或多个相似的子问题，因此必须使用递归实现。（ ）

如果将城市视作顶点，公路视作边，将城际公路网络抽象为简单图，可以满足城市间的车道级导航需求。（ ）

无论哈希表采用何种方式解决冲突，只要管理的元素足够多，都无法避免冲突。（ ）

C++语言中，指针变量指向的内存地址不一定都能够合法访问。（ ）

C++语言中，表达式 9 & 12 的结果类型为 int 、值为 8 。（ ）

在C++语言中，类的构造函数和析构函数均可以声明为虚函数。（ ）

一般情况下， long long 类型占用的字节数比 float 类型多。（ ）

二叉排序树的中序遍历序列一定是有序的。（ ）

对 n 个元素的数组进行快速排序，最差情况的时间复杂度为 O(n log n)。（ ）

线图

时间限制：1 s，内存限制：512 MB

【问题描述】

给定由 n 个结点与 m 条边构成的简单无向图 G，结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建：

（1）初始时线图 L(G) 为空。

（2）对于无向图 G 中的一条边，在线图 L(G) 中加入与之对应的一个结点。

（3）对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2)，若存在 G 中的结点同时连接这两条边（即 u1, v1之一与 u2, v2之一相同），则在线图 L(G) 中加入一条无向边，连接  (u1, v1)、(u2, v2) 在线图中对应的结点。

请你求出线图 L(G) 中所包含的无向边的数量。

【输入描述】

第一行，两个正整数 n、m，分别表示无向图 G 中的结点数与边数。

接下来 m 行，每行两个正整数 ui、vi，表示 G 中连接 ui、vi 的一条无向边。

【输出描述】

输出共一行，一个整数，表示线图 L(G) 中所包含的无向边的数量。

【样例输入1】

5 4
1 2
2 3
3 1
4 5

【样例输出1】

3

【样例输入2】

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

【样例输出2】

30

【样例解释1】

【数据范围】

对于60%测试点，保证 1 <= n、m <= 500。

对于所有测试点，保证 1 <= n、m <= 100000。

调味平衡

时间限制：1 s，内存限制：512 MB

【问题描述】

小 A 准备了 n 种食材用来制作料理，这些食材依次以 1、2、……、n 编号，第 i 种食材的酸度为 ai，甜度为 bi。

对于每种食材，小 A 可以选择将其放入料理，或者不放入料理。料理的酸度 A 为放入食材的酸度之和，甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等，那么料理的调味是平衡的。

过于清淡的料理并不好吃，因此小 A 想在满足料理调味平衡的前提下，合理选择食材，最大化料理的酸度与甜度之和。

你能帮他求出在调味平衡的前提下，料理酸度与甜度之和的最大值吗？

【输入描述】

第一行，一个正整数 n，表示食材种类数量。

接下来 n 行，每行两个正整数 ai、bi，表示食材的酸度与甜度。

【输出描述】

输出共一行，一个整数，表示在调味平衡的前提下，料理酸度与甜度之和的最大值。

【样例输入1】

3
1 2
2 4
3 2

【样例输出1】

8

【样例输入2】

5
1 1
2 3
6 1
8 2
5 7

【样例输出2】

2

【数据范围】

对于40%的测试点，保证 1 <= n <= 10，1 <= ai、bi <= 10。

对于另外20%的测试点，保证 1 <= n <= 50，1 <= ai、bi <= 10。

对于所有测试点，保证 1 <= n <= 100，1 <= ai、bi <= 500。