110年 - 110 國立臺灣大學_碩士班招生考試_生物機電工程學研究所丙組:資料結構(C)#100901

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

試卷資訊

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

選擇題 (0)

申論題 (7)

1. (10%) Write down the sequence of the 7 keys in the array that results after performing 3 successive delete-the-max opecrations on the following maximun-oriented binary heap of size 10:
97 82 89 3466 78 8515 28 51

2. (10%) Write down the sequence of the 13 keys in the array that results after inserting the sequence of 3 keys: 25 16 12
into the following maximum-oriented binary heap of size 10:
86 82 77 75 70 35 68 31 45 30

3. (20%) Write a pseudocode function that can re-construct a binary tree by using its preorder and inorder traversals. Please return the root of the binary tree as the output. Note: A node in a binary tree has two pointers, named 'lett' and 'right', respectively, where the 'left' pointer is used to find the left child of the node and the 'right' pointer is used to find the right child.

4. (20%) Write a pseudocode function that removes the nodes in even positions (the second, fourth, sixth, and so forth) in a given linked list. No return values are expected. Note: A node in a null-terminated linked list has one pointer, named 'next', that points to the next node if it is not null.

5. (20%) Given a reference that points to a node x in a doubly circular linked list. Please write a pseudocode function to delete the node x from the doubly circular linked list. No return values are expected. Note: A node in a doubly circular linked list has two pointers, named 'next' and 'prev', respectively, where the 'next' pointer is used to find the next node and the ' prev' pointer is used to find the previous

(10%) a. List both the advantages and disadvantages of adjacency list and adjacency matrix for the graph representation, respectively.

(10%) b. Analyze the complexity of depth-first search (DFS) on a graph represented by the adjacency list or adjacency matrix, respectively.