[理工] 幾題資結請教

[newpuma (還很新)]

是非
(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
推 joeboy: 第二B tree order=2表示你只能有一個key所以會等於binary
→ joeboy: ，然後妳又要滿足leaf都在同一層，所以會變成full
這樣有滿足AVL吧？(有平衡)
※ 編輯: newpuma (223.137.200.66), 01/25/2017 23:26:07
推 kyuudonut: 第一題若p則q，q的命題恆對，所以true
→ kyuudonut: B tree of order 2 定義為 full binary tree
→ kyuudonut: 單藍有平衡~
推 kyuudonut: 最後一題 radix sort也可以選喔!
→ kyuudonut: 第三題你的問題有打完嗎?
手機app一直吃字＝＝ 補上了 感謝！！
※ 編輯: newpuma (223.137.200.66), 01/25/2017 23:58:16
→ yupog2003: 最後一題還可以選radix sort，然後E就變不能選了
→ yupog2003: 4我覺得BFS從root開始相當於level order，DFS從root開
→ yupog2003: 始相當於pre-order，所以剩pre-order、post-order、
→ yupog2003: level-order要考慮，可是這三個印象中沒有tree可以讓
→ yupog2003: 他們的順序變成一種排序的，印象中拉
推 Transfat: 第一題雖然SCC基本上是定義在directed graph上，不過如
→ Transfat: 果今天是undirected graph又connected,就一定可以雙向互
→ Transfat: 通，我覺得跟有沒有bridge沒啥關係，他還是SCC
→ Transfat: 第二題跟上幾樓講的一樣, B-tree的external node規定要
→ Transfat: 在同一層，所以會是balanced,符合AVL的性質
→ Transfat: 第四題有點看不懂他想問啥，tree sort（?)不是每個都可
→ Transfat: 以用嗎
推 Transfat: 最後一題我選ACE,merge sort你要拆成兩兩配對（或是2-3
→ Transfat: 各自下去做sort,sort到一半不會有這種排列方式
→ Transfat: radix sort 從個位數開始sort,他個位數是2,3,4,5,7,所以
→ Transfat: 有可能是radix sort
→ Transfat: insertion sort第一個挑12,第二個應該會挑27,63不可能跑
→ Transfat: 到那個位置
推 yupog2003: 我發現我剛剛講錯，E也可以選才對，radix sort也不會大
→ yupog2003: 於nlogn沒錯，T大是對的