資料結構幾題 - 考試

想問前中後序的一些問題

例如說 1+2-3*4/5*6/7-8/9轉換成另外兩種

postorder: 12+34*5/6*7/-89/-

preorder: --+12/*/*34567/89

以上是用括號拆解獲得

如果是畫二元樹 就變成

postorder: 12+34567/*/*-89/-

preorder: --+12*3/4*5/67/89

好像表示出來結果有點出入 是因為題目沒有定義前序或後序是如何

才會變成解出來沒有唯一解?

另外

下為一運算式樹 於下列陳述何者為正確?

(A)Preorder搜尋方法為AB/CD-*E+

(B)Preorder搜尋方法為+*/+ABCDE

(C)Inorder搜尋方法為A/B*C+D+E

(D)Postorder搜尋方法為+*/AB+CDE

(E)以上皆非

某年輔大資管所考題

答案是(C) 不過(B)不知道哪裡有誤 我畫運算式樹畫得出來說

若以$表示乘冪 則關於((A+B)$C$D-E+F)/G之敘述何者為非?

(A)為中序表示

(B)其前序表示為/+-$A+B$CDEFG

(C)其後序表示為AB+CD$$E-F+G/

(D)大部分程式語言編譯器在編譯時採用後序表示法 因計算時只需配合堆疊操作 由左向

右執行即可求值

某年大葉資管所考題

答案是(B)

對(C)有點問題 因為我畫二元樹跟括號拆解是AB+C$D$E-F+G/

好像也有點出入

其實好像都是差不多類似的疑問 只是想釐清讓在考場時沒有疑慮

還有

Draw a binary tree that you could use to store the list R S T U V W X Y Z

for further searching

某年高師大資教考題

解答是畫成 U
S X
R T V Y
W Z

我是畫成

U
S X
R T W Y
V Z

不確定自己畫的對不對

至少高度平衡有弄到

--