一、选择题

1. 真题梳理

1. 若函数声明为 void f(int &a, int b, const int &c)，且在主函数内已经声明了 $x,y,z$ 三个 int 类型变量。如下哪个调用可以通过编译？

   A. f(x,x,0)
   B. f(0,0,z)
   C. f(0,y,y)
   D. f(1,2,3)

2. 下面的 C++ 代码执行后，输出的是

   int main() {
     int arr[10] = {0,1,2,3,4};
     char ovo[] = "ovo";
     cout << sizeof(ovo) << ' ' << sizeof(arr) << endl;
   }
   

   A. 3 10
   B. 4 10
   C. 3 40
   D. 4 40

3. 下面的 C++ 代码执行后，输出的是

   int foo(char *x) {
     return 3**x*2;
   }
   
   int main() {
     char arr[10] = {char(10)};
     arr[1] = foo(arr);
     cout << int(arr[0]) * int(arr[1]) << endl;
   }
   

   A. 10
   B. 60
   C. 600
   D. 100

4. 对三维数组 int arr[2][3][4]，其占用的内存大小是 （） 字节

   A. $9$
   B. $24$
   C. $96$
   D. $144$

5. 对三维数组 int arr[2][3][4]，则 arr + 1 是如下哪个数组元素的地址？

   A. arr[1][0][0]
   B. arr[0][0][1]
   C. arr[0][1][0]
   D. arr[2][3][5]

6. 下面的 C++ 代码执行后，输出的是

   int main() {
     char *p = "I love GESP!";
     cout << *(p+5) << endl;
   }
   

   A. e
   B. ve GESP!
   C. e GESP!
   D. v

7. 下列 C++ 代码被执行后的输出是？

   int rc = 5;
   int main() {
     int rc = 3;
     cout << ::rc++ << endl;
   }
   

   A. 3
   B. 4
   C. 5
   D. 6

8. 已知数组 arr[10]，下列语句执行时不会产生越界错误的是：

   A. false && arr[100]
   B. true && arr[10]
   C. false || arr[100]
   D. false || arr[10]

9. 归并排序算法的空间复杂度是？

   A. $\Theta (n^2)$
   B. $\Theta (n)$
   C. $\Theta (n\log n)$
   D. $O(1)$

10. 已知变量 $x$ 的地址是 0x6ffe14，则下⾯C++代码执行以后输出的是？

    int main() {
      int x = 100;
      int *p = &x;
      cout << *p + 3 << endl;
    }
    

    A. 0x6ff17
    B. 0x6ff20
    C. 101
    D. 103

11. 输入 Luogu A K，则下列 C++ 代码执行后的输出是（ ）？

    int main() {
      string s;
      char x, y;
      cin >> s >> x >> y;
      cout << s << x << y << endl;
    }
    

    A. Luo
    B. LAK
    C. Luogu A
    D. LuoguAK

12. 下列 C++ 函数用于判定输入的数 $x$ 是不是质数。则在横线上填写哪条语句可以使得函数得到正确的结果？

    bool isPrime(int x) {
      if (x == 1) return false;
      for (int i = 2; ___; ++i) if (x % i == 0) return false;
      return true;
    }
    

    A. i < x
    B. i <= x
    C. i * i == x
    D. 不填

13. 如下 C++ 代码的时间复杂度是：

    for (int i = 1; i <= n; i *= 2) {
      for (int j = 1; j <= i; ++j) {
        cout << j << '\n';
      }
    }	
    

    A. $\Theta (n\log n)$
    B. $\Theta (n^2)$
    C. $\Theta (n)$
    D. $O(1)$

14. 洛谷官方网站是 www.luogu.com.cn。其中 www 的含义是？（ ）？

    A. 局域网
    B. 万维网
    C. 广域网
    D. 洛谷子网

15. 如下编程常用软件中，不属于集成开发环境（IDE）的是（ ）？

    A. Dev-C++
    B. IntelliJ IDEA
    C. visual Studio Code（VS Code）
    D. GUIDE

2. 真题答案

【答案】 $ADCCAACABDDACBC$
【解析】

1. 牢记函数和调用的内容：

#include <iostream>
using namespace std;

void f(int x, int &y, int *z)
{
    cout << "参数x:" << x << endl;
    cout << "参数y:" << y << endl;
    cout << "参数z:" << *z << endl;
}

int main()
{
   int a = 1, b = 2, c = 3, *p = &c;
   f(a, b, p); // f(a, b, &c)
   return 0;
}

口诀：
函数定义有细节，
调用参数要简洁。
变量定义传变量，
常量定义传常量。
定义地址传变量，
去掉引用取数值。
指针定义传地址，
加上星号来取值。

故选 $A$。

2. sizeof 用于返回指定变量或者数据类型占用的存储空间大小（以字节为单位）。在本题中，arr[] 开了 $10$ 个 int 空间。一个 int 变量会占 $4$ 个字节，十个这样的变量就占了 $4\times 10=40$ 个字节；ovo[] 并没有开大小，但是根据存储的数据我们知道，至少需要 $4$ 个 char 空间。一个 char 变量会占 $1$ 个字节，四个这样的变量就占了 $1\times 4=4$ 个字节。故选 $D$。

数据类型	所占空间(单位:字节)
int	$4$
long long	$8$
float	$4$
double	$8$
bool	$1$
char	$1$

3. 这道题目虽然是 char[]，但这只是为了迷惑大家，所以我们可以这么看：

int foo(int *x) {
  return 6* *x;
}

int main() {
  int x = 10;
  int y = foo(&x);
  cout << x * y << endl;
}

然后一步一步地模拟即可。顺便提醒一下，数组传入的默认都是引用，所以代码不是 foo(&arr) 哦。故选 $C$。

4. 开的空间大小是 $2\times 3\times 4=24$，一个 int 变量占 $4$ 个字节，$24\times 4=96$。故选 $C$。
5. arr[0] 拥有 $+1$ 的偏移量后就变成了 $arr[1]$。故选 $A$。
6. *p 原来指向 'I'，拥有 $+5$ 的偏移量后指向了 'e'。故选 $A$。
7. 全局变量可以在局部中使用 :: 来获得。故选 $C$。
8. 在 && 运算的时候，从左到右依次判断条件的真假，一旦发现一个假就停止判断，返回假的值；在 || 运算的时候，从左到右依次判断条件的真假，一旦发现一个真就停止判断，返回真的值。故选 $A$。
9. 下面是常见的排序算法及其时间复杂度和空间复杂度的汇总：

排序算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$
插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
归并排序	$O(nlog(n))$	$O(nlog(n))$	$O(nlog(n))$	$O(n)$
快速排序	$O(nlog(n))$	$O(nlog(n))$	$O(n^2)$	$O(log(n))$
堆排序	$O(nlog(n))$	$O(nlog(n))$	$O(nlog(n))$	$O(1)$
希尔排序	$O(nlog(n))$	取决于步长序列	$O(n^2)$	$O(1)$
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(k)$
桶排序	$O(n+k)$	$O(n+k)$	$O(n^2)$	$O(n+k)$
基数排序	$O(nk)$	$O(nk)$	$O(nk)$	$O(n+k)$

$n$：输入数组的长度
$k$：输入数据的范围
故选 $B$。

10. “加上星号来取值”。故选 $D$。
11. 模拟即可。故选 $D$。
12. 按照最普通的素数判断方式，从 $2$ 遍历到 $n-1$ 作因数。故选 $A$。
13. 外循环的迭代次数是 $O(\log n)$，内循环的迭代次数是 $O(i)$，其中 $i$ 是外循环迭代的当前值。因此，总的迭代次数可以表示为：${\sum }_{i=1}^{\log n}i$。
    通过求解上述求和，可以得到总的迭代次数是 $\Theta (n)$。其实这就是 vector 开空间的过程。故选 $C$。
14. www 是 World Wide Web（万维网）的缩写。故选 $B$。
15. vs code 只是 text editor。故选 $C$。

3. 重难点点播

(1) 指针和地址

详见配套课程。

#include <iostream>
using namespace std;

int main()
{
    int x = 100;
    int *p = &x; // 一个指向 x 地址的指针
    cout << "x 的地址是: " << p << endl;
    cout << "x 原来的值是: " << *p << endl; // 访问方式1
    *p = 50;
    cout << "x 现在的值是: " << x; // 访问方式2
    return 0;
}

#include <iostream>
using namespace std;

void f(int a, int &b, const int *c) // 函数定义有细节
{
    cout << a << endl;
    cout << b << endl; // 去掉引用取数值
    cout << *c // 加上星号来取值
}

int main()
{
    int x, y; // 变量定义传变量
    const int z = 100; // 常量定义传常量
    cin >> x >> y;
    int *p = &z; // 指针定义传地址
    f(x, y, p); // 调用参数要简洁
    return 0;
}

(2) 时间复杂度

时间复杂度的几个典型示例：

时间复杂度	典型代码	备注
$O(1)$	for (int i = 1; i <= 1000; i++)
$O(\log n)$	for (int i = 1; i <= n; i *= 2)	相当于 $O(\log 2^n)$
$O(\sqrt{n})$	for (int i = 1; i * i <= n; i++)	也能是 i <= sqrt(n)
$O(n)$	for (int i = 1; i <= n; i++)
$O(n^2)$	for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
$O(n!)$	for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++)

二、判断题

1. 真题梳理

1. 可以通过构造特殊数据使得 C++ 的 sort 函数在给 $10^5$ 个 int 范围内的整数排序时的用时超过一秒（在现代常用计算机上）。
2. 在 Windows 系统下，用命令行对程序进行输入时，可以同时按下 ctrl 和 Z 键给程序输入一个输入结束符（EOF）。
3. Windows 系统下，使用如下命令编译程序：g++ -o b a.cpp，则程序可使用的栈空间大约是 $1024\text{MiB}$。
4. 在 C++ 中，有符号整型的溢出是未定义行为（UB），而无符号整型的溢出不是未定义行为。
5. C++ 中，对于已定义的数组 int a[2][5]，可以通过访问 a[1][-1] 来访问 a[0][4]。
6. 在 C++ 语言中，函数指针可以作为函数的参数被传递到另一个函数里。
7. 可以使用 a^=b^=a^=b 来交换两个 float 类型变量的数值。
8. 语句 a / b == c / d 的计算涉及两次除法比较慢，为了加速可以对两个分式进行通分，计算 a * d == b * c 的值。当 $b$ 和 $d$ 不为 $0$ 时，这两种计算方法得到的值总是相同的。
9. 使用 64 位系统编译 C++ 代码得到的 64 位可执行程序里，一个指针所占的空间恒定为 $8$ 字节。
10. Linux 操作系统内核是用 C++ 语言编写的。
11. 求解一个正整数 $x$ 的算术平方根，可以使用枚举法完成。
12. 在 C++ 语言中，逻辑表达式 (0x3f == 63) 的结果为 false。
13. 执行下列 C++ 代码，输出为 GES123P。

string s = "GESP";
s.insert(2, "123");
cout << s << endl;

14. 执行下列 C++ 代码，输出为 $2$。

string s = "Luogu GESP Simulation Test";
int x = s.rfind("o");
cout << x << endl;

15. 执行下列 C++ 代码，输出为一个负数。

char s1[]="Luogu";
char s2[]="Vijos";
cout << strcmp(s1,s2) << endl;

16. $(629{)}_{16}+(2024{)}_8$ 的结果，可以表示为 $16$ 进制下的 $A3D$，也可以表示为二进制下的 $101001101101$。

17. 假设有四个变量 A,B,C,D，其中 A = B = 1，C = D = 0，则表达式 (A & (B | C | D) | D) 的结果为 $1$。

18. 执行下列 C++ 代码，输出中不含有整数 $3$。

int a[1000];
for (int i = 0; i < 1000; i++)
    a[i] = i + 1;
for (int i = 0; i < 1000; i++)
    cout << (a[i] * a[i]) % 10 << " ";

19. 一个正整数使用二进制表示需要 $200$ 位，则其使用十六进制表示，需要至少 $25$ 位。

20. 执行下列 C++ 代码，则输出的结果为 $20$。

    int a[10], b[10];
    a[1] = 1; a[2] = 1;
    b[1] = 1; b[2] = 2;
    for (int i = 3; i <= 6; i++) {
        a[i] = a[i - 1] + a[i - 2];
        b[i] = b[i - 1] + a[i];
    }
    cout << b[6] << endl;
    

2. 真题答案

【答案】 $FTFTTTFFTFTFFFTFTTFT$
【解析】

1. 至少要 $10^7$ 个 int 类型的相同数据才有可能超过一秒。
2. 这个很多同学都没有接触过，一定要记住。
3. 一般默认的是 $1MB$。
4. 在C++中，有符号整型的溢出被定义为未定义行为（Undefined Behavior）。这意味着当有符号整型的值超过了它所能表示的范围时，它的行为是不确定的。
5. 二维数组的空间是一维的，即如果有二维数组 a[n][m]，则空间有一维数组 b[n*m]。
6. 略。
7. float 类型不能异或。牢记下表：

数据类型	与	或	异或	取反	左移	右移
int	✔️	✔️	✔️	✔️	✔️	✔️
long long	✔️	✔️	✔️	✔️	✔️	✔️
float	❌	❌	❌	❌	❌	❌
double	❌	❌	❌	❌	❌	❌
bool	✔️	✔️	✔️	❌	❌	❌

说明：

• int 和 long long 类型支持与、或、异或、取反、左移、右移等位运算。
• float 和 double 类型不支持位运算，因为它们是浮点数类型，不是整数类型。
• bool 类型仅支持与、或、异或位运算，不支持取反和位移运算。

8. 没有考虑非整除的情况。

9. 略。

10. Linux 操作系统主要是由 $C$ 语言编写的。

11. 一个数字的算术平方根可能是无理数，没办法枚举所有的无理数。

12. $0x3f_{(16)}=63_{(10)}$，所以逻辑表达式 (0x3f == 63) 的结果是 true。

13. 如果在开头插入，下标是 $0$。所以应该是 GE123SP。

14. rfind() 从末尾开始遍历寻找。

15. "Luogu" 在字典序上小于 "Vijos"，所以返回一个负数。

16. 二进制是 $101000111101$。

17. 代入，$(1\&1|0)=(1|0)=1$。牢记：
    () > ! > 算术运算符 > 关系运算符 > 逻辑运算符
    算术运算符：$+,-,\times ,÷$
    关系运算符：$<,>,\le ,\ge ,==,\ne$
    逻辑运算符：$\&\&,||$（逻辑与的优先级大于逻辑或的优先级）

18. 没有一个数字平方的个位数是 $3$。

19. 四位二进制数可以对应一个十六进制数，所以二进制 $200$ 位可以对应 $50$ 位的十六进制数。

20. 模拟即可：

执行所在行	$i$	a[]	b[]
1	/	[]	[]
2	/	[1,1]	[]
3	/	[1,1]	[1,2]
5	3	[1,1,2]	[1,2]
6	3	[1,1,2]	[1,2,4]
5	4	[1,1,2,3]	[1,2,4]
6	4	[1,1,2,3]	[1,2,4,7]
5	5	[1,1,2,3,5]	[1,2,4,7]
6	5	[1,1,2,3,5]	[1,2,4,7,12]
5	6	[1,1,2,3,5,8]	[1,2,4,7,12]
6	6	[1,1,2,3,5,8]	[1,2,4,7,12,20]