[DS]98台大電機數題

[DZASHIANG (DZASHIANG)]

http://i.imgur.com/3LFoeKU.jpg
請問第四題的b為什麼是true

http://i.imgur.com/v42NsvL.jpg
第六題的c為什麼false

http://i.imgur.com/5sx4zbD.jpg
第十六題的a為什麼true,若紅黑樹中樹葉是紅的->無children->false 這樣的推論成立嗎

拜託各位高手~謝謝 答案是參考手邊別人寫的解答

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.15.66.138
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1478539805.A.B01.html
※ 編輯: DZASHIANG (101.15.66.138), 11/08/2016 01:31:13
※ 編輯: DZASHIANG (101.15.66.138), 11/08/2016 01:33:45
※ 編輯: DZASHIANG (101.15.66.138), 11/08/2016 01:34:21
→ gigayaya: http://imgur.com/47FcTou 不一樣吧
→ ken52011219: 紅黑樹external node 必有兩black nil
→ ken52011219: 6(c 應該是指 circular queue 會更好吧
了解,忘了nil視為black,寫到傻了
手邊沒電腦,所以四的b選項false無誤
謝謝兩位
※ 編輯: DZASHIANG (101.15.66.138), 11/08/2016 09:43:30
推 aa06697: 一樓不能這樣看 題目記體空間跟你寫的是不一樣的
→ aa06697: 不過4 b應該是false沒錯 *x會是912 x是806
推 aa06697: 7 c 是因為 一般queue 是從rear差值進去 如果你把head 放
→ aa06697: front 等於每次插入刪除 都要先從front 跑到rear再改指標
→ aa06697:  如果head 放rear 直接改指標就好
→ aa06697: 更正 6 c
→ aa06697: 抱歉再更正qq 是只有插入的時候
→ aa06697: 插入次數一定>=刪除次數 所以對於插入的效率較好者會較佳
→ aa06697:  我是這樣想的～
→ ken52011219: 這樣子感覺用Circular link回來就更省事了
→ ken52011219: 令Delete + Insert = n times,Delete為 O(1)
→ ken52011219: Insert O(n)  O(n*(x))+O(n*(x-n))=O(nx)
→ ken52011219: 而Circular Insert or Delete 皆為 O(1)
→ ken52011219: 總運算 頂多O(n) 用單純link worst case為O(n^2)
推 ken52011219: 話說可以問一下為什麼是912嗎@@? 912是x[3]的addr吧
→ ken52011219: 更正 x[3]的content
推 aa06697: 沒錯呀 x的address是800 因為x是pointer 放的content:806
→ aa06697: 是address *x會去取806的content 所以是912 有點久沒寫要
→ aa06697: 處理指標的語言了....有誤還請更正
推 aa06697: 是說E比較詭異XD 剛剛想說一個存在register內的consrant
→ aa06697: 要怎麼取址 試了一下果然compile不了 會當成是and 運算元
→ ken52011219: 所以因為是pointer 所以會+6 嗎
→ ken52011219: 會想問這個是因為我記得 cont *x 應該是讀取它的addr
→ ken52011219: 假若因為Pointer的關係了話 cont *x 應該是806
→ ken52011219: 而 x[0] 的content 也是 806 這題就是true了
→ ken52011219: 沒事 我記錯了 qq~