資訊處理 108 年資料結構考古題

下列程式函式 doit()以C 語言語法呈現，用以對雙向鏈結串列（doubly linked list）進行處理。請依據該函式回答問題。 void doit(struct node **head){ struct node *temp = NULL; struct node *current = *head; while(current != NULL){ temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } if(temp != NULL) *head = temp->prev; } ㈠ 若X 指向一個雙向鏈結串列如下，其中X->prev 指向NULL，X->next 指向資料為21 的節點。請顯示並說明doit（&X）執行過後該串列變化 結果。（10 分） ㈡ 若X 指向一個雙向鏈結串列如下，其中X->prev 指向資料為17 的節點， X->next 指向資料為35 的節點。請顯示並說明doit（&X）執行過後該 串列的變化結果。（5 分） ㈢ 若X 指向一個環狀雙向鏈結串列（circular doubly linked list），請說明 doit（&X）是否仍能順利執行。（5 分） NULL NULL X 17 21 35 74 95 NULL NULL X 17 21 35 74 95

給定T 為一個以陣列表示的二元搜尋樹（binary search tree）。 ㈠ 若有一些介於1 及1,000 的正整數被儲存於T，且要搜尋數字364，請 說明搜尋過程是否有可能為3, 400, 388, 220, 267, 383, 382, 279, 364？ （5 分） ㈡ 若有一些介於1 及1,000 的正整數被儲存於T，且要搜尋數字364，請 說明搜尋過程是否有可能為926, 203, 912, 241, 913, 246, 364？（5 分） ㈢ 若對T 進行前序遍歷（pre-order traversal）的結果為30, 20, 10, 15, 25, 23, 39, 35, 42。請說明若以後序遍歷（post-order traversal），結果為何。（5 分） ㈣ 若對T 進行後序遍歷（post-order traversal）的結果為25, 20, 34, 37, 31, 49, 46, 57, 60, 52, 41。請說明若以中序遍歷（in-order traversal），結果為何。 （5 分） ㈤ 請說明可將二元搜尋樹T 轉換為最小堆積（min heap）的程序為何？（10 分）

給定以相鄰矩陣（adjacency matrix）表示的圖G，矩陣中的數字為相鄰兩 節點間的距離，若空白則代表兩節點不相鄰。 G a b c d e f g h j a 1 6 5 b 1 6 c 6 6 7 3 d 5 2 10 e 7 12 f 3 2 8 g 10 7 3 h 12 8 7 8 j 3 8 圖G ㈠ 請說明若以Kruskal’s 演算法建立最小生成樹（minimum spanning tree） 的過程中，依序被加入生成樹的邊。（5 分） ㈡ 請說明若以Prim’s 演算法建立最小生成樹（minimum spanning tree）的 過程中，依序被加入生成樹的邊。（5 分） ㈢ 請說明Dijkstra’s 演算法的用途，並說明該演算法應用上的限制。（10 分） ㈣ 請說明將圖G 從f 節點開始執行Dijkstra’s 演算法的過程並顯示節點加 入的順序。（10 分）

請將所給定數字藉由所指定雜湊函數依序置入雜湊表 ㈠ 若雜湊函數為H(k) = k mod 11，並以線性探測（linear probing）解決溢 位（overflow）問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12, 0, 21 依序置入11 桶（buckets）x 2 槽（slots）雜湊表的最終結果。 （10 分） ㈡ 若雜湊函數為H(k) = k mod 7，並以平方探測（quadratic probing）解決 溢位（overflow）問題，請顯示將15, 23, -12, 3, -8, 8, 9, 11, -3, -5, 14, 10, 25, 12 依序置入7 桶（buckets）x 2 槽（slots）雜湊表的最終結果。（10 分） A[.] 0 1 2 3 4 … 槽1 槽2

將下列六個鍵值: 33, 72, 71, 55, 112, 109 存入大小為19 的雜湊表（a hash table of size 19） 雜湊函數h 為: h(key) = key mod 19 分別用下面兩種衝突處理方式（collision handler）： ㈠間隔為1（offset of 1）（12 分） ㈡間隔為商（quotient-offset）（8 分） 請分別寫出兩個雜湊表；並在間隔為1 的雜湊表上，標示出一次聚集 （primary clustering）。 40 62 83 10 20 31 45 55 70 78 90 92 李四(LS) 趙六(CL) 王五 (WW) 張三 (CS)