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

第 1 题 已知小写字母b 的ASCII码为98,下列C++代码的输出结果是( )｡

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

{{ select(1) }}

• b
• c
• 98
• 99

第 2 题 已知a 为int 类型变量,p 为int * 类型变量,下列表达式不符合语法的是( )｡ {{ select(2) }}

• a * a
• p * p
• a && a
• p && p

第 3 题 下列关于C++类的说法,错误的是( )｡ {{ select(3) }}

• 如果一个类包含纯虚函数,则它不能包含成员变量｡
• 如果一个类包含纯虚函数,则不能用它定义对象｡
• 派生类对象占用的内存总是不小于基类对象｡
• 派生类可以不实现基类的虚函数｡

第 4 题 已知数组a 的定义int a[10] = {-1}; ,下列说法不正确的是( )｡ {{ select(4) }}

• 数组a 至少占用10 个int 大小的内存,一般为40 个字节｡
• 数组a 的所有元素均被初始化为-1 ｡
• 语句a[-1] = 0; 不会产生编译错误,但会导致难以预测的运行结果｡
• 语句a[13] = 0; 不会产生编译错误,但会导致难以预测的运行结果｡

第 5 题 一棵完全二叉树有165个结点,则叶结点有多少个?( ) {{ select(5) }}

• 38
• 82
• 83
• 84

第 6 题 下列关于二叉树的说法,错误的是( )｡ {{ select(6) }}

• 二叉排序树的中序遍历顺序与元素排序的顺序是相同的｡
• 自平衡二叉查找树(AVL树)是一种二叉排序树｡
• n 个元素的二叉排序树,其高一定为 $\left\lfloor\log_{2} n\right\rfloor$ ｡
• 任意的森林,都可以映射为一颗二叉树进行表达和存储｡

第 7 题 下列关于树和图的说法,错误的是( )｡ {{ select(7) }}

• 保留树的所有节点,并把树的每个节点指向其父节点,则可以将树转换为一个有向弱连通图｡
• 保留树的所有节点,并把树的每个节点指向其子节点,则可以将树转换为一个有向无环图｡
• 每个连通图都存在生成树｡
• 每个存在生成树的有向图,都一定是强连通的｡

第 8 题 对一个包含V个顶点、E条边的图,执行广度优先搜索,其最优时间复杂度是( )｡ {{ select(8) }}

• $O(V+E)$
• $O(V)$
• $O(E)$
• $O\left(V^{2}\right)$

第 9 题 以下哪个方案不能合理解决或缓解哈希表冲突( )｡ {{ select(9) }}

• 用新元素覆盖发生冲突的哈希表项｡
• 在每个哈希表项处,使用单链表管理该表项的冲突元素｡
• 建立额外的单链表,用来管理所有发生冲突的元素｡
• 使用不同的哈希函数再建立一个哈希表,用来管理所有发生冲突的元素｡

第 10 题 以下关于贪心法和动态规划的说法中,错误的是( )｡ {{ select(10) }}

• 对特定的问题,贪心法不一定适用｡
• 当特定的问题适用贪心法时,通常比动态规划的时间复杂度更低｡
• 对很多问题,递推实现和递归实现动态规划方法的时间复杂度相当｡
• 采用动态规划的算法一定具有多项式时间复杂度｡

第 11 题 下面程序的输出为( )｡

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

{{ select(11) }}

• 8
• 13
• 21
• 无法正常结束｡

第 12 题 下面程序的时间复杂度为( )｡

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

{{ select(12) }}

• $O(\phi^{n})$, $\phi=\frac{\sqrt{5}+1}{2}$
• $O(2^n)$
• $O(n^2)$
• $O(n)$

第 13 题 下面init_sieve 函数的时间复杂度为( )｡

int sieve[MAX_N]; 
void init_sieve(int n) {
    for (int i = 1; i <= n; i++)
        sieve[i] = i;
    for (int i = 2; i <= n; i++) 
        for (int j = i; j <= n; j += i)
            sieve[j]--;
}

{{ select(13) }}

• $O(n)$
• $O(n\log \log n)$
• $O(n \log n)$
• $O(n^2)$

第 14 题 下面count_triple 函数的时间复杂度为( )｡

int gcd(int m, int n) {
    if (m == 0) return n;
    return gcd(n % m, m);
}
int count_triple(int n) { 
    int cnt=0;
    for(int v=1; v*v*4<=n; v++) 
        for(int u=v+1; u*(u+v)*2<=n; u+=2)
            if(gcd(u,v)==1){
                int a=u*u-v*v;
                int b=u*v*2; 
                int c=u*u+v*v; 
                cnt+= n/(a+b+c);
            }
    return cnt;
}

{{ select(14) }}

• $O\left(n^{2}\right)$
• $O\left(n^{2} \log n\right)$
• $O(n \log n)$
• $O(n)$

第 15 题 下列选项中,哪个不可能是下图的深度优先遍历序列()。 {{ select(15) }}

• 2,3,5,7,8,9,6,4,1
• 5,7,8,9,1,2,4,3,6
• 6,8,9,5,7,1,2,3,4
• 8,5,7,9,1,2,3,6,4