CSP-S 2025 第一轮 第4题：将字符串 \tt cat, \tt car, \tt cart, \tt cas

题目

将字符串 $\tt cat$, $\tt car$, $\tt cart$, $\tt case$, $\tt dog$, $\tt do$ 插入一个空的 Trie 树（前缀树）中。构建完成 Trie 树（包括根节点）共有多少个结点？

选项

• A. $8$
• B. $9$
• C. $10$
• D. $11$

答案

D

题解

答案是 D．\(11\)。

Trie 树中，相同的前缀共用结点，构建结果如下：

``text 根 ├── c │ └── a │ ├── t cat │ ├── r car │ │ └── t cart │ └── s │ └── e case └── d └── o do └── g dog ``

• c 开头的分支有 \(7\) 个结点。
• d 开头的分支有 \(3\) 个结点。
• 加上根结点，共 \(7+3+1=\boxed{11}\) 个。

注意：字符串结束只需在对应结点上做标记，不额外增加结点。所以 car 和 do 分别结束在已有的 r、o 结点上。