| 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
试题名称：公倍数问题
⼩ A 写了⼀个 N X M 的矩阵 A ，我们看不到这个矩阵 ，但我们可以知道 ，其中第 i ⾏第j 列的元素 Ai，j 是 i 和 j 的 公倍数（ ，） 。现在有 K 个⼩朋友 ，其中第 K 个⼩朋友想知道 ，矩阵 A 中最多有多少个元 素可以是 k（ ） 。请你帮助这些⼩朋友求解。
注意：每位⼩朋友的答案互不相关 ，例如 ，有些位置既可能是 ，⼜可能是 ，则它同可以时满⾜ c , y 两名⼩朋友的 要求。
⽅便起见 ，你只需要输出Kk=1 k × ank 即可 ，其中 ansk 表⽰第 k 名⼩朋友感兴趣的答案。
第⼀⾏三个正整数N,M, K。
输出⼀⾏， 即 Kk=1 k × ansk 。
请注意 ，这个数可能很⼤ ，使⽤ C++语⾔的选⼿请酌情使⽤ long long 等数据类型存储答案。
在常规程序中 ，输⼊ 、输出时提供提⽰是好习惯 。但在本场考试中， 由于系统限定 ，请不要在输⼊ 、输出中附带任 何提⽰信息。
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; } |
· 试题名称：接⽵竿
⼩杨同学想⽤卡牌玩⼀种叫做“接⽵竿” 的游戏。
游戏规则是：每张牌上有⼀个点数 v ，将给定的牌依次放⼊⼀列牌的末端 。若放⼊之前这列牌中已有与这张牌点数相 同的牌 ，则⼩杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列（包括这两张牌本⾝） 。
⼩杨同学现在有⼀个长度为 n 的卡牌序列 A ，其中每张牌的点数为 Ai 1（ ） 。⼩杨同学有 q 次询问 。第 次 ( ) 询问时 ，⼩杨同学会给出 li ri ，⼩杨同学想知道如果⽤下标在 i Ti的所有卡牌按照下标顺序玩“接⽵ 竿” 的游戏 ，最后队列中剩余的牌数。
第⼀⾏包含⼀个正整数 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”;
}
}
}
来源：6547题库网 http://www.6547.cn/doc/w4rnc2iitk
-
扫码下载安卓APP
-
微信扫一扫关注我们
-
返回顶部
发表评论