[課業] 資料結構幾題

看板Examination作者 (馬贏狗)時間11年前 (2013/06/28 19:32), 編輯推噓11(11推 0噓 25→)
留言36則, 5人參與, 最新討論串1/2 (看更多)
想問前中後序的一些問題 例如說 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 不確定自己畫的對不對 至少高度平衡有弄到 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.35.166.245
推
06/28 20:21, , 1F
請用[課業]標題分類 置底文有修改標題教學 感謝
06/28 20:21, 1F
→
06/28 20:40, , 2F
你畫錯了還會覺得題目沒定義？你用括號會轉用二元樹就不會
06/28 20:40, 2F
→
06/28 20:40, , 3F
道理是一樣的自己在重畫吧
06/28 20:40, 3F
推
06/28 20:41, , 4F
1. 只有中序 沒有括號 連續同樣優先權存在可能模糊
06/28 20:41, 4F
→
06/28 20:42, , 5F
當然如果你括錯就另當別論
06/28 20:42, 5F
→
06/28 20:42, , 6F
基本上我是覺得應該是你沒畫二元樹
06/28 20:42, 6F
→
06/28 20:42, , 7F
畫對了你就不會錯
06/28 20:42, 7F
→
06/28 20:43, , 8F
大葉那題 你二元樹一定畫錯了
06/28 20:43, 8F
→
06/28 20:43, , 9F
c沒有問題
06/28 20:43, 9F
→
06/28 20:43, , 10F
第二題你的運算樹沒出來
06/28 20:43, 10F
→
06/28 20:49, , 11F
$<-這個是右結合 你應該結合性沒搞清楚才會做錯
06/28 20:49, 11F
→
06/28 20:52, , 12F
高師這一題不是你除法有問題就是你左右的INDEX加錯
06/28 20:52, 12F
不是單純Right Skewed Tree靠旋轉轉換成AVL Tree而已? ※ 編輯: Mayinggo 來自: 114.35.166.245 (06/28 21:06) ※ 編輯: Mayinggo 來自: 114.35.166.245 (06/28 21:07) ※ 編輯: Mayinggo 來自: 114.35.166.245 (06/28 21:12)
推
06/28 21:50, , 13F
第一題單純是你樹畫錯;我畫完的解答跟你的解答是一樣的
06/28 21:50, 13F
→
06/28 21:51, , 14F
第二題B會需要用括號調整運算順序,不像C不用加上括號
06/28 21:51, 14F
推
06/28 22:02, , 15F
第三題根據前面大大說的右結合就搞定一切了(?
06/28 22:02, 15F
推
06/28 22:10, , 16F
第四題原PO應該是在+Y的時候就再轉了,問題是+Y仍然高度平衡
06/28 22:10, 16F
→
06/28 22:10, , 17F
雖然我的答案跟解答不同>< 還在思考到底怎轉的...
06/28 22:10, 17F
推
06/28 22:13, , 18F
第四題答案有錯吧? 解答X跟W畫反了??
06/28 22:13, 18F
推
06/28 22:13, , 19F
那題AVL TREE答案對嗎?
06/28 22:13, 19F
→
06/28 22:14, , 20F
恩恩 我畫出來也反了
06/28 22:14, 20F
→
06/28 22:14, , 21F
我在想錯誤的機率很高 中序的順序跟插入的順序不一樣
06/28 22:14, 21F
推
06/28 22:24, , 22F
畫avl的話 我的答案跟原PO好像也一樣XD
06/28 22:24, 22F
推
06/28 23:25, , 23F
prefix跟preorder infix跟inorder postfix跟postorder是不同
06/28 23:25, 23F
→
06/28 23:26, , 24F
如果第二題是要問搜尋方法答案是B沒錯
06/28 23:26, 24F
→
06/28 23:29, , 25F
針對(A+B)$C$D 轉成postfix 應該是AB+CD$$ 其中括號先做
06/28 23:29, 25F
→
06/28 23:30, , 26F
然後再右結合
06/28 23:30, 26F
→
06/28 23:34, , 27F
高師那一題要你畫二元樹你用AVL做什麼直接用BST去做就一樣
06/28 23:34, 27F
→
06/28 23:36, , 28F
我看到題目怎麼想都不會想要用AVL去畫樹不知道大大從哪看
06/28 23:36, 28F
→
06/28 23:36, , 29F
出來要用AVL
06/28 23:36, 29F
推
06/28 23:37, , 30F
m大的意思是高師那題直接用二元樹做嗎?這當然也是沒錯啦~~
06/28 23:37, 30F
→
06/28 23:38, , 31F
不過就for further searching 其實我也會想要轉成AVL TREE
06/28 23:38, 31F
→
06/28 23:39, , 32F
不然skew tree搜尋起來很悲劇~不過這題我想只要說明清楚就可
06/28 23:39, 32F
→
06/28 23:42, , 33F
不過我AVL TREE怎麼一直畫不出來解答那樣......
06/28 23:42, 33F
→
06/28 23:42, , 34F
題目給的是照順序排了用AVL會有很多旋轉，直接用BST也會有
06/28 23:42, 34F
→
06/28 23:43, , 35F
一樣的效果
06/28 23:43, 35F
推
06/29 00:07, , 36F
直接用BST不是變成right skew了嗎?
06/29 00:07, 36F
‣ 更多 Mayinggo 的文章
文章代碼(AID): #1HpNHB3A (Examination)
‣ 更多 Mayinggo 的文章
文章代碼(AID): #1HpNHB3A (Examination)