103年 - 103 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105840

科目：中山◆資工◆作業系統與資料結構 | 年份：103年 | 選擇題數：0 | 申論題數：23

試卷資訊

所屬科目：中山◆資工◆作業系統與資料結構

選擇題 (0)

申論題 (23)

1.A computer has six tape drives, with n processes competing for them. Each process may need two drives. For which values of n is the system deadlock free?

(a)61e625883988c.jpg

(b) 61e625931bad0.jpg
(a) What is a lower bound on the number of page faults?
(b) What is an upper bound on the number of page faults?
(a) What would be the size of the smallest file allowed in bytes?
(b) What would be the size of the largest file allowed in bytes?
(a) How long does it take to read a 200 block randomly placed file?
(b) How long does it take to read a 200 block clustered file?
(1) A red-black tree is a binary search tree where every node is either red or black. What are the four properties of a red-black tree?
(2) Suppose that a red-black tree contains n internal nodes. What is its maximum height? What is the time to search one value? What is the time to find the maximum value?
(3) Do you think whether a red-black tree is balanced or not? Please give your reason.
(1) Suppose that each internal node of a tree has at most three children. Given the BFS sequence "iceodImfhjbgna" and the DFS sequence "icdbglemnofhaj" of the tree, please draw that tree.
(2) Given a postfix expression "8 3 2 + -493 / + *3*7 t", please translate it into an infix expression and give the calculation result.
(1) Given the following treap, please show the final result after inserting a node (D:9).
(2) Following (I), please show the final result after inserting a node (F:2).
(1) What are the two major characteristics of hash functions to make them be widely adopted in authentication applications?
(2) What is a hash collision? How can you solve this problem by chaining?
(3) What is a perfect hashing?
(1) What is a binomial heap?
(2) Please explain the two binomial-heap properties.
(3) Suppose that two binomial heap Hi and H2 have ni and n2 nodes, respectively. Then, what is the worst-case running time to unite H1 and H2?
(4) What is a Fibonacci heap?