二技計概!三元樹和二元搜尋法的問題~

Question

1.有300個節點的三元樹.其最小高度為何?(註:僅有一個節點的三元樹.其高度為1)

答:6

詳解寫著3的n次方-1>300,3的n次方>301.故n=6

就是看不懂詳解的意思耶>\"<

2.在以排序的1000個相異元素之陣列中.欲執行二元搜尋法以找尋某資料.若要找

尋的資料並不在陣列中.則大約要比對多少個元素才能確定他不在陣列中?

(A)4 (B)10(C)500(D)1000

答案B

詳解寫2的n次方~1000.n=10

不懂怎ㄇ會是10??

3.用2的補數來計算00010100(旁邊有小小的2)-46(旁邊有小小的10)

算出來是11100110(旁邊有小小的2)

我一直算錯>\"<

Answer 1

最佳解答

1.

詳解的過程有問題

應該是(等比級數和的公式)

1* (3^n -1)/(3-1) >= 300

所以應該是 (3^n -1) >= 600

3^n >= 601

n = 6

2.

跟第一題類似

1000個元素的陣列經過排序其實就是一個有1000個節點的二元搜尋樹

比對多少個元素就等於算最小高度

因此

1* (2^n-1)/(2-1) >= 1000

2^n >= 1001

n = 10

3.

46的2進位值是00101110

因此-46的2補數就是0變1,1變0最後再加1

也就是11010010

因此 2進位的00010100-10進位的46

就變成2進位的00010100 + 10進位的-46

00010100 [phone] = 11100110