# 2024q1 Homework2 (quiz1+2)
contributed by < `marsh-fish` >

### 第一週測驗題

[測驗 1](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-1)

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

[測驗 2](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)

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

### 第二週測驗題

[測驗 1](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-1)

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

[測驗 2](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-2)

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

digraph structs {
    node[shape=plaintext];
    Lastest [fontcolor="blue"];
    Oldest [fontcolor="blue"];
    
    node[shape=box];
    struct0 [label= "5"];
    struct1 [label= "4"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }
    Lastest -> struct0;
    Oldest -> struct4;
}

digraph structs {
    node[shape=plaintext];
    put [fontcolor="black"];
    Lastest [fontcolor="blue"];
    Oldest [fontcolor="blue"];
    
    
    node[shape=box];
    struct0 [label= "5"];
    struct1 [label= "4"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    struct5 [label= "6"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }
    Lastest -> struct0;
    Oldest -> struct4;
    put -> struct5
}

digraph structs {
    node[shape=plaintext];
    put [fontcolor="black"];
    Lastest [fontcolor="blue"];
    Oldest [fontcolor="blue"];
    
    
    node[shape=box];
    struct0 [label= "5"];
    struct1 [label= "4"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label=<<s>1</s>>];
    struct5 [label= "6"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct5 -> struct0
        struct4
    }
    Lastest -> struct5;
    Oldest -> struct3;
    put -> struct5
}

[測驗 3](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3)

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