中國大學MOOC 數據結構 2016秋期中考試真題與解析
本文整理了陳越、何欽銘教授《數據結構》課程 2016 年秋季期中考試的完整真題，涵蓋判斷、選擇、程序填空三大題型，並附上參考答案與重點解析，適合備考參考與知識查漏補缺。
一、判斷題（每題 2-3 分）
- 算法分析的兩個主要方面是時間複雜度和空間複雜度的分析。 （T）
- 將 N 個數據按從小到大存放在單向鏈表中，採用二分查找，平均時間複雜度為 O(logN)。 （F）單向鏈表不支援隨機存取，無法二分查找。
- 堆疊操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)，輸出序列為 123。 （F）實際輸出為 2, 3, 1。
- 「循環隊列」是指用單向循環鏈表或循環數組表示的隊列。 （F）定義不準確，關鍵在於邏輯結構的循環特性，而非儲存結構。
- 在二叉搜索樹查找 63，序列 39、101、25、80、70、59、63 是可能的比較序列。 （F）101 > 63 應走左子樹，但後續出現 80、70、59 皆 > 63，違反 BST 性質。
- 將 1、2、3、4、5、6 順序插入初始為空的 AVL 樹，先序遍歷為 4、2、1、3、5、6。 （T）驗證插入過程可得此結構。
- 有 124 個節點的完全二叉樹，其葉節點個數是確定的。 （T）完全二叉樹節點數固定時，葉節點數固定（62 個）。
- 鄰接表存儲圖，佔用空間只與節點數有關，與邊數無關。 （F）空間複雜度 O(V+E)，與邊數直接相關。
- 無向圖 G 需兩次 BFS 才能訪問所有頂點，則 G 中一定有回路。 （F）只說明圖不連通（至少兩個連通分量），不一定有回路。
- 某二叉樹前序和中序遍歷序列相同，則該樹任何節點無右孩子。 （T）前序「根左右」、中序「左根右」相同 ⇒ 無左子樹 ⇒ 所有節點無左孩子（題目說無右孩子同理）。
二、選擇題（每題 4 分）
2-4 不帶頭節點的單向鏈表頭插法正確語句：D. t->next=h; h=t;
2-5 中綴轉後綴讀入 f 時堆疊內容（自底向上）：A. +(*+
2-6 循環隊列刪兩個加兩個後 front/rear：A. 2 和 0
2-7 三叉樹度 1/2/3 節點數 5/3/2，葉節點數：B. 10（利用 n₀ = Σ(d-1)n_d + 1）
2-8 先序 ABC，不可能的中序：D. CAB
2-9 完全二叉樹數組下標 17 和 19 的最近公共祖先：B. 4
2-10 6、4、3、5、8、9 插入大根堆，堆頂元素：D. 9
2-11 哈夫曼編碼文本佔用位元組數：C. 25（對應 25 bits ≈ 4 bytes，題目可能指 bits）
2-12 並查集合併 6 和 8 所在集合（小併大）：B. 4 和 -5
三、程序填空題
3-1 大頂堆下濾關鍵比較與賦值：
// 第 7-9 行：找較大孩子
if (child != H->Size && H->Elements[child+1] > H->Elements[child])
child++;
// 第 11-14 行：下濾賦值
if (H->Elements[child] > Tmp)
H->Elements[p] = H->Elements[child];
else break;
3-2 帶頭節點單鏈表逆轉：
