contributed by < johnny69527 > quiz1 - 測驗 1 實作中利用 begin 與 end 陣列模擬 recursive 的堆疊，並以排序串列長度 2 倍為堆疊的大小。 當測試資料量達到 1,000,000 時，因為 begin 與 end 陣列配置記憶體太大，發生 segmentation fault。 把 non recursive quick sort 整合到 lab0-c 在 lab0-c 中加入此 quick sort，使用 Linux 核心風格的 List API 改寫上述程式，並使用鏈結串列模擬堆疊，排除 segmentation fault。此變更使 quick sort 不是 in-place algorithms： typedef struct {

contributed by < johnny69527 > 開發環境 $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 Copyright (C) 2021 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu

contributed by < chunplusplus > 題目 解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等 futex 是 Linux 提供一個底層的同步功能, 可以用來實作上層同步工具。 程式碼中, 展示了用 atomic operators 實作 spinlock, 然後用 spinlock 和 futex 實作 mutex 和 condition variable。 測試方法中, 用 condition variable 實作出 clock_wait 和 node_wait。

題目 測驗 α − 1 S-Tree 是不完整的 AVL tree。以 insertion 為例，AVL tree 有 LL, RR, RL, LR 四個不平衡 case; 其中 LL, RR 需要 1 個 rotate 做 rebalance; RL, LR 需要 2 rotate 做 rebalance。 林軒田教授公開的 DSA 課程筆記 S-Tree 只分左傾 (對應 AVL 的 LL, LR) 和右傾 (對應 AVL 的 LL, LR) 兩個不平衡 case, 都只用一個 rotate 處理 rebalance。所以 S-Tree 並不能處理 LR 和 RL 不平衡。 以 LR 不平衡為例, S-Tree 經過 st_rotate_left 後, 只會轉為 RL 不平衡。

quiz2 測驗 1 解釋上述程式碼原理 假設輸入 x digraph structs { node [shape=record]; struct1 [label="0|...|0|1|x|...|x"];

contributed by < chunplusplus > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

contributed by < chunplusplus > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

quiz1 測驗 1 解釋上述程式碼運作原理 初始狀態： digraph { rankdir=LR head[shape=none] head -> 4 -> 1 -> 3 -> 5 -> 2 -> 7