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

(a) What is the completion time of process Pi using a nonpreemptive priority (a smaller priority number implies a higher priority) scheduling?

(b) What is the average waiting time using shortest-job-first scheduling?

2. A machine has 64-bit virtual addresses and 32-bit physical addresses. Pages are 32 KB. How many entries are needed for the page table?

(a) f

(b)

4. What would be the output of the following C program that uses the Pthreads API? (Nole that the line
mumbers are for reference only.)

(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) SSTF

(b) SCAN

(c) LOOK

(d) C-SCAN

(e) C-LOOK

7. Given the following weighted graph, show the order in which the edges are added to the minimnum cost spanning tree using Kruskal's algorithm. (Use weight to represent edges in your answer and just show the order.)

8. Show the Hufinan tree created from the following nodes arranged in a priority queue.

9. For any input of size n and assuming that ki denotes the maximum number of digits and Iz the number of buckets, what is the average-case running time of each of the following sorting algorithms: (a) selection sort, (b) merge sort, (c) heap sort, (d) radix sort, and (e) bucket sort?

10. The Ackermann function A(m, n) is defined recursively for non-negative integers m and n as follows:

Its value grows very quickly, even for small values of m and n. For instance, A(4. 1) = 65533. What would
be the values of A(3.2) and A(2, 4)?

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

試卷資訊

選擇題 (0)

申論題 (17)