百度 2014 校招研發筆試真題（濟南站）深度解析：存儲層次、僵屍進程、Socket 編程、字符串反轉、括號消除

一、簡答題（30 分）

1. 計算機存儲系統層次結構與原理（10 分）

典型三級結構：Cache（高速緩存）→ 主存（內存）→ 輔存（磁盤/SSD）。

層次間特性遞進：容量↑、速度↓、價格/位↓。

核心原理——局部性原理：

• **時間局部性**：剛訪問的數據近期大概率再次被訪問 → 留在 Cache；
• **空間局部性**：訪問某地址時，鄰近地址近期大概率被訪問 → 以塊/頁為單位調入。

效果：CPU 主要訪問高速 Cache，僅缺頁時訪問主存/輔存。綜合實現「速度接近 Cache、容量接近輔存、價格接近輔存」的最佳平衡。

2. Linux 僵屍進程產生、危害與預防（10 分）

產生：子進程 `exit` 後，內核保留其 `task_struct`（含退出碼、資源統計等）等待父進程 `wait`/`waitpid` 回收。若父進程未安裝 `SIGCHLD` 處理器、未調用 `wait`、未忽略信號，子進程長期滯留 → 僵屍。

危害：佔用有限的 PID 號碼，導致無法創建新進程；`ps` 顯示 `` 污染進程表。

預防方案：

1. 父進程捕獲 `SIGCHLD`，處理器中循環 `waitpid(-1, NULL, WNOHANG)` 非阻塞回收；
2. 註冊 `signal(SIGCHLD, SIG_IGN)` 讓內核自動回收（Linux 支持，POSIX 未強制）；
3. 雙重 `fork`：父→子→孫，子進程立即退出，孫進程由 `init` (PID 1) 收養自動回收；
4. 父進程定時調用 `waitpid` 清理。

3. Linux Socket 服務端編程標準流程（10 分）

// TCP 服務端
int sockfd = socket(AF_INET, SOCK_STREAM, 0);
bind(sockfd, (sockaddr*)&serv_addr, sizeof(serv_addr));
listen(sockfd, BACKLOG);
while (1) {
    int connfd = accept(sockfd, (sockaddr*)&cli_addr, &len);
    // 可 fork/thread/epoll 處理並發
    read(connfd, buf, sizeof(buf));
    write(connfd, resp, strlen(resp));
    close(connfd);
}
close(sockfd);

關鍵 API：`socket`→`bind`→`listen`→`accept`→`read`/`write`/`send`/`recv`→`close`。
客戶端：`socket`→`connect`→`read`/`write`→`close`。

二、算法與程序設計題

1. 字符串原地反轉（15 分）

要求：不使用庫函數，時間複雜度最低。
解法：雙指針頭尾交換，O(n) 時間、O(1) 空間，單次遍歷完成。

char* reverse_str(char* str) {
    if (!str) return nullptr;
    char *l = str, *r = str + strlen(str) - 1;
    while (l < r) swap(*l++, *r--);
    return str;
}

2. 消除嵌套括號（15 分）

輸入：`(1,(2,3),(4,(5,6),7))` → 輸出：`(1,2,3,4,5,6,7)`。錯誤格式報錯。
解法：棧 + 隊列/字符串構建器。掃描字符：

• 數字/逗號 → 直接加入結果；
• `(` → 入棧標記層級；
• `)` → 出棧，若棧空報錯（括號不匹配）；
• 最終棧非空 → 報錯。

時間 O(n)，空間 O(深度)。

面試復盤提示

• 基礎知識題（存儲、進程、網絡）必須條理清晰、術語準確；
• 算法題先講思路、複雜度、邊界，再寫代碼；
• 括號匹配、棧應用是高頻必考，熟練掌握變體（如最長合法括號、表達式求值）。

本文整理自 “驿落黃昏” 博客，原文鏈接：https://yiluohuanghun.blog.51cto.com/3407300/1299814