[理工] 幾題資結請教

看板Grad-ProbAsk作者 (還很新)時間7年前 (2017/01/25 22:30), 7年前編輯推噓6(6推 0噓 21→)
留言27則, 4人參與, 最新討論串1/1
是非 (1) If an undirected connected graph G has no bridge edge then G is a strongly c 請問在無向圖中 只要連通應該都是scc吧 沒有bridge代表 任意一邊刪去後還是有連通吧？ 但看不懂題目意思... (2) A B-tree of order 2 is an A VL tree .. 我知道B tree能變成RB tree，但B tree的order是2的話可以稱之為AVL嗎？沒聽過這種說 法 (3) For static hashing with linear open addressing to be efficient, the loadin g factor α > 1.0 must hold. 請問這題的α是指loading density嗎 翻筆記發現我只抄半頁而已 也有點看不懂linear open addressing是什麼(猜測是linear probling？) (4) Which traversal operation is used in tree sort? (A) Level-order (B) In-order (C) Pre-order (D) Post-order (E) BFS (F) DFS 我是選inorder 想法是在bst裡頭應該 inorder的輸出才是排序資料 不過其他的選項感覺好像能選？ 最後想問一題排序 http://i.imgur.com/nccczMz.jpg
我只有選quick sort 其他不知道該不該選 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.200.66 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485354623.A.391.html
推
01/25 22:48, , 1F
第二B tree order=2表示你只能有一個key所以會等於binary
01/25 22:48, 1F
→
01/25 22:48, , 2F
，然後妳又要滿足leaf都在同一層，所以會變成full
01/25 22:48, 2F
這樣有滿足AVL吧？(有平衡) ※ 編輯: newpuma (223.137.200.66), 01/25/2017 23:26:07
推
01/25 23:29, , 3F
第一題若p則q，q的命題恆對，所以true
01/25 23:29, 3F
→
01/25 23:30, , 4F
B tree of order 2 定義為 full binary tree
01/25 23:30, 4F
→
01/25 23:30, , 5F
單藍有平衡~
01/25 23:30, 5F
推
01/25 23:33, , 6F
最後一題 radix sort也可以選喔!
01/25 23:33, 6F
→
01/25 23:33, , 7F
第三題你的問題有打完嗎?
01/25 23:33, 7F
手機app一直吃字＝＝ 補上了 感謝！！ ※ 編輯: newpuma (223.137.200.66), 01/25/2017 23:58:16
→
01/26 07:02, , 8F
最後一題還可以選radix sort，然後E就變不能選了
01/26 07:02, 8F
→
01/26 07:05, , 9F
4我覺得BFS從root開始相當於level order，DFS從root開
01/26 07:05, 9F
→
01/26 07:05, , 10F
始相當於pre-order，所以剩pre-order、post-order、
01/26 07:05, 10F
→
01/26 07:06, , 11F
level-order要考慮，可是這三個印象中沒有tree可以讓
01/26 07:06, 11F
→
01/26 07:06, , 12F
他們的順序變成一種排序的，印象中拉
01/26 07:06, 12F
推
01/26 10:42, , 13F
第一題雖然SCC基本上是定義在directed graph上，不過如
01/26 10:42, 13F
→
01/26 10:42, , 14F
果今天是undirected graph又connected,就一定可以雙向互
01/26 10:42, 14F
→
01/26 10:42, , 15F
通，我覺得跟有沒有bridge沒啥關係，他還是SCC
01/26 10:42, 15F
→
01/26 10:43, , 16F
第二題跟上幾樓講的一樣, B-tree的external node規定要
01/26 10:43, 16F
→
01/26 10:43, , 17F
在同一層，所以會是balanced,符合AVL的性質
01/26 10:43, 17F
→
01/26 10:44, , 18F
第四題有點看不懂他想問啥，tree sort（?)不是每個都可
01/26 10:44, 18F
→
01/26 10:44, , 19F
以用嗎
01/26 10:44, 19F
推
01/26 10:46, , 20F
最後一題我選ACE,merge sort你要拆成兩兩配對（或是2-3
01/26 10:46, 20F
→
01/26 10:46, , 21F
各自下去做sort,sort到一半不會有這種排列方式
01/26 10:46, 21F
→
01/26 10:47, , 22F
radix sort 從個位數開始sort,他個位數是2,3,4,5,7,所以
01/26 10:47, 22F
→
01/26 10:47, , 23F
有可能是radix sort
01/26 10:47, 23F
→
01/26 10:47, , 24F
insertion sort第一個挑12,第二個應該會挑27,63不可能跑
01/26 10:47, 24F
→
01/26 10:47, , 25F
到那個位置
01/26 10:47, 25F
推
01/26 10:50, , 26F
我發現我剛剛講錯，E也可以選才對，radix sort也不會大
01/26 10:50, 26F
→
01/26 10:50, , 27F
於nlogn沒錯，T大是對的
01/26 10:50, 27F
‣ 更多 newpuma 的文章
文章代碼(AID): #1OYBP_EH (Grad-ProbAsk)