C++算法程序填空题（CSP-J/S考试专项练习）

以下是100道针对CSP-J/S考试的C++算法程序填空题，涵盖了常见的算法和数据结构知识点。

1. 基础语法与结构

题目 1: 计算两个整数的和

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;  // 填空：计算a和b的和
    return 0;}

题目 2: 判断奇偶数

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int n;
    cin >> n;
    if (n % 2 == 0) {  // 填空：判断n是否为偶数
        cout << "Even" << endl;
    } else {
        cout << "Odd" << endl;
    }
    return 0;}

题目 3: 求三个数的最大值

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int max = a;
    if (b > max) max = b;  // 填空：判断b是否大于当前最大值
    if (c > max) max = c;  // 填空：判断c是否大于当前最大值
    cout << max << endl;
    return 0;}

题目 4: 计算阶乘

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int n;
    cin >> n;
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;  // 填空：计算阶乘
    }
    cout << result << endl;
    return 0;}

题目 5: 判断素数

cpp

复制

下载

#include <iostream>#include <cmath>using namespace std;int main() {
    int n;
    cin >> n;
    bool isPrime = true;
    if (n <= 1) {
        isPrime = false;
    } else {
        for (int i = 2; i <= sqrt(n); i++) {  // 填空：循环终止条件
            if (n % i == 0) {
                isPrime = false;
                break;
            }
        }
    }
    cout << (isPrime ? "Yes" : "No") << endl;
    return 0;}

2. 数组与字符串

题目 6: 数组元素求和

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int n;
    cin >> n;
    int arr[n], sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        sum += arr[i];  // 填空：累加数组元素
    }
    cout << sum << endl;
    return 0;}

题目 7: 查找数组最大值

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int n;
    cin >> n;
    int arr[n], max;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (i == 0 || arr[i] > max) {  // 填空：判断当前元素是否大于最大值
            max = arr[i];
        }
    }
    cout << max << endl;
    return 0;}

题目 8: 数组逆序输出

cpp

复制

下载

#include <iostream>using namespace std;int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = n - 1; i >= 0; i--) {  // 填空：逆序输出起始索引
        cout << arr[i] << " ";
    }
    return 0;}

题目 9: 统计字符出现次数

cpp

复制

下载

#include <iostream>#include <string>using namespace std;int main() {
    string s;
    char target;
    cin >> s >> target;
    int count = 0;
    for (char c : s) {
        if (c == target) {  // 填空：判断字符是否匹配目标
            count++;
        }
    }
    cout << count << endl;
    return 0;}

题目 10: 字符串反转

cpp

复制

下载

#include <iostream>#include <string>#include <algorithm>using namespace std;int main() {
    string s;
    cin >> s;
    reverse(s.begin(), s.end());  // 填空：反转字符串
    cout << s << endl;
    return 0;}

3. 排序算法

题目 11: 冒泡排序

cpp

复制

下载

#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]) {  // 填空：比较相邻元素
                swap(arr[j], arr[j+1]);
            }
        }
    }}int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    bubbleSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;}

题目 12: 选择排序

cpp

复制

下载

#include <iostream>using namespace std;void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {  // 填空：找到最小元素的索引
                min_idx = j;
            }
        }
        swap(arr[i], arr[min_idx]);
    }}int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;}

题目 13: 插入排序

cpp

复制

下载

#include <iostream>using namespace std;void insertionSort(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 main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;}

题目 14: 快速排序分区函数

cpp

复制

下载

#include <iostream>using namespace std;int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {  // 填空：元素与基准比较
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i+1;}void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }}int main() {
    int n;
    cin >> n;
    int arr[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] << " ";
    return 0;}

题目 15: 归并排序合并函数

cpp

复制

下载

#include <iostream>using namespace std;void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {  // 填空：比较左右子数组元素
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];}void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }}int main() {
    int n;
    cin >> n;
    int arr[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] << " ";
    return 0;}

4. 搜索算法

题目 16: 线性搜索

cpp

复制

下载

#include <iostream>using namespace std;int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {  // 填空：找到目标元素
            return i;
        }
    }
    return -1;}int main() {
    int n, x;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cin >> x;
    int result = linearSearch(arr, n, x);
    cout << result << endl;
    return 0;}

题目 17: 二分查找

cpp

复制

下载

#include <iostream>using namespace std;int binarySearch(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) {  // 填空：找到目标元素
            return mid;
        }
        if (arr[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return -1;}int main() {
    int n, x;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cin >> x;
    int result = binarySearch(arr, 0, n-1, x);
    cout << result << endl;
    return 0;}

题目 18: 深度优先搜索(DFS)

cpp

复制

下载

#include <iostream>#include <vector>using namespace std;void DFS(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {  // 填空：判断邻居节点是否已访问
            DFS(neighbor, graph, visited);
        }
    }}int main() {
    int n, e;
    cin >> n >> e;
    vector<vector<int>> graph(n);
    vector<bool> visited(n, false);
    
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    DFS(0, graph, visited);
    return 0;}

题目 19: 广度优先搜索(BFS)

cpp

复制

下载

#include <iostream>#include <queue>#include <vector>using namespace std;void BFS(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    queue<int> q;
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {  // 填空：判断邻居节点是否已访问
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }}int main() {
    int n, e;
    cin >> n >> e;
    vector<vector<int>> graph(n);
    vector<bool> visited(n, false);
    
    for (int i = 0; i < e; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    BFS(0, graph, visited);
    return 0;}

题目 20: 回溯算法 - N皇后问题

cpp

复制

下载

#include <iostream>#include <vector>using namespace std;bool isSafe(vector<vector<int>>& board, int row, int col, int n) {
    for (int i = 0; i < col; i++) {
        if (board[row][i]) return false;
    }
    
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j]) return false;
    }
    
    for (int i = row, j = col; i < n && j >= 0; i++, j--) {
        if (board[i][j]) return false;  // 填空：检查右下对角线
    }
    
    return true;}bool solveNQUtil(vector<vector<int>>& board, int col, int n) {
    if (col >= n) return true;
    
    for (int i = 0; i < n; i++) {
        if (isSafe(board, i, col, n)) {
            board[i][col] = 1;
            if (solveNQUtil(board, col+1, n)) return true;
            board[i][col] = 0;
        }
    }
    return false;}int main() {
    int n;
    cin >> n;
    vector<vector<int>> board(n, vector<int>(n, 0));
    
    if (solveNQUtil(board, 0, n)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No solution exists" << endl;
    }
    return 0;}

5. 动态规划

题目 21: 斐波那契数列

cpp

复制

下载

#include <iostream>using namespace std;int fibonacci(int n) {
    if (n <= 1) return n;
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // 填空：计算斐波那契数列
    }
    return dp[n];}int main() {
    int n;
    cin >> n;
    cout << fibonacci(n) << endl;
    return 0;}

题目 22: 最长递增子序列

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;int lis(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[i] < dp[j] + 1) {  // 填空：判断递增条件
                dp[i] = dp[j] + 1;
            }
        }
    }
    return *max_element(dp, dp+n);}int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << lis(arr, n) << endl;
    return 0;}

题目 23: 0-1背包问题

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;int knapSack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i-1] <= w) {
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);  // 填空：状态转移方程
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];}int main() {
    int n, W;
    cin >> n >> W;
    int val[n], wt[n];
    for (int i = 0; i < n; i++) cin >> val[i];
    for (int i = 0; i < n; i++) cin >> wt[i];
    cout << knapSack(W, wt, val, n) << endl;
    return 0;}

题目 24: 最长公共子序列

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;int lcs(string X, string Y, int m, int n) {
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (X[i-1] == Y[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;  // 填空：状态转移方程
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];}int main() {
    string X, Y;
    cin >> X >> Y;
    cout << lcs(X, Y, X.length(), Y.length()) << endl;
    return 0;}

题目 25: 矩阵链乘法

cpp

复制

下载

#include <iostream>#include <climits>using namespace std;int matrixChainOrder(int p[], int n) {
    int dp[n][n];
    for (int i = 1; i < n; i++) {
        dp[i][i] = 0;
    }
    for (int L = 2; L < n; L++) {
        for (int i = 1; i < n-L+1; i++) {
            int j = i+L-1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int q = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < dp[i][j]) {  // 填空：更新最小值
                    dp[i][j] = q;
                }
            }
        }
    }
    return dp[1][n-1];}int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << matrixChainOrder(arr, n) << endl;
    return 0;}

6. 图算法

题目 26: Dijkstra算法

cpp

复制

下载

#include <iostream>#include <climits>using namespace std;int minDistance(int dist[], bool sptSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;}void dijkstra(int graph[][100], int src, int V) {
    int dist[V];
    bool sptSet[V];
    
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    
    dist[src] = 0;
    
    for (int count = 0; count < V-1; count++) {
        int u = minDistance(dist, sptSet, V);
        sptSet[u] = true;
        
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                && dist[u] + graph[u][v] < dist[v]) {  // 填空：更新距离条件
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    
    for (int i = 0; i < V; i++) {
        cout << i << " : " << dist[i] << endl;
    }}int main() {
    int V;
    cin >> V;
    int graph[100][100];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> graph[i][j];
        }
    }
    dijkstra(graph, 0, V);
    return 0;}

题目 27: Floyd-Warshall算法

cpp

复制

下载

#include <iostream>using namespace std;#define INF 99999void floydWarshall(int graph[][100], int V) {
    int dist[V][V];
    
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }
    
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {  // 填空：更新最短路径
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << endl;
    }}int main() {
    int V;
    cin >> V;
    int graph[100][100];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> graph[i][j];
        }
    }
    floydWarshall(graph, V);
    return 0;}

题目 28: Prim算法

cpp

复制

下载

#include <iostream>#include <climits>using namespace std;int minKey(int key[], bool mstSet[], int V) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;}void primMST(int graph[][100], int V) {
    int parent[V];
    int key[V];
    bool mstSet[V];
    
    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }
    
    key[0] = 0;
    parent[0] = -1;
    
    for (int count = 0; count < V-1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
        
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {  // 填空：更新键值条件
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    
    for (int i = 1; i < V; i++) {
        cout << parent[i] << " - " << i << " : " << graph[i][parent[i]] << endl;
    }}int main() {
    int V;
    cin >> V;
    int graph[100][100];
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cin >> graph[i][j];
        }
    }
    primMST(graph, V);
    return 0;}

题目 29: Kruskal算法

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;struct Edge {
    int src, dest, weight;};bool compare(Edge a, Edge b) {
    return a.weight < b.weight;  // 填空：比较边权重}int find(int parent[], int i) {
    if (parent[i] == i) return i;
    return find(parent, parent[i]);}void unionSets(int parent[], int x, int y) {
    parent[x] = y;}void kruskalMST(Edge edges[], int V, int E) {
    sort(edges, edges+E, compare);
    
    int parent[V];
    for (int i = 0; i < V; i++) parent[i] = i;
    
    Edge result[V];
    int e = 0, i = 0;
    
    while (e < V-1 && i < E) {
        Edge next_edge = edges[i++];
        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);
        
        if (x != y) {
            result[e++] = next_edge;
            unionSets(parent, x, y);
        }
    }
    
    for (i = 0; i < e; i++) {
        cout << result[i].src << " - " << result[i].dest << " : " << result[i].weight << endl;
    }}int main() {
    int V, E;
    cin >> V >> E;
    Edge edges[E];
    for (int i = 0; i < E; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }
    kruskalMST(edges, V, E);
    return 0;}

题目 30: 拓扑排序

cpp

复制

下载

#include <iostream>#include <list>#include <stack>using namespace std;class Graph {
    int V;
    list<int>* adj;
    
    void topologicalSortUtil(int v, bool visited[], stack<int>& Stack) {
        visited[v] = true;
        for (auto i = adj[v].begin(); i != adj[v].end(); i++) {
            if (!visited[*i]) {
                topologicalSortUtil(*i, visited, Stack);
            }
        }
        Stack.push(v);  // 填空：将当前顶点入栈
    }
    public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    
    void topologicalSort() {
        stack<int> Stack;
        bool* visited = new bool[V];
        for (int i = 0; i < V; i++) visited[i] = false;
        
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                topologicalSortUtil(i, visited, Stack);
            }
        }
        
        while (!Stack.empty()) {
            cout << Stack.top() << " ";
            Stack.pop();
        }
    }};int main() {
    int V, E;
    cin >> V >> E;
    Graph g(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }
    g.topologicalSort();
    return 0;}

7. 数论与组合数学

题目 31: 最大公约数

cpp

复制

下载

#include <iostream>using namespace std;int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);  // 填空：递归计算gcd}int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;}

题目 32: 最小公倍数

cpp

复制

下载

#include <iostream>using namespace std;int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);}int lcm(int a, int b) {
    return (a * b) / gcd(a, b);  // 填空：计算最小公倍数}int main() {
    int a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;}

题目 33: 模幂运算

cpp

复制

下载

#include <iostream>using namespace std;long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;  // 填空：更新base
    }
    return result;}int main() {
    long long base, exp, mod;
    cin >> base >> exp >> mod;
    cout << power(base, exp, mod) << endl;
    return 0;}

题目 34: 组合数计算

cpp

复制

下载

#include <iostream>using namespace std;int nCr(int n, int r) {
    if (r == 0 || r == n) return 1;
    return nCr(n-1, r-1) + nCr(n-1, r);  // 填空：递归计算组合数}int main() {
    int n, r;
    cin >> n >> r;
    cout << nCr(n, r) << endl;
    return 0;}

题目 35: 素数筛法

cpp

复制

下载

#include <iostream>#include <vector>using namespace std;void sieveOfEratosthenes(int n) {
    vector<bool> prime(n+1, true);
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;  // 填空：标记非素数
            }
        }
    }
    
    for (int p = 2; p <= n; p++) {
        if (prime[p]) cout << p << " ";
    }}int main() {
    int n;
    cin >> n;
    sieveOfEratosthenes(n);
    return 0;}

8. 数据结构

题目 36: 栈的实现

cpp

复制

下载

#include <iostream>#define MAX 1000using namespace std;class Stack {
    int top;
    public:
    int a[MAX];
    Stack() { top = -1; }
    bool push(int x);
    int pop();
    bool isEmpty();};bool Stack::push(int x) {
    if (top >= MAX-1) {
        cout << "Stack Overflow";
        return false;
    } else {
        a[++top] = x;  // 填空：压入栈顶
        return true;
    }}int Stack::pop() {
    if (top < 0) {
        cout << "Stack Underflow";
        return 0;
    } else {
        int x = a[top--];  // 填空：弹出栈顶
        return x;
    }}bool Stack::isEmpty() {
    return top < 0;}int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << " Popped from stack\n";
    return 0;}

题目 37: 队列的实现

cpp

复制

下载

#include <iostream>#define MAX 1000using namespace std;class Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
    public:
    Queue(unsigned capacity) {
        this->capacity = capacity;
        front = size = 0;
        rear = capacity - 1;
        array = new int[capacity];
    }
    
    bool isFull();
    bool isEmpty();
    void enqueue(int item);
    int dequeue();};bool Queue::isFull() {
    return size == capacity;}bool Queue::isEmpty() {
    return size == 0;}void Queue::enqueue(int item) {
    if (isFull()) return;
    rear = (rear + 1) % capacity;
    array[rear] = item;
    size++;}int Queue::dequeue() {
    if (isEmpty()) return INT_MIN;
    int item = array[front];
    front = (front + 1) % capacity;  // 填空：更新队首指针
    size--;
    return item;}int main() {
    Queue q(1000);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << q.dequeue() << " dequeued from queue\n";
    return 0;}

题目 38: 链表节点定义

cpp

复制

下载

#include <iostream>using namespace std;class Node {public:
    int data;
    Node* next;
    Node(int data) {
        this->data = data;
        next = nullptr;  // 填空：初始化next指针
    }};void printList(Node* n) {
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }}int main() {
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    
    head->next = second;
    second->next = third;
    
    printList(head);
    return 0;}

题目 39: 二叉树节点定义

cpp

复制

下载

#include <iostream>using namespace std;class Node {public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = nullptr;  // 填空：初始化左右子树
        right = nullptr;
    }};void printInorder(Node* node) {
    if (node == NULL) return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);}int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    printInorder(root);
    return 0;}

题目 40: 二叉搜索树插入

cpp

复制

下载

#include <iostream>using namespace std;class Node {public:
    int key;
    Node *left, *right;
    Node(int item) {
        key = item;
        left = right = NULL;
    }};Node* insert(Node* node, int key) {
    if (node == NULL) return new Node(key);
    
    if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);  // 填空：递归插入右子树
    }
    
    return node;}void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }}int main() {
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    
    inorder(root);
    return 0;}

9. 贪心算法

题目 41: 活动选择问题

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;struct Activity {
    int start, finish;};bool activityCompare(Activity s1, Activity s2) {
    return s1.finish < s2.finish;  // 填空：按结束时间排序}void printMaxActivities(Activity arr[], int n) {
    sort(arr, arr+n, activityCompare);
    
    int i = 0;
    cout << "Selected activities: " << arr[i].start << ", " << arr[i].finish << endl;
    
    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].finish) {  // 填空：判断活动是否兼容
            cout << arr[j].start << ", " << arr[j].finish << endl;
            i = j;
        }
    }}int main() {
    Activity arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
    int n = sizeof(arr)/sizeof(arr[0]);
    printMaxActivities(arr, n);
    return 0;}

题目 42: 硬币找零问题

cpp

复制

下载

#include <iostream>#include <vector>#include <algorithm>using namespace std;vector<int> coinChange(int coins[], int n, int amount) {
    sort(coins, coins+n, greater<int>());
    vector<int> result;
    
    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {  // 填空：使用当前硬币的条件
            amount -= coins[i];
            result.push_back(coins[i]);
        }
    }
    return result;}int main() {
    int coins[] = {1, 2, 5, 10, 20, 50, 100, 500, 1000};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 93;
    vector<int> result = coinChange(coins, n, amount);
    
    for (int coin : result) {
        cout << coin << " ";
    }
    return 0;}

题目 43: 霍夫曼编码

cpp

复制

下载

#include <iostream>#include <queue>#include <vector>using namespace std;struct Node {
    char data;
    unsigned freq;
    Node *left, *right;
    Node(char data, unsigned freq) {
        left = right = NULL;
        this->data = data;
        this->freq = freq;
    }};struct compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;  // 填空：比较频率
    }};void printCodes(Node* root, string str) {
    if (!root) return;
    if (root->data != '$') {
        cout << root->data << ": " << str << "\n";
    }
    printCodes(root->left, str + "0");
    printCodes(root->right, str + "1");}void HuffmanCodes(char data[], int freq[], int size) {
    priority_queue<Node*, vector<Node*>, compare> minHeap;
    
    for (int i = 0; i < size; i++) {
        minHeap.push(new Node(data[i], freq[i]));
    }
    
    while (minHeap.size() != 1) {
        Node *left = minHeap.top(); minHeap.pop();
        Node *right = minHeap.top(); minHeap.pop();
        
        Node *top = new Node('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }
    
    printCodes(minHeap.top(), "");}int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(arr)/sizeof(arr[0]);
    HuffmanCodes(arr, freq, size);
    return 0;}

题目 44: 分数背包问题

cpp

复制

下载

#include <iostream>#include <algorithm>using namespace std;struct Item {
    int value, weight;
    Item(int value, int weight) : value(value), weight(weight) {}};bool cmp(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;  // 填空：按价值密度排序}double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr+n, cmp);
    
    int curWeight = 0;
    double finalValue = 0.0;
    
    for (int i = 0; i < n; i++) {
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalValue += arr[i].value;
        } else {
            int remain = W - curWeight;
            finalValue += arr[i].value * ((double)remain / arr[i].weight);
            break;
        }
    }
    
    return finalValue;}int main() {
    int W = 50;
    Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Maximum value: " << fractionalKnapsack(W, arr, n);
    return 0;}

题目 45: 任务调度问题

cpp

复制

下载

#include <iostream>#include <algorithm>#include <vector>using namespace std;struct Task {
    int id, deadline, profit;};bool comparison(Task a, Task b) {
    return a.profit > b.profit;  // 填空：按利润降序排序}void scheduleTasks(Task arr[], int n) {
    sort(arr, arr+n, comparison);
    
    vector<bool> slot(n, false);
    vector<int> result(n, -1);
    
    for (int i = 0; i < n; i++) {
        for (int j = min(n, arr[i].deadline)-1; j >= 0; j--) {
            if (!slot[j]) {
                result[j] = i;
                slot[j] = true;
                break;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (slot[i]) {
            cout << arr[result[i]].id << " ";
        }
    }}int main() {
    Task arr[] = {{1, 2, 100}, {2, 1, 19}, {3, 2, 27}, {4, 1, 25}, {5, 3, 15}};
    int n = sizeof(arr)/sizeof(arr[0]);
    scheduleTasks(arr, n);
    return 0;}

10. 分治算法

题目 46: 归并排序

cpp

复制

下载

#include <iostream>using namespace std;void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    
    int L[n1], R[n2];
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
        
    int i = 0, j = 0, k = l;
    
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];  // 填空：合并右半部分
            j++;
        }
        k++;
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];}void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }}int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    mergeSort(arr, 0, n-1);
    
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;}

题目 47: 快速排序

cpp

复制

下载

#include <iostream>using namespace std;int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i+1;}void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);  // 填空：递归排序左半部分
        quickSort(arr, pi+1, high);
    }}int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    quickSort(arr, 0, n-1);
    
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;}

题目 48: 二分查找

cpp

复制

下载

#include <iostream>using namespace std;int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        
        if (arr[mid] == x)
            return mid;
            
        if (arr[mid] > x)
            return binarySearch(arr, l, mid-1, x);
            
        return binarySearch(arr, mid+1, r, x);  // 填空：递归搜索右半部分
    }
    return -1;}int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n-1, x);
    cout << "Element found at index " << result;
    return 0;}

题目 49: 最大子数组和

cpp

复制

下载

#include <iostream>#include <climits>using namespace std;int maxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }
    
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = m+1; i <= h; i++) {
        sum += arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }
    
    return left_sum + right_sum;  // 填空：返回跨越中点的最大和}int maxSubArraySum(int arr[], int l, int h) {
    if (l == h) return arr[l];
    
    int m = (l + h) / 2;
    
    return max(max(maxSubArraySum(arr, l, m),
                maxSubArraySum(arr, m+1, h)),
                maxCrossingSum(arr, l, m, h));}int main() {
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n-1);
    cout << "Maximum subarray sum is " << max_sum;
    return 0;}

题目 50: 矩阵乘法

cpp

复制

下载

#include <iostream>using namespace std;void multiply(int A[][2], int B[][2], int C[][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            C[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                C[i][j] += A[i][k] * B[k][j];  // 填空：矩阵乘法计算
            }
        }
    }}int main() {
    int A[2][2] = {{1, 2}, {3, 4}};
    int B[2][2] = {{5, 6}, {7, 8}};
    int C[2][2];
    
    multiply(A, B, C);
    
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            cout << C[i][j] << " ";
        }
        cout << endl;
    }
    return 0;}

• 转载请注明出处：英飞凌(Infineon)公司官方授权中国代理,北京晶川电子技术发展有限责任公司
• 本文地址：https://oliyun.com/infineon-mcu/156.html