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

科目：研究所、轉學考(插大)-資料結構 | 年份：109年 | 選擇題數：0 | 申論題數：11

試卷資訊

所屬科目：研究所、轉學考(插大)-資料結構

選擇題 (0)

申論題 (11)

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分)
2. Obtain the position of the element \( a_{ij} \) in an upper triangular matrix as shown in Figure 2 where \( a_{00} \) is in the first position by using (a). Column major (b) Row major. (14分)
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 分)
6. 使用 linked list 實作 stack，運用以下 C 語言程式：
typedef struct node { int value; node *next;}
void push (node **top, int new_value) { // assume top is not null
node *new_node = (node *) malloc (sizeof (node));
//(A)實作以下敘述 (5 分)
// add new_node to stack by top
}
int pop (node **top) { // assume top is not null
int value;
node *deleting_node = *top;
//(B)實作以下敘述(5 分)
// remove the deleting node from stack, get the value of deleting node
free(deleting_node);
return value;
}
7. 使用 stack解決老鼠走迷宮問題 (Maze path search)，設計並描述如何實作，包含(15分)
(A)如何搜尋八個方向來移動
(B)如何找到合法移動和出口
(C)解決死路問題