108年 - 108 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：資料結構與演算法#147274

1. (5分) 說明 int list[5], int plist[5], int *pplist[5] 的差别。
(5分) 說明系統堆疊的內容和運作原理。

2. (10分)使用以下 inorder 敘述來呈現 preorder, postorder, and level order:
AB+C/D+EF

a. 移動到終點

b. 解決死路

4. (20 分) 使用 linked list 完成以下 stack 程式
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));
// Your answer starts here
// add new_node to stack by top
}
int pop (node **top) { // assume top is not null
int value;
node deleting_node = top;
// Your answer starts here
// remove the deleting node from stack, get the value of deleting node
free(deleting_node);
return value;
}

5. (10 分) Find the Breadth-First-Search tree of the following graph. The starting vertex is a.

6. (15分) Fibonacci numbers: Their recursive definitions are as follows: \( F_n=0 \) if \( n=0 \); \( F_n=1 \) if \( n=1 \); \( F_n=1 \) if \( n=2 \); \( F_n = 2F_{n-1} + F_{n-2} + F_{n-3} \) if \( n \ge 3 \). Design an \( O(\lg n) \)-time algorithm to compute \( F_n \).

7. (15分) Describe an O(nlog n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.