三级考纲

• 进制转换
• 数据编码
• 位运算
• 一维数组
• 字符串
• 模拟、枚举算法

知识点解析

一.进制转换

数制概念

数制也称为计数制，是一种计数的方法，用一组固定的符号和统一的规则来表示数值的方法。在计数过程中采用进位的方法称为进位计数制(进制)，包括数位、基数和位权三个要素。

• 数位:指数字符号在一个数中所处的位置。
• 基数:指在某种进位计数制中数位上所能使用的数字符号的个数。(例如十进制的基数为10)
• 位权:数制中某一位上的1所表示数值的大小(所处位置的价值)。(例如十进制的567，5的位权是100，6的位权是10，7的位权是1)

进制概念 进制就是进位计数制，是人为定义的带进位的计数方法。对于任何一种进制一X进制，每一位上的数做运算时都是逢X进一(借位时借一当X)，各数位上的数字可以使用0,1.X-1共X个数字来表示

为什么计算机选择二进制

1、很难在一种物质上体现10种不同的状态，即使表示出来也很容易出错

2、电线的高、低电平（电压）表示两种状态非常方便，并且不容易出错。

八进制

在计算机科学中，由于二进制数据的基数较小，所以二进制数据的书写和阅读不方便，为此在小型机中引入八进制。八进制的基数为8，数位上的数字由0~7组成，一位八进制数字刚好对应三位二进制数，可以很好地反映二进制。

十六进制

计算机中采用十六进制，一方面是因为每四位二进制数字可以直接映射到一个十六进制数字，可以实现数据的压缩和简化，同时减少所需的空间和带宽，易于人机交互和阅读;其次是在底层编程中，十六进制允许开发者更直接地访问和操作内存和寄存器，使用十六进制可以更容易地调试和识别数据模式。

二进制、八进制、十进制、十六进制及其相互转换

进制转换	方法	举例
X进制数转成十进制数	按权展开求和： 【1】对于整数部分，从右往左看，第i位的位权等于$X^i-1$; 【2】对于小数部分，从左往右看，第j位的位权为$X^{-j}$。 【3】把每个数位上数值与对应的位权相乘后，将乘积相加求和。 把每一个数位数字乘以对应权值相加
十进制整数转换成X进制数	除X取余，逆序排列： 【1】将X作为除数，用十进制整数除以X，可以得到一个商和余数; 【2】保留余数，用商继续除以X，又得到一个新的商和余数; 【3】如此反复进行，每次都保留余数，用商接着除以N，直到商为0时为止。 【4】先得到的余数作为X进制数的低位数字，后得到的余数作为X进制数的高位数字，依次排列起来.
十进制小数转换成X进制数	乘X取整，顺序排列： 【1】将十进制小数部分乘以X，乘完后将乘积的整数部分取出; 【2】余下的小数部分继续乘以X，再将新乘积的整数部分取出 【3】如此反复进行，每次都取出整数部分，用剩下的小数部分接着乘以X，直到乘积中的小数部分为0，或者达到所要求的精度为止。 【4】把取出的整数部分按顺序排列起来，先取出的整数作为X进制小数的高位数字，后取出的整数作为低位数字。
二进制与八进制互相转换	二转八:“三合一” 【整数部分】从低位向高位每三个二进制数分为一组，转换成一位八进制数字。高位不足三位前补零。 【小数部分】从高位向低位每三个二进制数分为一组，转换成一位八进制数字。低位不足三位后补零。 八转二：“一分三" 将每一位八进制数字转换为三位二进制数字，把转换后的二进制数字拼在一起后，分别抹掉整数部分的高位零和小数部分的末尾零。	$(315.2)_8=(11001101.01)_2$ $(11010.01)_2=(32.2)_2$
二进制与十六进制互相转换	二转十六:“四合一"【整数部分】从低位向高位每四个二进制数分为一组，转换成一位十六进制数字。高位不足四位前补零。 【小数部分】从高位向低位每四个二进制数分为一组，转换成一位十六进制数字。低位不足四位后补零。 十六转二：“一分四" 将每一位十六进制数字转换为四位二进制数字，把转换后的二进制数字拼在一起后，分别抹掉整数部分的高位零和小数部分的末尾零。	$(2C.F)_{16}=(101100.111)_2$ $(11010.01)_2=(1A.4)_{16}$

注:八进制与十六进制间无法直接转换，需要借助二或十进制作为桥梁。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout << "35的8进制:" <<oct << 35<< endl;
    cout << "35的10进制" <<dec << 35 << endl;
    cout << "35的16进制:" <<hex << 35 << endl;
    cout << "35的2进制: " <<bitset<8>(35)<< endl;//<8>：表示保留8位输出
    return 0;
}

真题举例

1.下列关于进制的叙述，不正确的是（ ）。
A. 正整数的二进制表示中只会出现 0 和 1。
B. 10 不是 2 的整数次幂，所以十进制数无法转换为二进制数。
C. 从二进制转换为 8 进制时，可以很方便地由低到高将每3 位二进制位转换为对应的一位 8 进制位。
D. 从二进制转换为 16 进制时，可以很方便地由低到高将每4 位二进制位转换为对应的一位 16 进制位。

2.下列关于进制的叙述，正确的是( )。
A.只有十进制和二进制能够用来表示小数，八进制和十六进制不可以。
B.常用的进制包括二进制、八进制、十进制、十六进制，其他进制在日常生活中很少使用。
C.对任意正整数，其二进制表示不会比它的十进制表示更短，
D.正整数的八进制表示中，每一位可能出现的最大数字是8.

3.二进制数11.01在十进制下是( )。
A.3.01 B.3.05 .3.125 D.3.25

4.十进制数 111.111 的二进制表示可以是下面的（ ）。
A. 1101111.0001110001  B. 1101110.1001110001  
C. 1101111.1001110001  D. 1101111.0011110001

5.8进制数3703转换成16进制数是（）。
A. 7C3    B. 7A3    C. 7B3    D. 7D3

6.CCF(十九进制) = 21AC(十三进制)
  正确  错误

7.C++的字符变量的码值是整数，下面字面量形式的字符码值最大的是（ ）。
A. 100   B. 075   C. 0x70   D. 0x60

8.在C++语言中，表达式 (0xff == 255) 的值为 true 。
正确   错误

二.数据编码

1.计算机编码

​ 计算机只能识别两个数字：0和1。因此计算机中的所有的信息：数值、字符、图形、视频、声音等需要转换为0和1表示的代码，这个过程就是编码。

2.ASCII码

美国标准信息交换代码(American Standard Code For Information Interchange),简称ASCII码。

ASCII码是7位的二进制编码，能表示$2^7=128$种常见的英文字符

常见的ASII码对应的值：字符'0'的编码是48，'A'的编码是65，'a'的编码是97

3.汉字编码

计算机内部处理的信息，都是用二进制代码表示的，汉字也补例外。而二进制代码使用起来是不方便的，于是需要采用信息交换码。中国标准总局制定了GB2312-80标准，包括6763个汉字，采用两个字节存储。

4.Unicode编码

​ Unicode：Unicode 是国际标准字符集，它将世界各种语言的每个字符定义一个唯一的编码，以满足跨语言、跨平台的文本信息转换

​ UTF-8:Unicode的一种实现方法，它使用1-4个字节来编码字符。

​ UTF-16：它将字符编码成 2 字节 或者 4 字节

5.Base64编码

Base64是一种基于64个可打印字符来表示二进制数据的表示方法，常用于电子邮件和HTML中的数据传输。它将3个字节的数据转换为4个ASCII字符，减少了数据长度，但确保了数据的安全传输。

6.数的编码

​ 机器数

一个数在计算机中的二进制表示形式, 叫做这个数的机器数。

有符号机器数的最高位为符号位，0 表示正数，1 表示负数。

将带符号位的机器数对应的真正数值称为机器数的真值。

真值：3 机器数：0000 0011

真值：-3 机器数：1000 0011

在用二进制原码表示的数中，符号位为0表示正数，符号位为1表示负数，其余各位表示数值部分。

• 作用

  • 零只有一个
  • 取消减法，加减运算统一成加法

• 补码的减法

真题举例

1.（判断题）数据编码方式只有原码、反码、补码三种.
 正确  错误

2.(选择题)在C++中，一个8位有符号整数（使用补码表示）的范围是（）
A. -128 到 127  B. -127 到 128  C. -256 到 255   D. 0 到 255

3.(选择题)Base64 编码将每3字节的输入数据编码为 4 字节的输出数据。
如果输入数据长度不是 3 的倍数，会用 = 号填充。在Base64编码中，
如果输入字符串的长度为10字节，编码后的字符串长度是多少（ ）
A. 12 字节  B. 13 字节   C. 14 字节  D. 16 字节

4.下列二进制表示的十进制数值分别是（ ）
[10000011]原=（ ）
[10000011]补=（ ）
A. -125，-3   B. -3, -125   C. -3，-3   D. -125，-125

5.关于计算机中的编码，下列说法中错误的是（）
A. 对于无符号数，原码就是真值
B. 正数的反码是其本身
C. 负数的反码和补码是不一样的
D. 负数的反码，在其原码的基础上, 各个位取反

6.(判断题)整数-6的16位补码可用十六进制表示为FFFA。
  正确   错误

7.整数-5的16位补码表示是( )
A. 1005  B. 1006   C. FFFA   D. FFFB

8.已知字符 '0' 的ASCII编码的十进制表示为48，则执行下面C++代码后，输出是（ ）。
int main()
{
    string s="316";
    int n=s.length();
    int x=0;
    for(int i = 0; i < n; i++)
        x += s[i];
    cout << x << endl;
    cout << endl;
    return 0;
}
A. 10  B. 58  C. 154  D. 316

三.位运算

计算机中的数在内存中都是以二进制形式进行存储的，位运算是将每个二进制位作为 布尔值，分别对一个或两个二进制数中对应的二进制位做布尔运算。

注意:在手动进行 位运算计算 时，需要将数转换成二进制的表示形式，再进行计算。如3&5，先写成二进制形式的 0011和0101，右边最低位对齐后再分别对相应位进行位运算。

位运算规则

位运算常用性质

(1)a与自身之间的操作

a&a=a;
a|a=a;
a^a=0;

(2)判断奇偶

//通过&1取出最后一个二进制位以达到模2的效果，位运算效率更高
if(a & 1 == 1)//奇数
if(a & 1 == 0)//偶数
//同(a % 2)

(3)比较两个整数是否相等

a ^ b//如果结果为0则为相等，反之不等

(4)正整数乘或除以 $2^x$

a=a<<x;//乘以2^X
a=a>>x;//除以2^x;

(5)交换两个整数

a^=b;
b^=a;
a^=b;

真题举例

1.一个int类型的值乘以8，等价于以下哪个位运算( )。
A.左移3位 B.右移3位C.左移8位 D.右移8位

2.一个 int 类型的值，做以下哪个操作，一定会变回原来的值？（）
A. 左移 3 位，再右移 3 位。
B. 右移 3 位，再左移 3 位。
C. 按位或 7，再按位与-8。
D. 按位异或 7，再按位异或 7。

3.(判断题)这段程序进行的是判断一个从键盘输入的字符的ASCII 是否是奇数，若是，输出 YES，否则，输出 NO
int main() {
        char x;
        scanf("%c", &x);
        int ASCII = (int)x;
        cout << (x & 1 ? "YES" : "NO") << '\n';
        return 0;
}
正确  错误

4.补码1111 1101进行运算1111 1101>>1以后得到的结果是（）
A. 1111 1100   B. -2   C. 1111 1101   D. 1111 1010

5.a|10（a与10都是10进制，且二进制表示最高位为1）运算的结果是（ ）。
A. 使a的二进制表示从右往左的第二位为1
B. 使a的二进制表示从右往左的第一位为0
C. 使a的二进制表示从右往左第二位为0
D. 使a的二进制表示最高位为0

6.(判断题)下列程序输出的是 A
char x=65;
x=x&00001111;
cout<<x<<endl;
正确   错误

7.一个 int 类型变量 a ，执行操作 (a<<2>>2) 后的值一定是 a 。（ ）
正确  错误

8.如果 a 和 b 均为 int 类型的变量，下列表达式能正确判断“a 等于b”的是（ ）
A. ((a / b) == 1)    B. ((a & b) == a)    C. ((a ^ b) == 0)    D. ((a | b) == b)

9.如果 a 为 int 类型的变量，下列哪个表达式可以正确求出满足“小于等于a且是 4 的倍数”的整数中最大的？（ ）
A. (a & (~3))  B. ((a << 2) >> 2)  C. (a ^ 3)  D. ((a - 1) | 3) + 1

四.一维数组

数组是存储固定大小相同数据类型的集合，并且这些数据在内存中是连续存储的。(线性结构、顺序结构)

定义

1.数据类型 数组名[数组长度];

2.数据类型 数组名[数组长度]={值1，值2...);

3.数据类型 数组名[]={值1，值2..);

声明及初始化

int a[5];//如果定义在主函数之上，数组a所有元素的值赋为0
int b[5]={1,2,3,4.5};//b[0]、b[1],b[2]、b[3]、b[4]的值分别赋为1,2,3,4,5
int c[5]={1,2,3};//c[0]、c[1]、c[2]、c[3]、c[4]的值分别赋为1,2,3,0,0
int d[5]={0};
int e[]={1,2,3};//e[0]、e[1]、e[2]的值分别赋为1,2,3，且将数组的长度定义为3

【注意事项】

1.局部数组默认值为随机值，全局数组默认值为0;

2.数组长度可以使是一个常量或包含运算符的表达式;

3.大数组须定义为全局数组，在局部定义大数组会爆栈;

使用 数组名[下标]

数组下标从0的位置开始，下标最大值为数组长度减1。

例如 a[0]、b[1]、c[b[i]]、d['L']

只能逐个引用数组元素的值，而不能一次引用整个数组中全部元素的值。

【注意事项】

1.数组名是常量，不可以进行赋值操作;整型数组输出数组元素时，输出数组名得到的是首元素地址而不是批量元素。

2.使用数组时下标不能越界(上界和下界)，否则会造成内存的混乱，但不会导致编译错误;

计算占用空间

计算数组占用内存总空间的大小，主要有两种方式

①数组相当于有多个变量组成，可以通过单个数组元素所占用的空间乘以数组长度

②也可以使用sizeof(数组名)得到整个数组占用的内存大小

int array[10];
printf("array占用的内存大小为=%d\n",sizeof(array));//i古用的内存大小为=40
printf("int古用的内存大小为=%d\n",sizeof(int)*10);//int占用的内存大小为=4

函数（了解）

排序:sort(起始地址，结束地址，排序规则);(地址遵循“左闭右开“的原则)

int arr[4]={1,3,2,4};
sort(arr,arr+4);//对a[0~a[3]四个元素按升序排序

初始化:memset(数组,值,空间代销);

memset(a，0，sizeof(a));//将数组a元素全部初始化为0
注意:memset函数是按照字节来赋值的!

数组应用

(1)求和、平均、极差

【例】输出一个整数序列中最大的数和最小的数的差。

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],maxn=INT_MIN,minn=INT_MAX,sum=0; 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        if(maxn<a[i]){
            maxn=a[i];
        }
        if(minn>a[i]){
            minn=a[i];
        }
    }
    sum=maxn-minn;
    cout<<sum;
    return 0;
}

(2)查找或统计

【例】找重复数

在一次数学考试结束后，班级n位(2<=n<=100)同学中有两位同学考了了相同的分数(百分制)请你找到此分数并输出。

#include<bits/stdc++.h>
using namespace std;
int n,a[105],cnt[100];
int main(){
    cin>>n;
    for (int i=1;i <= n; i++){
        cin >> a[i];
        cnt[a[i]]++;
    }
    //方法1:枚举查找
    for (int i=1; i<=n;i++){
        for(int j=i+1;j<=n; j++){
            if(a[i]==a[j]){
                cout << a[i];
                break;
            }
        }
    }
    //方法2:计数原理
    for (int i=0;i<=100; i++){
        if(cnt[i]>1){
            cout<<i;
            break;
        }
    }
    return 0;
}

(3)计数或标记

【例】整数去重

给定含有$n$个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该数第一次出现的位置，删除其余位置。

#include<bits/stdc++.h>
using namespace std;
int a[100001],n,num;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num;
        if(a[num]==0){
            cout<<num<<" ";
            a[num]++;
        }
    }
    return 0;
}

真题举例

1.下列关于C++语言中数组的叙述，不正确的是( ).
A.数组必须先定义后使用。
B.数组的所有元素在内存中是连续存放的。
C.除了字符数组，在定义数组时“”内必须有常数。
D.不能对数组赋值，但可以对数组的每个基础类型的元素赋值。

2.以下数组定义，符合C++语言语法的是( )。
A.int a[]; B.int b['3’]; c.int c[3.0]; D.int [3] d;

3.一个数组定义为double array[3];则这个数组占用内存的大小为( )。
A.24  B.12  C.6  D.3

4.执行下面C++代码后输出的第一个数是（ ）。
int main()
{
    int a[20],i;
    for(i = 0; i < 20; i++)
    a[i] = i+1;
    for( ; i > 0; i--)
    cout << a[i-1] << " ";
    cout << endl;
    return 0;
}
A. 20  B. 19  C. 1  D. 不确定

5.(判断题)在C++语言中，数组下标的大小决定元素在逻辑上的先后顺序，与元素在内存中位置的先后顺序无关。
 正确  错误

6.(判断题)在C++语言中，定义数组时， [] 中必须指定元素个数。
 正确  错误

7.在下列代码的横线处填写（ ），可以使得输出是“120”。
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[5]={1,2,3,4,5};
    int res=0;
    for(int i=0;i<5;i++)
        ________;//在此处填入代码
    cout<<res<<endl; 
    return 0;
}
A. res += array[i];  B. res *= array[i]  C. res = array[i]   D. 以上均不对。

8.在下列代码的横线处填写（ ），可以使得输出是“2”
#include <bits/stdc++.h>
using namespace std;
int main() {
    int array[5]={3,7,5,2,4};
    int min=0;
    for(int i=0;i<5;i++)
        if(______) //在此处填写代码
           min=array[i];
    cout<<min<<endl;
    return 0;
}

五.字符串

字符串是一个接一个字符的连在一起（类似于烤肉串由一根竹签串起很多烤肉），所以字符串的基本组成元素是字符。

存储

存储字符串比如"tuling"时，有两种不同的方式，一种是字符型数组，另一种是string类.

在字符串中使用标识符'\0'作为结束标志，结束符0'也需要占用一个存储位，所以声明数组时长度至少为7。

char a[7]= "tuling"; //C++编译器会自动在字符串末尾添加空字符 '\0'。
string s="tuling";// string s("tuling") 或 string=("tuling")

【注意事项】

1.由n个字符个数组成的字符串在内存中应占(n+1)个字节。 2.'0'代表字符0，对应ASCI码值为48，'\0'代表空字符NULL(转义字符)，对应ASCI码值为0。

输入与输出

方法1:可以使用 cin、cout 整体输入输出(不保存空白符，如空格、回车、换行符等)

方法2:利用循环结合下标逐次操作

string s;
getline(cin,s);//带空格的输入
//cin>>s;不带空格的输入
for(int i=0;i<s.size();i++){
          cout<<s[i];//单个字符输出
}

注意点：cin>>n;getline(cin,s);组合使用时，一定要在cin>>n;后面加一行cin.get(); 否则会少接收一行数据，原因是cin换行符还在缓存区，会被getline()接收

函数

(1)字符转换 判断字符ch是否为小写字符，如果是转为大写字符

//方法1
if(ch >= 'a'&& ch <= 'z')或 if(ch >= 97 && ch <= 122)
    ch=ch-'a'+'A';//或ch -= 32;
//方法2:
if (islower(ch)){
    toupper(ch);
}

判断一个字符 ch 是否为大写字符，如果是转为小写字符

//方法1:
if(ch >='A'&& ch<='z')或 if(ch >= 65 && ch <= 90)
    ch = ch - 'A'+ 'a';//或ch += 32;
//方法2:
if (isupper(ch)){
    to1ower(ch);
}

判断一个是否为数字字符

//方法1
if (ch >= '0’& ch <= '9')或 if (ch >= 48 && ch <= 57)
//方法2
if(isdigit(a[i])){
}

(2)获取长度

使用 size()可以计算字符串中有效字符个数(不包括'\0')

string s="tuling";
cout<<s.size();//6

char a[5]= "tuling";
cout << strlen(a);//6

常用函数

string str="hello";
string s="c++";
str.insert(1,s);//在原串下标为1的字符e前插入字符串s
cout<<str<<endl;//hc++ello

// void replace(size_t pos, size_t len, const string& str);
std::string s = "Hello, world!";
s.replace(7, 5, "C++"); // 从位置7开始，替换长度为5的子字符串为"C++"
// 结果为 "Hello, C++!"

真题举例

1.如果a为 char 类型的变量，下列哪个表达式可以正确判断“a是大写字母”?( )
A. a-'A' <= 26 
B.'A' <= a <= 'Z’ 
C.'A' <= 'a' <= 'Z'’ 
D.('A' <= a) && (a <= 'Z’)

2. 在下列代码的横线处填写（ ），可以使得输出是 GESP IS INTERESTING 。
int main()
{
    string str="gEsP is Interesting";
    int x = str.length();
    for(int i = 0; i < x; i++)
    if ((str[i]>='a') && (str[i]<='z'))
        ________________________;
    cout << str << endl;
    cout << endl;
    return 0;
}
A. str[i]+='a'-'A'  B. str[i]+=20  C. str[i]+='A'-'a'  D. 无法实现

3.下列代码输出的是( )
string s="1234@@chenadai";
string str="12345";
s.replace(1,5,str);
cout<<s<<endl;
A. 12345  B. 2345@   C. 112345chenadai  D. 12345chenadai

4.下列程序输出的是（ ）
string ch="hello";
if(ch[5]==NULL) {
    cout<<"right"<<endl;
} else if (ch[5]=='\0') {
    cout<<"wrong"<<endl;
} else {
    cout<<"hello"<<endl;
}
A. right  B. wrong  C. hello   D. 不能正确执行

六.模拟及枚举算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列。

模拟法 现实生活中有些问题难以找到公式或规律来求解，只能 按照一定的步骤不停的模拟 下去，最后才能得到答案。 这样的问题用计算机求解十分合适，只要能让计算机模拟人在解决此问题时的行为即可。这种求解问题的思想，称为模拟。

枚举法

基本思想

逐一列举问题所涉及的所有可能情形，并根据问题提出的条件检验排查出是问题的解。(也称为列举法、穷举法，是暴力策略的具体体现)

特点

(1)枚举算法的思路简单，正确性容易证明，方便程序编写和调试

(2)当问题的规模变大的时候，运算量过大，执行速度越慢，解题效率不高

解题步骤

(1)确定枚举对象;

(2)确定枚举范围和判断条件;

(4)逐一筛选出问题的解

常用语法:循环+判断语句。

for(所有可能的答案){
    if(答案是否正确){
        得出答案 
    } 
}

优化

由于枚举法对要所有可能的情况进行筛选，不重复不遗漏地进行检验，通过牺牲时间来换取答案的全面性。为此优化的主要方向是: 减少状态总数，从而减少计算量;

【经典例题】求水仙花数、百元买百鸡

真题举例

枚举算法的主要特点是()。
A.以空间换时间 B.逐个尝试所有可能的解  C.动态规划 D.贪心策略

编程题单