一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

【第 1 题】

给定一个含 N 个不相同数字的数组，在最坏情况下，找出其中最大或最小的 数，至少需要 N−1 次比较操作。则最坏情况下，在该数组中同时找最大与 最小的数至少需要（ ）次比较操作。（ ⌈⌉ 表示向上取整，⌊⌋ 表示向下取整）

{{ select(1) }}

• $⌈\frac{3N}{2}-2⌉$
• $⌊\frac{3N}{2}-2⌋$
• $2N-2$
• $2N-4$

【第 2 题】

若某算法的计算时间表示为递推关系式：

$T(N)=2T(\frac{N}{2})+NlogN$

$T(1)=1$

则该算法的时间复杂度为（ ）。

{{ select(2) }}

• $O(N)$
• $O(NlogN)$
• $O(Nlog^2N)$
• $O(N^2)$

【第 3 题】

在一条长度为 $1$ 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）。

{{ select(3) }}

• $\dfrac{1}{2}$
• $\dfrac{1}{3}$
• $\dfrac{2}{3}$
• $\dfrac{3}{5}$

【第 4 题】

关于 Catalan 数 $C_n=\dfrac{(2n)!}{(n+1)!\,n!}$，下列说法中错误的是（ ）。

{{ select(4) }}

• $C_n$ 表示有 $n+1$ 个结点的不同形态的二叉树的个数。
• $C_n$ 表示含 $n$ 对括号的合法括号序列的个数。
• $C_n$ 表示长度为 $n$ 的入栈序列对应的合法出栈序列个数。
• $C_n$ 表示通过连接顶点而将 $n+2$ 边的凸多边形分成三角形的方法个数。

【第 5 题】

假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。

{{ select(5) }}

• $1:2$
• $2:1$
• $1:3$
• $1:1$

【第 6 题】

若 $f_0=0$，$f_1=1$，$f_{n+1}=\frac{f_n+f_{n-1}}{2}$，则随着 i 的增大，$f_i$ 将接近于（ ）。

{{ select(6) }}

• $\frac{1}{2}$
• $\frac{2}{3}$
• $\frac{\sqrt{5}-1}{2}$
• $1$

【第 7 题】

在 n(n≥3) 枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c 三行代码补全到算法中。

a. A ← X ∪ Y

b. A ← Z

c. n ← |A|

算法 Coin(A, n)

1. k ← ⌊n/3⌋   
2. 将 A 中硬币分成 X，Y，Z 三个集合，使得 |X| = |Y| = k,|Z| = n - 2k  
3. if W(X) ≠ W(Y)       //W(X), W(Y) 分别为 X 或 Y 的重量   
4. then __________   
5. else __________   
6. __________   
7. if n>2 then goto 1   
8. if n=2 then 任取 A 中 1 枚硬币与拿走硬币比较，若不等，则它不合格； 若相等，则 A 中剩下的硬币不合格.    
9. if n=1 then A 中硬币不合格

正确的填空顺序是（ ）。

{{ select(7) }}

• b, c, a
• c, b, a
• c, a, b
• a, b, c

【第 8 题】 2017 年 10 月 1 日是星期日，1949 年 10 月 1 日是（ ）。

{{ select(8) }}

• 星期三
• 星期日
• 星期六
• 星期二

【第 9 题】 由四个不同的点构成的简单无向连通图的个数是（ ）。

{{ select(9) }}

• 32
• 35
• 38
• 41

【第 10 题】 将 $7$ 个名额分给 $4$ 个不同的班级，允许有的班级没有名额，有（ ）种不同的分配方案。

{{ select(10) }}

• 60
• 84
• 96
• 120

【第 11 题】

有正实数构成的数字三角形排列如图所示。第一行的数为 $a_{1,1}$；第二行的数从左到右依次为 $a_{2,1},\,a_{2,2}$；……；第 $n$ 行的数为 $a_{n,1},\,a_{n,2},\,\ldots,\,a_{n,n}$。从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1},\,a_{n,2},\,\ldots,\,a_{n,n}$ 中某个数的路径，使得该路径上的数之和达到最大。令 $C_{i,j}$ 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数和的最大值，并且 $C_{i,0}=C_{0,j}=0$，则 $C_{i,j}=$（ ）。

{{ select(11) }}

• $\max\{C_{i-1,j-1},\, C_{i-1,j}\}+a_{i,j}$
• $C_{i-1,j-1}+C_{i-1,j}$
• $\max\{C_{i,j-1},\, C_{i-1,j}\}+1$
• $\max\{C_{i,j-1},\, C_{i-1,j}\}+a_{i,j}$

【第 12 题】

小明要去南美洲旅游，共要乘坐三趟航班才能到达目的地，其中第 1 个航班准点的概率为 0.9，第 2 个航班准点的概率为 0.8，第 3 个航班准点的概率为 0.9。若存在第 $i$ 个（$i=1,2$）航班晚点，第 $i+1$ 个航班准点，则小明将赶不上第 $i+1$ 个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是（ ）。

{{ select(12) }}

• 0.5
• 0.648
• 0.72
• 0.74

【第 13 题】

欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”，正方形场地中心能不断喷出彩色乒乓球。以场地中心为圆心还有一圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。

假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个小火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球。每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到（ ）个乒乓球。假设乒乓球喷出的速度为 $2$ 个/秒，每节车厢的面积是整个场地面积的 $\dfrac{1}{20}$。

{{ select(13) }}

• 60
• 108
• 18
• 20

【第 14 题】

某计算机的 CPU 和内存之间的地址总线宽度是 $32$ 位（bit），这台计算机最多可以使用（ ）的内存。

{{ select(14) }}

• 2GB
• 4GB
• 8GB
• 16GB

【第 15 题】 具有 $n$ 个顶点、$e$ 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。

{{ select(15) }}

• $\Theta(n^2)$
• $\Theta(e^2)$
• $\Theta(ne)$
• $\Theta(n+e)$

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 ⨉ ；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

阅读程序1

1   #include <iostream>
2   using namespace std;
3   const int mod = 2048;
4   long long c, n;
5   long long f(long long x, long long m) {
6       long long res = 1;
7       while(m){
8           if(m&1){
9               res = (res*x)%mod;
10          }
11          x = (x*x)%mod;
12          m >>= 1;
13      }
14      return res;
15  }
16  int main(){
17      cin >> n >> c;
18      if(n == 3){
19          printf("%lld", c*(c-1));
20          return 0;
21      }
22      long long ans = ((f(c-1, n)+(c-1)*f(-1,n))%mod+mod)%mod;
23      cout << ans << endl;
24      return 0;
25  }

判断题

16、将第9行和第11行的括号去掉，程序输出结果一定不变。

{{ select(16) }}

• 正确
• 错误

17、将第12行的 m>>=1 改成 m*=0.5，程序输出结果一定不变。

{{ select(17) }}

• 正确
• 错误

18、若输入为“4 4”，则输出为“78”。

{{ select(18) }}

• 正确
• 错误

19、此程序的时间复杂度为 O(logn)。

{{ select(19) }}

• 正确
• 错误

单选题

20、若输入为“3 4”，则输出为（ ）。

{{ select(20) }}

• 9
• 12
• 18
• 19

21、f(2046,13)的返回值为（ ）。

{{ select(21) }}

• 0
• 2022
• 2
• 2024

阅读程序2

1   #include <iostream>
2   #define N 1005
3
4   using namespace std;
5   int num[N];
6
7   int main(){
8       int al = 1, n, x;
9       scanf("%d", &n);
10      num[1] = 1;
11      for(int i = 1; i <= n; i++) {
12          x = 0;
13          for(int j = 1; j <= al; ++j){
14              num[j] = num[j] * 5 + x;
15              x = num[j] / 10;
16              num[j] %= 10;
17          }
18          if(x > 0) num[++al] = x;
19      }
20      cout << "0.";
21      for(int i = al; i < n; ++i) {
22          cout << 0;
23      }
24      for(int i = al; i >= 1; i--) {
25          cout << num[i];
26      }
27      cout << endl;
28      return 0;
29  }

判断题

22、程序执行到 27 行时，i 的值为1。。

{{ select(22) }}

• 正确
• 错误

23、对于任意 1<=i<=al，都有 0<=num<=9。

{{ select(23) }}

• 正确
• 错误

24、程序输出的是一个小数，且小数末尾可能有多余的 0。

{{ select(24) }}

• 正确
• 错误

25、程序输出的是 $5^n$ 的值。

{{ select(25) }}

• 正确
• 错误

单选题

26、此程序的时间复杂度是（ ）。

{{ select(26) }}

• $O(n)$
• $O(n^2)$
• $O(n^3)$
• $O(2^n)$

27、若输入3，则输出为（ ）。

{{ select(27) }}

• 8
• 0.125
• 0.8
• 125

阅读程序3

1   #include<bits/stdc++.h>
2   using namespace std;
3   const int MAXN=2e5+5;
4   int nums[MAXN];
5   int left_bound (int n, int target) {
6       int left = 0, right = n - 1;
7       while (left <= right) {
8           int mid = (left + right) / 2;
9           if(nums[mid] < target)
10              left = mid + 1;
11          else
12              right = mid - 1;
13      }
14      if(left < n && nums[left] == target)
15          return left;
16      return -1;
17  }
18  int right_bound(int n, int target) {
19      int left = 0, right = n - 1;
20      while (left <= right) {
21          int mid = (left + right) / 2;
22          if(nums[mid] <= target)
23              left = mid + 1;
24          else
25              right = mid - 1;
26      }
27      if(right >= 0 && nums[right] == target)
28          return right;
29      return -1;
30  }
31  int main()
32  {
33      int n, c;
34      cin>>n>>c;
35      for (int i = 0; i < n; ++i)
36          cin>>nums[i];
37      sort(nums, nums + n);
38      long long ans = 0;
39      for (int i = 0; i < n; ++i) {
40          int left = left_bound(n, nums[i] + c);
41          int right = right_bound(n, nums[i] + c);
42          if(left != -1)
43              ans += right - left + 1;
44      }
45      cout<<ans;
46      return 0;
47  }

输入数据 n、c、nums[i]≤${2 \times 10^5}$，且均为正整数。

判断题

28、将第38行中的long long 替换为 int，程序的运行结果不变。（ ）

{{ select(28) }}

• 正确
• 错误

29、将第3行中的 const 去掉，程序的运行结果不变。（ ）

{{ select(29) }}

• 正确
• 错误

30、将第14行中的left < n 去掉，程序的运行结果不变。（ ）

{{ select(30) }}

• 正确
• 错误

单选题

31、第8行的写法在某些时候会导致程序运行有问题，最好换成写法（ ）。

{{ select(31) }}

• mid = （left +right）<< 1
• mid = left + (right - left)/2
• mid = (left + right) >> 1
• mid = (left + right) % 2

32、本程序的时间复杂度为（ ）。

{{ select(32) }}

• $O(logn)$
• $O(n)$
• $O(n^2)$
• $O(nlogn)$

33、 当输入 4 1 1 1 2 3 时，程序的输出结果为（ ）。

{{ select(33) }}

• 1
• 2
• 3
• 4

三、完善程序（单选题，每小题 3 分，共计 30 分）

程序填空1

（交朋友）根据社会学研究表明，人们都喜欢找和自身身高相近的人做朋友。现在有 $n$ 名身高两两不同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为 1.80 米的同学进入教室时，有一名身高为 1.79 米的同学和一名身高为 1.81 米的同学在教室里，那么这名身高为 1.80 米的同学会更想和身高为 1.81 米的同学做朋友。对于第一名走入教室的同学我们不做预测。由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序和栈的方法帮助每个人找到在他之前进入教室并且和他身高最相近的人。

试补全程序。

#include <iostream> 
using namespace std; 
#define MAXN 200000
#define infinity 2147483647
int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN];
int rank[MAXN];
int n;
void sort(int l, int r)
{
    int x = height[rank[(l + r) / 2]], i = l, j = r, temp;
    while (i <= j)
    {
        while (height[rank[i]] < x)
            i++;
        while (height[rank[j]] > x)
            j--;
        if ((____1____))
        {
            temp = rank[i];
            rank[i] = rank[j];
            rank[j] = temp;
            i++;
            j--;
        }
    }
    if (i < r)
        sort(i, r);
    if (l < j)
        sort(l, j);
}
int main()
{
    cin >> n;
    int i, higher, shorter;
    for (i = 1; i <= n; i++)
    {
        cin >> height[i];
        rank[i] = i;
	}
	sort(1, n);
	for (i = 1; i <= n; i++)
	{
		previous[rank[i]] = rank[i - 1];
		(____2____);
	}
	for (i = n; i >= 2; i--)
	{
		higher = shorter = infinity;
		if (previous[i] != 0)
			shorter = height[i] - height[previous[i]];
		if (next[i] != 0)
			(____3____);
		if ((____4____))
			answer[i] = previous[i];
		else
			answer[i] = next[i];
		next[previous[i]] = next[i];
		(____5____);
	}
	for (i = 2; i <= n; i++)
		cout << i << ":" << answer[i];
	return 0;
}

34、① 处应填（ ）

{{ select(34) }}

• rank[i]<rank[j]
• rank[i]<=rank[j]
• i<=j
• i<j

35、② 处应填（ ）

{{ select(35) }}

• next[rank[i]]=rank[i+1]
• rank[next[i]]=i+1
• rank[i]=next[1+1]
• next[i]=rank[i+1]

36、③ 处应填（ ）

{{ select(36) }}

• higher=height[next[i]]-height[i]
• higher=height[next[i]]+height[i]
• previous[next[i]]=previous[i]
• previous[next[i]]=previous[i+1]

37、④ 处应填（ ）

{{ select(37) }}

• shorter<higher
• shorter<=higher
• previous[next[i]]=previous[i]
• previous[next[i]]=previous[i+1]

38、⑤ 处应填（ ）

{{ select(38) }}

• previous[next[i]]=previous[i]
• higher=height[next[i]]+height[i]
• previous[next[i+1]]=previous[i]
• previous[next[i]]=previous[i+1]

程序填空2

（交通中断）有一个小国家，国家内有 $n$ 座城市和 $m$ 条双向的道路，每条道路连接着两座不同的城市。其中 $1$ 号城市为国家的首都。由于地震频繁可能偶尔导致某一个城市与外界交通全部中断。这个国家的首脑很烦恼，如果只有第 $i\ (i>1)$ 个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因无法通过第 $i$ 个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。

对于每一个城市 $i$，假定只有第 $i$ 个城市与外界交通中断，输出有多少个城市会因此导致到首都的最短路径长度发生改变。

我们采用邻接表的方式存储图的信息，其中 head[x] 表示顶点 $x$ 的第一条边的编号，next[i] 表示第 $i$ 条边的下一条边的编号，point[i] 表示第 $i$ 条边的终点，weight[i] 表示第 $i$ 条边的长度。 .

#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 6000
#define MAXM 100000
#define infinity 2147483647
int head[MAXN], next[MAXM], point[MAXM], weight[MAXM];
int queue[MAXN], dist[MAXN], visit[MAXN];
int n, m, x, y, z, total = 0, answer;
void link(int x, int y, int z)
{
    total++;
    next[total] = head[x];
    head[x] = total;
    point[total] = y;
    weight[total] = z;
    total++;
    next[total] = head[y];
    head[y] = total;
    point[total] = x;
    weight[total] = z;
}
int main()
{
    int i, j, s, t;
    cin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        link(x, y, z);
    }
    for (i = 1; i <= n; i++)
        dist[i] = infinity;
    (1);
    queue[1] = 1;
    visit[1] = 1;
    s = 1;
    t = 1;
    // 使用 SPFA 求出第一个点到其余各点的最短路长度
    while (s <= t)
    {
        x = queue[s % MAXN];
        j = head[x];
        while (j != 0)
        {
            if ((2))
            {
                dist[point[j]] = dist[x] + weight[j];
                if (visit[point[j]] == 0)
                {
                    t++;
                    queue[t % MAXN] = point[j];
                    visit[point[j]] = 1;
                }
            }
            j = next[j];
        }
        (3);
        s++;
    }
    for (i = 2; i <= n; i++)
    {
        queue[1] = 1;
        memset(visit, 0, sizeof(visit));
        visit[1] = 1;
        s = 1;
        t = 1;
        while (s <= t)
        { // 判断最短路长度是否不变
            x = queue[s];
            j = head[x];
            while (j != 0)
            {
                if (point[j] != i && (4) && visit[point[j]] == 0)
                {
                    (5);
                    t++;
                    queue[t] = point[j];
                }
                j = next[j];
            }
            s++;
        }
        answer = 0;
        for (j = 1; j <= n; j++)
            answer += 1 - visit[j];
        cout << i << ":" << answer - 1 << endl;
    }
    return 0;
}

1、①处应填（ ）。

{{ select(39) }}

• dist[0]=infinity
• dist[1]=infinity
• dist[0]=0
• dist[1]=0

2、②处应填（ ）。

{{ select(40) }}

• dist[point[j]]>=dist[x]+weight[j]
• dist[point[j]]>dist[x]+weight[j]
• dist[point[i]]>dist[x]+weight[i]
• dist[point[i]]>=dist[x]+weight[i]

3、③处应填（ ）。

{{ select(41) }}

• visit[x]=0
• visit[x]=1
• visit[point[j]] = 1
• visit[point[j]] = 0

4、④处应填（ ）。

{{ select(42) }}

• weight[j]+dist[x]>dist[point[j]]
• weight[j]+dist[x]<dist[point[j]]
• weight[j]+dist[x]==dist[point[j]]
• weight[j]+dist[x]!=dist[point[j]]

5、⑤处应填（ ）。

{{ select(43) }}

• visit[point[j]]=1
• visit[point[j]]=0
• point[j] ==0
• point[j] ==1