Examly題庫立即開始練習
地方政府公務人員四等-電子工程類科計算機概要10813單選題

如果一個二元搜尋樹以後序(postorder)方式走訪(traversal)的結果為一個嚴格遞增數列(即:x1 < x2< … < xn),1 < n,則下列敘述何者恆為正確?

A此二元搜尋樹為歪向左傾的樹(left skewed,即所有非樹葉節點都只有左子)正確答案
B此二元搜尋樹為歪向右傾的樹(right skewed,即所有非樹葉節點都只有右子)
C此二元搜尋樹既不為歪向右傾,亦不為歪向左傾
D此二元搜尋樹的高度必為二
答案與詳解
A
正確答案
BST後序走訪(左-右-根)若為遞增,代表最後印出的「根節點」是最大值,這意味著整棵樹不能有右子樹,必定是向左傾斜的樹。

為什麼答案是 A

後序走訪順序為「左子樹→右子樹→根節點」。若結果為遞增數列,代表最後拜訪的「根節點」是整棵樹的最大值。在二元搜尋樹(BST)中,要讓根節點成為最大值,就絕對不能有右子樹(因為右子樹的值必大於根)。套用到每個節點,整棵樹只能有左子樹,即為歪向左傾的樹。

考點:左傾樹特性考點:右傾樹特性考點:樹的型態推論考點:樹的高度
載入中…

想練更多計算機概要考古題?

Examly 收錄 38 萬+ 道歷屆題目,每題都有像這樣的精選詳解。免費下載,立即開練。

Download on theApp Store即將推出Google Play
黑皮