110年 - 110 國立清華大學碩士班考試入學試題_生命科學院/丙組(計算生物與人工智慧組):計算機概論(演算法與計算機數學)#104514

科目：研究所、轉學考(插大)、學士後-計算機概論 | 年份：110年 | 選擇題數：0 | 申論題數：13

試卷資訊

所屬科目：研究所、轉學考(插大)、學士後-計算機概論

選擇題 (0)

申論題 (13)

(a) Please explain what a recursive function is. (6%)

(b) Write a recursive function sum(n) to return the summation of the sequence of consecutive integers from 1 to n using any programming language or pseudo- code.(10%)

2. (16%) Please propose an algorithm that can find the intersection between two arrays consisting of m and n integers respectively with time complexity better than O(mn) (8%) and analyze its time complexity. (8%)

(a) This tree can be used to find out all subsets of {W₁, W₂, W₃}that sum to W(the sum-of-subscts problem); please explain what this tree represents and how it works to solve this problem. (6%)

(b) Consider another sum-of-subsets problem with n = 4, W =13, and w₁= 3, w₂ = 4, w₃ = 5, w₄ = 6. Use a similar tree as above, give a strategy to avoid searching every possible traversing route in the tree, and show that it can still get to the correct answer. (10%)

(a) Please design a reflection transformation matrix (T) that can map [x1 x2] to [X1-X2].(4%)

(b) What are the eigenvalues and corresponding eigenvectors of T? (4%)

(c) What is the inverse of T? (4%)

(d) Please calculate . (4%)

5. (8%) Please convert the following infix expression to postfix expression with a stack. Please illustrate the step-by-step operations.

(a) Given a sequence of integers: 28, 5, 32, 44, 12, 35, 69, 57, 1, please insert them sequentially (i.e., first inserting 28, then 5, and so on) into an initially empty binary search tree and draw the resulting binary search tree. (12%)

(b) Suppose there are n numbers in the binary search tree, what is the worst-case time complexity of searching a number in it? Please answer with big-O notation and give an example when such worst case happens. (8%)

(c) Please draw the resulting binary search tree after deleting 32 from the tree constructed in (a).(8%)