卷別

資料結構與演算法

選擇

國立臺灣大學 2024 · 考試 · 第 8 題

(5 points) We define the height of a tree to be the maximum number of edges from the root to a leaf. We also define the level of a node $v$ , denoted as $l(v)$ , to be the height of the subtree rooted at $v$ . Which of the following descriptions is correct?

(A)
If $v$ is a leaf, then $l(v) = 1$ .
(B)
If $v$ is an internal node, $l(v) = \max_{s \in S} l(s)$ , where $S$ is the set of children of $v$ .
(C)
We can compute $l(v)$ by starting a breadth-first-search (BFS) from $v$ , traversing all nodes of the subtree rooted at $v$ , and computing the maximum distance to a leaf as $l(v)$ . Since there are no more than $n$ $v$ 's and each BFS takes $O(n)$ time, the total time complexity is $O(n^2)$ .
(D)
We can compute the levels for all nodes by a depth-first-search (DFS) starting from the root of $T$ . That is, we can compute the level of an internal node $v$ after we compute the $l$ values of all children of $v$ .
(E)
Since there are $n$ tree nodes to visit, the DFS from the root takes $O(n)$ time.

標準解析

AI 已複查