小码农

趣味编程-面向每个人的创意编程
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

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

A. 13

B. 42

C. 63

D. 108

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

A. 6

B. 1440

C. 2520​​​​​​​

D. 3628800

第 题  以下⼆维数组的初始化 ,哪个是符合语法的? (  )。

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

第  下⾯有关C++拷贝构造函数的说法 ,错误的是(  )。

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

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

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

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

第  使⽤邻接表表达⼀个⽆向简单图, 图中包含 v 个顶点、  e 条边 ,则该表中边节点的个数为(  )。

口 A. 0 × (      1 )

B0 × 0

  C. 2 × e

口 D. e

第  关于⽣成树的说法 ,错误的是(  )。

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

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

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

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

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

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

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

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

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

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

口 A0) 、0()

口 B0(⑴ 、o(log n)

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

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

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

)  。

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

B.  r * r * t / 2

C.  r * r * (t – s in(t))

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″)

B.  ,其中 =

口 C. 0(n)

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″)

口 B0(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;

}

}

}

A. 0()

口 B0(n × logn)

口 C. 0(n × 1oglog n)

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

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
答案

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

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

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

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

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

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

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

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

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

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

}

}

}

来源:6547题库网 http://www.6547.cn/doc/w4rnc2iitk


发表评论