选择题
01
有以下程序
#include <iostream> #include <cstdio> using namespace std; int main() { int m = 0123, n = 123; printf("%o %o\n", m, n); return 0; }
程序运行后的输出结果是()
A 0123 0173
B 0123 173
C 123 173
D 173 173
题目解析:
int m = 0123
:以 0 开头代表这个数是八进制的哈!%o
:表示将数字以 8 进制的方式进行输出。n = 123
对应的 8 进制数是 173.
答案:C
知识点总结:
八进制数
八进制数是以数字 0 开头的整数。例如,
0123
是一个八进制数。在C语言中,可以使用
%o
或%#o
作为格式说明符来输出八进制数。其中,%o
会输出不带前导0的八进制数,而%#o
会输出带前导0
的八进制数。十六进制数
十六进制数是以
0x
或0X
开头的整数,后面跟着0-9的数字和A-F(或a-f)的字母。例如,0x1A3F
是一个十六进制数。在C语言中,可以使用
%x
、%X
、%#x
或%#X
作为格式说明符来输出十六进制数。其中,%x
和%X
会分别输出小写和大写字母的十六进制数,而%#x
和%#X
会在前面加上0x
或0X
前缀。
02
以下哪个选项一定可以将flag的第二个bit置0()
A flag&=~2
B flag|=2
C flag^=2
D flag>>=2
题目解析:
- A:
~2
表示将 2 的二进制位按位取反,取反之后只有第二个比特位是 0 其余的比特位都是 1。然后与 flag 相与就能正确将flag的第二个bit置0。 - B:B 选项是将 flag 的第二个比特位置 1 哈!
- C:C 选项使用异或结果是不确定的。当 flag 的第二个比特位是 1 那么就是置 0,flag 的第二个比特位是 0 就是置 1 啦!
- D:选项 D 是将 flag 右移两位,相当于除以 4 与题目毫不相关哈!
答案:A
知识点总结:
- 按位与
(&)
:它将参与运算的两个二进制数进行与运算。如果两个二进制位都为1,则运算结果为1,否则为0。例如,6(二进制为00000110)和11(二进制为00001011)进行按位与运算,结果为00000010,即数值2。 - 按位或
(|)
:它将参与运算的两个二进制数进行或运算。如果两个二进制位上有一个值为1,则运算结果为1,否则为0。继续以上面的例子为例,6和11进行按位或运算,结果为00001111,即数值15。 - 按位异或
(^)
:它将参与运算的两个二进制数按照对应的位进行异或运算。如果两个二进制位相同,则运算结果为0,否则为1。对于任意数a,a0=a,aa=0。 - 按位取反
(~)
:这是位运算符中唯一的单目运算符,它将操作数的每一位取反(0→1,1→0)。例如,6(二进制为00000110)进行按位取反运算,结果为11111001,即数值-7(在计算机中,负数通常使用补码表示)。 - 左移
(<<)
:它将一个数的各二进制位全部左移若干位,左移后右边补入0,左边移出的位舍弃。例如,如果a=3(二进制为0011),则a<<1的结果为6(二进制为0110)。左移一位相当于乘以2。 - 右移
(>>)
:它将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃。
03
请声明一个指针,其所指向的内存地址不能改变,但内存中的值可以被改变。
A const int const *x = &y;
B int * const x = &y;
C const int *x = &y;
D int const *x = &y;
E const int * const x = &y;
题目解析:
- 选项 A,C,D 表示内存中的值不可以改变。
- 选项 E 表示内存地址不能改变,内存中的值也不可以改变
答案:B
知识点总结:
- 看是哪种情况其实只要看
const
在*
的左边还是在*
的右边哈! - 如果 const 在 * 的左边,那么就是指针指向的内容不可变。
- 如果 const 在 * 的右边,那么就是指针本身不可以改变。
04
以下C语言指令:
int a[5] = {1,3,5,7,9}; int *p = (int *)(&a+1); printf(“%d,%d”,*(a+1),*(p-1));
运行结果是什么?
A 2,1
B 3,1
C 3,9
D 运行时崩溃
题目解析:
- 第一个数字肯定是 3 哈!数组名 a 表示数组首元素地址,
*(a + 1)
就等价于a[1]
。 &a
中的数组名 a 就是表示整个数组的地址啦!(&a + 1)
会跳过整个数组,指向数组最后一个元素的下一个位置。然后在强转为(int*)
表明 p 解引用的时候会被解析为int
类型。因此*(p - 1)
就是数组的最后一个元素哈!也就是 9。
答案:C
知识点总结:
指针类型在 C 语言中的意义:
指针类型决定了指针解引用操作符能访问的字节数。例如,
char*
类型的指针解引用时会访问1个字节,而int*
类型的指针解引用时会访问4个字节(这取决于具体的系统和编译器,对于int
类型的大小可能会有所不同)。指针类型决定了指针进行算术运算(如加、减)时移动的字节数。例如,对于
char*
类型的指针,p+1
会跳过一个字节;而对于int*
类型的指针,p+1
则会跳过一个整型的大小(如4个字节)。
数组名代表数组首元素的地址。但在
&数组名
以及sizeof 数组名
的时候,数组名表示的是整个数组。
05
二维数组X按行顺序存储,其中每个元素占1个存储单元。若
X[4][4]
的存储地址为Oxf8b82140,X[9][9]
的存储地址为Oxf8b8221c,则X[7][7]
的存储地址为()。A Oxf8b821c4
B Oxf8b821a6
C Oxf8b82198
D Oxf8b821c0
题目解析:
首先,我们知道二维数组X
按行顺序存储,即每一行的元素是连续存储的。因此,X[i][j]
的存储地址可以通过X[0][0]
的初始地址加上偏移量得到。偏移量是由前面的所有元素所占的存储单元数决定的。
对于X[4][4]
和X[9][9]
的存储地址,我们可以先计算它们之间有多少元素,然后计算这些元素占用的存储单元数,从而确定每个元素占用的地址偏移量。
X[4][4]
到X[9][9]
跨越了(9-4) * 4 + (9-4)
个元素(前9行中,从第5行到第9行,每行4个元素;再加上第9行本身的4个元素)。- 这些元素总共占用了
(9-4) * 4 + (9-4) = 25
个存储单元(因为每个元素占1个存储单元)。 - 地址偏移量可以通过存储单元数计算,因为地址通常是连续增长的。所以,每个元素占用的地址偏移量是
(Oxf8b8221c - Oxf8b82140) / 25
。 - 然后,为了找到
X[7][7]
的地址,我们需要从X[4][4]
的地址开始,加上从X[4][4]
到X[7][7]
的元素数量对应的偏移量。从X[4][4]
到X[7][7]
跨越了(7-4) * 4 + (7-4)
个元素。 - 因此,
X[7][7]
的地址为:Oxf8b82140 + ((7-4) * 4 + (7-4)) * (Oxf8b8221c - Oxf8b82140) / 25
。
答案:A
知识点总结:
- 无论是几维的数组,在内存的视角看都是顺序存储的!
06
根据下面递归函数:调用函数Fun(2),返回值是多少()
int Fun(int n) { if (n == 5) return 2; else return 2 * Fun(n + 1); }
A 2
B 4
C 8
D 16
题目解析:
根据给定的递归函数Fun
,当调用Fun(2)
时,会执行以下步骤:
- 检查
n
是否等于5,此时n
为2,所以条件不满足,进入else
分支。 - 在
else
分支中,函数会调用自身,参数n
加1,即Fun(n + 1)
变为Fun(3)
。 - 再次检查
n
是否等于5,此时n
为3,条件依然不满足,再次进入else
分支。 - 函数再次调用自身,参数
n
变为4,即Fun(4)
。 - 再次检查
n
是否等于5,此时n
为4,条件依然不满足,继续进入else
分支。 - 函数再次调用自身,参数
n
变为5,即Fun(5)
。 - 此次调用检查
n
是否等于5,此时n
确实为5,条件满足,函数返回2。 - 回到
Fun(4)
的调用,它返回2 * Fun(5)
,即2 * 2 = 4
。 - 回到
Fun(3)
的调用,它返回2 * Fun(4)
,即2 * 4 = 8
。 - 最后回到
Fun(2)
的调用,它返回2 * Fun(3)
,即2 * 8 = 16
。
如果你不理解的话,可以尝试画递归展开图:
知识点总结:
递归想想不出来可以画递归展开图来理解。
07
以下程序的输出结果是:
#include <iostream> using namespace std; void func(char **m) { ++m; cout << *m << endl; } int main() { static char *a[] = {"morning", "afternoon", "evening"}; char **p; p = a; func(p); return 0; }
A afternoon
B 字符o的起始地址
C 字符o
D 字符a的起始地址
题目解析:
- 在主函数
main()
中,p
是一个指向指针的指针,它被设置为指向数组a
的第一个元素的地址。 - 主函数中调用了
func(p)
,将指向a
的指针传递给func()
函数。 - 在
func()
函数中,++m
增加了m
的值,所以m
指向了数组a
中的下一个元素,即"afternoon"
。 *m
表示取m
所指向的地址的值,即取"afternoon"
的值,所以输出结果是"afternoon"
。
答案:A
知识点总结:
- 字符串常量就是该字符串第一个字符的地址哈!
08
求函数返回值,输入x=9999
int func(int x) { int count = 0; while (x) { count++; x = x & (x - 1); } return count; }
A 8
B 9
C 10
D 12
题目解析:
这个函数就是统计参数 x 的二进制表示中有多少个 1 的。9999 的二进制表示中有 8 个 1。因此选择答案 A。不理解的话可以举一个例子。
( 0110 ) 2 − 1 = ( 0101 ) 2 ( 0101 ) 2 & ( 0110 ) 2 = ( 0100 ) 2 (0110)_2 - 1 = (0101)_2 \\ (0101)_2 \& (0110)_2 = (0100)_2 (0110)2−1=(0101)2(0101)2&(0110)2=(0100)2
是不是消去了二进制表示的最后一个 1。
答案:A
知识点总结:
常见的位运算技巧:
- 清零最低位的1:
x = x & (x - 1)
。这个技巧会清除x
中最低位的1。 - 获取最低位的1:
x & -x
。这个技巧会得到x
中最低位的1。 - 判断奇偶性:
x & 1
。如果结果为1,表示x
是奇数;如果结果为0,表示x
是偶数。 - 交换两个数的值:使用异或运算,
a = a ^ b; b = a ^ b; a = a ^ b;
。这个技巧不需要额外的内存空间就可以交换两个变量的值。 - 取反:
~x
。这个操作会对x
的每一位取反。 - 右移一位:
x >> 1
。这个操作会将x
的二进制表示向右移动一位。相当于除以 2。 - 左移一位:
x << 1
。这个操作会将x
的二进制表示向左移动一位。相当于乘以 2。 - 检查特定位是否为1:
(x & (1 << n)) != 0
。这个技巧可以检查x
的第n
位是否为1。 - 将特定位置的位设为1:
x |= (1 << n)
。这个技巧可以将x
的第n
位设为1。 - 将特定位置的位设为0:
x &= ~(1 << n)
。这个技巧可以将x
的第n
位设为0。
09
下列程序执行后,输出的结果为()
#include <stdio.h> int cnt = 0; int fib(int n) { cnt++; if (n == 0) return 1; else if (n == 1) return 2; else return fib(n - 1) + fib(n - 2); } void main() { fib(8); printf("%d", cnt); }
A 41
B 67
C 109
D 177
题目解析:
该函数就是求斐波那契数列哈,打印 cnt 就是让我们求出来 fib(8) 调用了多少次 fib 函数。
根据上面的流程图,我们看到:
- fib(0), fib(1) 只需要调用 1 次 fib 函数。
- fib(2) 需要调用 1 + f i b ( 1 ) + f i b ( 0 ) = 3 1 + fib(1) + fib(0) = 3 1+fib(1)+fib(0)=3 次 fib 函数。
- fib(3) 需要调用 1 + f i b ( 2 ) + f i b ( 1 ) = 5 1 + fib(2) + fib(1) = 5 1+fib(2)+fib(1)=5 次 fib 函数。
- fib(4) 需要调用 1 + f i b ( 3 ) + f i b ( 2 ) = 9 1 + fib(3) + fib(2) = 9 1+fib(3)+fib(2)=9 次 fib 函数。
- fib(5) 需要调用 1 + f i b ( 4 ) + f i b ( 3 ) = 15 1 + fib(4) + fib(3) = 15 1+fib(4)+fib(3)=15 次 fib 函数。
- fib(6) 需要调用 1 + f i b ( 5 ) + f i b ( 4 ) = 25 1 + fib(5) + fib(4) = 25 1+fib(5)+fib(4)=25 次 fib 函数。
- fib(7) 需要调用 1 + f i b ( 6 ) + f i b ( 5 ) = 41 1 + fib(6) + fib(5) = 41 1+fib(6)+fib(5)=41 次 fib 函数。
- fib(8) 需要调用 1 + f i b ( 7 ) + f i b ( 6 ) = 67 1 + fib(7) + fib(6) = 67 1+fib(7)+fib(6)=67 次 fib 函数。
答案:B
知识点总结:
无
10
在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是()
struct A { int a; short b; int c; char d; }; struct B { int a; short b; char c; int d; };
A 16,16
B 13,12
C 16,12
D 11,16
题目解析:
对于结构体A:
int a
需要4个字节short b
需要2个字节,但是由于对齐要求,它会被对齐到4字节边界,因此也需要4个字节int c
需要4个字节char d
需要1个字节
因此,结构体A的总大小是4 + 4 + 4 + 1 = 13 字节。但由于对齐要求,会向上取整到4的倍数,所以实际上结构体A占用了16字节。
对于结构体B:
int a
需要4个字节short b
需要2个字节char c
需要1个字节int d
需要4个字节,由于对齐要求,d 需要在 8 偏移量处对齐。
因此,结构体B的总大小是4 + 2 + 1 + 1 + 4 = 12 字节。12 字节正好是最大对齐数 4 的整数倍,所以 B 结构体就是 12 字节
所以,sizeof(A) 是 16,sizeof(B) 是 16。
答案:C
知识点总结:
的内存对齐原则:
- 结构体的第一个成员在结构体变量偏移量为 0 的地址处,即第一个成员变量无论什么类型都是对齐到结构体的首地址(偏移量为 0 的位置)
- 结构体的其他成员变量需要对齐到某个对齐数的整数倍地址偏移量处,其中某个对齐数是成员变量自身的大小和编译器默认对齐数的较小值。
- 结构体的总大小是每个结构体成员变量对齐数的最大值的整数倍。
- 如果出现结构体嵌套,那么嵌套的结构体对齐到该结构体的最大对齐数的整数倍地址偏移量处。
- Visual Studio 中默认对齐数是 8。
__attribute__((packed))
:取消变量对齐,按照实际占用字节数对齐(就是让变量之间排列紧密,不留缝隙)。(gcc支持)#pragma pack (n)
:修改默认对齐数。
编程题
原题链接:
https://www.nowcoder.com/practice/02d8d42b197646a5bbd0a98785bb3a34?tpId=85&&tqId=29857&rp=1&ru=/activity/oj&qru=/ta/2017test/question-ranking
- ACM编程题 标题:计算糖果 | 时间限制:1秒 | 内存限制:32768K
A,B,C三个人是好朋友,每个人手里都有一些糖果,我们不知道他们每个人手上具体有多少个糖果,但是我们知道以下的信息:
A - B, B - C, A + B, B + C. 这四个数值.每个字母代表每个人所拥有的糖果数.
现在需要通过这四个数值计算出每个人手里有多少个糖果,即A,B,C。这里保证最多只有一组整数A,B,C满足所有题设条件。
输入描述:
输入为一行,一共4个整数,分别为A - B,B - C,A + B,B + C,用空格隔开。 范围均在-30到30之间(闭区间)。
输出描述:
输出为一行,如果存在满足的整数A,B,C则按顺序输出A,B,C,用空格隔开,行末无空格。 如果不存在这样的整数A,B,C,则输出No
示例1:
输入
1 -2 3 4
输出
2 1 3
题目解析:
A,B,C是三个人手里的糖果数量,我们不知道A,B,C是多少?但是我们知道A - B, B - C, A + B, B + C的结果,这个结果题目是通过输入测试用例给我们的。所以本题本质是一个表达式求解问题。
解题思路:
1、A - B = a 2、B - C = b 3、A + B = c 4、B + C = d 这道题目的实质是:判断三元一次方程组是否有解及求解, 这里是小学生都会的问题了^^ 1+3可以得到A=(a+c)/2;4-2可以得到C=(d-b)/2;
2+4可以得到B2=(b+d)/2,3-1可以得到B1=(c-a)/2;
如果B1不等B2则表达式无解
完整代码:
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
int A = (a + c) / 2;
int C = (d - b) / 2;
int B1 = (c - a) / 2;
int B2 = (b + d) / 2;
if (B1 != B2)
cout << "No";
else
cout << A << " " << B1 << " " << C;
return 0;
}
02
- ACM编程题 标题:进制转换 | 时间限制:1秒 | 内存限制:32768K
给定一个十进制数M,以及需要转换的进制数N。将十进制数 M 转化为 N 进制数
输入描述:
输入为一行,M(32位整数)、N(2 ≤ N ≤ 16),以空格隔开。
输出描述:
为每个测试实例输出转换后的数,每个输出占一行。如果N大于9,则对应的数字规则参考16进制(比如,10用A表示,等等)
示例1:
输入
7 2
输出
111
题目解析:
本题题目很简单,题目的本意就是将10进制的数转换成N进制。N(2 ≤ N ≤ 16)可以看出进制最多可以到16进制。
解题思路:
本题思路很简单,首先想清楚原理:N进制数,每个进制位的值分别是X0*N^0,X1*N^1, X2*N^2.....,X0,X1
,X2就是这些进制位的值,就是就是进行取模余数就是当前低进制的位的值是多少,通过除掉进制数,进入下一个进制位的计算。
完整代码:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string s, table = "0123456789ABCDEF";
int m, n;
cin >> m >> n;
bool flag = false;
// 如果是负数,则转成正数,并标记一下
if (m < 0)
{
m = 0 - m;
flag = true;
}
// 按进制换算成对应的字符添加到s
while (m)
{
s += table[m % n];
m /= n;
}
if (flag)
s +='-' ;
reverse(s.begin(), s.end());
cout << s << endl;
return 0;
}