一、选择题

第一题

C++

中，

bool

类型的变量占用字节数为（

）。

A

、

1

B

、

2

C

、

3

D

、

4

答案：A

解析：（C++ 中 bool 类型与 char 类型一样，都需要1 byte。一些其他类型的占用字节数：short：2 byte。int：4 byte。long long：8 byte。double：8 byte。）

第二题

以下关于数组的说法，不正确的是（

）。

A

、数组中所有元素的类型必须相同

B

、数组中各元素在内存中是顺序存放的

C

、数组最后一个元素的索引是数组的长度

D

、数组名的第一个字符可以是下划线

答案：C

解析：(A中结构体中可以定义成员变量，也可以定义只有该结构体类型变量可调用的成员函数 B中 所谓结构体的继承特性，指的是在一个已经定义好的旧结构体的基础上，创建一个新结构体，并且新结构体可以复用旧结构体的成员和函数。C正确，D中构造函数可以在创建结构体变量时，按照函数预设的构造规则，将对应成员变量赋值，并执行其他操作。构造函数在创建结构体类型的对象时自动执行，因此无法由用户主动调用，也没有返回值。）

第三题

设只含根结点的二叉树高度为

1

，共有

62

个结点的完全二叉树的高度为（

）。

A

、

4

B

、

5

C

、

6

D

、

7

第四题

以下关于

C++

结构体的说法，正确的是（

）。

A

、结构体中只能包含成员变量，不能包含成员函数

B

、结构体不能从另一个结构体继承

C

、结构体里面可以包含静态成员变量

D

、结构体里面不能包含构造函数

答案：C

解析：以 int a[100]; 为例，最后一个元素为 a[99]，下标索引 99 为数组长度减 1。

第五题

执行以下代码，输出的结果是（

）。

#include <iostream>

using namespace std;

int f(int k)

{

if (k == 1)

{

return 3;

}

return 2 * f(k - 1) + 1;

}

int main()

{

int n = 6;

cout << f(n);

return 0;

}

A、127

B

、

97

C

、

63

D

、

126

二、编程题

第一题

编程实现：特殊运算符

题目描述：

假定有一个运算符“

>>>

”，它的功能如下所示：

>>>257 = 25

>>>182 = 18

>>>933 = 93

3

给定一个正整数

N

（

100<N<1000

），请计算

N – (>>>N)

的结果。

例如：

N=257

时，

257 – (>>>257)

= 257 – 25

= 232

输入描述：

输入一个正整数

N

（

100<N<1000

）

输出描述：

输出一个整数，表示

N - (>>>N)

的结果

样例输入：

257

样例输出：

232

第二题

编程实现：四叶玫瑰数

题目描述：

四叶玫瑰数是指一个四位数，其各位上的数字的四次方之和等于本身的数。

给定两个正整数

N

和

M

，请将

N~M

（

1

≤

N

≤

M

≤

1000000

）之间（含

N

和

M

）的四叶玫瑰数按从小到大的顺序输

出。

例如：

N=1234

，

M=2345

时，有一个四叶玫瑰数

1634

，因为

1^4 + 6^4 + 3^4 + 4^4 = 1634

，故输出

1634

。

输入描述：

第一行输入两个正整数

N

、

M

（

1

≤

N

≤

M

≤

1000000

）

输出描述：

输出一行，包含若干个用一个空格隔开的正整数，表示

N~M

之间的四叶玫瑰数按从小到大的顺序的输出结果

注意：

题目数据保证给定的

N~M

范围内至少有一个四叶玫瑰数

样例输入：

1234 2345

样例输出：

1634

4

第三题

编程实现：质因数的个数

提示信息：

因数：又称为约数，如果整数

a

除以整数

b(b

≠

0)

的商正好是整数而没有余数，我们就说

b

是

a

的因数。

质数：又称为素数，一个大于

1

的自然数，除了

1

和它自身外，不能被其他自然数整除的数叫做质数。

2

是最

小的质数。

质因数：如果一个数

a

的因数

b

同时也是质数，那么

b

就是

a

的一个质因数，例如：

8=2

×

2

×

2

，

2

就是

8

的质

因数；

12

＝

2

×

2

×

3

，

2

和

3

就是

12

的质因数。

题目描述：

给定两个正整数

N

和

M

（

1

≤

N

≤

M

≤

1e7

），统计

N

到

M

之间（含

N

和

M

）每个数所包含的质因数的个数，输出其

中最大的个数。

例如：

当

N=6

，

M=10

，

6

到

10

之间

6

的质因数是

2

、

3

，共有

2

个

7

的质因数是

7

，共有

1

个

8

的质因数是

2

、

2

、

2

，共有

3

个

9

的质因数是

3

、

3

，共有

2

个

10

的质因数是

2

、

5

，共有

2

个

6

到

10

之间的数中质因数最多的是

8

，质因数有

3

个，故输出

3

。

输入描述：

输入两个正整数

N

和

M

（

1

≤

N

≤

M

≤

1e7

），两个正整数之间用一个空格隔开

输出描述：

输出一个整数，表示质因数个数中的最大值

样例输入：

6 10

样例输出：

3

<code>#include <bits/stdc++.h>

using namespace std;

// 声明常量及变量

const int N = 1e7 + 5; // N表示可能的质数的上限

int primes[N], p; // primes数组保存已知的质数列表，p表示质数个数

bool sign[N]; // sign数组用来标记某个数是否是质数

int s[N]; // s数组用来记录每个数的最大质因子个数

// 埃氏筛法初始化质数表

void init_Primes(int n) {

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

if (!sign[i]) primes[p++] = i; // i是质数，加入质数表中

for (int j = 0; primes[j] <= n / i; j++) {

sign[primes[j] * i] = true; // 将i和质数表中所有不大于n/i的数的积标记为合数

if (i % primes[j] == 0) break; // 如果primes[j]是i的因子，则退出循环

}

}

}

// 计算数n的最大质因子个数

int tj_(int n) {

int tj = 0; // tj表示n的最大质因子个数

for (int i = 0; i < p; i++) { // 枚举质数表中所有质数

while (n % primes[i] == 0) { // 如果当前质数是n的因子

tj++; // 更新最大质因子个数

n /= primes[i]; // 去掉该质因子

if (n == 1) return tj; // 如果n变为了1，则说明所有质因子均被枚举完毕

}

}

}

int main() {

int n, m;

cin >> n >> m;

init_Primes(m); // 初始化质数表

int res = 0; // res表示区间内最大质因子个数

for (int i = n; i <= m; i++) { // 枚举每个数，计算其最大质因子个数，更新res

res = max(res, tj_(i));

}

cout << res; // 输出结果

return 0;

}

第四题

编程实现：最大的矩形纸片

题目描述：

5

一张半边参差不齐的网格纸（网格边长均为

1

），有一边是完整没有破损的。现要从中剪出一片面积最大的

矩形纸片。

给定网格纸中完整边的长度

N

（

1

≤

N

≤

1000000

），以及网格中每一列残存部分的高度（

1

≤高度≤

10000

），输出能够剪出的最大矩形纸片面积。

例如：

N=6

，每一列残存部分的高度依次为

3

、

2

、

1

、

4

、

5

、

2

，如下图所示：

可以发现，沿着红色框可以剪出的矩形纸片面积最大，为

8

，所以输出

8

。

输入描述：

第一行输入一个正整数

N

（

1

≤

N

≤

1000000

），表示纸片完整边的长度

第二行输入

N

个正整数（

1

≤正整数≤

10000

），表示每列格子残存部分的高度，两个正整数之间用一个空格

隔开

输出描述：

输出一个正整数，表示能够剪出的最大矩形纸片面积

样例输入：

6

3 2 1 4 5 2

样例输出：

8

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5;

long long n,a[N];

int main() {

cin>>n;

for(int i=1; i<=n; i++) cin>>a[i];

long long ans=0,min_n=0; // ans 记录最大的面积，min_n 记录当前区间中的最小值

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

min_n=N;

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

min_n=min(min_n,a[j]); // 更新当前区间中的最小值

ans=max(ans,(j-i+1)*min_n); // 根据更新后的最小值来计算当前区间的面积，并记录最大值

}

}

cout<<ans; // 输出最大面积

return 0;

}

第五题

编程实现：数字游戏

题目描述：

老师给出了一组数，要求小蓝对这组数进行调整，调整的规则如下：

1.

第

1

次，从这组数中选出一个最小的数，把它调整为和第二小的数一样大

;

6

2.

第

2

次，再从这组数中选出一个最大的数，把它调整为和第二大的数一样大

;

3.

重复执行

1

、

2

步骤

;

4.

当这组数中所包含的不同的数少于

3

个时，结束调整。

现在给定了一组数，请帮小蓝编写程序计算出总共的调整次数，以及调整结束时这组数中的最小数和最大

数。

例

1

：

当这组数是

2 2 2 2

时，这组数中所包含的不同的数少于

3

个（只有

2

这一种数），无需调整，最后输出：

0 2 2

例

2

：

当这组数是

1 3 4 2

时，调整过程如下：

1.

先将这组数中最小的数

1

，改成

2

，这组数变为：

2 3 4 2

2.

再将这组数中最大的数

4

，改成

3

，这组数变为：

2 3 3 2

这时，这组数中只包含

2

、

3

两个数了，满足规则

4

，调整结束，总共调整了

2

次，故最后输出：

2 2 3

输入描述：

第一行输入一个正整数

N

（

3

≤

N

≤

1000000

），表示这组数中数的个数

第二行输入

N

个正整数（

1

≤正整数≤

1000000

），正整数之间用一个空格隔开

输出描述：

输出一行，包含三个整数，分别是总的调整次数、调整结束时的最小值和最大值，整数之间用一个空格隔开

样例输入：

4

1 3 4 2

样例输出：

2 2 3

#include <bits/stdc++.h>

using namespace std;

const int N=1e6 +7;

//using LL = long long;

int a[N],b[N],mp[N];

long long ct[N];

int main() {

int n;

scanf("%d",&n);

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

scanf("%d",a + i);

b[i]= a[i];

}

//离散化

sort(b+1,b+n+1);//去重以后，m即为不同的元素个数

int m =unique(b+1,b+n+1)-b-1;

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

mp[b[i]]= i;

}

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

ct[mp[a[i]]]++;

}

int l=1,r= m;

long long tot =0;//每一轮都从最小值开始

while(l+1<r) {

if(ct[l]<= ct[r]) {

//左边删掉ct[1]，右边先删掉ct[1]-1

tot += ct[l]+ ct[l]-1;

ct[1+1]+= ct[l];

ct[r]-= ct[l]-1;

ct[r-1]+=ct[l]-1;

//判断此时能否结束

if(++l+1 == r) break;

//对应删除最右边的1个

tot++,ct[r]--,ct[r-1]++;

//判断右边是否个数为0

if(!ct[r])--r;

} else {

tot += ct[r]+ ct[r];

ct[l+1]+= ct[r];

ct[l]-= ct[r];

ct[r-1]+= ct[r];

r--;

}

}

printf("%lld %d %d",tot,b[l],b[r]);

}

第六题

编程实现：活动人数

题目描述：

有一个大型企业集团，由

N

个部门组成，编号从

1

到

N

。这些部门之间的层次关系形成了一个树状结构，一个

上级部门可能会有

1

个或多个直接下级部门，一个下级部门只有一个直接上级部门。

本月集团举办了一个大型活动，这次的活动组织方按如下要求安排活动：

1.

来的人越多越好；

2.

如果一个上级部门参加本次活动，那么他们的直接下级部门就不能参加，而他的间接下级部门可以参加

（如下图，如果部门

1

参加，那么部门

2

、

3

不能参加，而部门

4

、

5

、

6

可以参加）。

请你帮他们计算一下，如何安排可以使参加活动的人数最多，并输出参加活动的最多人数。

例如：当

N=6

，每个部门编号为

1

到

6

，部门上下级关系和部门的人数如下图所示：

注意：示例中，部门

1

是层级最高的部门，没有直接上级，故将其直接上级部门设为

0

；

当安排（

1

、

4

、

5

、

6

）这

4

个部门参加活动时，人数最多，为

11

，所以输出

11

。

输入描述：

第一行输入一个正整数

N

（

1

≤

N

≤

100000

），表示集团所有部门的数量

接下来有

N

行，每行输入三个非负整数

F

、

S

和

C

，（

0

≤

F

≤

N

，

1

≤

S

≤

N

，

F≠S

，

1

≤

C

≤

1000

），

F

表示部门

S

的直接上级，

C

表示部门

S

的人数，整数之间用一个空格隔开

注意：如果是最上层的部门，其直接上级部门编号设为

0

输出描述：

输出一个整数，表示参加活动的最多人数

样例输入：

6

8

0 1 2

1 2 4

1 3 3

2 4 3

3 5 2

3 6 4

样例输出：

11

#include <bits/stdc++.h> // 包含常用的头文件

using namespace std;

const int N=1e5 + 7;

// 记录每个部门及其直接下属参与活动的人数

int f[N][2];

// 存储每个部门的人数

int p[N];

//边结构体表示树形结构

struct Edge {

int v; // 目标部门ID

Edge *nx; // 指向下一个边

Edge(int _v, Edge *_n):v(_v), nx(_n) {} // 构造函数

}* hd[N];

// 负责存储当前部门下级链表的指针

//Edge* hd[N];

// 深度优先搜索，计算最大参与人数

void dfs(int u, int pa) {

// 部门u参加活动，则自身人数加上直接下属的参加人数

f[u][1] += p[u];

// 遍历u的所有下级

for(Edge *i = hd[u]; i; i = i->nx) {

int v = i->v; // 当前处理的下级部门

if (v == pa) continue; // 跳过父级

// 递归处理下级部门

dfs(v, u);

// 更新u的参与人数，包括直接下属和间接下级

f[u][1] += f[v][0];

f[u][0] += max(f[v][0], f[v][1]); // 取两者中的较大值

}

}

// 主函数入口

int main() {

int n;

scanf("%d", &n); // 读取部门总数

// 遍历各部门信息

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

int u, v, w; // 上级部门、下级部门、人数

//scanf("%d %d %d", &u, &v, &w);

cin>>u>>v>>w;

// 添加边并记录人数

hd[u] = new Edge(v, hd[u]);

p[v] = w; // 如果作为上级，它的直接下属人数增加

}

// 初始化根节点

dfs(0, 0);

// 输出最大参加人数

// printf("%d\n", f[0][0]);

cout<<f[0][0];

}