下载掌阅APP，畅读海量书库
立即打开
1．在C++中，下列关键字中用于声明一个变量，其值不能被修改的是（ ）。
A．unsigned
B．const
C．static
D．mutable
【考点识别】
2 C++程序设计|2.1程序基本概念|【1】标识符、关键字、常量、变量、表达式的概念、【2】常量与变量的命名、定义及作用
【分析讲解】
题目询问的是在C++中哪个关键字用于声明一个变量，并且该变量的值不能被修改。下面逐一分析选项：
A．Unsigned：unsigned是一个类型修饰符，表示变量是无符号类型，如unsigned int。它与变量是否可修改无关，因此不是答案。
B．const：const关键字用于声明常量。使用const声明的变量在初始化后不能再被修改。例如：
const int x = 10;
x = 20; // 错误，x 的值不可修改
所以，这是正确答案。
C．static：static是一个存储类别修饰符，用于改变变量的存储方式和生命周期。它与变量是否可修改无关。
D．mutable：mutable修饰符允许即使在const对象中，也可以修改被mutable修饰的成员变量。例如：
struct Test {
mutable int x;
};
const Test obj{10};
obj.x = 20; // 合法，mutable 允许修改
因此，这也不是答案。
【参考答案】
B．const
【编程魔法师讲解考点】
一、const是什么
在C++中，const是一个关键字，用于声明常量。声明为const的变量，其值在初始化后就不能被修改。它是一种保证变量不可变的机制，在程序中提供了一种保护手段，防止意外更改数据。
二、const基本语法
1．声明常量
const int a = 10;
a = 20; // 错误：const 修饰的变量不可被修改
2．指针与const
const int *p; // 指向常量的指针，不能通过指针修改值
int *const p; // 常量指针，指针本身不可变
const int *const p; // 指向常量的常量指针
三、const的应用场景
1．函数参数
在函数参数前加const，可以防止函数内部修改参数的值。例如：
void print(const int x) {
// x 不能被修改
}
2．常量成员函数
声明为const的类成员函数不能修改类中的任何成员变量（除非被mutable修饰）。例如：
class Test {
int x;
public:
void func() const {
// 不能修改 x
}
};
【题目总结】
本题通过考查C++中关键字的功能，重点引导对const的理解。这一关键字在程序的安全性和逻辑性方面起到了非常重要的作用。
2．八进制数(12345670) 8 和(07654321) 8 的和为（ ）。
A．(22222221) 8
B．(21111111) 8
C．(22111111) 8
D．(22222211) 8
【考点识别】
5 数学|5.1数及其运算|【2】数的进制：二进制、八进制、十六进制和十进制及其相互转换
【分析讲解】
本题要求计算两个八进制数的和。为此，需要将八进制数转换为十进制，进行加法运算后，再将结果转换回八进制。
解题步骤：
要计算八进制数(12345670) 8 和(07654321) 8 的和，我们可以按照以下步骤进行计算：
第一步：对齐两个八进制数
为了方便计算，我们将两个八进制数对齐，并在前面补零，使它们的位数相同：
第二步：逐位相加，并从右到左计算
我们从最右边的一位开始，逐位相加。如果相加的结果大于或等于8，则需要向高位进位。
逐位计算：
1．第1位（从右到左）：0+1=1
结果：1，不进位。
2．第2位：7+2=9
9≥8，所以写1，并向高位进1。
3．第3位：6+3=9，加上进位的1，总和为10
10≥8，所以写2，并向高位进1。
4．第4位：5+4=9，加上进位的1，总和为10
10≥8，所以写2，并向高位进1。
5．第5位：4+5=9，加上进位的1，总和为10
10≥8，所以写2，并向高位进1。
6．第6位：3+6=9，加上进位的1，总和为10
10≥8，所以写2，并向高位进1。
7．第7位：2+7=9，加上进位的1，总和为10
10≥8，所以写2，并向高位进1。
8．第8位：1+0=1，加上进位的1，总和为2
结果：2，不进位。
第三步：写出最终结果
将每一步的结果写出来：
因此，八进制数(12345670) 8 和(07654321) 8 的和是(22222211) 8 。
【参考答案】
D．(22222211) 8
【编程魔法师讲解考点】
一、什么是进制
进制是指采用不同的基数表示数值的方式。例如：
二进制（基数为2）：由数字0和1组成。
八进制（基数为8）：由数字0到7组成。
十进制（基数为10）：由数字0到9组成。
十六进制（基数为16）：由数字0到9和字母A到F组成。
二、进制相互转换的基本方法
1．其他进制转换为十进制
例如，将八进制123 8 转换为十进制：1×8 2 +2×8 1 +3×8 0 =64+16+3=83
2．十进制转换为其他进制
使用“除基取余法”：将十进制数不断除以目标进制的基数，记录每次的余数，直到商为0，然后逆序写出余数即可。
例如，将十进制83转换为八进制：
83÷8=10余3
10÷8=1余2
1÷8=0余1
所以八进制为123 8
三、进制运算技巧
在进行不同进制间的加法运算时，建议先转换为十进制运算，然后再转换回目标进制。
【题目总结】
本题通过八进制数的加法运算，考查了进制间的转换和加法计算的能力。熟练掌握进制间的转换方法是信奥赛中的重要基础知识之一，能够为后续的算法学习打下坚实的基础。
3．阅读下述代码，询问修改data的value成员以存储3.14，正确的方式是（ ）。
union Data {
int num;
float value;
char symbol;
};
union Data data;
A．data.value=3.14;
B．value.data=3.14;
C．data->value=3.14;
D．value->data=3.14;
【考点识别】
2 C++程序设计|2.10结构体类型|【1】结构体的定义及应用
2 C++程序设计|2.11指针类型|【1】指针的概念及调用
2 C++程序设计|2.13 STL模板应用|【2】联合体（union）的基本使用及限制
【分析讲解】
题目涉及的是联合体（union）的使用及访问成员的正确方式。下面逐项分析选项并得出结论。
1．代码解释
union Data {
int num;
float value;
char symbol;
};
union Data data;
union是一种特殊的数据结构，其中所有成员共享同一块内存，因此在同一时间只有一个成员可以有效保存值。
在union中访问成员的语法与struct相似，通过点运算符（.）访问成员。
2．对选项的逐一分析
A．data.value=3.14;
这是正确的方式。因为data是union Data的变量，访问成员时直接使用点运算符即可。语法合法且符合联合体的访问规则。
B．value.data=3.14;
错误。value是union Data的成员，而不是变量，不能通过value.data这种方式访问。语法错误。
C．data->value=3.14;
错误。箭头运算符（->）用于指针访问，但data是普通变量，而非指针，因此不能使用箭头运算符。语法错误。
D．value->data=3.14;
错误。类似于选项B，这种语法完全不符合C++的访问规则。语法错误。
【参考答案】
A．data.value=3.14;
【编程魔法师讲解考点】
一、联合体（union）的基本使用
1．什么是联合体（union）
联合体（union）是一种特殊的数据类型，所有成员共享同一块内存。因此，在任意时刻，联合体只能存储一个成员的值。
联合体在节省内存方面有优势，但需要特别小心对成员的访问。
2．基本特点
（1）共享内存：联合体的大小等于其最大成员的大小。例如：
union Example {
int a; // 4字节
float b; // 4字节
char c[10]; // 10字节。联合体的大小为 10 字节（最大成员的大小）
};
（2）成员访问：使用点运算符（.）或箭头运算符（->）来访问成员，具体取决于变量是否为指针。
3．声明和初始化
（1）声明联合体变量：
union Example {
int x;
float y;
};
union Example example;
（2）初始化成员：
example.x = 42;
example.y = 3.14f; // 修改 y 会覆盖 x
4．联合体的局限性
只能存储一个成员的值，如果同时访问多个成员，可能会导致未定义行为。
需要清楚成员的用途和顺序，避免误用。
示例代码：
注意：
在使用联合体时，尽量避免频繁修改不同成员。
如果需要存储多种数据同时使用，struct比union更合适。
【题目总结】
本题考查了联合体成员的访问方法，以及点运算符（.）的正确使用。
4．假设有一个链表的节点定义如下：
struct Node {
int data;
Node* next;
};
现在有一个指向链表头部的指针Node *head。如果想要在链表中插入一个新节点，其成员data的值为42，并使新节点成为链表的第一个节点。下列操作中正确的是（ ）。
A．
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
head = newNode;
B．
Node* newNode = new Node;
head->data = 42;
newNode->next = head;
head = newNode;
C．
Node* newNode = new Node;
newNode->data = 42;
head->next = newNode;
D．
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
【考点识别】
入门级|2.11指针类型|【4】指针、【4】基于指针的数组访问、【4】字符指针、【4】指向结构体的指针
入门级|3.1线性表|【3】链表：单链表、双向链表、循环链表
【分析讲解】
本题要求在链表中插入一个新节点，并让该节点成为链表的第一个节点。下面逐步分析各选项：
选项A：
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
head = newNode;
分析：
创建一个新节点newNode。
将newNode->data设置为42。
将newNode->next指向当前的头节点head。
最后将head指向newNode，使其成为新的链表头。
该操作正确完成了链表的插入操作。
结果：正确
选项B：
Node* newNode = new Node;
head->data = 42;
newNode->next = head;
head = newNode;
分析：
修改了当前头节点的数据域为42，这破坏了链表原有的数据结构。
newNode->next和head的操作顺序没有问题，但新节点的data值未设置。
该操作逻辑混乱，无法正确完成插入操作。
结果：错误
选项C：
Node* newNode = new Node;
newNode->data = 42;
head->next = newNode;
分析：
创建了一个新节点并设置其data值为42。
将head->next设置为newNode，这会导致新节点插入到头节点的后面，而非成为头节点。
该操作没有完成题目要求，插入逻辑错误。
结果：错误
选项D：
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
分析：
创建了一个新节点，设置了其data和next。
但未更新head，导致head仍指向旧的链表头，新节点未被链表接纳。
结果：错误
【参考答案】
A．
Node* newNode = new Node;
newNode->data = 42;
newNode->next = head;
head = newNode;
【编程魔法师讲解考点】
一、链表的基本结构
链表由一个个节点组成，每个节点包含两部分：
数据域data：存储节点的数据。
指针域next：指向下一个节点。
例如：
[Node1 | next] -> [Node2 | next] -> [Node3 | null]
链表的第一个节点称为头节点（head），通过它可以访问整个链表。
二、链表的插入操作
在链表中插入一个节点的通用步骤：
（1）创建一个新节点并为其分配内存。
（2）设置新节点的数据域（data）。
（3）更新新节点的next指针，使其指向当前链表的头节点（或其他目标位置的节点）。
（4）更新链表的头指针（head），使其指向新节点。
代码示例：
Node* newNode = new Node; // 创建新节点
newNode->data = 42; // 设置数据域
newNode->next = head; // 指向当前的头节点
head = newNode; // 更新头指针
三、指针在链表中的作用
指针在链表中起到连接节点的作用，每个节点通过next指针连接到下一个节点。正确操作指针是链表操作的核心。
常见错误：
（1）未正确更新head，导致新节点未被接纳。
（2）修改了原链表节点的内容，破坏了链表结构。
（3）忘记为新节点分配内存。
【题目总结】
链表操作是信奥赛中常见的基础知识点。须重点掌握以下几个考点：
（1）理解链表结构和节点的指针作用。
（2）掌握链表插入操作的步骤。
（3）注意链表操作中的指针更新顺序。
5．根节点的高度为1，一棵拥有2023个节点的三叉树高度至少为（ ）。
A．6
B．7
C．8
D．9
【考点识别】
入门级|3.2简单树|【3】树的定义及其相关概念、【3】二叉树的定义及其基本性质
入门级|3.3特殊树|【4】完全二叉树的定义与基本性质
【分析讲解】
1．三叉树的性质
（1）在一棵三叉树中，每个节点最多可以有三个子节点。
（2）假设树的高度为h，那么在高度为h的三叉树中，节点数最多为
。
这是满三叉树的节点数。
2．问题转化
（1）要求高度h，使得节点总数N≥2023。
（2）解不等式：
，3
h
≥4047。
（3）当h=7:3 7 =2187≤4047，所以h=7不满足。
（4）当h=8，3 8 =6561≥4047，所以h=8满足。
【参考答案】
C．8
【编程魔法师讲解考点】
一、树和高度的定义
在树中，高度是从根节点到叶子节点的最长路径所包含的节点数。对于根节点，其高度为1。
例如：
（1）一棵只有根节点的树，高度为1。
（2）一棵根节点下面有若干层子节点的树，高度就是从根节点到最远子节点路径上的节点数。
二、三叉树的性质
三叉树是一种特殊的树，每个节点最多有三个子节点。
对于高度为h的满三叉树（每个节点都有三个子节点），节点总数公式为
。
三、根据节点数推算高度
当题目给定节点数 N ，求树的最小高度时，可以反推高度 h ：
。
接着逐个试算 h ，直到找到满足条件的最小 h 。
【题目总结】
掌握三叉树的基本性质和高度计算方法后，这类题目只需要熟悉公式并进行推导即可快速解答。这类题的常见陷阱：
（1）忘记根节点的高度是1而非0。
（2）错误理解公式，未考虑三叉树每层节点数量的几何增长。
6．小明在某一天依次有7个空闲时间段，他想要选出至少一个空闲时间段来练习唱歌，但他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息，则小明可选择时间段的方案一共有（ ）。
A．31种
B．18种
C．21种
D．33种
【考点识别】
入门级|5.数学|5.4组合数学|【2】加法原理、【2】乘法原理
【分析讲解】
本题要求选择空闲时间段进行练习，并且满足以下条件：
（1）至少选择一个空闲时间段。
（2）任意两个练习的时间段之间至少有两个空闲时间段。
可以使用枚举法和组合数学的思想来解答：
（1）选择1个时间段：有77种方式。
（2）选择2个时间段：首先选择第一个时间段，然后至少跳过两个时间段选择第二个。方案如下：(1,4)(1,4)，(1,5)(1,5)，(1,6)(1,6)，(1,7)(1,7)，(2,5)(2,5)，(2,6)(2,6)，(2,7)(2,7)，(3,6)(3,6)，(3,7)(3,7)，(4,7)(4,7)。一共1010种方式。
（3）选择3个时间段：只有一种方案，即(1,4,7)(1,4,7)。
（4）选择4个或更多的时间段是不可能的，因为不可能在每两个时间段之间都有两个空闲时间段。
所以总的选择方案是7+10+1=187+10+1=18。
【参考答案】
B．18种
【编程魔法师讲解考点】
一、什么是加法原理
加法原理的精髓：如果完成一件事有几种互不重叠的方案，那么总的方案数就是这些方案数的总和。
例子：小明想要去超市买零食，有两个选择：
选择一种饮料（3种选择：可乐、果汁、矿泉水）。
选择一种零食（2种选择：饼干、薯片）。
这两件事是互不重叠的，所以总方案数为3+2=5。
二、什么是乘法原理
乘法原理的核心：如果完成一件事需要分几步，并且每一步都有多种选择，那么总的方案数就是所有步方案数的乘积。
例子：小明有两个选择：第一步选择一件上衣（4种选择）；第二步选择一条裤子（3种选择）。
总方案数是：4×3=12。
【题目总结】
在比赛中，解决类似问题可以遵循以下步骤：
（1）理解题意，分析限制条件：这是解决问题的第一步，也是最重要的一步。
（2）枚举或分类讨论：遇到复杂的情况，可以通过枚举所有可能的合法组合来解决。
（3）应用加法与乘法原理：把分类讨论的结果结合起来，用加法原理计算总数。
7．以下关于高精度运算的说法中错误的是（ ）。
A．高精度计算主要是用来处理大整数或需要保留多位小数的运算
B．大整数除以小整数的处理步骤可以是：将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
C．高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
D．高精度加法运算的关键在于逐位相加并处理进位
【考点识别】
入门级|4.算法|4.4数值处理算法|【4】高精度的加法、【4】高精度的减法、【4】高精度的乘法、【4】高精度整数除以单精度的商和余数
【分析讲解】
题目问的是关于高精度运算的说法中错误的一项。下面逐一分析选项的正确性。
A．高精度计算主要是用来处理大整数或需要保留多位小数的运算
正确。高精度运算主要应用于普通整数、小数的范围不足以支持的场景，例如计算大数的阶乘、超长浮点数等。
B．大整数除以小整数的处理步骤可以是：将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
正确。这是高精度整数除法的基本实现方法，也称为「竖式除法」，即逐位处理，被除数每位处理后通过减法得到新的被除数，并累加商。
C．高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
错误。高精度乘法的运算时间不仅与较长的整数位数有关，还与两个整数的总位数有关。常规方法需要逐位相乘，并处理进位，时间复杂度大约为 O ( n × m )，其中 n 和 m 是两个整数的位数。
D．高精度加法运算的关键在于逐位相加并处理进位
正确。高精度加法的核心步骤是逐位相加，如果某位的和大于10（或其他进制的基数），需要向前一位进位，这是高精度加法的标准流程。
【参考答案】
C．高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
【编程魔法师讲解考点】
高精度运算听起来很高大上，其实就是计算机在帮人做人用笔算也能做的事情，比如那些数字特别长的加减乘除。今天我们换个角度来聊聊这个话题，保证你看完就会觉得高精度运算不过如此。
一、为什么要用高精度
普通编程里的数据类型，如int或long long，是有范围限制的。例如int类型数据的范围是-2 31 ～2 31 -1，你要是想算100的阶乘，这些类型肯定就顶不住了，会直接爆炸。
这时候怎么办？用高精度啊！它的本质是模拟人们用笔算的过程，没有范围限制，能算得特别准。
二、高精度运算都在干啥
简单来说，高精度运算就是教计算机「小学四则运算」。主要包括：
1．高精度加法
把两个数字从低位开始一位一位地加，就像我们小时候写竖式加法。
如果加起来超过了10，就要进位给前一位。
2．高精度减法
一样是从低位开始一位一位地减，如果不够减就得向前借位。
跟小时候做减法没啥区别。
3．高精度乘法
还记得小时候用竖式乘法吗？一位一位地乘，然后把结果累加起来。
计算复杂度挺高的，需要处理很多位数。
4．高精度除法
就是竖式除法，从高位开始一位一位地试商，看被除数能被除数整除几次。
这个过程也得反复运用减法，直到算完为止。
三、真正的难点在哪
1．进位和借位
加法和减法中最容易出问题的地方就是忘记处理进位或者借位。每次运算都得小心别漏了。
2．位数处理
高精度运算通常会用数组存储每一位数字，例如1234存成[4, 3, 2, 1]。这样方便一位一位地算，但你得记得结果要倒过来输出。
3．效率问题
特别是高精度乘法，时间复杂度是 O ( n × m )，两个数字的位数越多，算起来越慢。
【题目总结】
学高精度运算的窍门：
（1）从加法和减法开始：这些最简单，练练手就能搞懂进位和借位。
（2）用笔算模拟：如果不会写代码，就自己用笔算，照着思路一步步写程序。
（3）多画流程图：列清楚每一步要干啥，特别是进位、借位或者试商。
8．数101010 2 和166 8 的和为（ ）。
A．10110000 2
B．236 8
C．158 10
D．A0 16
【考点识别】
入门级|2.进制间的转换与表示|2.1各种进制间的转换
【1】十进制与二进制之间的转换
【2】十进制与八进制之间的转换
【3】二进制与八进制之间的转换
【4】十六进制的表示与转换
【分析讲解】
（1）转换为十进制：101010 2 =42 10 ，166 8 =118 10 。
（2）计算和：42+118=160 10 。
（3）转换为目标进制：160 10 =10100000 2 ，240 8 ，A0 16 。
（4）对比选项，正确答案为D．A0 16 。
【参考答案】
D．A0 16
【编程魔法师讲解考点】
一、进制之间的转换
二进制、八进制、十六进制可以转换为十进制，再从十进制转换为目标进制实现。
常用方法包括逐步除法和乘法展开。
二、不同进制之间的转换
（1）二进制转十进制：将每一位按权重展开后相加。例如：
101010 2 =1×2 5 +0×2 4 +1×2 3 +0×2 2 +1×2 1 +0×2 0 =42 10 。
（2）八进制转十进制：类似于二进制转换，只是基数是8。例如：
166 8 =1×8 2 +6×8 1 +6×8 0 =64+48+6=118 10 。
（3）十进制转其他进制：使用逐步除法，将数字反复除以目标基数，记录余数，从低位到高位输出。例如：160 10 ÷2依次得到10100000210100000 2 。
【题目总结】
（1）快速转换：二进制与八进制、十六进制之间可以直接按每3位或4位分组。例如：
101010 2 =52 8 （每3位对应一个八进制数字）。
101010 2 =2A 16 （每4位对应一个十六进制数字）。
（2）直接计算：某些进制计算（如二进制）可以直接逐位运用加法或乘法，无须转换为十进制。
9．后缀表达式6 2 3 +- 3 8 2 / + * 2 ^ 3 +对应的中缀表达式是（ ）。
A．((6-(2+3))*((3+8/2)) 2 )+3
B．6-2+3*3+8/2 2 +3
C．(6-(2+3))*((3+8/2) 2 )+3
D．6-((2+3)*(3+8/2)) 2 +3
【考点识别】
入门级|6.数据结构|6.2栈|
【1】表达式的后缀（逆波兰）表示法。
【2】后缀表达式与中缀表达式的相互转换。
【3】利用栈求解后缀表达式。
【分析讲解】
后缀表达式（又称逆波兰表达式）的计算和转换遵循从左到右扫描的原则，使用栈辅助运算。下面逐步分析讲解题中的后缀表达式：
6 2 3 + 3 8 2 / + * 2 ^ 3 +。
我们从左到右逐步处理：
（1）遇到数字时，直接压入栈。
（2）遇到运算符时，从栈中弹出需要的操作数，计算结果后再压入栈。
过程如下：
起始表达式：6 2 3+3 8 2 /+* 2 ^ 3 +
初始栈：空
读6：压入栈，栈：[6]
读2：压入栈，栈：[6, 2]
读3：压入栈，栈：[6, 2, 3]
读+：弹出3和2，形成中缀表达式(2+3)，结果压入栈，栈：[6,(2+3)]
读-：弹出(2+3)和6，形成中缀表达式(6(2+3))，结果压入栈，栈：[(6(2+3))]
读3：压入栈，栈：[(6(2+3)), 3]
读8：压入栈，栈：[(6(2+3)), 3, 8]
读2：压入栈，栈：[(6(2+3)), 3, 8, 2]
读/：弹出2和8，形成中缀表达式(8/2)，结果压入栈，栈：[(6(2+3)), 3,(8/2)]
读+：弹出(8/2)和3，形成中缀表达式(3+(8/2))，结果压入栈，栈：[(6(2+3)),(3+(8/2))]
读*：弹出(3+(8/2))和(6(2+3))，形成中缀表达式((6(2+3))*(3+(8/2)))，结果压入栈，栈：[((6(2+3))*(3+(8/2)))]
读2：压入栈，栈：[((6(2+3))*(3+(8/2))), 2]
读^：弹出2和((6(2+3))*(3+(8/2)))，形成中缀表达式(((6(2+3))*(3+(8/2)))^2)，结果压入栈，栈：[(((6(2+3))*(3+(8/2)))^2)]
读3：压入栈，栈：[(((6(2+3))*(3+(8/2)))^2), 3]
读+：弹出3和(((6(2+3))*(3+(8/2)))^2)，形成中缀表达式((((6(2+3))*(3+(8/2)))^2)+3)，结果压入栈，栈：[((((6(2+3))*(3+(8/2)))^2)+3)]
【参考答案】
A．((6(2+3))*(3+(8/2))^2)+3
【编程魔法师讲解考点】
后缀表达式是一种计算机科学中非常重要的表达式形式，它在计算中避免了括号的使用，使计算逻辑更加高效，特别适合用栈这种数据结构实现。
一、什么是后缀表达式
后缀表达式，又叫逆波兰表达式（Reverse Polish Notation，RPN）。
运算符写在操作数之后，例如3 4 +，表示3+4。
二、后缀表达式的计算过程
后缀表达式计算常用栈（stack）来实现，步骤如下：
（1）准备一个空栈。
（2）遍历表达式：
如果遇到数字，压入栈。
如果遇到运算符，弹出两个操作数，计算结果后再压回栈。
（3）表达式遍历结束后，栈顶的值就是最终结果。
后缀表达式的转换过程其实是将每一步的操作用括号表示并嵌套起来。例如，6 2 3 +对应中缀为(6(2+3))。
三、后缀表达式转换为中缀表达式的方法
要将后缀表达式转换回中缀表达式，需要重点关注运算优先级和括号：
（1）从左到右扫描后缀表达式。
（2）遇到操作数，直接入栈。
（3）遇到运算符，弹出栈顶的两个元素，构造一个新表达式并加括号，再将新表达式压入栈。
（4）最后栈中剩下的唯一元素即为完整的中缀表达式。
例子：
后缀表达式：6 2 3 - - 3 8 2 /+* 2 ^ 3 +
转换过程：
计算2-3：(2-3)
计算6-(2-3)：(6-(2-3))
计算3+8/2：(3+8/2)
计算((3+8/2) 2 )
计算整个表达式：((6-(2-3))*((3+8/2) 2 ))+3
【题目总结】
后缀表达式考查了栈这种经典数据结构的运用，以及对表达式运算的理解。这类题目简单易学，但逻辑严密，需要熟练掌握操作顺序：
（1）确定运算顺序：在栈中后入的操作数先被运算，体现了后进先出（LIFO）的原则。
（2）确保先弹出的是右操作数，后弹出的是左操作数。
10．假设有一组字符{a, b, c, d, e, f}，对应的频率分别为5%、9%、12%、13%、16%、45%。以下选项中为字符a, b, c, d, e, f分别对应的一组哈夫曼编码是（ ）。
A：1111, 1110, 101, 100, 110, 0
B：1010, 1001, 1000, 011, 010, 00
C：000, 001, 010, 011, 10, 11
D：1010, 1011, 110, 111, 00, 01
【考点识别】
入门级|数据结构|特殊树|【4】哈夫曼树的定义和构造、哈夫曼编码
【分析讲解】
哈夫曼编码是一种前缀编码方法，它根据字符出现的频率生成最优二进制编码，使得编码后的平均长度最短。
以下是具体解答步骤：
1．根据频率构造哈夫曼树
给定频率：{a:5%,b:9%,c:12%,d:13%,e:16%,f:45%}
构造过程：
（1）将频率最低的两个字符合并为一个新节点，形成树的分支，新节点的权值是两个频率的和。
（2）重复上述过程，直到只有一个根节点。
2．具体过程
（1）合并a(5%)和b(9%)生成节点N1(14%)。
（2）合并c(12%)和d(13%)，生成节点N2(25%)。
（3）合并N1(14%)和e(16%)，生成节点N3(30%)。
（4）合并N2(25%)和N3(30%)，生成节点N4(55%)。
（5）合并N4(55%)和f(45%)，生成根节点Root(100%)。
3．生成编码
从根节点出发，左分支编码为0，右分支编码为1。最终字符对应的编码为从根到叶子节点路径上的编码序列。
【参考答案】
A．1111, 1110, 101, 100, 110, 0
【编程魔法师讲解考点】
一、哈夫曼树是什么
哈夫曼树是一种带权路径长度最短的二叉树。这里“带权路径长度”可以理解为树中每个叶子节点的权重乘以它到根的路径长度之和。构造时总是优先合并权值最小的节点，形成新的分支节点。
二、如何构造哈夫曼树
（1）把所有字符看成单独的节点，每个节点的权值是字符出现的频率。
（2）找出权值最小的两个节点，合并成一个新节点，新节点的权值等于两个节点的权值之和。
（3）重复这一步，直到所有节点合并成一棵树。
【题目总结】
哈夫曼树和哈夫曼编码是一种基于字符出现频率的最优前缀编码方法，能让编码后的数据更节省空间。简单说，出现得越频繁的字符，它的编码就越短；出现少的字符，编码会稍长一些，但总体是最优的。
11．给定一棵二叉树，其前序遍历结果为ABDECFG，中序遍历结果为DEBACFG。这棵树的后序遍历结果是（ ）。
A．EDBGFCA
B．EDGBFCA
C．DEBGFCA
D．DBEGFCA
【考点识别】
入门级|数据结构|简单树|【4】二叉树的定义及其基本性质、【4】二叉树的遍历：前序、中序、后序遍历
【分析讲解】
1．前序遍历和中序遍历的特点
前序遍历：按顺序访问根、左子树、右子树。
中序遍历：按顺序访问左子树、根、右子树。
根据这些特点，可以利用前序遍历的第一个节点确定树的根节点，从中序遍历中分割出左子树和右子树的节点集合。
2．构造二叉树
（1）从前序遍历中，根节点是A。
（2）在中序遍历中，A的位置将中序序列分割为：
左子树：DEB；
右子树：CFG。
（3）在左子树DEB中：
从前序遍历中，接下来的根是B。
在中序遍历中，B的位置将左子树分割为：
左子树：DE；
右子树：无。
（4）在左子树DE中：
从前序遍历中，接下来的根是D。
在中序遍历中，D的位置将左子树分割为：
左子树：空；
右子树：E。
（5）回到右子树CFG：
从前序遍历中，接下来的根是C。
在中序遍历中，C的位置将右子树分割为：
左子树：F；
右子树：G。
（6）F和G是叶子节点。
3．后序遍历
根据二叉树的后序遍历规则（左子树→右子树→根节点），可以得到结果：
左子树的后序遍历：E→D→B；
右子树的后序遍历：G→F→C。
最后访问根节点A。
组合结果：EDBGFCA。
【参考答案】
A．EDGBFCA
【编程魔法师讲解考点】
一、什么是前序、中序、后序遍历
（1）前序遍历（Pre-order Traversal）：按顺序访问根节点→左子树→右子树。
（2）中序遍历（In-order Traversal）：按顺序访问左子树→根节点→右子树。
（3）后序遍历（Post-order Traversal）：按顺序访问左子树→右子树→根节点。
二、怎么根据遍历序列推导二叉树
通常会给参赛者两种遍历结果（如前序+中序），要求构造一棵二叉树。
（1）先从前序遍历找根节点：前序遍历的第一个节点是树的根。
（2）从中序遍历里分左右子树：找到根节点在中序遍历的位置，分成左右两部分，分别是左子树和右子树。
（3）递归构造子树：用剩余的前序和中序序列重复上述过程。
【题目总结】
二叉树遍历虽然简单，掌握前序、中序、后序的规则和结合方式，再多练几道题，就能在竞赛中“得心应手”！
记住遍历特点：前序第一个是根；中序分割左右子树；后序最后一个是根。
12．考查一个有向无环图，该图包括4条有向边：(1, 2), (1, 3), (2, 4), (3, 4)。以下选项中为这个有向无环图的一个有效的拓扑排序是（ ）。
A．4, 2, 3, 1
B．1, 2, 3, 4
C．1, 2, 4, 3
D．2, 1, 3, 4
【考点识别】
入门级|数据结构|简单图|【4】图的定义与相关概念、【4】图的表示与存储：邻接矩阵、邻接表、【6】有向无环图的拓扑排序
【分析讲解】
1．拓扑排序过程
（1）初始化入度为0的节点队列：1。
（2）依次从队列中取出节点，并将其加入拓扑排序结果中，同时更新依赖它的节点的入度。
（3）重复上述过程，直到所有节点都被处理。
2．具体操作
（1）取出节点1：
加入排序结果：1。
减少2和3的入度：2的入度变为0，3的入度变为0。
队列更新为：2,3。
（2）取出节点2：
加入排序结果：1,2。
减少4的入度：4的入度变为1。
队列更新为：3。
（3）取出节点3：
加入排序结果：1,2,3。
减少4的入度：4的入度变为0。
队列更新为：4。
（4）取出节点4：
加入排序结果：1,2,3,4。
队列为空，排序结束。
【参考答案】
B．1, 2, 3, 4
【编程魔法师讲解考点】
一、什么是拓扑排序
拓扑排序的目标是为有向无环图中的所有节点安排一个线性顺序，使得每条有向边( u , v )中，节点 u 必须排在节点 v 之前。通俗地说，所有“依赖关系”都被正确地满足了。
二、如何进行拓扑排序
拓扑排序常用的方法有两种：基于入度的Kahn算法（常用）、基于深度优先搜索（DFS）的递归方法。
1．基于入度的Kahn算法
（1）统计每个节点的入度（即有多少条边指向它）。
（2）将所有入度为0的节点加入队列。
（3）从队列中取出节点，将它加入排序结果，同时移除它的出边并更新目标节点的入度。
（4）如果目标节点的入度变为0，则将其加入队列。
（5）重复上述过程，直到所有节点都被处理。
2．基于深度优先搜索的递归方法
（1）从未访问过的节点出发，沿着有向边递归访问。
（2）在递归返回时，将节点加入栈（或直接加入结果表）。
（3）最终栈中的节点顺序即为拓扑排序结果。
【题目总结】
拓扑排序是非常重要的图论算法，用来解决有向无环图中的顺序问题。通过学习Kahn算法和DFS方法，可以轻松应对各种涉及依赖的排序问题！
13．在计算机中，以下选项描述的数据存储容量最小的是（ ）。
A．字节(byte)
B．比特(bit)
C．字(word)
D．千字节(kilobyte)
【考点识别】
入门级|计算机基础与编程环境|计算机的基本构成|【1】计算机存储单位：bit（比特）、byte（字节）、KB、MB等
【分析讲解】
1．各选项的解释和比较
A．比特(bit)：比特是计算机存储的最小单位。1比特可以表示两个状态（如0和1）。
B．字节(byte)：字节由8比特组成，即1字节=8比特。常用来表示一个字符（如字母、数字）。
C．字(word)：字是CPU一次可以处理的数据位数，其大小因CPU架构而异。通常为16位、32位或64位等（即2字节、4字节或8字节）。
D．千字节(kilobyte)：1千字节(KB)=1024字节=8192比特。
2．单位比较
从小到大的顺序为：比特(bit)<字节(byte)<字(word)<千字节(kilobyte)
【参考答案】
B．比特(bit)
【编程魔法师讲解考点】
在计算机中，存储单位是一个非常基础的概念。今天我们就来搞懂这些单位的关系和实际意义，让它们不再是你的拦路虎！
一、什么是存储单位
存储单位是用来描述数据大小的标准。计算机的存储是以二进制为基础的，因此单位之间是以2的幂次进行换算的。
二、各存储单位的大小关系
1．比特(bit)
比特是存储的最小单位，一比特可以存储一个二进制位（0或1）。
例子：一比特可以表示一盏灯的开关状态（开／关）。
2．字节(byte)
字节是最常用的存储单位，1字节等于8比特。
例子：一个英文字母（如A）通常需要1字节，一个汉字通常需要2～3字节。
3．字(word)
字是计算机处理数据的单位，通常由16位（2字节）或32位（4字节）组成，具体取决于CPU的架构。
例子：早期的计算机是16位字长（2字节），现代计算机通常为32位或64位。
4．千字节(kilobyte)
1千字节等于1024字节（注意，计算机采用二进制换算）。
例子：一篇普通TXT格式的文本文档大小大一般是10～20KB。
三、单位换算口诀
计算机存储单位的换算规律：
1字节(B)=8比特(bit)；
1KB=1024字节(B)；
1MB=1024KB；
1GB=1024MB；
1TB=1024GB。
【题目总结】
当你看到存储单位时，第一步是判断哪个更小、哪个更大。比特是最小单位，往上逐步累加，记住它们的大小关系和换算规律，就能轻松搞定这类题！
14．一个班级有10个男生和12个女生。如果要选出一个3人的小组，并且小组中必须至少包含1个女生，那么可能的组合为（ ）。
A．1420种
B．1770种
C．1540种
D．2200种
【考点识别】
入门级|数学与逻辑|组合数学|【1】排列与组合的基本概念和应用
【分析讲解】
本题属于组合数学问题，需要根据题意计算所有符合条件的组合数。问题要求小组中必须至少有1个女生，因此需要用排除法或分情况讨论法解决。
方法1
在所有男生、女生里面挑3个的方案数：挑选3个男生的方案数，
。
方法2
至少包括一个女生，最多包含3个女生，所以可以分为三种情况：
（1）包含一个女生，有
种方法。
（2）包含两个女生，有
种方法。
（3）包含三个女生，有
种方法。
因此，共有540+660+220=1420种方案。
【编程魔法师讲解考点】
排列与组合是一种用数学方法解决分配问题的基本工具，也是信奥赛中常见的考点。
什么是排列与组合
1．排列
从一组对象中选出若干个并按顺序排列的方法，顺序很重要。
公式为
，表示从
n
个对象中选取
r
个的排列数。
2．组合
从一组对象中选出若干个，不考虑顺序的方法。
公式为
，表示从
n
个对象中选取
r
个的组合数。
【题目总结】
排列与组合的计算看似复杂，但只要理解公式和题目要求就可以轻松解决。最重要的是练习多个类似题目，形成“下意识解法”。
15．以下不是操作系统名称的是（ ）。
A．Linux
B．Windows
C．Android
D．HTML
【考点识别】
入门级|计算机基础与编程环境|操作系统与应用软件|【2】常见操作系统：Windows、Linux、macOS等【4】操作系统的基本功能与分类
【分析讲解】
本题考查的是对操作系统和相关技术的理解，重点是识别哪个选项不是操作系统。
1．什么是操作系统
操作系统（Operating System，OS）是管理计算机硬件和软件资源的系统软件。它为用户提供友好的界面，同时管理底层资源，如CPU、内存、硬盘、输入输出设备等。常见的操作系统有：
Windows：微软公司开发的操作系统，适用于个人计算机。
Linux：一种开源的操作系统，常用于服务器、嵌入式设备和开发环境。
Android：基于Linux内核的移动操作系统，主要用于智能手机和平板计算机。
2．关于选项的分析
A．Linux：一种开源的操作系统，广泛应用于服务器、嵌入式设备等。
B．Windows：微软公司开发的著名操作系统，个人计算机最常用。
C．Android：基于Linux内核的移动操作系统，广泛应用于智能设备。
D．HTML：一种超文本标记语言，用于网页开发，不是操作系统。
【参考答案】
D．HTML
【编程魔法师讲解考点】
一、操作系统（Operating System, OS）
1．定义
操作系统是计算机中的系统软件，直接运行在硬件之上，负责管理硬件资源并为用户和应用软件提供服务。
2．功能
资源管理：管理CPU、内存、硬盘、输入输出设备等资源。
任务调度：同时运行多个程序时，操作系统决定谁先用CPU，谁等着。
文件管理：组织和存储文件，提供读写文件的接口。
用户接口：提供图形用户界面（GUI）或命令行界面（CLI），方便用户与计算机交互。
设备管理：处理打印机、键盘、鼠标等外部设备的操作请求。
3．常见的操作系统
桌面操作系统：Windows、macOS、Linux。
移动操作系统：Android、iOS。
服务器操作系统：Windows Server、Ubuntu Server、CentOS。
嵌入式操作系统：VxWorks、FreeRTOS。
二、应用软件（Application Software）
1．定义
应用软件是为满足用户特定需求开发的软件，依赖操作系统运行。它解决的是具体的任务，比如文字处理、图像编辑、游戏等。
2．功能
文字处理：编辑文档、排版，如Microsoft Word。
表格处理：数据分析、财务管理，如Microsoft Excel。
多媒体处理：图片编辑、视频制作，如Photoshop、Premiere。
浏览器：访问网页，如Chrome、Edge。
通讯软件：邮件、即时通讯，如Outlook、微信。
娱乐软件：游戏、音乐播放器，如Steam、Spotify。
3．分类
通用型应用软件：满足大多数用户需求，如办公软件（Microsoft Office）、浏览器（Chrome）。
专业型应用软件：用于特定领域，如AutoCAD（工程设计）、MATLAB（科学计算）。
定制型应用软件：为某一机构或企业量身定制的软件，如ERP系统、CRM系统。
【题目总结】
操作系统是计算机的“大脑”，提供管理与支持功能；
应用软件是“工具”，解决用户的具体问题。
两者紧密结合，为现代计算设备提供强大的功能和良好的用户体验。