14天速成PAT-BASIC基础知识！

两周关于PAT的基础学习计划。

Day 1: 基本语法和输入输出

知识点

数据类型（int, long, float, double, char）变量声明和初始化输入输出函数（scanf, printf）控制结构（if-else, switch, for, while, do-while）

代码练习

编写一个程序，读取两个整数并输出它们的和。编写一个程序，根据用户输入的成绩判断是否及格（60分以上）。编写一个程序，使用for循环打印1到100的所有整数。 #include <stdio.h> int main() { int a, b; scanf("%d %d", &a, &b); printf("Sum: %d\n", a + b); return 0; } // 判断成绩是否及格 #include <stdio.h> int main() { int score; scanf("%d", &score); if (score >= 60) { printf("Pass\n"); } else { printf("Fail\n"); } return 0; } // 打印1到100 #include <stdio.h> int main() { for (int i = 1; i <= 100; ++i) { printf("%d ", i); } return 0; } Day 2: 数组和字符串

知识点

一维数组的声明、初始化和访问字符串的基本操作（strlen, strcpy, strcat, strcmp, strstr）

代码练习

编写一个程序，读取一个数组并输出其最大值。编写一个程序，读取两个字符串并比较它们是否相等。编写一个程序，将两个字符串连接起来并输出结果。 #include <stdio.h> #include <string.h> int main() { int arr[5]; for (int i = 0; i < 5; ++i) { scanf("%d", &arr[i]); } int max = arr[0]; for (int i = 1; i < 5; ++i) { if (arr[i] > max) { max = arr[i]; } } printf("Max: %d\n", max); return 0; } // 比较两个字符串 #include <stdio.h> #include <string.h> int main() { char str1[100], str2[100]; scanf("%s %s", str1, str2); if (strcmp(str1, str2) == 0) { printf("Equal\n"); } else { printf("Not Equal\n"); } return 0; } // 连接两个字符串 #include <stdio.h> #include <string.h> int main() { char str1[100], str2[100], result[200]; scanf("%s %s", str1, str2); strcpy(result, str1); strcat(result, str2); printf("Result: %s\n", result); return 0; } Day 3: 函数和指针

知识点

函数的定义和调用参数传递（值传递和指针传递）指针的基本概念和用法

代码练习

编写一个函数，计算两个整数的乘积并返回结果。编写一个函数，交换两个整数的值（使用指针）。编写一个函数，查找数组中的最大值（使用指针）。 #include <stdio.h> int multiply(int a, int b) { return a * b; } void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int find_max(int *arr, int size) { int max = arr[0]; for (int i = 1; i < size; ++i) { if (arr[i] > max) { max = arr[i]; } } return max; } int main() { int a = 5, b = 10; printf("Product: %d\n", multiply(a, b)); swap(&a, &b); printf("After swap: a = %d, b = %d\n", a, b); int arr[] = {1, 2, 3, 4, 5}; int size = sizeof(arr) / sizeof(arr[0]); printf("Max in array: %d\n", find_max(arr, size)); return 0; } Day 4: 结构体和文件操作

知识点

结构体的定义和使用文件的打开、读写和关闭（fopen, fscanf, fprintf, fclose）

代码练习

定义一个学生结构体，包含姓名和成绩，并编写一个程序读取多个学生的信息并输出。编写一个程序，从文件中读取数据并处理。 #include <stdio.h> #include <string.h> struct Student { char name[50]; int score; }; void read_students(struct Student students[], int n) { for (int i = 0; i < n; ++i) { scanf("%s %d", students[i].name, &students[i].score); } } void print_students(struct Student students[], int n) { for (int i = 0; i < n; ++i) { printf("Name: %s, Score: %d\n", students[i].name, students[i].score); } } int main() { struct Student students[3]; read_students(students, 3); print_students(students, 3); return 0; } // 从文件中读取数据 #include <stdio.h> int main() { FILE *file = fopen("data.txt", "r"); if (file == NULL) { printf("File not found!\n"); return 1; } int num; while (fscanf(file, "%d", &num) != EOF) { printf("%d\n", num); } fclose(file); return 0; } Day 5: 动态内存分配

知识点

malloc, calloc, realloc, free动态数组的创建和管理

代码练习

编写一个程序，动态分配一个数组并读取用户输入的数据。编写一个程序，动态分配一个二维数组并进行基本操作。 #include <stdio.h> #include <stdlib.h> int main() { int n; printf("Enter the number of elements: "); scanf("%d", &n); int *arr = (int *)malloc(n * sizeof(int)); if (arr == NULL) { printf("Memory allocation failed!\n"); return 1; } for (int i = 0; i < n; ++i) { scanf("%d", &arr[i]); } for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); free(arr); return 0; } // 动态分配二维数组 #include <stdio.h> #include <stdlib.h> int main() { int rows, cols; printf("Enter the number of rows and columns: "); scanf("%d %d", &rows, &cols); int **matrix = (int **)malloc(rows * sizeof(int *)); for (int i = 0; i < rows; ++i) { matrix[i] = (int *)malloc(cols * sizeof(int)); } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { scanf("%d", &matrix[i][j]); } } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { printf("%d ", matrix[i][j]); } printf("\n"); } for (int i = 0; i < rows; ++i) { free(matrix[i]); } free(matrix); return 0; } Day 6: 排序算法

知识点

冒泡排序选择排序插入排序快速排序（qsort）

代码练习

实现冒泡排序、选择排序和插入排序。使用qsort对数组进行排序。 #include <stdio.h> #include <stdlib.h> void bubble_sort(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]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } void selection_sort(int arr[], int n) { for (int i = 0; i < n - 1; ++i) { int min_index = i; for (int j = i + 1; j < n; ++j) { if (arr[j] < arr[min_index]) { min_index = j; } } int temp = arr[i]; arr[i] = arr[min_index]; arr[min_index] = temp; } } void insertion_sort(int arr[], int n) { for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; --j; } arr[j + 1] = key; } } int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b); } int main() { int arr[] = {5, 3, 8, 1, 2}; int n = sizeof(arr) / sizeof(arr[0]); // Bubble Sort int arr_bubble[n]; for (int i = 0; i < n; ++i) { arr_bubble[i] = arr[i]; } bubble_sort(arr_bubble, n); printf("Bubble Sort: "); for (int i = 0; i < n; ++i) { printf("%d ", arr_bubble[i]); } printf("\n"); // Selection Sort int arr_selection[n]; for (int i = 0; i < n; ++i) { arr_selection[i] = arr[i]; } selection_sort(arr_selection, n); printf("Selection Sort: "); for (int i = 0; i < n; ++i) { printf("%d ", arr_selection[i]); } printf("\n"); // Insertion Sort int arr_insertion[n]; for (int i = 0; i < n; ++i) { arr_insertion[i] = arr[i]; } insertion_sort(arr_insertion, n); printf("Insertion Sort: "); for (int i = 0; i < n; ++i) { printf("%d ", arr_insertion[i]); } printf("\n"); // Quick Sort int arr_quick[n]; for (int i = 0; i < n; ++i) { arr_quick[i] = arr[i]; } qsort(arr_quick, n, sizeof(int), compare); printf("Quick Sort: "); for (int i = 0; i < n; ++i) { printf("%d ", arr_quick[i]); } printf("\n"); return 0; } Day 7: 递归和回溯

知识点

递归的基本概念回溯算法（八皇后问题、全排列）

代码练习

实现阶乘函数（递归）实现斐波那契数列（递归）解决八皇后问题（回溯） #include <stdio.h> int factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1); } int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n - 1) + fibonacci(n - 2); } int board[8][8]; int is_safe(int row, int col) { for (int i = 0; i < col; ++i) { if (board[row][i]) { return 0; } } for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) { if (board[i][j]) { return 0; } } for (int i = row, j = col; i < 8 && j >= 0; ++i, --j) { if (board[i][j]) { return 0; } } return 1; } int solve_n_queens(int col) { if (col >= 8) { return 1; } for (int i = 0; i < 8; ++i) { if (is_safe(i, col)) { board[i][col] = 1; if (solve_n_queens(col + 1)) { return 1; } board[i][col] = 0; } } return 0; } void print_board() { for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { printf("%d ", board[i][j]); } printf("\n"); } printf("\n"); } int main() { int n = 5; printf("Factorial of %d: %d\n", n, factorial(n)); printf("Fibonacci of %d: %d\n", n, fibonacci(n)); if (solve_n_queens(0)) { print_board(); } else { printf("No solution exists.\n"); } return 0; } Day 8: 数学问题

知识点

素数筛法（埃氏筛法）最大公约数（欧几里得算法）组合数计算

代码练习

实现埃氏筛法求素数实现欧几里得算法求最大公约数计算组合数 #include <stdio.h> #include <stdbool.h> const int MAXN = 1000000; bool is_prime[MAXN + 1]; void sieve() { for (int i = 0; i <= MAXN; ++i) { is_prime[i] = true; } is_prime[0] = is_prime[1] = false; for (int i = 2; i * i <= MAXN; ++i) { if (is_prime[i]) { for (int j = i * i; j <= MAXN; j += i) { is_prime[j] = false; } } } } int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } long long combination(int n, int k) { if (k > n - k) { k = n - k; } long long result = 1; for (int i = 0; i < k; ++i) { result *= (n - i); result /= (i + 1); } return result; } int main() { sieve(); for (int i = 0; i < 20; ++i) { if (is_prime[i]) { printf("%d ", i); } } printf("\n"); int a = 48, b = 18; printf("GCD of %d and %d: %d\n", a, b, gcd(a, b)); int n = 5, k = 3; printf("Combination C(%d, %d): %lld\n", n, k, combination(n, k)); return 0; } Day 9: 字符串处理进阶

知识点

字符串分割（strtok）字符串转换（atoi, itoa）字符串逆序

代码练习

实现字符串分割实现字符串到整数的转换实现字符串逆序 #include <stdio.h> #include <string.h> #include <stdlib.h> void split_string(const char *str, const char *delim, char *result[]) { char *token = strtok((char *)str, delim); int index = 0; while (token != NULL) { result[index++] = token; token = strtok(NULL, delim); } } int string_to_int(const char *str) { int result = 0; int sign = 1; int i = 0; if (str[0] == '-') { sign = -1; i = 1; } for (; str[i] != '\0'; ++i) { result = result * 10 + (str[i] - '0'); } return result * sign; } void reverse_string(char *str) { int len = strlen(str); for (int i = 0; i < len / 2; ++i) { char temp = str[i]; str[i] = str[len - i - 1]; str[len - i - 1] = temp; } } int main() { const char *str = "Hello,World,This,Is,PAT"; char *result[10]; split_string(str, ",", result); for (int i = 0; result[i] != NULL; ++i) { printf("%s\n", result[i]); } const char *num_str = "-12345"; int num = string_to_int(num_str); printf("String to Int: %d\n", num); char str_reverse[] = "PAT"; reverse_string(str_reverse); printf("Reversed String: %s\n", str_reverse); return 0; } Day 10: 模拟题训练

知识点

综合运用前面所学的知识点解决实际问题

代码练习

从PAT Basic历年真题中挑选几个题目进行练习。 // 例题1：统计字母频率 #include <stdio.h> #include <string.h> int main() { char str[1000]; int freq[26] = {0}; scanf("%s", str); for (int i = 0; str[i] != '\0'; ++i) { if (str[i] >= 'a' && str[i] <= 'z') { freq[str[i] - 'a']++; } else if (str[i] >= 'A' && str[i] <= 'Z') { freq[str[i] - 'A']++; } } for (int i = 0; i < 26; ++i) { if (freq[i] > 0) { printf("%c: %d\n", 'a' + i, freq[i]); } } return 0; } // 例题2：矩阵转置 #include <stdio.h> int main() { int rows, cols; scanf("%d %d", &rows, &cols); int matrix[100][100]; for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { scanf("%d", &matrix[i][j]); } } for (int i = 0; i < cols; ++i) { for (int j = 0; j < rows; ++j) { printf("%d ", matrix[j][i]); } printf("\n"); } return 0; } Day 11: 模拟题训练

知识点

继续综合运用前面所学的知识点解决实际问题

代码练习

从PAT Basic历年真题中再挑选几个题目进行练习。 // 例题3：查找子串 #include <stdio.h> #include <string.h> int main() { char str[1000], sub[100]; scanf("%s %s", str, sub); char *pos = strstr(str, sub); if (pos != NULL) { printf("Found at position: %ld\n", pos - str); } else { printf("Not Found\n"); } return 0; } // 例题4：最大子数组和 #include <stdio.h> int max_subarray_sum(int arr[], int n) { int max_so_far = arr[0]; int current_max = arr[0]; for (int i = 1; i < n; ++i) { current_max = (current_max + arr[i] > arr[i]) ? current_max + arr[i] : arr[i]; max_so_far = (max_so_far > current_max) ? max_so_far : current_max; } return max_so_far; } int main() { int n; scanf("%d", &n); int arr[1000]; for (int i = 0; i < n; ++i) { scanf("%d", &arr[i]); } printf("Max Subarray Sum: %d\n", max_subarray_sum(arr, n)); return 0; } Day 12: 模拟题训练

知识点

继续综合运用前面所学的知识点解决实际问题

代码练习

从PAT Basic历年真题中再挑选几个题目进行练习。 // 例题5：字符串压缩 #include <stdio.h> #include <string.h> void compress_string(const char *input, char *output) { int len = strlen(input); int count = 1; int j = 0; for (int i = 0; i < len; ++i) { if (i + 1 < len && input[i] == input[i + 1]) { count++; } else { output[j++] = input[i]; if (count > 1) { sprintf(output + j, "%d", count); j += strlen(output + j); } count = 1; } } output[j] = '\0'; } int main() { char input[1000], output[1000]; scanf("%s", input); compress_string(input, output); printf("Compressed: %s\n", output); return 0; } // 例题6：最长公共子序列 #include <stdio.h> #include <string.h> int lcs_length(const char *X, const char *Y, int m, int n) { int L[m + 1][n + 1]; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (i == 0 || j == 0) { L[i][j] = 0; } else if (X[i - 1] == Y[j - 1]) { L[i][j] = L[i - 1][j - 1] + 1; } else { L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1]; } } } return L[m][n]; } int main() { char X[100], Y[100]; scanf("%s %s", X, Y); int m = strlen(X); int n = strlen(Y); printf("Length of LCS: %d\n", lcs_length(X, Y, m, n)); return 0; } Day 13: 模拟题训练

知识点

继续综合运用前面所学的知识点解决实际问题

代码练习

从PAT Basic历年真题中再挑选几个题目进行练习。 // 例题7：二叉树的层次遍历 #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* create_node(int val) { TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); node->val = val; node->left = NULL; node->right = NULL; return node; } void level_order_traversal(TreeNode *root) { if (root == NULL) { return; } int front = 0, rear = 0; TreeNode *queue[1000]; queue[rear++] = root; while (front < rear) { TreeNode *node = queue[front++]; printf("%d ", node->val); if (node->left != NULL) { queue[rear++] = node->left; } if (node->right != NULL) { queue[rear++] = node->right; } } } int main() { TreeNode *root = create_node(1); root->left = create_node(2); root->right = create_node(3); root->left->left = create_node(4); root->left->right = create_node(5); root->right->left = create_node(6); root->right->right = create_node(7); level_order_traversal(root); return 0; } // 例题8：快速排序 #include <stdio.h> #include <stdlib.h> void quick_sort(int arr[], int low, int high) { if (low < high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; ++j) { if (arr[j] < pivot) { ++i; int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ++i; int temp = arr[i]; arr[i] = arr[high]; arr[high] = temp; quick_sort(arr, low, i - 1); quick_sort(arr, i + 1, high); } } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quick_sort(arr, 0, n - 1); printf("Sorted array: "); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } printf("\n"); return 0; } Day 14: 总结与模拟考试

知识点

复习前两周所学的知识点解决实际问题

代码练习

从PAT Basic历年真题中再挑选几个题目进行练习。模拟一次完整的PAT Basic考试，严格按照考试时间进行。 // 例题9：合并两个有序数组 #include <stdio.h> void merge(int arr1[], int n1, int arr2[], int n2, int merged[]) { int i = 0, j = 0, k = 0; while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) { merged[k++] = arr1[i++]; } else { merged[k++] = arr2[j++]; } } while (i < n1) { merged[k++] = arr1[i++]; } while (j < n2) { merged[k++] = arr2[j++]; } } int main() { int arr1[] = {1, 3, 5, 7}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = {2, 4, 6, 8}; int n2 = sizeof(arr2) / sizeof(arr2[0]); int merged[100]; merge(arr1, n1, arr2, n2, merged); printf("Merged array: "); for (int i = 0; i < n1 + n2; ++i) { printf("%d ", merged[i]); } printf("\n"); return 0; } // 例题10：矩阵旋转 #include <stdio.h> void rotate_matrix(int matrix[100][100], int n) { for (int layer = 0; layer < n / 2; ++layer) { int first = layer; int last = n - 1 - layer; for (int i = first; i < last; ++i) { int offset = i - first; int top = matrix[first][i]; matrix[first][i] = matrix[last - offset][first]; matrix[last - offset][first] = matrix[last][last - offset]; matrix[last][last - offset] = matrix[i][last]; matrix[i][last] = top; } } } int main() { int n; scanf("%d", &n); int matrix[100][100]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { scanf("%d", &matrix[i][j]); } } rotate_matrix(matrix, n); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { printf("%d ", matrix[i][j]); } printf("\n"); } return 0; }