笔试强训错题总结(一)

笔试强训错题总结

选择题

1. 以下程序的运行结果是（）

#include 
int main(void) {
    printf("%s , %5.3s\n", "computer", "computer");
    return 0;
}
1
2
3
4
5

A.computer , puter

B.computer , com

C.computer , computer

D.computer , compu.ter

这里对于第二种打印方式理解的不到位，%5.3s指的是域宽为5，但是只打印三个字符，不足的地方用空格来填充

最后答案选：B

---

2. 在头文件及上下文均正常的情况下，下列代码的运行结果是（）

int a[] = {1, 2, 3, 4};
int *b = a;
*b += 2;
*(b + 2) = 2;
b++; 
printf("%d,%d\n", *b, *(b + 2));

1
2
3
4
5
6
7

A. 1,3 B. 1,2 C. 2,4 D. 3,2

这里我忽略了b++这个语句，单纯的将*(b+2)与上述语句中的等换了，其实在经历过上述语句之前a数组中的内容就变为了3 ,2,2,4这样的数组，原本b指向的是首元素，但是b++以后指向的就是第二个元素的位置，由于b是整形指针，所以+1就是跳过一个整形大小，因此b+2就是指向了4的位置

最后答案选：C

---

3. 在32位cpu上选择缺省对齐的情况下，有如下结构体定义：

struct A
{ 
    unsigned a : 19; 
    unsigned b : 11;
    unsigned c : 4;
    unsigned d : 29; 
    char index;
}; 
1
2
3
4
5
6
7
8

则sizeof（struct A）的值为（）

A. 9 B. 12 C. 16 D. 20

这是位段，变量后面跟的数字代表的是占用多少个比特位；一个unsigned是一个四字节的类型，也就是32个比特位，a和b共同占用四个字节，然后c和d各自单独占用四个字节（因为c和d总计要占用33个比特位，超过unsigned的大小，所以只能给它们各自开一个unsigned的空间），char占用一个字节，最后内存对齐以下总共占用16个字节

最后答案选：C

---

4. 假设在一个 32 位 little endian 的机器上运行下面的程序，结果是多少？

#include 
int main()
{
 	long long a = 1, b = 2, c = 3;
 	printf("%d %d %d\n", a, b, c); 
 return 0;
}
1
2
3
4
5
6
7

A. 1,2,3 B. 1,0,2 C. 1,3,2 D. 3,2,1

首先我们要知道什么是小端，所谓的小端就是低位存低地址，高位存高地址。但这个题目恶心的点在于变量都是long long类型的，但是打印方式采用的是十进制整形打印，所谓十进制整形打印就是只选取前四个字节打印，而long long 是有八个字节的，具体情况见下图：

所以该题最后的答案选：B

此外如果你想验证一个机器是小端机还是大端机，只要将一个整型变量的第一个字节取出来就可

#include
using namespace std;
int main()
{
	int a = 1;
	if ((*(char*)&a) == 1)
		cout << "小端" << endl;
	else
		cout << "大端" << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11

---

5. 求函数返回值，输入x=9999

int func(int x)
{
    int count=0;
    while (x)
    {
        count++;
        x=x&(x-1);//与运算
    }
return count;
}

1
2
3
4
5
6
7
8
9
10
11

A. 8 B. 9 C. 10 D. 12

这题的关键在于理解x=x&(x-1)是用于去除比特位中1的，也就是说x的比特位中有多少个1，循环就进行多少次，要获得x中1的个数，可以采用短除法来得到：

所以最后答案是选A

---

6. 二维数组X按行顺序存储，其中每个元素占1个存储单元。若X[ 4 ] [ 4 ]的存储地址为Oxf8b82140,X[9] [9]的存储地址为Oxf8b8221c,则X[7] [7]的存储地址为()。

A. Oxf8b821c4 B. Oxf8b821a6 C. Oxf8b82198 D. Oxf8b821c

关键的问题在于不知道这个数组一共有多少行，每行又有多少列，所以可以假设这个数组有M行，N列，所以可以得到下面的推算：

最后答案啊选A

---

7. 下列程序的打印结果是（）//day5

char p1[15] = "abcd", *p2 = "ABCD", str[50] = "xyz";
strcpy(str + 2, strcat(p1 + 2, p2 + 1));
printf("%s", str);
1
2
3

A. xyabcAB B. abcABz C. ABabcz D. xycdBCD

首先要了解strcpy和strcat两个函数的作用，strcpy（p，q）是字符串拷贝函数，将q字符串拷贝给p，然后返回p；strcat(p,q)是字符串追加函数，将q追加给p（会找到字符串p的末尾追加），然后返回p。这两个函数都要求p中有足够大的空间。strcat(p1+2,p2+1)执行完p1中的结果是abcdBCD，然后执行strcpy(str+2,p1+2)就得到xycdBCD

所以最后答案是选：D

---

8. 有一个如下的结构体： 请问在64位编译器下用sizeof(struct A)计算出的大小是多少（）

struct A
{
    long a1;
    short a2;
    int a3;
    int *a4;
};
1
2
3
4
5
6
7

A. 24 B. 28 C. 16 D. 18

该题的关键点在于是64位环境，在64位环境下指针是8个字节，也就是：4+4+4+8=20字节，最后对齐一下就是24字节

所以最后答案选：A

---

9. 执行下面语句后的输出为

int I=1;
if(I<=0) 
 printf("****\n") ;
else 
 printf("%%%%\n");
1
2
3
4
5

A. %% B. * * * * C. 有语法错，不能正确执行 D. %%%%

转义字符是我没想到的，两个%只能输出一个%，所以答案选A

---

10. C++ 中，有如下类模板定义： 已知 b1, b2 是 BigNumber 的两个对象，则下列表达式中错误的是（）

template<class T> class BigNumber
{
 	long n;
public:
	 BigNumber(T i) :n(i) {}
 	BigNumber operator+(BigNumber b) 
	 {
 		return BigNumber(n + b.n);
 	}
}
1
2
3
4
5
6
7
8
9
10

A. 3+3 B. b1+3 C. b1+b2 D. 3+b1

对于A选项来说，加号本身就支持内置类型之间的相加，所以它根本不走类中的函数；如果一个类拥有单个参数的构造函数，那么该构造函数还具有类型转换的作用，所以针对B选项时，构造函数会将3从整形转换成BingNumber的类型，所以B选项没有问题，但是this指针要求必须是类类型的对象，所以D是不正确的，因此该题选D

---

11. 以下代码共调用多少次拷贝构造函数：

Widget f(Widget u)
{ 
 	Widget v(u);
	Widget w=v;
  return w;
}
int main()
{
 Widget x;
 Widget y=f(f(x));
}
1
2
3
4
5
6
7
8
9
10
11

A. 1 B. 3 C. 5 D. 7

首先分析f(x)调用一次有多少次拷贝构造，首先传参数的时候是传值传参一次拷贝构造(原本是先构造一个临时变量，再用临时变量拷贝构造给形参，但是编译器优化以后变成一次拷贝构造)，然后函数题内部调用了两次拷贝构造（其中Widget w=v调用的也是拷贝构造，因为它是用的已初始化的对象起构造一个未初始化的对象；最后在返回的时候还有一次拷贝构造；再用这个返回值作为第二次函数调用，在第二次函数调用的时候，编译器有些优化，比如在传参的时候，因为返回值和参数都是临时变量，所以就不用调用拷贝构造了，传参的那次拷贝构造被省略了，在函数体内的两次拷贝构造无法省略，最后在返回值的时候又有一次优化，原本是要先构造一个临时变量，再用临时变量构造y，但是这里直接用返回值去构造y了。所以最后的结果就是：4+2+1=7次，答案选D

---

13. 下面有关c++静态数据成员，说法正确的是（）

A. 不能在类内初始化 B. 不能被类的对象调用 C. 不能受private修饰符的作用 D. 可以直接用类名调用

对于const的静态成员来说，可以在类中初始化，静态成员被所有的类对象共享，成员变量一般都是私有的，所以该题选D

---

14. 在C++中，为了让某个类只能通过new来创建（即如果直接创建对象，编译器将报错），应该（）

A. 将构造函数设为私有 B. 将析构函数设为私有 C. 将构造函数和析构函数均设为私有 D. 没有办法能做到

将析构函数设置成私有即可，因为如果将构造函数设置成私有，连new都无法创建对象，因为new首先要开辟空间，然后再调用构造函数对空间进行初始化，如果构造函数是私有的就无法在类外调用，所以这题选B

---

15. 拷贝构造函数的特点是（）

A. 该函数名同类名，也是一种构造函数，该函数返回自身引用

B. 该函数只有一个参数，是对某个对象的引用

C. 每个类都必须有一个拷贝初始化构造函数，如果类中没有说明拷贝构造函数，则编译器系统会自动生成一个缺省拷贝构造函数，作为该类的保护成员

D. 拷贝初始化构造函数的作用是将一个已知对象的数据成员值拷贝给正在创建的另一个同类的对象

拷贝构造函数没有返回值，只有一个参数并且必须是本类类型对象的引用，如果没有拷贝构造，则编译器会自动生成一个作为公有成员，所以答案选D

---

16. 以下程序输出是____。

#include 
using namespace std;
int main(void)
{
 	const int a = 10;
 	int * p = (int *)(&a);
 	*p = 20;
 	cout<<"a = "<<a<<", *p = "<<*p<<endl
  return 0;
}
1
2
3
4
5
6
7
8
9
10

A. 编译阶段报错运行阶段报错

B. a = 10, *p = 10

C. a = 20, *p = 20

D. a = 10, *p = 20

E. a = 20, *p = 10

C++中被const修饰的变量有两个特点：1.该变量是一个常量了 2.具有替换作用，即使是使用指针对该变量中的值做了修改，在打印该变量中，仍然使用那个常量

所以本题选D

---

18. 假定有类AB，有相应的构造函数定义，能正确执行 语句，请问执行完此语句后共调用该类的构造函数次数为___ //day11

AB a(4),b(5),c[3],*p[2]={&a,&b}
1

A. 5 B. 4 C. 3 D. 9

创建a对象和b对象各调用一次构造函数，c数组中有三个类对象的变量，最后的指针并没有创造对象，所以不会调用构造函数

所以此题选A

---

19. 下列关于赋值运算符“=”重载的叙述中，正确的是

A. 赋值运算符只能作为类的成员函数重载

B. 默认的赋值运算符实现了“深层复制”功能

C. 重载的赋值运算符函数有两个本类对象作为形参

D. 如果己经定义了复制拷贝构造函数，就不能重载赋值运算

默认的赋值重载是按字节进行浅拷贝，赋值运算符重载只能重载成类的成员函数，并且只有一个参数，因为还有一个隐藏的this指针，如果定义了拷贝构造也是可以重载赋值运算的

所以本题选A

---

20. 若PAT是一个类，则程序运行时，语句“PAT(*ad)[3];”调用PAT的构造函数的次数是（）

A. 2 B. 3 C. 0 D. 1

ad是一个数组指针，是一个指针并没有创建对象，所以没有调用构造函数。选C

---

21. 下面对析构函数的正确描述是（）

A. 系统不能提供默认的析构函数

B. 析构函数必须由用户定义

C. 析构函数没有参数

D. 析构函数可以设置默认参数

如果不显示定义析构函数，编译器会自动身材一个默认的析构函数，析构函数没有参数，所以析构函数不能重载

所以这题选C

---

编程题

连续最大和

题目描述：一个数组有 N 个元素，求连续子数组的最大和。

例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3 输入描述：输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。 输出描述：所有连续子数组中和最大的值。

---

解法

我原本就是暴力破解，搞一个双重循环，从第一个位置开始往后加，然后将结果与max进行判断，再从第二个位置往后加，再将结果与max判断，最后得到最大值。但是这样的解法是一个O(N^2）效率极差，所以这里就不放代码了。

优化解法

这题可以使用动态规划的思想，将复杂度优化到O(N)；动态规划最关键的是状态方程：

求最大子数组连续和的状态方程是GetMax=(dp[i-1]+arr[i],arr[i])

如果i位置前的数组元素和是一个正数，那么对于i位置来说，最大和肯定是arr[i]加上之前的元素和，但是如果之前的元素和是一个负数，那么对于i位置来说，它的最大和就是它自己本身，因此我们可以得到如下代码：

#include
#include
using namespace std;

int GetMax(int a,int b)
{
    return a>b?a:b;
}

int main() {
    int n = 0;
    cin >> n;
    vector<int> v;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int sum = v[0];
    int maxsum = v[0];
    for (int i = 1; i < n; i++) {
        sum=GetMax(sum+v[i],v[i]);

        if(sum>=maxsum)
            maxsum=sum;
    }
    cout << maxsum << endl;
    return 0;
}

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

---

不要二

二货小易有一个W*H的网格盒子，网格的行编号为0_{H-1，网格的列编号为0}W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。

对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为: ( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根

小易想知道最多可以放多少块蛋糕在网格盒子里。

#include
#include
using namespace std;

int main()
{
    int w, h;
    int count = 0;
    cin >> w >> h;
    vector<vector<int>> vv;//需要定义一个w行，h列的二维数组
    vv.resize(w);
	for (auto& e : vv)
		e.resize(h,1);//将每一行的元素扩容为h个，并初始化为1
//遍历判断，当x1，y1位置放了蛋糕以后，（x1+2，y1）或者（x1，y1+2）的位置不能放蛋糕，最后统计非0元素的个数即可
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
        	if (vv[i][j] == 1)
        	{
           	 	count++;
            	if (i + 2 < w)
                	vv[i + 2][j] = 0;
           	 	if (j + 2 < h)
                	vv[i][j + 2] = 0;
        	}
        }
    }
    cout << count << endl;
    return 0;
}
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
31

---

最近公共祖先

将一棵无穷大满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。

测试样例：

2，3
返回：1
1
2

解题思路

其实这道题的思路很简单，因为编号是层序从小到大编号的，所以子节点的值一定大于父节点的值，让大的节点去找它的父节点，将这个父节点再与小的节点作比较看是否相等，如果不相等就再让大的节点去找父节点，知道相等为止

所以可以得到这样的代码：

class LCA {
public:
    int getLCA(int a, int b) {
        // write code here

        while(a!=b)
        {
            if(a>b)
            {
                a=a/2;
            }
            else
            {
                b=b/2;
            }
        }
        return a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

最大连续的bit数

求一个int类型数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

数据范围：数据组数：1≤t≤5 1\le t\le 5\ 1≤t≤5 ，1≤n≤500000 1\le n\le 500000\ 1≤n≤500000

进阶：时间复杂度：O(logn) O(logn)\ O(logn) ，空间复杂度：O(1) O(1)\ O(1)

解题思路

判断一个数的比特位中有多少个1，只要不断左移再让每一个比特位按位与上1即可，这里不建议使用右移，因为右移补的是符号位，也就是说如果是一个负数，那么就会不断在高位补1，永远无法结束

#include 
using namespace std;

int main() {
    int num=0;
    while(cin>>num)
    {
        int count=0,maxcount=0;
        for(int i=0;i<32;i++)
        {
            if(num&(1<<i))
            {
                count++;
                maxcount=maxcount>count?maxcount:count;
            }
            else{ 
             count=0;
            }
        }
        cout<<maxcount<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

幸运的袋子

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入描述:

第一行输入一个正整数n(n ≤ 1000)
第二行为n个数正整数xi(xi ≤ 1000)
1
2

输出描述:

输出可以产生的幸运的袋子数
1

---

解题思路

这个题目要采用回溯的办法来解决：

1.首先要清楚，如果一些数的和大于它们的乘积那就说明这些数里面至少包括一个1

2.先对这些数据进行排序，这样可以减少重复次数，排序也为后面的去重打下了一定的基础

3.首先以最小的数打头，开始往后一旦到某个数不再幸运，那么就说明比这个数大的数放进来也不会是幸运的，那么此时就打断回溯

4.回溯以后进行去重，如果有两个一样的数，就不能再将这个数作为开头了，否则会将两个重复的结果作为两次输出，而且因为前面排序的原因，不用担心会有131和113这样随机的相同序列产生。

#include
#include
#include
using namespace std;

int getLuckPacket(vector<int>& x, int n, int pos, int sum, int mul)
{
	int count = 0;
	for (int i = pos; i < n; i++)
	{
		//第一个数直接加上去就行
		sum += x[i];
		mul *= x[i];

		if (sum > mul)
			count += 1 + getLuckPacket(x, n, i + 1, sum, mul);
		else if (x[i] == 1)//如果不幸运就看第一个数是不是1，是1的话后面还可能会是幸运的,否则后面的数再加进来也不会幸运，直接打断回溯
			count += getLuckPacket(x, n, i + 1, sum, mul);
		else
			break;

		//回溯就要将之前那个数的影响去掉
		sum -= x[i];
		mul /= x[i];
		
		//去重
		while (i < n - 1 && x[i] == x[i + 1])
			i++;

		

	}
	return count;
}

int main()
{
	int n = 0;

	while (cin >> n)
	{
		vector<int> v(n);
		
		for (int i = 0; i < n; i++)
			cin >> v[i];

		//排序
		sort(v.begin(), v.end());

		cout << getLuckPacket(v, n, 0,0, 1)<<endl;
	}

	return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

---

手套

在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。

给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。

测试样例：

4,[0,7,1,6],[1,5,0,6]
返回：10(解释：可以左手手套取2只，右手手套取8只)
1
2

解题思路

解决本题的关键在于如何拿一次就可以将所有的颜色都覆盖到，假设有这样一个手套数组[4,2,3,7,5]要想将其中每种颜色都包含进去的话，至少要拿19只手套，即总和sum减去最小值min再加1只手套。此外如果遇到某种颜色左手有，右手没有，或者右手有，左手没有，那么就要将该种颜色的手套也添加进去

class Gloves {
public:
    int findMinimum(int n, vector<int> left, vector<int> right)
     {
        // write code here

        int left_sum=0,left_min=INT_MAX;
        int right_sum=0,right_min=INT_MAX;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(left[i]*right[i]==0)
                sum+=left[i]+right[i];
            else
            {
                left_sum+=left[i];
                left_min=left_min<left[i]?left_min:left[i];
                
                right_sum+=right[i];
                right_min=right_min<right[i]?right_min:right[i];
            }
        }
        
        return sum+min(left_sum-left_min+1,right_sum-right_min+1)+1;
        //为零的累加和加上左右手中的最小值再+1
    }
};
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