109年 - 109 國立高雄大學_碩士班招生考試_資訊工程學系：資料結構#103082

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

試卷資訊

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

選擇題 (0)

申論題 (15)

(a) Θ(n)

(b) Θ(n ²)

(c) Θ(n³ )

(d) Θ(n ⁿ)

(a) Θ(nⁿ )

(b) Θ(n ²)

(c) Θ(log n)

(d) Θ(n)

3. Show that n! = O(nⁿ) by applying the definition (not using limits). (10%)

4. A palindrome is a string that can be read backwards, and forwards with the same result. For instance, the following string is a palindrome
abbbdacadbbba
Write an algorithm in pseudocode using a stack to test if a string is a palindrome. (20%)

5. For the max-heap below, draw the resultant max-heap from adding 65 and deleting the maximum element (in this order). Show the detailed steps. (20%)

(a) For the following data sequence:
5, 9, 3, 15, 2, 17
Show how to generate the binary search tree. (10%)

(b) Using the binary search tree constructed from (a), show the detailed steps about how to find which integer is closest to 8. (Hint: you may use any meaningful distance metric for computing the distance between two values.) (10%)

(c) The question in (b) is for finding the nearest neighbor of a given 1-dimensional instance. Now suppose you are given the following six 2-dimensional instances:
(5, 7), (9, 4), (3, 6), (15, 2), (2, 5), (17, 8)
Show how to generate the k-d tree (k-dimensional tree), where k = 2. (10%)

(d) Show how to use the k-d tree from (c) to find the nearest neighbor of (14,3). (Hint: you may use Euclidean distance for computing the distance between any pair of 2-dimensional instances.) (10%)