C++等级考试资料二
考试内容：
- 选择题：进制转换、冒泡与选择排序、二分思想、链表与顺序表、二维数组初始化、函数阅读
- 编程题：字符串操作、质数判断、排序、最小公倍数、最大公约数、百钱百鸡问题
考试资料：
进制转换公式
1. 十进制转二进制
整数部分：
- 不断将十进制数除以2，记录余数，直到商为0，然后将余数逆序排列。
小数部分：
- 不断将小数部分乘以2，记录整数部分，直到小数部分为0或达到所需精度，然后将记录的整数部分顺序排列。
示例：
- 十进制数 10.625 转换为二进制：
- 整数部分：10 -> 1010
- 小数部分：0.625 -> 0.101
- 结果：10.625 -> 1010.101
2. 二进制转十进制
整数部分：
- 将二进制数按位展开，每位乘以2的幂次方，然后求和。
小数部分：
- 将二进制小数按位展开，每位乘以2的负幂次方，然后求和。
示例：
- 二进制数 1010.101 转换为十进制：
- 整数部分：1010 -> 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 -> 8 + 0 + 2 + 0 -> 10
- 小数部分：0.101 -> 1*2^-1 + 0*2^-2 + 1*2^-3 -> 0.5 + 0 + 0.125 -> 0.625
- 结果：1010.101 -> 10.625
3. 十进制转十六进制
整数部分：
- 不断将十进制数除以16，记录余数，直到商为0，然后将余数逆序排列。
小数部分：
- 不断将小数部分乘以16，记录整数部分，直到小数部分为0或达到所需精度，然后将记录的整数部分顺序排列。
示例：
- 十进制数 255.6875 转换为十六进制：
- 整数部分：255 -> FF
- 小数部分：0.6875 -> 0.B
- 结果：255.6875 -> FF.B
4. 十六进制转十进制
整数部分：
- 将十六进制数按位展开，每位乘以16的幂次方，然后求和。
小数部分：
- 将十六进制小数按位展开，每位乘以16的负幂次方，然后求和。
示例：
- 十六进制数 FF.B 转换为十进制：
- 整数部分：FF -> 15*16^1 + 15*16^0 -> 240 + 15 -> 255
- 小数部分：0.B -> 11*16^-1 -> 0.6875
- 结果：FF.B -> 255.6875
- 整数部分：不断除以2，记录余数，逆序排列。
- 小数部分：不断乘以2，记录整数部分，顺序排列。
- 整数部分：按位展开，每位乘以2的幂次方求和。
- 小数部分：按位展开，每位乘以2的负幂次方求和。
- 整数部分：不断除以16，记录余数，逆序排列。
- 小数部分：不断乘以16，记录整数部分，顺序排列。
- 整数部分：按位展开，每位乘以16的幂次方求和。
- 小数部分：按位展开，每位乘以16的负幂次方求和。
公式总结
十进制转二进制
二进制转十进制
十进制转十六进制
十六进制转十进制
冒泡排序和选择排序
冒泡排序
介绍：冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，如果它们的顺序错误。这个过程会重复进行，直到没有需要交换的元素为止。排序方式：1. 从列表的第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
3. 对每一对相邻元素重复上述步骤，直到列表末尾。
- 重复步骤1-3，直到整个列表有序。
程序：
|
#include <iostream> using namespace std;
void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < n - i - 1; ++j) { if (arr[j] > arr[j + 1]) { // 交换 arr[j] 和 arr[j + 1] int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }
int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); cout << "Sorted array: \n"; for (int i = 0; i < n; ++i) { cout << arr[i] << " "; } cout << endl; return 0; } |
选择排序
介绍：选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序部分中选出最小（或最大）的元素，放到已排序部分的末尾。
排序方式：
- 从列表中找到最小的元素，将其与列表的第一个元素交换位置
- 在剩下的未排序元素中继续寻找最小的元素，将其与列表的第二个元素交换位置。
- 重复上述步骤，直到整个列表有序。
程序：
|
#include <iostream> using namespace std;
void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { // 找到未排序部分的最小元素 int minIndex = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[minIndex]) { minIndex = j; } } // 交换最小元素和第i个元素 int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } }
int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); cout << "Sorted array: \n"; for (int i = 0; i < n; ++i) { cout << arr[i] << " "; } cout << endl; return 0; } |
总结
- 冒泡排序：通过重复地比较和交换相邻元素来排序。每一轮比较后，最大的元素会“冒泡”到数组的末尾。
- 选择排序：通过反复选择未排序部分中的最小元素并将其放在已排序部分的末尾来排序。
链表和顺序表
链表
介绍：链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表可以是单向链表、双向链表或循环链表。
特点：
- 动态大小：链表的大小可以动态调整，不需要预先分配固定大小的内存。
- 插入和删除操作高效：在链表中插入和删除元素只需要修改指针，不需要移动其他元素。
- 顺序访问：链表中的元素只能按顺序访问，不能通过索引直接访问。
顺序表
介绍：顺序表是一种线性数据结构，使用连续的内存空间存储数据。顺序表的元素可以通过索引直接访问。
特点：
- 固定大小：顺序表的大小在创建时确定，不能动态调整（除非使用动态数组）。
- 插入和删除操作低效：在顺序表中插入和删除元素需要移动其他元素。
- 随机访问：顺序表中的元素可以通过索引直接访问，访问速度快。
区别：
|
特性 |
链表 |
顺序表 |
|
内存分配 |
动态分配 |
连续内存分配 |
|
大小调整 |
动态调整 |
固定大小(除非使用动态数组) |
|
插入和删除操作 |
高效（只需修改指针） |
低效（需要移动其他元素） |
|
访问方式 |
顺序访问（不能通过索引访问） |
随机访问（可以通过索引访问） |
|
内存利用率 |
可能有额外的指针开销 |
内存利用率高 |
|
适用场景 |
频繁插入和删除操作 |
频繁访问和修改操作 |
总结
- 链表：适用于需要频繁插入和删除操作的场景，具有动态大小和高效的插入删除操作，但访问速度较慢。
- 顺序表：适用于需要频繁访问和修改操作的场景，具有快速的随机访问能力，但插入和删除操作较低效。
二维数组
介绍
二维数组是数组的数组，可以用来表示矩阵或表格数据。它是一个具有行和列的矩形数据结构，每个元素可以通过两个索引（行索引和列索引）来访问。
定义和初始化方式
1. 静态初始化
定义：在声明数组时直接赋值。
示例：
|
#include <iostream> using namespace std;
int main() { // 定义并初始化一个3x4的二维数组 int arr[3][4] = { {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12} };
// 打印二维数组 for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { cout << arr[i][j] << " "; } cout << endl; }
return 0; } |
2. 部分初始化
定义：只初始化部分元素，未初始化的元素会被默认初始化为0。
示例：
|
#include <iostream> using namespace std;
int main() { // 定义并部分初始化一个3x4的二维数组 int arr[3][4] = { {1, 2}, {5, 6, 7} };
// 打印二维数组 for (int i = 0; i < 3; ++i) { for (int j = 0; j < 4; ++j) { cout << arr[i][j] << " "; } cout << endl; }
return 0; } |