CSP-S 賽前閉卷測驗
CSP-S 賽前閉卷測驗
時間： 30 分鐘
規則： 閉卷；每題選一個答案；Q1、Q2、Q5、Q6、Q8、Q10 必須寫出簡短計算或推理。
提示： 先圈出題目的限制字詞，再看選項。
Q1 — 計數
有 5 個完全相同的紅球和 5 個完全相同的藍球，排成一行。任何兩個藍球不能相鄰，共有多少種排列？
- A. 25
- B. 30
- C. 6
- D. 120
Q2 — KMP
對模式字串 P = abacaba，next[i] 表示 P[0..i] 最長的「真前綴同時是真後綴」長度。哪個陣列正確？
- A.
{0, 0, 1, 0, 1, 2, 3} - B.
{0, 1, 2, 3, 4, 5, 6} - C.
{0, 0, 1, 1, 2, 2, 3} - D.
{0, 0, 0, 0, 1, 2, 3}
Q3 — Trie（前綴樹）
把 cat、car、cart、case、dog、do 插入一棵空的 Trie。包括根節點，最後共有多少個節點？
- A. 8
- B. 9
- C. 10
- D. 11
Q4 — DAG（有向無環圖）
一個有 n 個頂點、m 條邊的 DAG，有多少種拓撲排序？
- A. 必定只有 1 種
- B. 最多
n種 - C. 必定為
n − m種 - D. 視乎圖的結構而定
Q5 — 雜湊
大小為 13 的雜湊表使用線性探查，H(key) = key mod 13。依次插入 18, 26, 35, 9, 68, 74，74 最後放在哪個索引？
- A. 5
- B. 7
- C. 9
- D. 11
Q6 — 最小生成樹
完全圖的頂點為 1 至 8，邊權重 (u, v) 為 |u − v|。最小生成樹總權重是多少？
- A. 7
- B. 8
- C. 9
- D. 10
Q7 — 堆疊限制
元素 a, b, c, d, e, f 依次入棧。入棧、出棧可交替，但不允許連續三次出棧。哪個輸出序列不可能？
- A.
dcebfa - B.
cbdaef - C.
bcaefd - D.
afedcb
Q8 — 大小端序
unsigned x = 0xDEADBEEF;，p 指向 x 的第一個 byte。小端序和大端序系統分別執行 printf("%X", *p)，輸出為何？
- A.
EF、EF - B.
EF、DE - C.
DE、EF - D.
DE、DE
Q9 — 歐拉圖
關於無向歐拉圖，下列哪項不一定正確？
- A. 每個頂點度數均為偶數。
- B. 圖是連通的。
- C. 圖存在歐拉環。
- D. 邊數是奇數。
Q10 — 遞迴式
已知 f(1) = 1，對 n ≥ 2，f(n) = f(n − 1) + f(floor(n / 2))。f(4) 等於多少？
- A. 4
- B. 5
- C. 6
- D. 7
作答欄
1 ___ 2 ___ 3 ___ 4 ___ 5 ___ 6 ___ 7 ___ 8 ___ 9 ___ 10 ___
