資料結構 < 王致強老師精選 > 高一 給定一個遞迴時間關係式 Θ 1, 1, 1 點請說明在下列情況之下,T(n) 的時間複雜度為何? ( 一 ) a<c ( 二 ) a=c ( 三 ) a>c 解 ( 一 ) a<c 時,n Ω, 故 T(n)=n ( 二 ) a=c 時,n Θ, 故 Θ Θ nlogn ( 三 ) a>c 時,n O, 故 Θ 說明 : 使用 Master method 二 有一時間關係式 T(n) T( n ) lgn, 請問 T(n) 的 tight bound 為何? 解 高取 n m m m, 遞迴式可以表示成 T( ) T( ) m, 再取 m k k k 1 k, 遞迴式可以表示成 T( ) T( ), k 令 ak T( ), 得 a 1 k k ak 特微方程式 (r-) =0, 解得 r=( 二重根 ) k k k 通解為 T( ) ak ( c1 k c) ( 上k ) 故 T(n)= ((loglogn)(logn)) 三 下面是 Ackermann s Function 的定義 1, 0, 1,1, 0 0 1,, 1, / ( 一 ) 請使用熟悉的語言寫出此遞迴程式 ( 二 ) 請問 A(,) 的結果為何? ( 三 ) 計算 A(,) 的過程, 函數 A 總共被呼叫中了多少次? ( 四 ) 請問 A(3,3) 的計算結果為何? 解 ( 一 ) 使用者 C 語言撰寫如下 int ack(int m, int n) { if (m==0) return n+1; else if (n==0) return ack(m-1,1); else return ack(m-1,ack(m,n-1)); } ( 二 ) A(,) 的結果為 7 ( 三 ) 計算 A(,) 的過程, 函數 A 總共被呼叫 7 次 ( 四 ) A(3,3)=61 1-1
四 請回答下面問題高( 一 ) 如果後序追踪順序為 HJFGDECA; 中序追踪為 HJAFDGCE, 請逐步重建二元樹 ( 二 ) 重建完成後, 請為此二元樹加上中序引線 ( 三 ) N 個節點的四元樹 (Quad Tree), 其高度最小為何? 假設樹根在 Level 1 ( 四 ) 為何樹常會轉換成以二元樹的方式來表示? 解 ( 一 ) postorder : HJFGDECA 樹根點inorder: HJAFDGCE A postorder:hj postorder:fgdec inorder: HJ inorder: FDGCE 處理 A 的左子樹 A postorder:fgdec 高inorder: FDGCE H J 處理 A 的右子樹 A 上C H J postorder:fgd postorder:e inorder: FDG inorder: E 處理 C 的左子樹, 得到最後二元樹 A C H J D E F G 1-
( 二 ) Threaded binary tree 如下, 其中虛線為 threads: 高A 首節點 C 點H J D E F G h 4-1 N+ 3 ( 三 ) N 個節點的 Quad Tree 高度為 h, 則 4(h - 1) + 1 N, 故 élog 4 (3N 1) ù + h 3 ê ú êë 4 ú û ( 四 ) 假設 order 為 k 的樹有 n 個節點, 則整棵樹的指標總數 =k n, 有用的指標為 n-1 個故空指標總數 = k n-(n-1)=(k-1)n+1 高空指標總數 (k 1) n 1 指標浪費率 = 指標總數 k n (k 1) n 1 = k n k n = k 1 1 k 1 k k n k 上1 當 k= 時 ( 即 binary tree 時 ), 指標浪費率, 為最小值 故以 binary tree 來表示樹 ( 或森林 ), 可以降低指標浪費率 五 一個二元樹如下, 請找出其前序引線二元樹與後序引線二元樹 A C D E F G H I J 1-3
解 高preorder seq.: ADECFHJIG header node A C 點D E F G H I J pre-threaded binary tree postorder seq.: DEJHIFGCA header node 高A C D E F G H I 上J post-threaded binary tree 六 ( 一 ) 請針對字串 ACADAA 編出它的 Huffman code, 寫出各符號碼, 並計算平均一個符號需要幾個位元 ( 二 ) 若有一套 Huffman code 如下 : A: 11, : 10, C: 001, D:000, E:01 請對下面訊息解碼 1000111011101000 解 ( 一 ) 先統計各字元的出現頻率字元 A C D 頻率 4 1 1 1-4
建立的 Huffman coding tree 如下 : 高8 0 1 A 4 0 1 0 1 C D 點Huffman coding table 如下 : 字元 A C D code 0 10 110 111 4 1 1 平均一個符號需要的位元數 = 1 8+ 8+3 8+3 8=1.75 bits ( 二 ) 解碼得到字串 :CAEAED 七 下面優先次序表之中有 6 個運算符號 : +. -, =, *, /,!, 整數值愈大代表愈優 symbol operator precedence associativity! unary 4 right 高to left * / binary 3 left to right - + binary right to left = binary 1 right to left 給予運算式 A = = C + D * E / F!! G * H ( 一 ) 請繪出運算式的算式樹 ( 二 ) 請說明如何得到此運算式的前置式與後置式 上( 三 ) 如果輸入一個前置式, 請設計一個建立算式樹的遞迴程序 解 ( 一 ) = A = + C - / * * F! H D E! ( 二 ) 對算式樹做前序追踪可得前置式 : =A=+C-/*DEF*!!GH 對算式樹做後序追踪可得後置式 : ACDE*F/G!!H*-+== G 1-5
( 三 ) 高TreePtr TreeConst() { TreePtr p; p = getnode(); p->data = gettoken(); if (IsOperand(p->data)) p->left = p->right =NULL; else { p->left = TreeConst(); 點p->right = TreeConst(); } return p; } 八 ( 一 ) 下面圖形是否可以找到 Eularian Cycle? 為什麼? 高( 二 ) 如果一個圖形找 Eularian Cycle, 但最後不用回到起點, 其條件為何? ( 三 ) 如果有一個圖形所有頂點的 degree 皆為 0~3 之間, 邊總共有 8 個 :degree 為 0 的頂點有 3 個 ;degree 為 1 的頂點有 個 ;degree 為 的頂點有 4 個 ;degree 為 3 的頂點可以有幾個? 上 解 ( 一 ) 可以, 因為所有頂點的 degree 皆為偶數 ( 二 ) 不用回到起點, 只有起點與終點為 odd degree, 其餘頂點須為 even degree ( 三 ) 0*3+1*+*4+3*x=*e, 其中 x 為 degree=3 的頂點人田戈口數,e 為邊的總數 解得 10+3x=*8, 故 x=3 九 若一棵二元搜尋樹一開始時是空的 ( 一 ) 依序插入資料 44 69 94 81 18 37 7 58 1 43 5 31 0 7, 請在圖 4 框中畫出此二元搜尋樹 ( 二 ) 接著若再刪除 37, 且刪除處理之後樹的高度減少 1, 請畫出此二元搜尋樹 1-6
解 ( 一 ) ( 二 ) 44 18 7 37 58 1 5 43 0 31 7 44 18 7 31 58 1 5 43 高69 81 69 81 點 高上94 94 0 7 1-7
十 ( 一 ) 假設資料輸入的順序如下 : 60, 80, 30, 90, 70, 100, 40, 0, 50, 10 請以 -3-4 樹儲存, 並列出結果 ( 二 ) 如下圖所示之 -3 樹 (-3 tree): 1. 若連續刪除 (Delete) 鍵值 (Key)58,65,55,40, 此 -3 樹之變化為何? 請依序用圖表示. 若從圖中直接刪除鍵值 50, 此 -3 樹之變化為何? 請用圖表示 點50 30 60,70 高0 0 40 70 90 100 40 50 70 90 100 10 40 55,58 65 75,80 30 60 80 插入 90 先 split root, 再插入 90 高60 60 => 30 80 30 80 90 插入 70 60 上30 70 80 90 插入 100 先 split node(70,80,90), 再插入 100 60 80 60 80 30 70 90 => 30 70 90 100 插入 40, 0 60 80 0 30 40 70 90 100 插入 50 先 split node(0,30,40), 再插入 50 30 60 80 30 60 80 => 解 ( 一 ) 插入 60, 80, 30 1-8
插入 10 先 split root(30,60,80), 再插入 10 ( 二 ) 1. 刪除 58 刪除 65 刪除 55 刪除 40 58 65 75,80 10 40 高60 30 80 10 0 40 50 70 90 100 點50 30 60,70 10 40 55 65 75,80 50 高30 60,75 10 40 55 70 80 50 上30 75 10 40 60,70 80 50,75 10,30 60,70 80 55 30 60,70. 刪除 50, 將 55 移動以取代 50, 轉換為刪除原 55 所在節點的一個 key 1-9
十一 試利用 ( 一 ) 深度優先搜尋 (Depth First Search) 及 ( 二 ) 廣度優先搜尋 (readth First Search) 求出下圖的擴展樹 (Spanning Tree), 並分別列出各節點之優先搜尋順序 高1 3 點4 5 6 7 8 解 ( 一 ) 深度優先搜尋 (Depth First Search):1,, 4, 8, 5, 6, 3, 7 ( 本題答案非唯一 ) 深度優先擴展樹如下 : 1 3 高4 5 6 7 8 上( 二 ) 廣度優先搜尋 (readth First Search):1,, 3, 4, 5, 6, 7, 8( 本題答案非唯一 ) 廣度優先擴展樹如下 : 1 3 4 5 6 7 8 1-10
十二 如果 G 代表一無向圖 (Undirected graph) 高的定義 : V(G) = {1,,3,4,5,6,7,8} E(G) = {(1,),(1,3),(,4),(,5),(3,6),(3,7),(4,5),(4,6),(5,5),(6,7),(7,8)} 其中 V(G) 為 G 之節點 (Vertices) 集合,E(G) 為邊線 (Edges) 集合 ( 一 ) 指出該定義有一不合法的邊線並說明原因 ( 二 ) 剔除該不合法的邊線後, 依節點編號次序編製, 寫出該無向圖的鄰接矩陣 (Adjacency matrix) 點( 三 ) 寫出其中任兩個不同的跨距樹 (Spanning tree) 解 ( 一 )(5,5) 為不合法, 因為圖形中一般不能有自我迴路 (self-loop) 註 : 沒有自我迴路的圖形稱為簡單圖形 (simple graph) ( 二 ) 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 ( 三 ) 只要使用 V -1 個 edges, 構成一個 connected acyclic 高graph 即為 spanning tree 原圖形為 1 3 上4 5 6 7 8 兩棵 spanning trees 可以為 ( 答案不只一組 ) 1 1 3 3 4 5 6 7 4 5 6 7 8 8 1-11
十三 高( 一 ) 說明什麼是優先權佇列 (priority queue) 的作用 ( 二 ) 試比較使用陣列 (array), 線性串列 (linked list), 和樹 (tree) 來表現優先權佇列 解 ( 一 ) 優先權佇列是一種抽象資料結構, 須支援兩個運算 : 加入新資料與刪除最大資料 ( 二 ) ( 二 ) 二元搜尋法 (inary search) 表現方式加入新資料刪除最大資料點陣列 ( 資料不排序 ) 將新資料加在末端即可, 時間 O(1) 須搜尋出最大資料再予以刪除, 時間 O(n) 陣列 ( 資料由小而大排序 ) 須按由小而大次序插入新資料, 時刪除最後一項資料即可, 時間 O(1) 間 O(n) 鏈結串列 ( 資料不排序 ) 將新資料加在串列開頭即可, 時間須搜尋出最大資料再予以刪除, 時 O(1) 間 O(n) 鏈結串列 ( 資料由小而大 須按由大而小次序插入新資料, 時 刪除第一項資料即可, 時間 O(1) 排序 ) 間 O(n) 最大堆積將資料加入最尾部, 向上調整, 時刪除樹根, 再進行調整, 時間間 O(logn) O(logn) 十四 請比較 Insertion sort ubble sort Selection sort Shell sort Quick sort Merge sort Heap sort MSD radix sort LSD radix sort 高 Count sort Distribution Counting sort 的時間複雜度 穩定性與額外儲存空間 解 additional Type name best case worst time average time stability storage O(n) O(n) Insertion O(n 排序好的資料反轉的資料 ) stable a little 上O(n) O(n) ubble O(n simple 排序好的資料反轉的資料 ) stable a little Selection O(n ) O(n) O(n 視實作方式而 ) a little 定 Shell O(nlogn) O(n) O(nlog n) unstable a little O(n) Quick O(nlogn) 排序好的資 O(nlogn) unstable O(log n)~(n) advanced 料 Merge O(nlogn) O(nlogn) O(nlogn) stable O(n) Heap O(nlogn) O(nlogn) O(nlogn) unstable a little O(nd) O(nlogn) 視實作方式而 MSD 資料分佈不 O(nd) radix 平均分佈資料定均 O(n) LSD O(d(n+r)) O(d(n+r)) O(d(n+r)) stable O(n+r) Count O(n ) O(n) O(n ) stable O(n) counting Distribution sort O(n+m) O(n+m) O(n+m) stable O(n+m) Couting 十五 請說明以下四種搜尋 (Search) 方法的基本原理, 並分別比較其優缺點 ( 一 ) 循序搜尋法 (Sequential search) 1-1
( 三 ) 內插搜尋法 (Interpolation search) 高( 四 ) 費氏搜尋法 (Fibonacci search) 解 基本原理優點缺點循序搜尋法由第一項資料開始, 逐一 1. 資料不需要先排序過 ; 搜尋資料 使用鏈結串列也可以. 適合動態資料 點3. 適合少量資料搜尋 二元搜尋法 1. 須先排序好資料, 並置時間複雜度為 O(logn), 於隨機存取記憶體 適合大量資料之搜尋. 取中間項比較, 相等則找到 ; 若小於中間項則往前半段繼續搜尋 ; 若大於中間項, 則往後半段繼續搜尋 內插搜尋法以 Fibonacci Number 之特 1. 時間複雜度為 O(logn), 性, 取中間項, 原理與二適合大量資料之搜尋 分搜尋法相同. 實作不需要使用除法運算, 只需要用到加減法高, 比二分搜尋法好 overhead 較高 費氏搜尋法以線性內插法之特性, 取時間複雜度為中間項, 原理與二分搜尋 O(loglogn), 適合大量資法相同料之搜尋 適合平均分佈之資料搜尋 上十六 試繪一 AVL 樹, 由空樹開始, 依序加入下列節點 50,60,6,79,,11,17,19,97,71,65,75,41,51,61,63 ( 一 ) 試表示出在建立此樹時, 每一旋轉 (Rotation) 前後之結構 ( 二 ) 欲在上述之 AVL 樹中去除 60 及 71 兩節點, 試分別表示出消除後之 AVL 樹 解 ( 一 ) 插入 50,60,6 之後進行 RR 旋轉 50 60 R 60 50 6 R 6 時間複雜度為 O(n), 大量資料時, 較費時間 1. 資料需要先排序過 ; 須使用陣列. 不適合動態資料 3. 使用除法計算中間項位置, 在少量資料搜尋時,overhead 較高 1. 資料需要先排序過 ; 須使用陣列. 不適合動態資料 3. 少量資料搜尋時, 資料需要先排序過 ; 須使用陣列 不適合動態資料 使用內插法計算中間項位置, 在少量資料搜尋時, overhead 最高 資料分佈平均時, 可能會與線性搜尋時間相同, 達到 O(n) 1-13
插入 79,,11 之後進行 LL 旋轉高60 60 50 6 L 6 79 L 11 50 79 點11 插入 17,19 之後進行 RR 旋轉 60 6 11 50 79 R 17 R 19 高插入 97 之後進行 RR 旋轉 60 6 R 17 50 79 上R 11 19 97 插入 71,65 之後進行 RL 旋轉 60 79 17 50 6 97 R 11 19 L 71 65 1-14
插入 75 之後進行 RL 旋轉高60 79 L 17 50 65 97 R 11 19 6 點71 75 插入 41,51,61 之後進行 LR 旋轉 60 71 17 50 65 L 79 11 19 4151 6 75 L 97 61 高插入 63 之後完成 60 71 上17 50 6 79 11 19 41 51 61 65 75 97 63 ( 二 ) 61 61 71 75 17 50 63 79 17 50 63 79 11 19 41 51 6 65 75 97 11 19 41 51 6 65 97 十七 -3-4 tree 與 red-black tree 間的轉換 ( 一 ) 試繪一棵 -3-4 樹, 由空樹開始, 依序加入下列節點 A D I A M O N D I S F O R E V E R ( 二 ) 請將此 -3-4 樹轉換成為 red-black tree 1-15
解 ( 一 )-3-4 tree 如下 : ( 二 ) 高I O D E M R A A D E F I N O R S V 點I D O A E M R A D F I N O S E R V 高上 Insert 1 1 Insert 3 1 3 十八 有關紅黑樹的問題 ( 一 ) 請說明 red-black tree 的重要特性 ( 二 ) 請將 1 3 7 5 8 9 11 10 插入一棵空的 red-black tree, 請繪出過程的樹 ( 三 ) 從 ( 二 ) 的 red-black tree 中刪除 7 與 9, 請繪出過程的樹 解 ( 一 ) 紅黑樹 (Red-lack tree) 是 -3-4 tree 的一種二元樹的表示法 red-black tree 的特點 : 1. 每一條由 root 到任一個 leaf 的 path 上面, 其 black nodes 的數目是相同的. 由 root 到任一個 leaf 的 path 上, 不可以有兩個連續的 red nodes 3.root 是 black node 4.failure nodes 是 black nodes ( 二 ) Insert 1-16
Insert 7 Insert 5 Insert 8 Insert 9 1 3 7 1 5 1 1 3 7 5 3 7 高點高上5 8 3 8 7 9 1-17
Insert 11 Insert 10 ( 三 ) Delete 7 Delete 9 高5 8 1 3 7 9 11 5 8 1 3 7 10 9 11 5 9 1 3 8 10 11 5 點高上1 3 8 11 1-18
3 1 3 6 5 V7 十九 ( 一 ) 請敘述 Kruskal 演算法, 此演算法用於求一個圖高(graph) 之最小跨越樹 ( 二 ) 圖一之最小跨越樹為何? A 11 16 6 1 step 5 0 14 F C 0 9 點5 E 13 D 解 ( 一 ) T Φ; while T 中少於 n-1 個 edges 且 E is not empty do begin (v,w) E 中 weight 最低的 edge; delete (v,w) from E; if (v,w) 不會造成 T 中的迴路 then add (v,w) to T else discard (v,w) end; if T 中的 edges 數少於 n-1 then not_found; 高( 二 ) A 11 16 6 1 14 F C 0 9 上5 E 13 D 二十 請求出下圖中 V1 到 V6 的最短路徑 ( 需將過程寫出 ) 解 最短路徑為 V1 -> V4 -> V7 -> V6 Dist V1 V V3 V4 V5 V6 V7 selected initial 0 1 V1 step 1 0 3 1 3 9 5 V4 step 0 3 1 3 9 5 V step 3 0 3 1 3 8 5 V3 step 4 0 3 1 3 8 5 V5 1-19
廿一 高( 一 ) 請用串列來表示下面多項式 8 4 6 4 6 4 Px,y,z ( ) = 3xyz + 5xyz + 4xyz + xyz ( 二 ) 請宣告節點結構, 並解釋所使用的結構的各欄位 解 ( 一 ) 點var z - ptr 1 nil var y - ptr nil var y - ptr 4 ptr nil var x - no 1 4 nil var x - no 3 8 no 5 6 nil var x - no 4 6 nil ( 二 ) 節點結構定義如下 : typedef enum {varname, coeficient, sublist} triple; typedef struct ListNode * ListPtr; struct ListNode { triple tag; union 高{ char vname; // 當 tag=varname 時, 存放變數名稱 float coef; // 當 tag=coeficient 時, 存放係數 ListPtr ptr; // 當 tag=coeficient 時, 存放 sublist 指標 }; int exp; // 存放冪數 ListPtr link; // }; 上 1-0