changed a year ago  
Published Linked with GitHub

2024q1 Homework2 (quiz1+2)

contributed by < marsh-fish >

第一週測驗題

測驗 1

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

測驗 2

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

第二週測驗題

測驗 1

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

測驗 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

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

Select a repo