110年 - 110 國立臺灣大學_碩士班招生考試_ 工程科學及海洋工程學研究所丁組:資料結構(A)#100759

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

試卷資訊

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

選擇題 (0)

申論題 (11)

1. (10 %) Write a recursive function isPrime that will return a Boolean value true if the given number is a prime number. Otherwise, it will return false.

2. (10 %) Write a function called removeNegativeNodes that traverses a singly linked list and deletes all nodes whose keys are negative.

3. (10 %) A binary tree has eight nodes. The inorder and postorder traversals of the tree are given below. Please draw the tree.

Inorder: NTUABHSG

Postorder: NUTHGSBA

4. (10 %) A binary search tree is a special instance of a graph. Describe (no code) an algorithm that takes a binary search tree as input and produces an adjacency list, which represents it as an undirected graph.

5. (10 %) Given that both x and y are positive variables that can grow arbitrarily large, prove that max

6. (10 %) What does the 2-3-4 tree on the right look like after remove(2)?

(a) (8%) Give the adjacency matrix representation.

(b) (7%) Draw the minimum spanning tree.

(a) (5%)Apply mergesort and trace it on arrays A=[I 6 25 30]and B=[3 14 28 32 36].

(b) (10%) Trace the heapsort as it sorts the following array into ascending order: [9 12 4 8 3 11 6 15].

9.(10 %) For the inputs (4, 11, 17, 14, 23, 8,31) and a hash function h(x) = x mod 7, show the linear probing hash table of size 7.