› 看板 Grad-ProbAsk 關於我們 聯絡資訊
作者angel861047 (你逆)
看板Grad-ProbAsk
標題[理工] 台大電機丙 考古題 有關hash/array/random binary tree
時間Sun Feb 12 23:23:07 2017
大家好，之前寫台大電機丙考古題的時候 好像不只一次看到這些問題，一直覺得很奇怪。 1.hash這種結構到底要怎麼找minimal data啊，不是只能跟array一樣從頭掃描到尾嗎 http://i.imgur.com/ABPF9dO.png
2.另外一個就是array的刪除，記得書上都寫說刪除的時候要搬移元素， 這我一直搞不太懂耶，如果原本array的資料不是經過排序、還是什麼特別方法處理過的， 空一格在那邊不行嗎 http://i.imgur.com/SEJZ2IW.png
3.隨機建立一個binary tree，得到最小高度的樹的機率>50%， 這個今天的考卷也有類似的。 當初爬文的時候版上說這是錯的，但也沒特別講原因， 難道要用 catalan number(建立任意二元樹的方法數) 減去 "不是最小高度的樹"的方法數 來算嗎? 沒想到這題之前沒找出答案來吃了個大虧啊 先謝謝大家看完我的問題，祝大家考試順利@@ 題外話:今天電機丙的DS算hash的那一題，其中一個選項給得參數是5566 9487， 該說出題者還蠻跟得上流行的嗎...科科 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.236.36.77 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486912989.A.382.html
推 joeboy: HASH 找最小應該要全部找一次 02/12 23:40
→ joeboy: array刪除記得是要補上去空的位置，空一格感覺怪怪的QQ 02/12 23:40
→ joeboy: #1OWFncmn 02/12 23:41
→ joeboy: 第三題我有問過，然後我今天好像手殘寫錯0......0 02/12 23:41
→ angel861047: 好吧，好像也只能接受了 ˋ皿ˊ 02/12 23:43
→ angel861047: 恩恩3Q我先來看一下 02/12 23:44
推 koozyooki: 最低高度是要full binary tree嗎 02/12 23:45
推 FRAXIS: array 刪除你空一格不是不行啊 但是這樣要怎麼使用這個 02/12 23:45
→ FRAXIS: array? 你需要有方法去判斷某一格是否有真的資料 02/12 23:46
→ angel861047: ㄜ...好像也是齁 02/12 23:47
→ FRAXIS: 得到最小高度是 O(lg n) 還是要 ceil(lg n) 02/12 23:48
→ FRAXIS: 後者感覺很難會 > 50% 02/12 23:48
→ angel861047: 哦....大概瞭了，最小高度的方法數/任意二元樹的比 02/12 23:51
→ angel861047: 值很小 02/12 23:52
→ angel861047: 如果要保持最小高度，好像也只能在 full binary tree 02/12 23:54
→ angel861047: 的leaves上動手腳而已，這樣的確蠻少的 02/12 23:56
→ a15151616: Q3我記得好像是問BST 02/13 05:17
推 k1992313: Minimum height 跟balance一樣嗎？？ 02/13 08:11
→ k1992313: 像紅黑樹就不為min height but balance 02/13 08:12
推 aa06697: minimum height 就是指接近full的那種 不是指高度O(logn) 02/13 10:25
→ aa06697: 如果題目是說可以接近balance那我可能會選 但是要minimu 02/13 10:25
→ aa06697: m height就不太可能了 02/13 10:25