《資料結構》嚴蔚敏版 第 2 章線性表習題完整解析

《資料結構》嚴蔚敏版 第 2 章線性表習題完整解析

基礎知識題精選

2.1 概念辨析：頭指標、頭節點、首元節點

• 頭指標：指向鏈表第一個節點的指標變數，若帶頭節點則指向頭節點。
• 頭節點：附加在首元節點之前的額外節點，不存放資料，便於統一插入/刪除邏輯。
• 首元節點：存放第一個資料元素的節點，即頭節點之後的第一個節點（或無頭節點時的第一個節點）。

2.2 填空題重點

1. 順序表插入/刪除平均移動 表中一半 元素，移動量與 元素位置 有關。
2. 順序表邏輯相鄰元素物理位置 必定相鄰；單鏈表邏輯相鄰元素物理位置 不一定相鄰。
3. 單鏈表中除首元節點外，任一節點位置由 其直接前驅節點的鏈域值 指示。
4. 設頭節點主要為了 插入和刪除首元素時不必進行特殊處理。

2.3 何時選順序表優於鏈表？

當頻繁隨機存取、元素數量較固定、記憶體空間敏感（無指標開銷）時，順序表更優。

算法設計題精講

2.10 刪除順序表第 i 個起 k 個元素——改進版

原算法以巢狀迴圈逐個移動，時間複雜度 O(k·n)。改進：一次性將後續元素前移 k 位，再更新 length，複雜度降為 O(n)。

Status DeleteK(SqList &L, int i, int k) {
    if (i < 1 || k < 0 || i + k > L.length) return INFEASIBLE;
    for (int j = i + k; j <= L.length; ++j)
        L.elem[j - k - 1] = L.elem[j - 1];
    L.length -= k;
    return OK;
}

2.11 有序順序表插入元素 x 保持有序

先二分查找插入位置，再後移元素，最後插入。時間複雜度 O(log n + n) ≈ O(n)。

2.12 兩順序表字典序比較（不破壞原表）

同步掃描兩表，首個不同元素決定大小；若一表提前結束則該表較小。無需顯式求前綴。

2.19 單鏈表刪除值在 (mink, maxk) 區間的所有節點

利用有序性，找到首個 > mink 的前驅 pre，與首個 ≥ maxk 的節點 rear，將 pre->next 接到 rear，並釋放中間節點。單次掃描 O(n)。

2.22 單鏈表就地逆置

三指標法：pre 初為 NULL，cur 為首節點，next 暫存後繼；迴圈中反轉 cur->next 指向 pre，三指標同步後移。O(n) 時間、O(1) 空間。

2.24 兩有序單鏈表歸並為非遞增序列，利用原節點空間

雙指標比較，每次取較大節點摘離插入新表頭部（頭插法），最後自動形成遞減序。O(m+n) 時間、無額外空間。

2.37 雙向循環鏈表重排為 a1,a3,...,an,...,a4,a2

先將奇數位節點摘出串成子表，偶數位節點逆序插入奇數子表尾部。一次遍歷完成，O(n) 時間。

附錄：型別定義

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct { ElemType *elem; int length, listsize; } SqList;
typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

本文彙整教材習題核心解法，適合備考資料結構考試或面試複習。完整程式碼與測試數據請參考原書配套資源。