108年 - 108 國立中山大學_碩士班招生考試_資工系(甲組#105764

(I) Given a prefix expression " *+ + (18)x(17)(16) x+x(15)(14) (13) (12)", convert it to an infix expression and calculate the result.

(2)What is simpl le uniforn rm hash shing? Given a a hash table with m slots that stores n elements, what is the expected time spent by a failed search if hash collisions a ions are solved by chaining?

(3) Except that every node is either red or black, how do you make a binary search tree become a red- black tree?

(4) Given n objects to be sorted, show the average-case r running time of the following algorithms: Heap sort, insertion sot, bubble sort, and quick sort.

(5) Given the adjacency matrix of an undirected graph:

Show the sequence of nodes that you visit by using breadth-first search and depth-first scarch. If
there are multiple choices to select nodes, just follow the alphabetical order.

(1) Given a directed graph G = (V, E), what is its strongly connected component?

(2) Using a B-tree to maintain disk blocks helps reduce the cost of disk access. Why?

(3) What is the difference between a B*-tree and a B*-tree?

(4) What are the two properties of a binomial-beap?

(5) Consider a Fibonacci heap as follows:

(1) What is a race condition? How to solve it?

(2) What is the difference between deadlock prevention and deadlock avoidance?

(3) When will you need to use a condition variable?

(4) What is the difference between asynchronous and deferred cancellation of a target thread?

(5) What are the four common conditions to cause process temination?

(1) Give two benefits of using paging.

(2) What are the working set and trashing?

(3) What is the difference betwe tween extemal al and internal fragmentation?

(4) What is the difference between synchronous and asynchronous IO?

(5) What are the four common registers for an I/O device?

(1) What is the principle of least privilege? How does Solaris 10 system implement it?

(2) What is the difference between a computer virus and a computer worm?

(3) Give two common solutions to deal with the sctuid-on problem in UNIX.

(4) What are masquerading and replay attack?

(5) What is the purpose of authentication? What is non-repudiation?

108年 - 108 國立中山大學_碩士班招生考試_資工系(甲組#105764

試卷資訊

選擇題 (0)

申論題 (25)