2024q1 Homework2 (quiz1+2)

contributed by < marsh-fish >

第一週測驗題

測驗 1

利用左右指標(左指標從頭部開始，右指標從尾部)紀錄所有大於和小於 pivot 的數之量，藉此得出 pivot 應插入之位置。

測驗 2

原理和 merge sort 類似，藉由分成數個 runs 來合併，由於在分成 runs 的過程中會轉成遞增的序列，所以能夠有效的減少合併的次數。

第二週測驗題

測驗 1

在 preorder 可以知道哪個節點是 root ，接著在 inorder 可以找到對應的節點，反覆尋找便可以建出整顆數。

測驗 2

將使用到的節點移動到最前面，由於每次使用過的節點都會被移至 head ，所以 tail 的節點會是最長時間沒被使用的節點，所以在有新的節點加入時刪除此節點。

測驗 3

藉由 __ffs 找到第一個設定的位元，並將要尋找的 word 中的第一個位元清除，重複此動作即可找到第 N 個設定的位元，其中 __ffs 的做法和二元搜尋的概念相似，先判斷前半段的位元，若前半段的位元都是零則 shift 相對應的位元。