經典面試題精講：算法、指針、作業系統與網絡核心知識總結

前言

技術面試往往聚焦於計算機科學基礎與工程實踐能力的交集。本文精選 10 道高頻面試題，涵蓋算法設計、位運算技巧、C/C++ 指針與內存模型、作業系統原理、網絡協議等核心領域，提供標準答案與深度解析，助你構建完整知識體系。

題目一：O(N) 時間復雜度找出重複數字

問題：數組 a[N] 存放 1 至 N-1 的數字，其中一個數字重複一次。要求 O(N) 時間找出該數字。

解法：利用輔助數組標記法（空間換時間），或數學求和法（sum(a) - N*(N-1)/2），或位運算異或法（最優空間 O(1)）。

// 標記法 O(N) 時間，O(N) 空間
int find(int a[], int n) {
    int *temp = calloc(n, sizeof(int));
    for (int i = 0; i < n; i++) {
        if (temp[a[i]]) { free(temp); return a[i]; }
        temp[a[i]] = 1;
    }
    free(temp);
    return -1;
}

題目二：一行代碼判斷 2 的冪次

核心結論：(n & (n - 1)) == 0 且 n > 0。

原理：2 的冪次二進制僅有一個 1（如 1000），減 1 後變為全 1（0111），按位與結果為 0。

bool isPowerOfTwo(int n) {
    return n > 0 && ((n & (n - 1)) == 0);
}

題目三：字符串指針與數組的比較陷阱

代碼：

char str1[] = "abc", str2[] = "abc";
const char str3[] = "abc", str4[] = "abc";
const char *str5 = "abc", *str6 = "abc";
char *str7 = "abc", *str8 = "abc"; // C++ 非法，C 警告

結果：0 0 1 1（C++ 編譯器常量合併優化）。

解析：

• 數組名（str1~str4）各自在棧上分配獨立內存，地址不同。
• 指針（str5~str8）指向只讀數據段的同一字面量常量區，地址相同（編譯器優化）。
• 注意：C 語言標準不保證字符串字面量合併，不可依賴此行為。

題目四：指針算術與數組指針進階

代碼：

int a[5] = {1,2,3,4,5};
int *ptr = (int *)(&a + 1);
printf("%d,%d", *(a+1), *(ptr-1)); // 輸出 2,5

核心區別：

• a：數組首元素地址（int*），a+1 偏移 sizeof(int)。
• &a：整個數組地址（int (*)[5]），&a+1 偏移 5*sizeof(int)，指向 a[5]（越界一個元素）。
• ptr 強轉為 int* 後，ptr-1 回退一個 int 大小，指向 a[4]（值 5）。

題目五：死鎖四個必要條件

1. 互斥條件：資源獨佔使用。
2. 請求保持條件：持有資源時請求新資源被阻塞，不釋放已持有資源。
3. 不可剝奪條件：資源只能由持有者主動釋放。
4. 循環等待條件：進程形成環路互相等待資源。

破壞任一條件即可預防死鎖。

題目六：死鎖處理策略

• 鴕鳥策略：忽略死鎖（多數通用 OS 採用）。
• 預防策略：破壞四條件之一（如一次性申請所有資源）。
• 避免策略：銀行家算法，動態判斷安全狀態。
• 檢測與解除：周期性檢測，發現後撤銷進程或剝奪資源。

題目七：進程調度算法

• FCFS：先來先服務，非搶佔，平均等待時間長。
• 優先級調度：可能導致飢餓，需老化機制。
• 時間片輪轉 (RR)：公平，響應快，時間片大小影響吞吐與響應平衡。
• 多級反饋隊列：綜合優先級與 RR，動態調整優先級，兼顧交互與批處理。

題目八：TCP/UDP 協議對比

題目九：指針強轉等價性分析

問題：(void *)ptr vs (*(void **))ptr 結果是否相同？

結論：相同（前提 ptr 類型為 void** 或兼容指針類型）。

解析：

1. (void *)ptr：直接將 ptr 強轉為 void*。
2. (*(void **))ptr：將 ptr 視為 void**（二級指針），解引用獲取其指向的 void* 值。若 ptr 本身指向一個 void* 變量，則結果一致。

題目十：絕對地址操作與代碼跳轉

賦值：*(unsigned int *)0x100000 = 1234;

跳轉執行：

typedef void (*FuncPtr)();
((FuncPtr)0x100000)(); // 或 *((void (*)())0x100000)();

應用場景：嵌入式 Bootloader 跳轉應用程序、記憶體映射 I/O (MMIO) 操作硬體暫存器。

總結與備戰建議

這 10 道題覆蓋了面試高頻考點。建議：

1. 手寫代碼：拒絕眼過腦不會，必須在白紙/編輯器無提示完成。
2. 追問準備：如「為什麼不用遞歸？」、「如何優化空間？」、「多線程下安全嗎？」。
3. 原理優先：背誦結論不如推導原理，面試官更看重思考路徑。