109年 - 109 國立臺北大學_日間學士班曁進修學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147498

1. Describe the algorithm for insertion of \( r \) as a right child of \( s \) in a threaded binary tree as shown in Figure 1.(14分)

(a). Column major 

(b) Row major.

3. Insert 17, 60, 24, 5, 7 and 66 into the AVL tree as shown in Figure 3. (14分)

4. 在一棵高度為 \( h(h = 0,1,2,\ldots) \) 的AVL tree中，高度為6之AVL tree最多可能有幾個nodes及最少可能有幾個nodes？(假設root之 \( h = 0 \) )(8分)

5. (A)在 C 語言中，int list[5] 和 int *plist[5] 的差別在哪裡，要如何將 int *plist[5] 實作為 2 維陣列？(5 分)

(B)將此 inorder statement : A*B+C*(D-E)/(F+H) 轉為 postorder，並畫出它的二元樹。須按照以左到右讀取順序來做，以達到單一解答。(5 分)

(C)設計一個算法使用 stack 來實現上述 inorder 轉 postorder，並且以上述 statement 說明如何使用 stack 來做轉換。(15 分)

(A)實作以下敘述 (5 分) 

(B)實作以下敘述(5 分) 

(A)如何搜尋八個方向來移動

(B)如何找到合法移動和出口

(C)解決死路問題