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

1. What would be the output of the following C program that uses the Ptbreads API? (Note that the line nunbers are for reference only.)

(a) What is an upper bound on the number of pige faults?

(b) What is a lower bound on the number of page faulls?

3. A computer whose proces esses have 2048 pages in their acldress spaces keeps its page tables in memory. The overhead required for reuding a w word from the pige table is 600 nsec. To reduce this overhead, the computer has a TLB, which holds 64 (page. frame) pairs and can do a lookup in 100 nsee. What hil rate is needed to reduce the mean overhead to 200 nsee or less

(a) What would be the size of the smallest file allowed in bytes?

(b) What would be the size of the largest file allorwed in bytes?

(a)How long does it take to sead a 300 block randomly placed file?

(b) How long does it take to read a 300 block clustered file?

6. Derlare in a single statement in C a pointer "p" w the arriy "int a [256] :" so ha p [1] is an alias of a [0]. p[2] is an alias of' a [1] , and so on, all the way up so that p [256] is an alias of a [255]

7. I The Ackermann Function . 1(mt.. ) is definedl reeursively for non-negative inegers s and n as Follows:

Its value grows very quickly, even for small values of m and n. For insiance. .A( 1. 1) = 65833. What would
be the value of .A(2.3)?

8. Assuming n = 2'". write out the closed form solution for the recurrence relation

9. Analyze the behavior of QUICKSORT in the case where a schizoplrenic advetsary picks the best pos- sible splitter (partitioning element) instead of the worst, every other time (ie., he alternates between best aund worst). What running time is induced by this "adversary?"

10. Transform the following expression to prefix and postfix.

(A+B)*(C+D-E)*F

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

試卷資訊

選擇題 (0)

申論題 (13)