資訊處理 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

一般常用的算術運算式（Arithmetic Expression）有：中序運算式（Infix Expression）、前序運算式（Prefix Expression）、後序運算式（Postfix Expression）三種表示法，請回答下列問題： 考慮中序運算式 7 4 )3 / 9 5 ( )

給予如下二元樹節點的宣告，分別寫出C 的遞迴程式計算二元樹節點個 數及計算二元樹葉節點（leaves）個數（Count the number of nodes in a binary tree and count the number of leaf nodes in a binary tree, respectively）。（25 分） struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void countTree(NODEPTR tree){ } void countLeaves(NODEPTR tree){ }

給定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 分）

6 ( × + + × − ，請說明其前序與後序運算式 分別為何？（8 分） 請說明為何中序運算式需要使用括號來輔助界定運算元的優先順序 而前序與後序運算式則無需括號？（7 分） 請說明如何利用一個堆疊（Stack）結構計算出一個後序運算式的值， 並以後序運算式a b × c + d c / −為例，其中a = 3, b = 5, c = 2, d = 6， 請逐步列出運算過程中堆疊的內容。（10 分） 二、以下是關於二元搜尋樹（Binary Search Tree）的問題： 請說明二元搜尋樹的定義？（5 分） 是否可以使用一個二元搜尋樹對鍵值（Key）來進行排序（Sorting）？ 如果不行，請解釋其原因。若可以，請描述作法及執行時間。（5 分） AVL 樹是一個基於二元搜尋樹的資料結構，請敘述AVL 樹的定義 並說明為何一個有n 個節點（鍵值）的AVL 樹其高度是O（log n）。 （5 分） 若將鍵值36、25、14、27、55、30 以依序加入的方式建構一個AVL 樹，請繪出每次加入後的AVL 樹。（10 分）

給予如下二元樹節點的宣告，寫一C 的遞迴程式swapTree（NODEPTR tree）將每一節點的左、右節點互換（Swap the left and right children of every node of a binary tree）。（25 分） struct node{ int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void swapTree(NODEPTR tree){ }

給定以相鄰矩陣（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 分）

優先佇列（Priority Qu 提供的功能有：加入 有最高優先權的資料物 有越高的優先權，加入 請說明如何利用優先 二元堆積（Binary H 定義。（6 分） 若我們分別使用排序 二元堆積三種資料結 三種方式在加入in 度。（6 分） 在考慮鍵值低的資料 稱為最小堆積（Min 請說明如何輸出所有 運算量）與鍵值小於

給予如下程式，假設x[] = [30, 75, 53, 47, 21, 94, 88, 39]，lb = 0，ub = 7， 請問執行完下列程式後，x[]的內容為何？（25 分） void divide&conquer(int x[], int lb, int ub, int *pj) { int a, down, temp, up; a = x[lb]; up = ub; down = lb; while(down < up){ while(x[down] <= a && down < ub) down++; while(x[up] > a) up--; if(down < up){ temp = x[down]; x[down] = x[up]; x[up] = temp; } } x[lb] = x[up]; x[up] = a; *pj = up; }

請將所給定數字藉由所指定雜湊函數依序置入雜湊表  若雜湊函數為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

一個圖形結構（Graph 一個有向圖（Directed 一個有向圖不具有迴 Acyclic Graph, DAG 種不同的拓樸排序 若在圖G 上由節點 請列出此一拓樸排序 一個有向圖若具有強 點u 與v 彼此可藉由 否具強連通性的方法 a d g ueue）用來管理具有優先權順序的 （Insert）任意資料物件，以及移 物件。我們在此假設鍵值（Key 入與移除功能分別命名為insert() 先佇列將資料物件以鍵值進行排 Heap）是一個實現優先佇列的資 序串列（Sorted List）、未排序串列 結構來實現有n 個資料物件的優 nsert()與移除remove_Min()功能 料物件有高的優先權的情況下， nimum Heap）。若給定一個最小堆 有鍵值小於或等於k 的資料物件 於或等於k 的資料物件之數量成線 h）中，若所有的邊都具有方向 d Graph）。 迴圈（Cycle）則稱為一個有向非 G），考慮下方的有向非循環圖G （Topological Sort）？（7 分） c 開始進行拓樸排序，並考慮字 序並說明方法與所需要的時間複 強連通性（Strong Connectivity） 由不同路徑相互連通。請提供一個 法，並說明其正確性與時間複雜 有向非循環圖G b c e f h i j 序的資料物件，主要 移除（Remove）具 y）越低的資料物件 )及remove_Min()。 排序。（5 分） 資料結構，請敘述其 列（Unsorted List）、 優先佇列，請比較這 能上所需的時間複雜 所使用的二元堆積 堆積與一個鍵值k， 件，而所花的時間（或 成線性比例。（8 分） ，則此圖形結構為 非循環圖（Directed G，請說明G 共有幾 字母順序進行排列， 複雜度。（8 分） ），則其中任意兩節 一個驗證一有向圖是 雜度。（10 分）

用G = (V, E)表示一個無方向性圖形，其中V 是點的集合，E 是一組節 點（Vertices）形成一個邊及對應權重（Weights）所組成的集合，例如： (0, 1, 28)表示節點0 至節點1 有一個邊，而且權重為28。今有一圖形G = (V, E)，V = {0, 1, 2, 3, 4, 5, 6}，E = {(0, 1, 27), (1, 2, 15), (2, 3, 11), (0, 5, 9), (1, 6, 13), (4, 5, 24), (4, 6, 23), (3, 4, 21), (3, 6, 17)}。請利用Kruskal 演算法 計算最小擴張樹（Minimum spanning tree）之最低權重或成本值。（25 分）

將下列六個鍵值: 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)