110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

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

試卷資訊

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

選擇題 (0)

申論題 (15)

1. (10%) Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

(a) (6%) What are the minimum and maximum numbers of elements in a heap of height h?

(b) (4%) What is the height of the heap with n elements?

3. (10%) Draw a binary tree that contains the letters: "b", "u", "o","s", "n", such that the inorder traversal spells "bonus" and the preorder traversal spells "obuns".

(a) (6%) For each of the three methods above (foo(), goo(), and poo(), what is the exact runtime for each method (in steps) in terms of A,B,C, and N? You should not count loop related operations.

(b) (4%) For N = 100, which one is the fastest algorithm? Why?

(c) (6%) Assuming that A, B, and C are constants, what is the asymptotic runtime of each method in terms of N?

(d) (4%) As N grows infinitely large, which one is the fastest algorithm?

(a) Queue [5%]

(b) Circularly Linked List [5%]

(c) Minimum Spanning Tree [5%]

(d) Breadth-First Search [5%]

6. [10%] Please write a recursive function F(n) to calculate Fibonacci numbers. (note: F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2))

7. [10%] Assume that a hash function (h(key)- key mod 8) is used for a chained hash table with linked lists, where linked lists can be used to handle the collision due to hash function. If we insert 10 items whose keys are 8, 9, 13, 17, 10, 15, 20, 16, 25 and 26 to an empty chained bash table with linked lists, what are the execution results of the hash table?

8. [10%] Please write the quick-sort code to sort n items and explain its average and worst-case time complexity.