当前位置: 首页 > news >正文

实用指南:GESP三级考纲+三级考试知识点详解

实用指南:GESP三级考纲+三级考试知识点详解

GESP三级考试知识点详解

一、GESP编程能力等级认证三级知识内容和目标

级别

知识内容(C++)

知识目标

三级

数据编码(原码、反码、补码)
进制转换(二进制、八进制、十进制、十六进制)
位运算(与(&)、或(|)、非(、异或(^)、左移(<<)、右移(>>))
算法的概念与描述(自然语言描述、流程图描述、伪代码描述)
C++一维数组基本应用
字符串及其函数
算法:枚举法
算法:模拟法

掌握数据编码、进制转换、位运算等知识,掌握一维数组、字符串及函数的使用,能够独立使用模拟法、枚举法解决对应的算法问题。

二、GESP三级知识点详述

  1. 了解二进制数据编码:原码、反码、补码。

  2. 掌握数据的进制转换:二进制、八进制、十进制、十六进制。

  3. 掌握位运算:与(&)、或(|)、非(、异或(^)、左移(<<)、右移(>>)的基本使用方法及原理。

  4. 了解算法的概念,熟练运用自然语言、流程图、伪代码方式来描述算法。

  5. 掌握字符串及其函数的使用包括但不限于大小写转换、字符串搜索、分割、替换。

  6. 理解枚举算法、模拟算法的原理及特点,可以解决实际问题。

  7. 掌握C/C++中数组的概念,了解数组的存储原理及特性,掌握一维数组的定义、初始化、引用等方法。

三、GESP三级部分知识点详解

1. 原码、补码和反码

(1)机器数和真值

在学习原码、反码和补码之前,需要先了解机器数和真值的概念。

① 机器数

一个数在计算机中的二进制表示形式,叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位存放符号,正数为0,负数为1。

例如,十进制中的数+3,计算机字长为8位,转换成二进制就是00000011。如果是-3,就是10000011。这里的00000011和10000011就是机器数。

② 真值

机器数的第一位是符号位,后边才是真正的数值,所以机器数的形式值就不等于真正的数值。例如上面的有符号数10000011,其最高位1代表负,其真正数值是-3而不是形式值131(10000011转换成十进制等于131)。所以,为区别起见,将带符号位的机器数对应的真正数值称为机器数的真值。

例:

00000001的真值 = +0000001 = +1

10000001的真值 = -0000001 = -1

(2)数的原码、补码和反码表示

原码、反码、补码是计算机存储一个具体数字的编码方式。数值在计算机中是以补码的方式存储的。

① 原码

原码就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值。比如如果是8位二进制:

[+1]原​=00000001
[−1]原​=10000001

第一位是符号位。因为第一位是符号位,所以8位二进制数的取值范围就是:

[11111111,01111111]⇒[−127,127]
② 反码

反码的表示方法是:正数的反码是其本身。负数的反码是在其原码的基础上,符号位不变,其余各个位取反。

[+1]=[00000001]原​=[00000001]反​
[−1]=[10000001]原​=[11111110]反​
③ 补码

补码的表示方法是:正数的补码就是其本身。负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1(即在反码的基础上+1)。

[+1]=[00000001]原​=[00000001]反​=[00000001]补​
[−1]=[10000001]原​=[11111110]反​=[11111111]补​
(3)数的定点表示和浮点表示

在计算机中小数点一般有两种表示法:一种是小数点固定在某一位置的定点表示法;另一种是小数点的位置可任意移动的浮点表示法。相应于这两种表示的计算机分别称为定点计算机和浮点计算机。

① 定点表示法

机器中所有数的小数点位置是固定不变的,因而小数点就不必使用记号表示出来。实际上,小数点可固定在任意一个位置上。

② 浮点表示法

在数的定点表示法中,由于数的表示范围较窄常常不能满足各种数值问题的需要。为了扩大数的表示范围,方便用户使用,有些计算机常采用浮点表示法。表示一个浮点数,要用两部分:尾数和阶码。尾数用以表示数的有效数值;阶码用以表示小数点在该数中的位置。

计算机多数情况下采用浮点数表示数值,它与科学计数法相似,把一个二进制数通过移动小数点位置表示成阶码和尾数两部分:

N=2E×S

其中E是N的阶码(Exponent),是有符号的整数。S是N的尾数(Mantissa),是数值的有效数字部分,一般规定取二进制定点纯小数形式。

例:

1011101B​=2+7×0.1011101
101.1101B​=2+3×0.1011101
0.01011101B​=2−1×0.1011101

2. 数制转换

(1)进位计数制的基本概念

将数字符号按序排列成数位,并遵照某种由低位到高位的进位方式计数表示数值的方法,称作进位计数制。

① 十进制

十进制计数制由0、1、2、3、4、5、6、7、8、9共10个数字符号组成。相同数字符号在不同的数位上表示不同的数值,每个数位计满十就向高位进一,即“逢十进一”。

② 八进制

八进制计数制由0、1、2、3、4、5、6、7共8个数字符号组成。相同数字符号在不同的数位上表示不同的数值,每个数位计满八就向高位进一,即“逢八进一”。

③ 二进制

二进制计数制由0和1共两个数字符号组成。相同数字符号在不同的数位上表示不同的数值,每个数位计满二就向高位进一,即“逢二进一”。

④ 其他进制

在日常生活和工作中还会使用其他进制数。如:十二进制数、十六进制数、百进制数和千进制数等。无论哪种进制数,表示的方法都是类似的。如:十六进制数由0、1、2、3、4、5、6、7、8、9、A、B、C、D、E和F共16个符号组成,“逢十六进一”。不同的是,用A、B、C、D、E和F分别表示10、11、12、13、14和15六个数字符号。

⑤ 基数与权

某进制计数制允许选用的基本数字符号的个数称为基数。一般而言,J进制数的基数为J,可供选用的基本数字符号有J个,分别为0到J-1,每个数位计满J就向高位进一,即“逢J进一”。

某进制计数制中各位数字符号所表示的数值表示该数字符号值乘以一个与数字符号所处位置有关的常数,该常数称为“位权”(简称“权”)。位权的大小是以基数为底、数字符号所处的位置的序号为指数的整数次幂。

十进制数允许使用十个基本数字符号,所以基数为10,每位数字符号代表的位数的大小是以10为底,数字符号所处位置的序号为指数的整数次幂。

十进制数的百位、十位、个位和十分位的权分别为102、101、100、10−1。故(555.5)10​可表示成(555.5)10​=5×102+5×101+5×100+5×10−1。J进制数相邻两位数相差了J倍,若小数点向左移n位,则整个数值就缩小Jn。反之,小数点向右移n位,数值就放大了Jn。

如下给出了任意进制数(K2,K1,K0,K−1,K−2),当J分别为2、8、10和16时各位权值对照。

数位 权 进位制J

K2

K1

K0

小数点位置

K−1

K−2

J=2

22=4

21=2

20=1

2−1=0.5

2−2=0.25

J=8

82=64

81=8

80=1

8−1=0.125

8−2=0.015625

J=10

102=100

101=10

100=1

10−1=0.1

10−2=0.01

J=16

162=256

161=16

160=1

16−1=0.0625

16−2=0.00390625

(2)数制之间的转换

计算机内部使用的数字符号只有“0”和“1”两个。也就是说,计算机内部使用的是二进制数,所有的数值数据和非数值数据,都是由“0”和“1”这两个数字符号加以组合而成的,我们称之为“二进制代码”。

计算机只用二进制的两个数码“0”和“1”来实现算术和逻辑运算,而人们仍然用十进制的形式向计算机中输入原始数据,并让计算机也用十进制形式显示和打印运算结果。所以,必须有一种自动转换方法,即让数据输入计算机后,将十进制转换成对应的二进制数,并在处理完毕后,再自动将二进制结果转换为十进制数。

为了表达方便起见,常在数字后加一个缩写字母后缀作为不同进制数的标识。各种进制数的后缀字母分别为:

  • B:二进制数。

  • O:八进制数。

  • D:十进制数。

  • H:十六进制数。

对于十进制数,通常不加后缀,也即十进制数后的字母D可省略。

① 二进制与十进制的转换

二进制转十进制

方法:“按权展开求和”

例:

(1011.01)2​=(1×23+0×22+1×21+1×20+0×2−1+1×2−2)10​=(8+0+2+1+0+0.25)10​=(11.25)10​

十进制转二进制

十进制整数转二进制数:“除以2取余,逆序输出”。

例:(89)10​=(1011001)2​

2∣892∣44⋯12∣22⋯02∣11⋯02∣5⋯12∣2⋯12∣1⋯00⋯1​

十进制小数转二进制数:“乘以2取整,顺序输出”。

例:(0.625)10​=(0.101)2​

0.625×2=1.25取整10.25×2=0.5取整00.5×2=1.0取整1​
② 八进制与二进制的转换

例:将八进制的37.416转换成二进制数。

3011​7111​..​4100​1001​6110​

即:(37.416)8​=(11111.10000111)2​

例:将二进制的10110.0011转换成八进制。

0102​1106​..​0011​1004​

即:(10110.0011)2​=(26.14)8​

③ 十六进制与二进制的转换

例:将十六进制数5DF.9转换成二进制。

50101​D1101​F1111​..​91001​

即:(5DF.9)16​=(10111011111.1001)2​

例:将二进制的1100001.111转换成十六进制。

01106​00011​..​1110E​

即:(1100001.111)2​=(61.E)16​

④ 八进制转换成十进制

把一个八进制的最后一位乘上80,倒数第二位乘上81,……,一直到最高位乘上8n,然后将各项乘积相加,结果即为它的十进制表达式。

例:把八进制数36转换为十进制。

(36)8​=3×81+6×80=24+6=(30)10​
⑤ 十六进制转换成十进制

把一个十六进制的最后一位乘上160,倒数第二位乘上161,……,一直到最高位乘上16n,然后将各项乘积相加,结果即为它的十进制表达式。

例:把十六进制数1E转换为十进制。

(1E)16​=1×161+14×160=16+14=(30)10​

3. 位运算:与(&)、或(|)、非(~)、异或(^)、左移(<<)、右移(>>)

位运算直接对整数在内存中的二进制位进行运算。常用位运算包括与、或、非、异或、左移、右移。

(1)与(&)

将参与运算的两个操作数各自对应的二进制位进行“逻辑与”操作。只有对应的两个二进制位均为1时,对应二进制位的运算结果才为1,否则为0。

(2)或(|)

将参与运算的两个操作数各自对应的二进制位进行“逻辑或”操作。只有对应的两个二进制位均为0时,对应二进制位的运算结果才为0,否则为1。

(3)非(~)

单目运算符,它将操作数中的二进制位0变成1,把1变成0。

(4)异或(^)

将参与运算的两个操作数各自对应的二进制位进行“异或”操作。只有对应的两个二进制位不相同时,对应二进制位的运算结果为1,当对应的两个二进制位相同时,对应二进制位的运算结果为0。

(5)左移(<<)

左移运算是将左操作数的二进制形式全部向左移动若干位(右操作数的值)后得到的值。左移时,高位丢弃,右边低位补0。左移n位,就是乘以2n。

(6)右移(>>)

右移运算的操作方式和左移运算类似,不同的是移动方向,移除最右边的位被丢弃。同样,右移n位相当于左操作数除以2n,并且将结果向下取整。对于无符号数,右移时高位总是补0。对于有符号数,在右移时,符号位(即最高位)一起移动。如果原符号位为1(代表负数),则右移时右边高位都补1;如果原符号位为0(代表正数),则右移时右边高位都补0,即保持原有的正负。

4. 算法概念与描述

(1)算法概念

在数学和计算机科学之中,算法(algorithm)是指一个被定义好的、计算机可实施的有限步骤或次序,常用于计算、数据处理和自动推理。算法是有效方法,包含一系列定义清晰的指令,并可于有限的时间及空间内清楚地表述出来。

通常用空间复杂度和时间复杂度来衡量一个算法的优劣,而同一个问题可以用具有不同时间复杂度和空间复杂度的算法来求解。

算法具有以下五个重要的特征:

  1. 输入项​:一个算法有0个或多个输入。

  2. 输出项​:一个算法有1个或多个输出。

  3. 确定性​:算法的每一个步骤必须有确定的定义,即语句的描述不能存在二义性,对于每一种情况,需要执行的动作都应该是严格的、清晰的。

  4. 有穷性​:算法必须能在执行有限步之后终止,即在执行完有限步之后自动结束,而不会出现无限循环,并且每一步都在规定的时间内完成。

  5. 可行性​:算法中执行的任何计算步骤都是可以被分解为基本的、可执行的操作步骤,即算法的每一条运算原则上都能精确地执行。

算法可采用多种描述语言来描述,各种描述语言在对问题的描述能力方面存在一定的差异。常用的方式有自然语言、流程图、伪代码等。不管用哪种描述方式表达算法,其描述的结果必须满足算法的五个特征。

(2)算法描述:自然语言描述、流程图描述、伪代码描述

算法有很多种方式,其中最常用的描述方式包括自然语言描述、流程图描述和伪代码描述。这些描述方式各有其优缺点,需要根据具体场景选择最合适的描述方式。

① 自然语言描述

算法的自然语言描述,指的是用日常使用的语言来描述解决问题的具体步骤。

用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时,比较直观,容易理解。缺点是如果算法中包含了判断结构和循环结构,并且操作步骤较多时,容易引起歧义,且描述得不够清晰。

② 流程图描述

流程图是以特定的图形符号加上说明来表示算法的图。流程图用一些图框来表示各种类型的操作,在框内写出各个步骤,然后用带箭头的线将它们连接起来,以表示算法执行的先后顺序。

使用流程图来描述算法,其优点是可以使读者更加清楚地了解整个算法的完整操作过程,有助于在工作过程中及时对算法进行修改。但流程图有其约定的符号,绘制时需要根据其符号进行搭建,绘制过程比较繁琐。

③ 伪代码描述

伪代码是一种非正式的用于描述模块结构图的语言。使用伪代码的目的是使被描述的算法可以容易地以任何一种编程语言实现。因此,伪代码必须结构清晰、代码简单、可读性好。伪代码介于自然语言与编程语言之间,以编程语言的书写形式说明算法功能。使用伪代码,不用拘泥于具体实现,相比程序语言它更类似自然语言,可以将整个算法运行过程的结构用接近自然语言的形式描述出来。

使用伪代码描述算法没有严格的语法限制,书写格式比较自由。只要把意思表达清楚就可以了,它更侧重于对算法本身的描述。在伪代码描述中,表述关键词的语句一般用英文单词,其他语句可以用英文语句,也可以用中文语句。

5. 字符串的处理

(1)字符数组与相关函数

字符数组是一种C语言风格的字符串,在C++中依然被保留下来。如下定义一个字符数组:

char a[10];

如果在定义的时候进行初始化,可以用:

char a[10] = "Hello";

等价于

char a[] = {'H', 'e', 'l', 'l', 'o'};

其中,a[5] = '\0'。'\0'是字符数组的终止符,它的ASCII码是0,有关字符数组的函数都需要利用终止符工作。对字符数组进行初始化或者读入等操作时,都会自动在字符数组末尾补上一个'\0',它也会占据字符数组的一个位置,如果没有预留这个位置就会造成数组越界。

除了数组本身的应用方式,字符数组还有其独有的函数。在cstring或string.h头文件中有许多对字符数组进行操作的函数,如下表所示。注意,使用这些函数前必须确保字符数组末尾有终止符'\0'。

函数

语法

功能

strcpy

strcpy(a, b);

将字符数组b复制到a中,并覆盖a中原有字符

strcat

strcat(a, b);

将字符数组b拼接到a的后面

strlen

strlen(a);

返回a的终止符'\0'前的字符个数

strcmp

strcmp(a, b);

如果a和b完全相同,则返回0;否则设第一对不相同的字符为a[i]和b[i],返回a[i]-b[i]的值(对应ASCII码相减)

strchr

strchr(a, x);

如果x在a中出现,则返回第一次出现的指针;否则返回空指针null

strstr

strstr(a, b);

如果b是a的子串,则返回第一次出现的位置的左端点指针;否则返回空指针null

(2)string类与相关函数

string是C++的字符串类型,需引用string头文件。如下定义一个字符串:

string a;
a = "Hello";

字符串的下标从0开始。它仅支持用a[i]的形式访问下标为i的位置的字符,但如果长度超出当前长度就会造成越界。

字符串常用方法如下表所示。

方法

语法

功能

+

c = a + b;

字符串a的末尾添加字符串b并赋给字符串c

+=

a += b;

字符串a的末尾添加字符串b

push_back

a.push_back(x);

在字符串的末尾加入一个字符x

find

a.find(b, pos);

忽略字符串a中严格在pos之前的字符,如果字符串b是a的子串,则返回第一次出现的左端点的下标;否则返回string::npos

insert

a.insert(pos, b);

在字符串a的下标pos之前插入字符串b

size

a.size();

返回字符串a中的字符个数

substr

a.substr(pos, len);

返回字符串a中从pos开始的len个字符形成的字符串

6. 基础算法:枚举算法、模拟算法

① 枚举算法

所谓枚举算法,指的是从可能的解的集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的、哪些是有用的。能使命题成立,即为其解。

有些问题可以使用循环语句和条件语句直接求解,有些问题用循环求解时循环次数太多,无法编写程序,则需要用到回溯、递归、分治等方法。

常见问题有“百钱买百鸡”“素数判断”等。

② 模拟算法

按照题目的意思和步骤来编写代码。

7. 数组

① 数组与数组下标

数组是一种数据结构。它可以存储一个固定长度的、由相同类型元素构成的序列。数组由连续的内存位置构成。数组中每个元素都有其对应的下标。

数组支持随机访问。随机访问指的是,对于任意一个下标,能在任意时刻访问数组中该下标对应的元素。

在C++中,数组的常用声明方法为:

T a[N];  // T代表数据类型,a代表数组名,N代表数组长度

数组长度即数组包含的元素个数,N必须是常数或常量表达式,并且其值必须是正整数。这条语句相当于声明了a[0], a[1], …, a[N-1]这N个元素,方括号内的数为该元素的下标,在程序中调用a[i]即可访问下标为i的元素。

对于下标i,如果它不在0到N-1的范围内,则访问a[i]会造成数组越界。这是一种未定义行为(undefined behavior),会导致不可预测的后果,例如经常会造成运行时错误(runtime error)。因此在程序设计中,应避免出现这种错误。

需要特别注意的是,在C++中数组的下标从0开始(即0-indexed),因此若声明大小为N的数组,访问a[N]就会造成数组越界。为了防止这类越界情况的发生,可以声明比所需稍大一点的数组。

如果直接声明,全局数组会被默认初始化(基础数据类型被赋值为0,结构体则调用默认构造函数),而局部数组不会。往往声明局部数组时要用大括号初始化。

int a[3] = {1, 2, 0};
// 声明长度为3的局部数组a,其初值为a[0]=1, a[1]=2, a[2]=0
// 等价写法1: int a[] = {1, 2, 0};(省略长度,按列表中元素数量设置长度)
// 等价写法2: int a[3] = {1, 2};(省略数组末尾的0)
int b[3] = {};

在C++中,用如下语句可以定义一个二维数组:

T a[N][M];

N代表数组的第一维长度,M代表数组的第二维长度,N和M必须是常数或常量表达式,其值必须是正整数。这条语句相当于声明了a[0][0], a[0][1], …, a[0][M-1], a[1][0], a[1][1], …, a[1][M-1], …, a[N-1][0], a[N-1][1], …, a[N-1][M-1]这N×M个元素,方括号内的数为元素下标,在程序中调用a[i][j]即可访问下标为i, j的元素。

② 数组的读入与输出

根据数组的定义,可使用循环结构来实现数组的读入与输出。

for (int i = 0; i > a[i];  // 输入a[i]
for (int i = 0; i < n; i++)
cout << a[i] << " ";  // 输出a[i]
③ 二维数组与多维数组

二维数组可看作一个N行M列的二维表格,也可以看作一个有N个元素的一维数组,而每个元素又都是一个长度为M的一维数组。在内存中存储时,二维数组按照先行后列的顺序连续存放数组元素,可以通过嵌套循环结构来访问其元素。超过三维的多维数组一般难以想象其对应的实际形态,但只需理解数组的每一个维度代表一类信息,常见于动态规划算法中记录多维状态信息

http://www.hskmm.com/?act=detail&tid=13801

相关文章:

  • github操作备忘录
  • 9.22每日总结
  • 算法人生
  • 动态规划专题
  • 【51单片机】【protues仿真】基于51单片机PM2.5温湿度测量蓝牙架构
  • 每日反思(2025.9.22)
  • 洛谷题单指南-进阶数论-P4942 小凯的数字
  • 【炼石计划NOIP】第八套 赛后总结
  • 下载了idea
  • vite7-webos网页版os管理|Vue3+Vite7+ArcoDesign搭建pc端os后台系统
  • 三门问题的多种解法,总有一个你看得懂
  • hbase学习——创建springboot+hbase项目
  • python_Day22笔记
  • .NET周刊【9月第1期 2025-09-07】
  • SUDO提权
  • 2025.9.19 总结
  • 2025.9.18 总结
  • 越南文识别技术:将纸质文档和信息快速、准确地转化为可编辑、可检索的数字数据
  • 23
  • 9.22日总结
  • 9.16 总结
  • Halcon抛出异常日志
  • [PaperReading] Mind Search: Mimicking Human Minds Elicits Deep AI Searcher
  • 穷举法(c语言版)
  • ZYNQ PS 端 UART 接收数据素材帧(初学者友好版)嵌入式编程 C语言 c++ 软件开发
  • 详细介绍:深入理解Kafka事务
  • 能碳园区 / 工厂系统 - 智慧园区
  • 代码随想录算法训练营第五天 |242.有效的字母异位词、349. 两个数组的交集、第202题. 快乐数、1. 两数之和
  • Photoshop 2025 v26.0(PS2025)下载安装教程(含一键安装包下载)
  • 网络加速原理