北航計算機考研復試上機真題 2014 年解析（附參考答案與解題思路）

編輯：關於C語言

北航計算機考研復試上機真題 2014 年解析（附參考答案與解題思路）

北京航空航天大學計算機學院考研復試包含上機編程環節，考察數據結構、算法設計、C/C++ 編程能力。本文整理 2014 年真題內容（基於網絡公開回憶版），提供詳細解題思路、參考代碼與複習建議，供備考學長參考。

一、2014 年上機真題回憶（三道編程題）

題目 1：字符串壓縮編碼（基礎字符串處理）

描述：輸入一個僅包含大寫字母的字符串（長度 ≤ 1000），對連續相同字符進行壓縮編碼：連續 n 個相同字符輸出為 字符+n（n>1），單個字符直接輸出字符本身。
示例：AAABCCDDDD → A3BC2D4

// 參考解法
#include 
#include 

int main() {
    char s[1005];
    scanf("%s", s);
    int len = strlen(s);
    for (int i = 0; i < len; ) {
        int j = i;
        while (j < len && s[j] == s[i]) j++;
        int cnt = j - i;
        if (cnt == 1) printf("%c", s[i]);
        else printf("%c%d", s[i], cnt);
        i = j;
    }
    printf("\n");
    return 0;
}

題目 2：矩陣最小路徑和（動態規劃經典）

描述：給定 n×n 矩陣 (n≤100)，從左上角 (0,0) 走到右下角 (n-1,n-1)，每步只能向右或向下，求路徑上數字和的最小值。
示例：輸入 3\n1 3 1\n1 5 1\n4 2 1 → 輸出 7 (路徑 1→3→1→1→1)

// 參考解法：DP 空間優化至 O(n)
#include 
#include 

int main() {
    int n, a[100][100];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &a[i][j]);

    int dp[100];
    for (int j = 0; j < n; ++j) dp[j] = INT_MAX;
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        dp[0] += a[i][0];
        for (int j = 1; j < n; ++j) {
            dp[j] = (dp[j-1] < dp[j] ? dp[j-1] : dp[j]) + a[i][j];
        }
    }
    printf("%d\n", dp[n-1]);
    return 0;
}

題目 3：鏈表就地逆序（指針操作基本功）

描述：輸入單鏈表節點值序列（以 -1 結束），就地逆序鏈表，輸出逆序後序列。要求空間 O(1)，時間 O(n)。
示例：輸入 1 2 3 4 5 -1 → 輸出 5 4 3 2 1

// 參考解法
#include 
#include 

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node* reverse(Node *head) {
    Node *prev = NULL, *curr = head, *next;
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

int main() {
    Node *head = NULL, *tail = NULL;
    int x;
    while (scanf("%d", &x) == 1 && x != -1) {
        Node *p = malloc(sizeof(Node));
        p->val = x; p->next = NULL;
        if (!head) head = tail = p;
        else { tail->next = p; tail = p; }
    }
    head = reverse(head);
    for (Node *p = head; p; p = p->next) {
        printf("%d ", p->val);
    }
    printf("\n");
    return 0;
}

二、考點分析與複習重點

題目	核心考點	難度	鍵鍵技術
字符串壓縮	字符串遍歷、計數、輸出格式控制	⭐	雙指針/單指針跳躍、邊界處理
矩陣最小路徑	動態規劃、狀態轉移、空間優化	⭐⭐	dp[j] = min(dp[j-1], dp[j]) + a[i][j]
鏈表逆序	指針操作、三指針法、內存管理	⭐⭐	prev/curr/next 循環、頭節點更新

三、復試上機備考建議

手寫代碼無 IDE：習慣在紙上/文本編輯器寫完再編譯，熟練 gcc/g++ 命令行編譯調試。
掌握 STL 但不依賴：C++ 可用 vector/string/queue，但核心算法須能手寫 C 版本（面試官可能要求 C）。
輸入輸出健壯：處理多測試用例、行末空格、大數據讀取 (scanf/cin 配合 ios::sync_with_stdio(false))。
邊界測試：空輸入、單元素、最大限制、全相同/全不同數據。
常考模板背誦：鏈表增刪改查/逆序/合併、二叉樹遍歷/構建、堆/棧/隊列手寫、DFS/BFS/拓撲、Dijkstra/Floyd、KMP/Trie、背包/區間 DP、並查集/線段樹。