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

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

試卷資訊

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

選擇題 (0)

申論題 (27)

(1) Explain the two basic models of inter-process communication.

(2) When will a race condition occur?

(3) What are the three requirements that a critical-section solution should meet?

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

(5) When will priority inversion occur in process synchronization?

(1) What device deals with address translation? In which case we will not use this device?

(2) Please give two benefits of using paging.

(3) Does any system use the optimal page replacement method? Why or why not?

(4) Let average page-fault time and memory-access time be 70us and 250ns, respectively. What is the expected page-fault rate if we want to get effective access time smaller than 285ns? List your calculation.

(5) What is reentrant code?

(1) When a file is opened, what are the four items of file information kept in UNIX?

(2) Consider a disk queue with requests for I/O to blocks on cylinders 100, 185, 40, 120, 2, 138, 75 and 87. Let the disk head currently stay at cylinder 60, and the maximum cylinder be 200. Please give the results of SSTF and C-LOOK scheduling methods.

(3) How does the parity bit work in RAID?

(4) Give three methods for CPU to know whether data are ready in an I/O device.

(1) What is the principle of least privilege? How does Sun Microsystems OS implement it?

(2) Why language-based protection may not be secure?

(3) How do polymorphic and tunneling viruses bypass the detection of antivirus software?

(4) How does the digital-signature algorithm work?

(5) How does DDoS work?

(1) Consider a binary tree. Suppose that its DFS result is "c, b, e, f, d, h, i, g, k, a, j" while BFS result is "c, b, g, e, d, k, j, f, h, i, a". Please draw the tree.

(2) Given the postfix of an equation "2 4 + 6 x 98 - 3 5 + x -", please compute its result. List your calculation.

(3) What is a binary search tree? Explain its property.

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

(5) Show that the worst-case complexity of quicksort is O(끄?).

(1) Given an n-key B-tree with minimum degree t, what is the upper bound of tree height? Prove the correctness of your answer.

(2) What is a B*-tree?

(3) Given a binomial tree Bt, show that there are exactly C(k, 1) nodes at depth i, where C(k, ) denotes a combination function.