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

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

{{ select(1) }}

• 麦克风
• 音箱
• 打印机
• 显示器

---

第 2 题 小明想了一个 $1$ 到 $100$ 之间的整数。你可以进行多次猜测，每次没有猜中时，小明会告诉你猜的数比他想的数大还是小。为了保证在最坏情况下用尽可能少的次数猜中，最多需要猜多少次？（包括最后猜中的那次）

{{ select(2) }}

• 6
• 7
• 8
• 100

---

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

{{ select(3) }}

• 分治算法的核心思想是分而治之，即把问题转化为多个规模更小的子问题求解。
• 分治算法可以不使用递归实现。
• 分治算法的时间复杂度是 $O(\log N)$，其中 $N$ 表示问题的规模。
• 二分法、快速排序等算法都是典型的使用分治思想的算法。

---

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

{{ select(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;
}

{{ select(5) }}

• Pet 类是基类，Dog 类是子类。
• Dog 类的构造函数中，将自动调用 Pet 类的构造函数。
• dog 是 Dog 类的实例。
• 最后一行（即输出行 A）会报错，因为 Pet 类中没有成员变量 color。

---

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

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

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

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 = 0) {}
};

{{ select(6) }}

• class A
• class B
• class C
• class D

---

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

{{ select(7) }}

• 下面两个运算符重载可以同时通过编译。虽然参数类型都是 int 与 Test 的组合，但二者的参数顺序不同，编译器能够确定调用哪一个实现。

  #include <iostream>
  using namespace std;
  
  class Test {
  public:
      int data;
      Test(int d) : data(d) {}
  };
  
  Test operator +(const Test& a, const int& b) {
      return Test(a.data + b);
  }
  
  Test operator +(const int& b, const Test& a) {
      return Test(-a.data - b);
  }
  
  int main() {
      Test obj(1);
      int data = 2;
      cout << (obj + data).data << endl;
      cout << (data + obj).data << endl;
      return 0;
  }
  

• A 的说法是错误的。因为加法满足交换律，调换 Test 和 int 的顺序后，加法运算的实现必须保持一致，编译器会检查这一点；如果将后一处 int 改为 double，则可通过编译。

• A 和 B 的说法都是错误的。运算符重载时，所有参数以及返回值的类型必须完全相同，因此下面的运算符重载也不能通过编译。

  class Test {
  public:
      int data;
      Test(int d) : data(d) {}
  };
  
  Test operator +(const Test& a, const int& b) {
      return Test(a.data + b);
  }
  

• A、B、C 的说法都是错误的。

---

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

{{ select(8) }}

• 编程语言中的异常和错误是不同的概念。
• 异常一旦发生，程序便一定不能继续执行。
• 通过 try、catch 等保留字提供异常处理功能。
• 程序可以使用 throw 抛出异常。

---

第 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;
}

{{ select(9) }}

• MoreData 类可用于构造队列（queue）数据结构。
• myData.push(4).push(5); 的连续 push() 用法将导致错误。
• 前两个 cout << myData.pop() << endl; 可以正确运行，分别输出 $4$ 和 $5$。
• 最后一个 cout << myData.pop() << endl; 可以通过编译，但不能正常运行，因为 pop 函数中的断言 assert(head < tail); 会失败。

---

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

                 T
              /     \
           40/       \60
            C         N3
                    /    \
                 30/      \30
                  N2       D
                /   \
             15/     \15
              N1      B
             /  \
           5/    \10
           A      E

{{ select(10) }}

• 1111
• 1010
• 1101
• 1001

---

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

{{ select(11) }}

• 格雷码是无权码。
• 格雷码是循环码。
• 011 和 100 是一组相邻的格雷码。
• 格雷码相邻的码组间仅有一位不同。

---

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

{{ select(12) }}

• $N/2$
• $N-1$
• $N$
• $N+1$

---

第 13 题 有关下图的二叉树，下列三个说法中正确的有多少个？

             62
          /      \
        47        88
       /  \      /  \
     35   51    73   99
       \    \       /
       37   58     93

• 是完全二叉树；
• 是二叉搜索树；
• 是平衡二叉树。

{{ select(13) }}

• 0
• 1
• 2
• 3

---

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

{{ select(14) }}

• $O(\log\log N)$
• $O(\log N)$
• $O(\sqrt{N})$
• $O(N)$

---

第 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);
}

{{ select(15) }}

• 递推
• 贪心
• 分治
• 搜索

---

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

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

{{ select(16) }}

• 正确
• 错误

---

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

{{ select(17) }}

• 正确
• 错误

---

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

{{ select(18) }}

• 正确
• 错误

---

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

{{ select(19) }}

• 正确
• 错误

---

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

{{ select(20) }}

• 正确
• 错误

---

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

{{ select(21) }}

• 正确
• 错误

---

第 22 题 深度优先遍历算法的时间复杂度为 $O(N\log N)$，其中 $N$ 为树的结点数。

{{ select(22) }}

• 正确
• 错误

---

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

{{ select(23) }}

• 正确
• 错误

---

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

{{ select(24) }}

• 正确
• 错误

---

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

{{ select(25) }}

• 正确
• 错误

---

来源

GESP C++ 六级样题