1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	D	C	B	A	C	D	D	A	D	B	C	A	C	B	C

第 1 题  为丰富⾷堂菜谱 ，炒菜部进⾏头脑风暴 。 ⾁类有鸡⾁ 、⽜⾁ 、⽺⾁ 、猪⾁4种 ，切法有⾁排、 ⾁块、 ⾁末3     种 ，配菜有圆⽩菜、油菜、⾖腐3种 ，辣度有⿇辣、微辣、不辣3种 。不考虑⼝感的情况下 ，选1种⾁ 、 1种切法、 1种 配菜、 1种辣度产⽣⼀道菜（例如：⿇辣⽜⾁⽚炒⾖腐） ，这样能产⽣多少道菜？ （  ）。

A. 13

B. 42

C. 63

D. 108

第 2 题  已知袋中有2个相同的红球、3个相同的绿球、5个相同的黄球 。每次取出⼀个不放回 ，全部取出 。可能产⽣ 多少种序列？ （  ）。

A. 6

B. 1440

C. 2520

D. 3628800

第 3 题  以下⼆维数组的初始化 ，哪个是符合语法的？ （  ）。

  A.  int a[][] = {{1, 2}, {3, 4}};

  B.  int a[][2] = {};

  C.  int a[2][2] = {{1, 2, 3}, {4, 5, 6}};

  D.  int a[2][] = {{1, 2, 3}, {4, 5, 6}};

第 4 题 下⾯有关C++拷贝构造函数的说法 ，错误的是（  ）。

  A. 必须实现拷贝构造函数 ，否则⼀定会出现编译错误。

  B. 对象作为函数参数、 以值传递⽅式传⼊函数时 ，会⾃动调⽤拷贝构造函数。

  C. 对象作为函数返回值、 以值传递⽅式从函数返回时 ，会⾃动调⽤拷贝构造函数。

  D. 使⽤⼀个对象初始化另⼀个对象时 ，会⾃动调⽤拷贝构造函数。

第 5 题 使⽤邻接表表达⼀个⽆向简单图， 图中包含 v 个顶点、  e 条边 ，则该表中边节点的个数为（  ）。

口 A. 0 × (      1 )

0 B. 0 × 0

  C. 2 × e

口 D. e

第 6 题 关于⽣成树的说法 ，错误的是（  ）。

  A. ⼀个⽆向连通图可以有多个⽣成树。

口 B. ⼀个⽆向图 ，只要连通 ，就⼀定有⽣成树。

  C.  n 个顶点的⽆向完全图 ，有棵⽣成树。

0 D.  n 个顶点的⽆向图 ，⽣成树包含 n-1 条边。

第 7 题  已知三个 double 类型的变量 a  、 b 和 theta 分别表⽰⼀个三角形的两条边长及⼆者的夹角（弧度） ，则 下列哪个表达式可以计算这个三角形的周长？ （  ）。

0 A.  a * b * s in(theta) / 2

0 B.  a + b + (a + b) * s in(theta) / 2

0 C.  a * b * cos(theta) / 2

0 D.   a + b + sqrt(a * a + b * b - 2 * a * b * cos(theta))

第 8 题 在有 n 个元素的⼆叉排序树中进⾏查找 ，其最好、最差时间复杂度分别为（  ）。

口 A. 0) 、0()

口 B. 0(⑴ 、o(log n)

口 C. o(log n) 、O(log n)

口 D. 0(log n) 、0()

第 9 题 如下图所⽰ ，半径为 r 、 圆⼼角为 t （弧度） 的扇形 ，下⾯哪个表达式能够求出顶部阴影部分的⾯积？  (

)  。

0 A.  r * r * s in(t) / 2

0 B.  r * r * t / 2

0 C.  r * r * (t - s in(t))

0 D.  r * r * (t - s in(t)) / 2

第 10 题  下⾯程序的时间复杂度为（  ）。

1 2 3 4 5

int fib(int n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); }

口 A. 0(2")

0 B.  ，其中 = 

口 C. 0(n)

0 D. 0 )

第 11 题  下⾯程序的时间复杂度为（  ）。

1 2 3 4 5

int choose(int n, int m) { if (m == 0 || m == n) return 1; return choose(n - 1, m - 1) + choose(n - 1, m); }

口 A. 0(2")

口 B. 0(2m × (n - m))

口 C. 0(C(n, M))

口 D. 0(m × (n - m))

第 12 题  下⾯程序的时间复杂度为（  ）。

1

2

3

4

5

6

7

8

9

10

11

12

13

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;

}

}

}

0 A. 0()

口 B. 0(n × logn)

口 C. 0(n × 1oglog n)

0 D. 0(n2)

第 13 题  下⾯程序的输出为（  ）。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

#include <iostream>

using namespace std;

int a[10][10];

int main() {

int m = 5, n = 4;

for (int x = 0; x <= m; x++)

a[x][0] = 1;

for (int y = 1; y <= n; y++)

a[0][y] = 1;

for (int x = 1; x <= m; x++)

for (int y = 1; y <= n; y++)

a[x][y] = a[x - 1][y] + a[x][y - 1];

cout << a[m][n] << endl;

return 0;

}

A. 4

B. 5

C. 126

D. 3024

第 14 题  下⾯程序的输出为（  ）。

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <iostream> using namespace std; int main() { int cnt = 0; for (int x = 0; x <= 10; x++) for (int y = 0; y <= 10; y++) for (int z = 0; z <= 10; z++) if (x + y + z == 15) cnt++; cout << cnt << endl; return 0; }

A. 90

B. 91

O C. 96

第 15 题  下⾯的程序使⽤邻接矩阵表达的带权⽆向图 ，则从顶点0到顶点3的最短距离为（  ）。

1 2 3 4 5

int weight[4][4] {  0,   1,   {  1,   0,   {  7,   5,   {100,  15,

= { 7, 100}, 5,  15}, 0,   6}, 6,   0}};

A. 100

B. 16

C. 12

D. 13

2      2

20 

1    2    3    4    5    6    7    8    9    10

答案

第 1 题  已知 int 类型的变量 a 和 b ，则执⾏语句 a, b = b, a; 后 ，变量 a 和 b 的值会互换。

第 2 题 ⼀个袋⼦中有3个完全相同的红⾊⼩球、2个完全相同的蓝⾊⼩球 。每次从中取出1个 ，再放回袋⼦ ，这样进 ⾏3次后 ，可能的颜⾊顺序有7种。

第 3 题 孙⼦定理是求解⼀次同余⽅程组的⽅法 ，最早见于中国南北朝时期（公元5世纪） 的数学著作《孙⼦算 经》 。⼜称中国余数定理 ，是中国数学史上的⼀项伟⼤成就。

第 4 题 个顶点的⽆向完全图有    条边。

第 5 题 为解决哈希函数冲突 ，在哈希表项内设置链表存储该项内的所有冲突元素 ，则该哈希表内查找元素的最差时 间复杂度为 。

第 6 题 求⼀个包含 v 个顶点、  e 条边的带权连通⽆向图的最⼩⽣成树 ，Prim算法的时间复杂度为 。

第 7 题  已知 int 类型的变量 a 、 b 和 c 中分别存储着⼀个三角形的三条边长 ，则这个三角形的⾯积可以通过表达 式 sqrt((a + b + c) * (b + c - a) * (a + c - b) * (a + b - c)) / 4 求得。

第 8 题 可以使⽤深度优先搜索算法判断图的连通性。

第 9 题 在个元素的⼆叉排序树中查找⼀个元素 ，平均情况的时间复杂度是 。

第 10 题 给定 double 类型的变量 x  ，且其值⼤于等于 ，我们可以通过⼆分法求出的近似值。

3      25  50 

3.1      1

  试题名称：公倍数问题

3.1.1     问题描述                                                                                                                                 

⼩ A 写了⼀个 N X M 的矩阵 A ，我们看不到这个矩阵 ，但我们可以知道 ，其中第 i ⾏第j 列的元素 Ai，j 是 i 和 j 的 公倍数（ ，） 。现在有 K 个⼩朋友 ，其中第 K 个⼩朋友想知道 ，矩阵 A 中最多有多少个元 素可以是 k（ ） 。请你帮助这些⼩朋友求解。

注意：每位⼩朋友的答案互不相关 ，例如 ，有些位置既可能是  ，⼜可能是  ，则它同可以时满⾜ c , y 两名⼩朋友的 要求。

⽅便起见 ，你只需要输出Kk=1 k × ank 即可 ，其中 ansk 表⽰第 k 名⼩朋友感兴趣的答案。

3.1.2     输入描述                                                                                                                               

第⼀⾏三个正整数N,M, K。

3.1.3     输出描述                                                                                                                               

输出⼀⾏， 即 Kk=1 k ×  ansk 。

请注意 ，这个数可能很⼤ ，使⽤ C++语⾔的选⼿请酌情使⽤  long long 等数据类型存储答案。

3.1.4     特别提醒                                                                                                                                 

在常规程序中 ，输⼊ 、输出时提供提⽰是好习惯 。但在本场考试中， 由于系统限定 ，请不要在输⼊ 、输出中附带任 何提⽰信息。

3.1.5     样例输入 1                                                                                                                                                       

3.1.6     样例输出 1

3.1.7     样例解释 1

只有 A , 可以是 1 ，其余都不⾏。

A1，1  A12  A2  1  A2,2  都可以是 2 ，⽽其余不⾏。

因此答案是 1  ×  1 + 2 × 4 ＝ 9。

3.1.8     样例输入 2

3.1.9     样例输出 2

3.1.10     数据规模

对于 30 的测试点 ，保证 N, M, K ≤ 10；

对于 60 的测试点 ，保证 N, M, K ≤ 500；

对于 100 的测试点 ，保证 N, M ≤ 105 ，K

3.1.11     参考程序

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <vector> using namespace std; vector<int> count_divisors(int limit, int num) { vector<int> s(num + 1, 0); for (int i = 1; i <= limit; ++i) { for (int j = i; j <= num; j += i) { s[j] += 1; } } return s; } int main() { int N, M, K; c in >> N >> M >> K; vector<int> s_N = count_divisors(N, 1000000); vector<int> s_M = count_divisors(M, 1000000); long long result = 0; for (int k = 1; k <= K; ++k) { result += (long long)k * s_N[k] * s_M[k]; } cout << result << endl; return 0; }

3.2     编程题 2                                                                                                                                            

·   试题名称：接⽵竿

3.2.1     题面描述                                                                                                                                  

⼩杨同学想⽤卡牌玩⼀种叫做“接⽵竿” 的游戏。

游戏规则是：每张牌上有⼀个点数 v ，将给定的牌依次放⼊⼀列牌的末端 。若放⼊之前这列牌中已有与这张牌点数相 同的牌 ，则⼩杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本⾝） 。

⼩杨同学现在有⼀个长度为 n 的卡牌序列 A ，其中每张牌的点数为 Ai    1（ ） 。⼩杨同学有 q 次询问 。第  次  ( )  询问时 ，⼩杨同学会给出 li  ri ，⼩杨同学想知道如果⽤下标在 i  Ti的所有卡牌按照下标顺序玩“接⽵  竿” 的游戏 ，最后队列中剩余的牌数。

3.2.2     输入格式                                                                                                                                

第⼀⾏包含⼀个正整数 T ，表⽰测试数据组数。

对于每组测试数据 ，第⼀⾏包含⼀个正整数 n ，表⽰卡牌序列 A 的长度。

第⼆⾏包含  个正整数 A ,A2， ，An ，表⽰卡牌的点数 A。

第三⾏包含⼀个正整数  ，表⽰询问次数。

接下来 q ⾏ ，每⾏两个正整数 i  Ti ，表⽰⼀组询问。

3.2.3     输出格式

对于每组数据 ，输出 q ⾏ 。第 i ⾏（ ）输出⼀个⾮负整数 ，表⽰第 i 次询问的答案。

3.2.4     样例 1

1 2 3 4 5 6 7 8

1 6 1 2 2 3 1 3 4 1 3 1 6 1 5 5 6

1 2 3 4

1 1 0 2

3.2.5     样例解释

对于第⼀次询问 ，⼩杨同学会按照 1 , 2  2  的顺序放置卡牌 ，在放置最后⼀张卡牌时 ，两张点数为 2  的卡牌会被收 ⾛， 因此最后队列中只剩余⼀张点数为 1  的卡牌。

对于第⼆次询问， 队列变化情况为：

{} → {1} → {1 , 2} → {1 , 2 , 2} → {1} → {1 , 3} → {1 , 3, 1} → {} → {3} 。 因此最后队列中只剩余⼀张点数为 3 的卡 牌。

3.2.6     数据范围

子任务编号   数据点占比    T                                     max Ai               特殊条件
1                        30           ≤ 5				0           ≤		13
2                     30            ≤ 5  ≤	1  5	104	≤  1 5 ×	104	≤	13     所有询问的右端点等于 n
3                     40           ≤ 5 ≤	1 . 5	104	≤  1 . 5  ×	104	≤	13

对于全部数据 ，保证有 1  ≤ T ≤ 5 ，1  ≤ n   1 . 5  ×  104 ， ， 。

3.2.7     参考程序

1

2

int nxt[N][30],pos[20];

int main(){

int t;

c in>>t;

while(t--){

int n;

c in>>n;

memset(pos,0,sizeof pos);

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

for(int i=1;i<=n;i++){

c in>>a[i];

for(int j=0;j<=20;j++)nxt[i][j]=n+1;

}

for(int i=n;i>=1;i--){

if(!pos[a[i]]){

nxt[a[i]][0]=n+1;

pos[a[i]]=i;

}else{

nxt[i][0]=pos[a[i]];

pos[a[i]]=i;

}

}

for(int i=n;i>=1;i--){

for(int j=1;j<=20;j++){

if(nxt[i][j-1]+1<=n)

nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];

}

}

int q;

c in>>q;

while(q--){

int l,r;

c in>>l>>r;

int ii=l;

int ans=0;

while(ii<=r){

while(ii<=r&&nxt[ii][0]>r){

ii++;

ans++;

}

if(ii>r)break;

for(int j=20;j>=0;j--){

if(nxt[ii][j]<=r){

ii=nxt[ii][j];

break;

}

}

ii++;

}

cout<<ans<<"\n";

}

}

}