2023 年 9 月 CCF编程能力 C++四级试卷
一、单选题
（每题2分，共30分）
14) 执⾏以下C++语⾔程序后，输出结果是（ ）。
#include <iostream>
using namespace std;
int main() {
int fib[10];
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < 10; i++)
fib[i] = fib[i - 1] + fib[i - 2];
cout << fib[10] << endl;
}15) 在下列代码的横线处填写（ ），完成对有 n个int类型元素的数组 array 由⼩到⼤排序。
void BubbleSort(int array[], int n) {
for (int i = n; i >= 2; i--)
for (________________) // 此处填入代码
if (array[j] > array[j + 1]) {
int t = array[j];
array[j] = array[j + 1];
array[j + 1] = t;
}
}二、判断题
（每题2分，共20分）
三、编程题
（每题 25 分，共 50 分）
26) 进制转换
【问题描述】
N进制数指的是逢N进⼀的计数制。例如，⼈们日常⽣活中⼤多使用⼗进制计数，而计算机底层则⼀般使用二进制。除此之外，⼋进制和⼗六进制在⼀些场合也是常⽤的计数制（⼗六进制中，⼀般使用字母A 至F表⽰⼗⾄⼗五；本题中， ⼗⼀进制到⼗五进制也是类似的）。
在本题中，我们将给出 N个不同进制的数。你需要分别把它们转换成⼗进制数。
【提示】
对于任意⼀个L位K进制数，假设其最右边的数位为第0位，最左边的数位为第 L - 1 位，我们只需要将其第i位的数码乘以权值 K^i，再将每位的结果相加，即可得到原K进制数对应的⼗进制数。下⾯是两个例⼦：
1.⼋进制数 1362 对应的⼗进制数为1 × 8^3＋3 × 8^2＋6 × 8^1＋2 × 8^0 = 754；
2.⼗六进制数 3F0 对应的⼗进制数为3 × 16^2＋15 × 16^1+ 0 × 16^0 = 1008。
【输入描述】
输⼊的第⼀⾏为⼀个⼗进制表示的整数N。接下来N⾏，每⾏⼀个整数K，随后是⼀个空格，紧接着是⼀个K进制数，表示需要转换的数。保证所有K进制数均由数字和⼤写字母组成，且不以0开头。保证K进制数合法。
保证N ≤ 1000；
保证2 ≤ K ≤ 16。
保证所有K进制数的位数不超过9。
【输出描述】
输出N行，每⼀个十进制数，表⽰对应K进制数的十进制数值。
【样例输入1】
2
8 1362
16 3F0
【样例输出1】
754
1008
【样例输入2】
2
2 11011
10 123456789
【样例输出2】
27
123456789
【问题描述】
N进制数指的是逢N进⼀的计数制。例如，⼈们日常⽣活中⼤多使用⼗进制计数，而计算机底层则⼀般使用二进制。除此之外，⼋进制和⼗六进制在⼀些场合也是常⽤的计数制（⼗六进制中，⼀般使用字母A 至F表⽰⼗⾄⼗五；本题中， ⼗⼀进制到⼗五进制也是类似的）。
在本题中，我们将给出 N个不同进制的数。你需要分别把它们转换成⼗进制数。
【提示】
对于任意⼀个L位K进制数，假设其最右边的数位为第0位，最左边的数位为第 L - 1 位，我们只需要将其第i位的数码乘以权值 K^i，再将每位的结果相加，即可得到原K进制数对应的⼗进制数。下⾯是两个例⼦：
1.⼋进制数 1362 对应的⼗进制数为1 × 8^3＋3 × 8^2＋6 × 8^1＋2 × 8^0 = 754；
2.⼗六进制数 3F0 对应的⼗进制数为3 × 16^2＋15 × 16^1+ 0 × 16^0 = 1008。
【输入描述】
输⼊的第⼀⾏为⼀个⼗进制表示的整数N。接下来N⾏，每⾏⼀个整数K，随后是⼀个空格，紧接着是⼀个K进制数，表示需要转换的数。保证所有K进制数均由数字和⼤写字母组成，且不以0开头。保证K进制数合法。
保证N ≤ 1000；
保证2 ≤ K ≤ 16。
保证所有K进制数的位数不超过9。
【输出描述】
输出N行，每⼀个十进制数，表⽰对应K进制数的十进制数值。
【样例输入1】
2
8 1362
16 3F0
【样例输出1】
754
1008
【样例输入2】
2
2 11011
10 123456789
【样例输出2】
27
123456789
27) 变长编码
【问题描述】
小明刚刚学习了三种整数编码方式:原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得生活中很少用到2^31-1这么大的数，生活中常用的0 ~ 100这种数也同样需要用4个字节的补码表示，太浪费了些。热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下:
1.对于给定的正整数，首先将其表达为二进制形式。例如，(0){10} =(0){2}， (926){10}=(1110011110){2}。
2.将二进制数从低位到高位切分成每组7 bit，不足7bit的在高位用0填补。例如 ，(0){2}变为0000000的一组,(1110011110){2}变为0011110和0000111的两组。
3.由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上0，否则在最高位填上1。于是，0的变长编码为00000000一个字节，926的变长编码为10011110和00000111两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，987654321012345678的二讲制为(0001101 1011010 0110110 1001011 1110100 0100110 1001000 0010110 1001110){2}于是它的变长编码为(十六进制表示) CE 96 C8 A6 F4 CB B6 DA OD，共9个字节。 你能通过编写程序，找到一个正整数的变长编码吗?
【输入描述】
输⼊第⼀⾏，包含⼀个正整数N。约定0≤N≤10^18。
【输出描述】
输出⼀⾏，输出N对应的变长编码的每个字节，每个字节均以2位⼗六进制表示（其中，A-F使⽤⼤写字母表⽰），两个字节间以空格分隔。
【样例输入1】
0
【样例输出1】
00
【样例输入2】
926
【样例输出2】
9E 07
【样例输入3】
987654321012345678
【样例输出3】
CE 96 C8 A6 F4 CB B6 DA 0D
【问题描述】
小明刚刚学习了三种整数编码方式:原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得生活中很少用到2^31-1这么大的数，生活中常用的0 ~ 100这种数也同样需要用4个字节的补码表示，太浪费了些。热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下:
1.对于给定的正整数，首先将其表达为二进制形式。例如，(0){10} =(0){2}， (926){10}=(1110011110){2}。
2.将二进制数从低位到高位切分成每组7 bit，不足7bit的在高位用0填补。例如 ，(0){2}变为0000000的一组,(1110011110){2}变为0011110和0000111的两组。
3.由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上0，否则在最高位填上1。于是，0的变长编码为00000000一个字节，926的变长编码为10011110和00000111两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，987654321012345678的二讲制为(0001101 1011010 0110110 1001011 1110100 0100110 1001000 0010110 1001110){2}于是它的变长编码为(十六进制表示) CE 96 C8 A6 F4 CB B6 DA OD，共9个字节。 你能通过编写程序，找到一个正整数的变长编码吗?
【输入描述】
输⼊第⼀⾏，包含⼀个正整数N。约定0≤N≤10^18。
【输出描述】
输出⼀⾏，输出N对应的变长编码的每个字节，每个字节均以2位⼗六进制表示（其中，A-F使⽤⼤写字母表⽰），两个字节间以空格分隔。
【样例输入1】
0
【样例输出1】
00
【样例输入2】
926
【样例输出2】
9E 07
【样例输入3】
987654321012345678
【样例输出3】
CE 96 C8 A6 F4 CB B6 DA 0D