[理工]98台大電機DS數題

看板Grad-ProbAsk作者 (DZASHIANG)時間7年前 (2016/11/08 01:30), 7年前編輯推噓5(5推 0噓 24→)
留言29則, 3人參與, 最新討論串1/2 (看更多)
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
→
11/08 02:27, , 1F
不一樣吧
11/08 02:27, 1F
→
11/08 04:49, , 2F
紅黑樹external node 必有兩black nil
11/08 04:49, 2F
→
11/08 05:02, , 3F
6(c 應該是指 circular queue 會更好吧
11/08 05:02, 3F
了解,忘了nil視為black,寫到傻了 手邊沒電腦,所以四的b選項false無誤 謝謝兩位 ※ 編輯: DZASHIANG (101.15.66.138), 11/08/2016 09:43:30
推
11/10 13:46, , 4F
一樓不能這樣看 題目記體空間跟你寫的是不一樣的
11/10 13:46, 4F
→
11/10 13:48, , 5F
不過4 b應該是false沒錯 *x會是912 x是806
11/10 13:48, 5F
推
11/10 13:52, , 6F
7 c 是因為 一般queue 是從rear差值進去 如果你把head 放
11/10 13:52, 6F
→
11/10 13:52, , 7F
front 等於每次插入刪除 都要先從front 跑到rear再改指標
11/10 13:52, 7F
→
11/10 13:52, , 8F
如果head 放rear 直接改指標就好
11/10 13:52, 8F
→
11/10 13:52, , 9F
更正 6 c
11/10 13:52, 9F
→
11/10 13:53, , 10F
抱歉再更正qq 是只有插入的時候
11/10 13:53, 10F
→
11/10 13:57, , 11F
插入次數一定>=刪除次數 所以對於插入的效率較好者會較佳
11/10 13:57, 11F
→
11/10 13:57, , 12F
我是這樣想的～
11/10 13:57, 12F
→
11/10 14:12, , 13F
這樣子感覺用Circular link回來就更省事了
11/10 14:12, 13F
→
11/10 14:14, , 14F
令Delete + Insert = n times,Delete為 O(1)
11/10 14:14, 14F
→
11/10 14:15, , 15F
Insert O(n) O(n*(x))+O(n*(x-n))=O(nx)
11/10 14:15, 15F
→
11/10 14:16, , 16F
而Circular Insert or Delete 皆為 O(1)
11/10 14:16, 16F
→
11/10 14:17, , 17F
總運算 頂多O(n) 用單純link worst case為O(n^2)
11/10 14:17, 17F
推
11/10 14:38, , 18F
話說可以問一下為什麼是912嗎@@? 912是x[3]的addr吧
11/10 14:38, 18F
→
11/10 14:39, , 19F
更正 x[3]的content
11/10 14:39, 19F
推
11/11 14:29, , 20F
沒錯呀 x的address是800 因為x是pointer 放的content:806
11/11 14:29, 20F
→
11/11 14:29, , 21F
是address *x會去取806的content 所以是912 有點久沒寫要
11/11 14:29, 21F
→
11/11 14:29, , 22F
處理指標的語言了....有誤還請更正
11/11 14:29, 22F
推
11/11 14:47, , 23F
是說E比較詭異XD 剛剛想說一個存在register內的consrant
11/11 14:47, 23F
→
11/11 14:47, , 24F
要怎麼取址 試了一下果然compile不了 會當成是and 運算元
11/11 14:47, 24F
→
11/11 15:33, , 25F
所以因為是pointer 所以會+6 嗎
11/11 15:33, 25F
→
11/11 15:33, , 26F
會想問這個是因為我記得 cont *x 應該是讀取它的addr
11/11 15:33, 26F
→
11/11 15:34, , 27F
假若因為Pointer的關係了話 cont *x 應該是806
11/11 15:34, 27F
→
11/11 15:35, , 28F
而 x[0] 的content 也是 806 這題就是true了
11/11 15:35, 28F
→
11/11 16:39, , 29F
沒事 我記錯了 qq~
11/11 16:39, 29F
‣ 更多 DZASHIANG 的文章
文章代碼(AID): #1O8BeTi1 (Grad-ProbAsk)
‣ 更多 DZASHIANG 的文章
文章代碼(AID): #1O8BeTi1 (Grad-ProbAsk)