---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)

---

# 2024q1 Homework2 (quiz1+2)
contributed by < [tintinjian12999](https://github.com/tintinjian12999) >

## 第 1 週測驗題
[2024q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### 測驗 `1`
#### 解釋程式碼運行
在 
```c
void quick_sort(node_t **list)
```
中會將比 `pivot` 大的數存入 right 中，比  `pivot` 小或相等的數則存入 left 中
```c
while (p) {
    node_t *n = p;
    p = n->next;
    list_add(n->value > value ? &right : &left, n);
}
```
而 begin 與 end 則用 
```c
//left, pivot, right
begin[i], begin[i + 1], begin[i + 2]
end[i], end[i + 1], end[i + 2]
```
來儲存 left, pivot, right 節點的開頭與結尾
```c
begin[i] = left;
end[i] = list_tail(left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(right);
```
程式的執行過程如下
假設需排序的序列如下
```graphviz
digraph structs {
    node[shape=plaintext];
    
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "1"];
    struct2 [label= "3"];
    struct3 [label= "5"];
    struct4 [label= "2"];
    struct5 [label= "7"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
        struct4 -> struct5
        
    }


}
```
則迭代過程為
```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 0\l"];
    pivot
    left
    right
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "1"];
    struct2 [label= "3"];
    struct3 [label= "5"];
    struct4 [label= "2"];
    struct5 [label= "7"];
    {
        rank="same";
        pivot -> struct0
    }
    
    {
        rank="same";
        left -> struct4 -> struct2 -> struct1
    }
    
    {
        rank="same";
        right -> struct3 -> struct5 
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 2\l"];
    pivot
    left
    right
    node[shape=box];
    struct3 [label= "5"];
    struct5 [label= "7"];
    NULL [label = "NULL"];
    {
        rank="same";
        pivot -> struct3
    }
    
    {
        rank="same";
        left -> NULL
    }
    
    {
        rank="same";
        right -> struct5
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 4\l"];
    result [fontcolor="blue"];
    node[shape=box];
    struct5 [label= "7"] [fontcolor="blue"];

    
    {
        rank="same";
        result -> struct5
    }

}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 3\l"];

    result [fontcolor="blue"];
    node[shape=box];
    struct3 [label= "5"][fontcolor="blue"];
    struct5 [label= "7"][fontcolor="blue"];

    
    {
        rank="same";
        result -> struct3 -> struct5
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 2\l"];
    LNULL [label="L = NULL"];
    i [label="i--"][fontcolor = "red"];
    {
        rank="same";
        LNULL -> i
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 1\l"];
    result [fontcolor="blue"];
    node[shape=box];
    struct3 [label= "5"][fontcolor="blue"];
    struct4 [label= "4"][fontcolor="blue"];
    struct5 [label= "7"][fontcolor="blue"];  
    {
        rank="same";
        result -> struct4 -> struct3 -> struct5
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 0\l"];
    pivot
    left
    right
    node[shape=box];
    struct1 [label= "1"];
    struct2 [label= "3"];
    struct4 [label= "2"];

    {
        rank="same";
        pivot -> struct4
    }
    
    {
        rank="same";
        left -> struct1
    }
    
    {
        rank="same";
        right -> struct2
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 2\l"];
    result [fontcolor="blue"];
    node[shape=box];
    struct2 [label= "3"][fontcolor="blue"];
    struct3 [label= "5"][fontcolor="blue"];
    struct4 [label= "4"][fontcolor="blue"];
    struct5 [label= "7"][fontcolor="blue"];  
    {
        rank="same";
        result -> struct2 -> struct4 -> struct3 -> struct5
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 1\l"];
    result [fontcolor="blue"];
    node[shape=box];
    struct1 [label= "2"][fontcolor="blue"];
    struct2 [label= "3"][fontcolor="blue"];
    struct3 [label= "5"][fontcolor="blue"];
    struct4 [label= "4"][fontcolor="blue"];
    struct5 [label= "7"][fontcolor="blue"];  
    {
        rank="same";
        result -> struct1 -> struct2 -> struct4 -> struct3 -> struct5
    }
}
```

```graphviz
digraph structs {
    node[shape=plaintext];
    iter [label = "i = 0\l"];
    result [fontcolor="blue"];
    node[shape=box];
    struct0 [label= "1"][fontcolor="blue"];
    struct1 [label= "2"][fontcolor="blue"];
    struct2 [label= "3"][fontcolor="blue"];
    struct3 [label= "5"][fontcolor="blue"];
    struct4 [label= "4"][fontcolor="blue"];
    struct5 [label= "7"][fontcolor="blue"];  
    {
        rank="same";
        result -> struct0 -> struct1 -> struct2 -> struct4 -> struct3 -> struct5
    }
}
```
#### 使用 Linux 核心風格的 List API 改寫上述程式碼



### 測驗 `2`


## 第 2 週測驗題
[2024q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗 `1`
這裡最重要的實作是使用 hash table 來實現在 inorder 裡尋找對應元素的過程。
在 `find` 裡有以下實作
```c
int hash = (num < 0 ? -num : num) % size;
hlist_for_each (p, &heads[hash]) {
    struct order_node *on = container_of(p, struct order_node, node);
    if (num == on->val)
        return on->idx;
}
```
透過 `hlist_for_each` 走訪 hash table 上的 linked list，如此比起直接走訪整個 inorder 的元素來得更有效率。
接著 `dfs` 透過遞迴的方式將左節點與右節點依序接上，如下圖所示
```graphviz
digraph BST {
    node [];
    root1  [ label = "3" ];
    left1 [ label = "9" ];
    right1 [ label = "20,15,7" ];

    root1  -> { left1 right1 };
    
    l3  [ label = "3" ];
    l4 [ label = "9" ];
    l5 [ label = "20" ];
    l6 [ label = "7" ];
    l7 [ label = "15" ];

    l3  -> { l4 l5 };
    l5->{ l6 l7};
}
```
### 測驗 `2`


### 測驗 `3`
