计算机考研复试机试-考前速记

考前速记 知识点

1. 链表篇

1. 循环链表报数3，输出最后一个报数编号

#include <iostream>
using namespace std;typedef struct Node {int no;struct Node* next;
}Node, *NodeList;void createNodeListTail(NodeList&L, int n) {L = (Node*)malloc(sizeof(Node));L->no = -1;L->next = NULL;Node* tail = L;for (int i = 0; i < n; i++) {Node* x = (Node*)malloc(sizeof(Node));x->no = (i + 1);x->next = NULL;tail->next = x;tail = x;}tail->next = L->next; // 形成循环链表return;
}int main() {int n;cin >> n;NodeList L;createNodeListTail(L, n);Node* pre = L; // 记录退出序号的前驱Node *p = pre->next;int LastNo = -1; // 记录每次退出的序号int count = 0; // 记录删除的结点个数while (count < n) {int i = 1;while (i < 3) {pre = p;p = p->next;i++;}Node* q = p; // 出队LastNo = q->no;pre->next = q->next;p = pre->next;free(q);count++;}cout << LastNo << endl;return 0;
}

2. 链表基本操作

#include <iostream>
#include <vector>
using namespace std;typedef struct LNode {int data;struct LNode* next;
}LNode, *LinkList;// 头插法建立链表
void createLinkListHead(LinkList &L, int n) {L = (LNode*)malloc(sizeof(LNode));L->data = -1;L->next = NULL;for (int i = 0; i < n; i++) {int data;cin >> data;LNode* x = (LNode*)malloc(sizeof(LNode));x->data = data;x->next = L->next;L->next = x;}
}// 删除第n个位置的元素
bool deleteN(LinkList& L, int n) {int count = 1;LNode* pre = L;LNode* p = pre->next;while (p) {if (count == n) {LNode* q = p;pre->next = q->next;p = pre->next;free(q);cout << "delete OK" << endl;return true;}else {pre = pre->next;p = p->next;}count++;}cout << "delete fail" << endl;return false;
}// 输出第n个位置元素
bool getN(LinkList L, int n) {int count = 1;LNode* p = L->next;while (p) {if (count == n) {cout << p->data << endl;return true;}p = p->next;count++;}cout << "get fail" << endl;return false;
}// 在第n个元素之后插入元素
bool insertBeforePOSN(LinkList& L, int pos, int data) {int count = 1;LNode* pre = L;LNode* p = pre->next;LNode* x = (LNode*)malloc(sizeof(LNode));if (p == NULL && pos == 1) { // 处理空链表插入x->data = data;x->next = NULL;L->next = x;cout << "insert OK" << endl;return true;}while (p) {if (count == pos) {x->data = data;x->next = p;pre->next = x;cout << "insert OK" << endl;return true;}else {pre = p;p = pre->next;}count++;}cout << "insert fail" << endl;return false;
}// 输出L
void showL(LinkList L) {LNode* p = L->next;if (p == NULL) {cout << "Link list is empty" << endl;return;}while (p) {cout << p->data << " ";p = p->next;}cout << endl;return;
}int main() {int n;cin >> n;LinkList L = (LNode*)malloc(sizeof(LNode));createLinkListHead(L, n);int m;cin >> m;vector<string> op(m);vector<int> param1(m);vector<int> param2(m);for (int i = 0; i < m; i++) {cin >> op[i];if (op[i] == "get" || op[i] == "delete") {cin >> param1[i];param2[i] = -1;}else if (op[i] == "insert") {cin >> param1[i] >> param2[i];}else if(op[i] == "show") {param1[i] = -1;param2[i] = -1;}}for (int i = 0; i < m; i++) {if (op[i] == "delete")deleteN(L, param1[i]);else if (op[i] == "get")getN(L, param1[i]);else if (op[i] == "insert")insertBeforePOSN(L, param1[i], param2[i]);else if (op[i] == "show")showL(L);}return 0;
}

2. vector & set

1. find方法

#include <vector>
#include <algorithm>
vector<int> arr;
auto it = find(arr.begin(), arr.end(), p->no);
if (it != arr.end()) {cout << it - arr.begin() << endl; // 获取下标//...
}

2. 一维数组，元素为[a, b]

vector<pair<int, int>> temp; // 记录感染的房间
temp.push_back({i, j});
for (int k = 0; k < temp.size(); k++) { int i = temp[k].first;int j = temp[k].second;//...
}

3. set去重

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;int main() {int arr[31] = { 0 };int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];sort(arr, arr + n);set <pair< int,int >> unique_pairs; // 定义setfor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j && unique_pairs.find({ arr[i], arr[j] }) == unique_pairs.end()) { // set查找cout << "(" << arr[i] << "," << arr[j] << ")" << endl;unique_pairs.insert({ arr[i], arr[j] }); // set插入}}}return 0;
}

3. 排序

1. 快速排序

#include <iostream>
using namespace std;int partition(int arr[], int left, int right) {int pivot = arr[left];while (left < right) {while (left<right && arr[right] >= pivot) right--;arr[left] = arr[right];while (left<right && arr[left] <= pivot) left++;arr[right] = arr[left];}arr[left] = pivot;return left;
}void QuickSort(int arr[], int left, int right) {if(left>=right) return;int mid = partition(arr, left, right);QuickSort(arr, left, mid - 1);QuickSort(arr, mid + 1, right);return;
}int main() {int arr[100];int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];QuickSort(arr, 0, n - 1);for (int i = 0; i < n; i++) cout << arr[i] << " ";cout << endl;return 0;
}

2. 归并排序

#include <iostream>
using namespace std;const int MAXN = 1e5 + 10;
int temp[MAXN];
int arr[MAXN];
void merge(int arr[], int left, int right) {for (int i = left; i <= right; i++)temp[i] = arr[i];int mid = (left + right) / 2;int i = left, j = mid + 1;int k = left; // 从left位置开始存储while (i <= mid && j <= right) {if (temp[i] <= temp[j])arr[k++] = temp[i++];elsearr[k++] = temp[j++];}while (i <= mid)arr[k++] = temp[i++];while (j <= right)arr[k++] = temp[j++];return;
}void mergeSort(int arr[], int left, int right) {if (left >= right) return;int mid = (left + right) / 2;mergeSort(arr, left, mid); // 对左边递归mergeSort(arr, mid + 1, right); // 对右边递归merge(arr, left, right); // 归并
}
int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];mergeSort(arr, 0, n - 1);for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

3. 希尔排序

#include <iostream>
using namespace std;const int MAXN = 1e5 + 10;
int arr[MAXN];void printArr(int arr[], int n) {for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;
}void insertSort(int arr[], int n, int dk) {for (int i = dk; i < n; i++) { // dk:n-1int k = arr[i];int j;for (j = i - dk; j >= 0; j -= dk) {if (arr[j] > k)arr[j + dk] = arr[j];elsebreak;}arr[j + dk] = k;}return;
}void shellSort(int arr[], int n) {for (int dk = n / 2; dk >= 1; dk /= 2){insertSort(arr, n, dk%2==0?dk+1:dk);printArr(arr, n);}return;
}int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];shellSort(arr, n);return 0;
}

4. 折半插入排序

#include <iostream>
using namespace std;void insertSort(int arr[], int n) {for (int i = 2; i <= n; i++) {arr[0] = arr[i]; // 待排元素int left = 1, right = i - 1;while (left <= right) { // 找位置int mid = (left + right) / 2;if (arr[mid] <= arr[0])left = mid + 1;elseright = mid - 1;}// 位置(含)之后元素后移for (int j = i - 1; j >= left; j--)arr[j + 1] = arr[j];// 插入待排元素arr[left] = arr[0];}return;
}
int arr[1000];
int main() {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i];insertSort(arr, n);for (int i = 1; i <= n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

5. 堆排序

#include <iostream>
using namespace std;void HeapAdjust(int arr[], int k, int len) {arr[0] = arr[k]; // 存储待排元素for (int i = k * 2; i <= len; i = 2 * i) { // 不停下坠找到存放arr[0]的位置if (i < len&& arr[i] < arr[i + 1])i++;if (arr[0] > arr[i])break;else {arr[k] = arr[i];k = i;}}arr[k] = arr[0]; // 放置待排元素return;
}void BuildMaxHeap(int arr[], int len) { // 建立大根堆for (int i = len / 2; i > 0; i--)HeapAdjust(arr, i, len);
}void swap(int& a, int& b) {int t = a;a = b;b = t;return;
}void HeapSort(int arr[], int len) {BuildMaxHeap(arr, len); // 建堆while (len > 1) {swap(arr[1], arr[len--]);HeapAdjust(arr, 1, len);}//for (int i = len; i > 1; i--) {//	swap(arr[1], arr[i]);  // 交换arr[1] 和 arr[len--] //	HeapAdjust(arr, 1, i - 1); // 重新调整堆//}return;
}const int MAXN = 1e5 + 10;
int arr[MAXN];int main() {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> arr[i];HeapSort(arr, n);for (int i = 1; i <= n; i++)cout << arr[i] << " ";cout << endl;return 0;
}

4. 数学

1. 质数

#include <iostream>
using namespace std;const int MAXN = 1000;
bool isPrime[MAXN];void init() {for (int i = 0; i < MAXN; i++)isPrime[i] = true; // 初始化都是质数isPrime[0] = false;isPrime[1] = false;for (int i = 2; i < MAXN; i++) {if (isPrime[i] == false)continue;// i是质数for (int k = i*i; k < MAXN; k += i) {isPrime[k] = false; // 质数的倍数不是质数}}
}int main() {int n;cin >> n;init();for (int i = 0; i <= n; i++)if (isPrime[i])cout << i << endl;return 0;
}

2. double小数问题

#include <iostream>
#include <iomanip> // ***
using namespace std;int main() {int n;cin >> n;double sum = 0;for (int i = 1; i <= n; i++) sum += double(1.0 / i);  // ** 1.0/icout << fixed << setprecision(6) << sum << endl; // ***return 0;
}

3. ip转16进制输出

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;int main() {int a, b, c, d;scanf("%d.%d.%d.%d", &a, &b, &c, &d);bool isFlag = true; // 输入是否合法if (a > 255 || b > 255 || c > 255 || d > 255)isFlag = false;if(a<0||b<0||c<0||d<0)isFlag = false;if(getchar() != '\n')isFlag = false;if (isFlag == false)printf("Error\n");elseprintf("0x%02X%02X%02X%02X", a, b, c, d); // printf("%4o %2X\n", num, num); // 输出8进制 16进制return 0;
}

4. 快速幂

#include <iostream>
using namespace std;int main() {long x, n;cin >> x >> n;int mod = 233333;long long res = 1;while (n != 0) {if (n % 2 == 1)res = (res * x) % mod;x = (x * x) % mod;n /= 2;}cout << res << endl;return 0;
}

5. 字符转数字 数字转字符

char c;
int n;
int num = c - '0';
char cc = n + '0';
string str="1234";
int num = stoi(str);

5.动态规划

1. 放苹果

#include <iostream>
#include <cstring>
using namespace std;int main() {int dp[13][13] = { 0 };int count;cin >> count;while (count--) {int m, n; // dp[m][n] m个苹果放入n个盘子cin >> m >> n;memset(dp, 0, 13 * 13);for (int i = 0; i <= m; i++) {dp[i][1] = 1; // 一个盘子只有1种方法放苹果}for (int i = 1; i <= n; i++) { // 至少一个盘子 从1开始遍历dp[0][i] = 1; // 0/1个苹果只有一种dp[1][i] = 1;}for (int i = 2; i <= m; i++) {for (int j = 2; j <= n; j++) {if (i >= j) { // 苹果大于等于盘子dp[i][j] = dp[i][j - 1] + dp[i - j][j];}else { // 苹果数量小于盘子 取决苹果dp[i][j] = dp[i][i];}}}cout << dp[m][n] << endl;}return 0;
}

2. 最长公共子序列长度

#include <iostream>
#include <algorithm>
using namespace std;int dp[1010][1010];int main() {string str1, str2;cin >> str1 >> str2;int m = str1.size(), n = str2.size();// dp[i][j] str1的前i个元素 str2的前j个元素的最大公共长度for (int i = 0; i <= m; i++) {dp[i][0] = 0;}for (int i = 0; i <= n; i++) {dp[0][i] = 0;}for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i-1] == str2[j-1])// str1[0, i-1] str2[0, j-1] ij元素取决于前0~i-1  0~j-1个元素dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = max(dp[i][j-1], dp[i-1][j]);}}cout << dp[m][n] << endl;return 0;
}

3. 最长连续公共序列 不含数字 只统计小写字母

#include <iostream>
#include <string>
#include <algorithm>using namespace std;int dp[1010][1010];
int main() {string str1, str2;cin >> str1 >> str2;int m = str1.size(), n = str2.size();// dp[i][j] str1前i个元素和str2前j个元素的最长连续字串长度for (int i = 0; i <= m; i++) dp[i][0] = 0;for (int i = 0; i <= n; i++)dp[0][i] = 0;int curmax = 0; // 记录当前最长连续子串长度for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i - 1] >= 'a' && str1[i - 1] <= 'z' && str1[i - 1] == str2[j - 1]) {// 右边缘相等为条件dp[i][j] = dp[i - 1][j - 1] + 1;curmax = max(dp[i][j], curmax);}elsedp[i][j] = 0;}}cout << curmax << endl;return 0;
}

4. 最大连续序列和

#include <iostream>
#include <algorithm>using namespace std;
int dp[1000];
int arr[1000];int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];dp[1] = arr[0];int curmax = dp[1];for (int i = 2; i <= n; i++) {if (dp[i - 1] > 0) // 前i-1个元素的连续序列和dp[i] = dp[i - 1] + arr[i-1]; // dp[i]代表前i个元素的连续序列和 arr[i-1] 代表第i个元素elsedp[i] = arr[i-1];curmax = max(dp[i], curmax);}cout << curmax << endl;return 0;
}

5. 最长递增子序列长度（非连续）

#include <iostream>
#include <algorithm>
using namespace std;const int MAXN = 1000 + 10;
int arr[MAXN];
int dp[MAXN];
int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];for (int i = 1; i <= n; i++) // 初始化 dp[i]都是1dp[i] = 1;int curmax = dp[1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) { // 第i个元素 与 前面的第j个元素比较 [i.....j] if (arr[i - 1] > arr[j - 1]) { // 第i个元素 > 第j个元素dp[i] = max(dp[j] + 1, dp[i]); // 刷新dp[i]的值curmax = max(dp[i], curmax);}}}cout << curmax << endl;return 0;
}

6. 01背包

#include <iostream>
#include <algorithm>
using namespace std;int dp[5001][202]; // 200个元素下标
int main() {int m, n; //01背包重量m n组数据 m[1, 5000]int w[202] = { 0 }, v[202] = { 0 }; // 每个物品的重量以及价值 [1, 200]cin >> m >> n;for (int i = 0; i < n; i++) // 输入n个物品的信息cin >> w[i] >> v[i];for (int i = 0; i <= m; i++) // 没有物品 价值0dp[i][0] = 0;for (int i = 0; i < n; i++) // 背包没有容纳重量 价值0dp[0][i] = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (i < w[j - 1]) {// 如果背包剩余容量无法容纳第j件物品 返回前j-1物品的【value】dp[i][j] = dp[i][j - 1]; // dp[i][j-1] 代表i重量，前j-1件物品的价值 实际物品下标[0, j-2]}else {int remainM = i - w[j - 1]; // dp[remainM][j - 1] 买了第y件商品后剩下的钱用于买剩下的y-1件商品dp[i][j] = max(dp[i][j - 1], dp[remainM][j - 1] + v[j - 1]); // 前j-1的结果+第j件物品的价值// 不买第y件商品的价值 与 买第y件商品之后的价值对比 。。。剩下的钱不一定买的起前面j-1件商品}}}cout << dp[m][n] << endl;return 0;
}

6. 回溯

1. 组合

#include <iostream>
#include <vector>
using namespace std;
int choosen[100];
vector<int> res;void backTracking(int n, int k, int startIndex) {if (res.size() == k) {for (int i = 0; i < res.size(); i++)cout << res[i] << " ";cout << endl;return;}for (int i = startIndex; i <= n; i++) {if (choosen[i])continue;choosen[i] = 1;res.push_back(i);backTracking(n, k, i + 1); // 第三个参数：0 全排列, i+1递增集合（元素不可重复）res.pop_back();choosen[i] = 0;}
}int main() {int n;cin >> n;backTracking(n, 2, 1);return 0;
}

2. 全排列输出字母

#include <iostream>
#include <vector>
using namespace std;bool choosen[100];
vector<char> res;void backTracking(string str, int n, int startIdx) {if (res.size() == n) {for (int i = 0; i < res.size(); i++) cout << res[i];cout << endl;}for (int i = startIdx; i < n; i++) {if (choosen[i])continue;choosen[i] = true;res.push_back(str[i]);backTracking(str, n, 0);res.pop_back();choosen[i] = false;}return;
}int main() {string str;cin >> str;backTracking(str, str.size(), 0);return 0;
}

2024真题

1. 直接插入排序 第k趟结果

#include <iostream>
using namespace std;const int MAXN = 1010;
int arr[MAXN];void InsertSort(int arr[], int &n, int k) { // 输出插入排序第k趟排序for (int i = 1; i < n && i<k; i++) {int temp = arr[i]; // 当前待排元素int j;for (j = i - 1; j >= 0; j--) { // 对[0, i-1]元素排序if (arr[j] > temp) // 后移arr[j + 1] = arr[j];elsebreak;}arr[j + 1] = temp;}for (int i = 0; i < n; i++)cout << arr[i] << " ";cout << endl;return;
}
int main() {int k, x;cin >> k;int n = 0;while (cin >> x)arr[n++] = x;InsertSort(arr, n, k);return 0;
}

2. 最大连续序列和

#include <iostream>
#include <algorithm>
using namespace std;int arr[1010];
int dp[1010];
int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];dp[1] = arr[0]; // dp[i] 前i个数的序列和int curmax = dp[1];for (int i = 2; i <=n; i++) { // 处理dp[n]if (dp[i - 1] <= 0)dp[i] = arr[i - 1]; // arr[i-1] 指代第i个元素 arr范围[0, i-1] // 前i个元素elsedp[i] = dp[i - 1] + arr[i - 1];curmax = max(curmax, dp[i]);}cout << curmax << endl;return 0;}

3. 动态规划-多组数据，输入餐馆位置，餐馆需指定间隔距离， 餐馆利润，计算最大利润

#include <iostream>
using namespace std;int main() {int n; // n组数据cin >> n;int p[101]; // 位置int v[101]; // 利润int dp[102]; // dp[i] 前i个元素的结果while (n--) {int posN, dis; // 店铺数 间隔距离cin >> posN >> dis;for (int i = 0; i < posN; i++) // 输入店铺位置cin >> p[i]; for (int i = 0; i < posN; i++) // 输入店铺对应位置的利润cin >> v[i]; dp[1] = v[0]; // 只有一个餐馆int curmax = dp[1];for (int i = 2; i <= posN; i++) {if (p[i - 1] - p[i - 2] >= dis)  // 第i个地点与前一个地点相差距离需要满足disdp[i] = dp[i - 1] + v[i - 1];else dp[i] = max(dp[i-1], v[i-1]);curmax = max(dp[i], curmax);}cout << curmax << endl;}return 0;
}

4. 找到第k个素数

#include <iostream>
#include <vector>using namespace std;const int MAXN = 1010;
bool isPrime[MAXN]; // 记录0-1000 是否是素数
vector<int> prime; // 存入素数void init() {for (int i = 0; i < MAXN; i++)isPrime[i] = true;isPrime[0] = false;isPrime[1] = false;for (int i = 2; i < MAXN; i++) {if (isPrime[i] == false)continue;prime.push_back(i);for (int k = i * i; k < MAXN; k += i) // 质数的倍数 不是质数isPrime[k] = false;}
}int main() {init();int n;cin >> n;if (isPrime[n]) {cout << true << endl;}else {for (int i = n + 1; i < MAXN; i++)if (isPrime[i]) {cout << i << endl;break;}	}return 0;
}

5.中缀表达式转后缀表达式

#include <iostream>
#include <string>
#include <vector>
using namespace std;bool isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}bool isAbleOut(vector<char> stackArr, char c) {int tail = stackArr.size()-1;if (c == '(')return false;if (c == ')' && stackArr[tail] != '(')return true;if (stackArr[tail] != '(') if (c == '+' || c == '-')return true;else if (stackArr[tail] == '*' || stackArr[tail] == '/')return true;return false;
}int main() {string str;cin >> str;vector<char> stackArr;string res;for (int i = 0; i < str.size(); i++) {if (isOperator(str[i]) == false)res += str[i];else {while (stackArr.size() && isAbleOut(stackArr, str[i])) {int tail = stackArr.size()-1;res += stackArr[tail];stackArr.pop_back();}	if (str[i] != ')')stackArr.push_back(str[i]);else// 右括号时 直到结束时， stack需要弹出(stackArr.pop_back();}}for (int i = stackArr.size() - 1; i >= 0; i--)res += stackArr[i];cout << res << endl;return 0;
}