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

科目：研究所、轉學考(插大)◆資料結構與演算法 | 年份：108年 | 選擇題數：0 | 申論題數：8

試卷資訊

所屬科目：研究所、轉學考(插大)◆資料結構與演算法

選擇題 (0)

申論題 (8)

1. (5分) 說明 int list[5], int plist[5], int *pplist[5] 的差别。
(5分) 說明系統堆疊的內容和運作原理。
2. (10分)使用以下 inorder 敘述來呈現 preorder, postorder, and level order:
AB+C/D+EF
3. (10分)請說明設計老鼠走迷宮的演算法，包含以下問題：

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:

Fn=0 if n=0; Fn=1 if n=1; Fn=1 if n=2; Fn=2Fn-1+ Fn-2+ Fn-3 if n≥3.
Design an O(lg n)-time algorithm to compute Fn.
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.
8. (10分) Run Insertion Sort on the following array: (7,6,5,4,2,3,1) step by step.