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

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

試卷資訊

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

選擇題 (0)

申論題 (21)

(a) Please draw four Gantt charts to show the execution of all processes based on the following scheduling algorithms: First-come first-served (FCFS), round robin (RR with quantum = 1), shortest job first (SJF), and non-preemptive priority (where a smaller priority number indicates a higher priority).

(b) Calculate the turnaround time of each process in the four scheduling algorithms.

(c) Which of the algorithms results in the minimum average waiting time? Note that you should give your calculation.

2.(a) What are the four conditions to result in a deadlock? Please detail each condition in your answer.

(b) Will a deadlock necessarily arise when any of the four conditions occur? Why or why not? Please explain your reason.

(a) Please explain what is demand paging?

(b) To support demand paging, what are the two types of hardware will you require? Note that you should give the functionality of each hardware.

(c) Suppose that you design demand paging for an operating system. Assume that the memory-access time is 200 nanoseconds and the average page-fault time is 75 microseconds. If you want the effective access time for demand paging no larger than 230 nanoseconds, what will be the expected page-fault rate? You need to give your calculation.

4. In a multimedia system, SCAN-EDF is a popular disk scheduling scheme. Suppose that you have the following file requests (request, deadline, cylinder):

(A, 150, 25), (B, 201, 112), (C, 399,95), (D,94, 31), (E, 295, 185), (F, 78,85), (G, 165, 150), (H, 125, 101), (I, 300,85), (J, 210, 90).

Considering that the disk head is currently on cylinder 49 and moving toward cylinder 50, please show how the disk head moves to satisfy all requests using SCAN-EDF.

5. Authentication is useful for proving that a message has not been modified during transmission. The message-authentication code and the digital-signature algorithm are two popular authentication solutions. Please explain how they operate.

6. In a local-area network, sites may want to transmit data over a link simultaneously. If nothing is done, this will cause serious collision. CSMA/CD and token passing are two popular techniques developed to avoid the aforementioned collision. Please explain how CSMA/CD and token passing operate.

7. (a) Given n objects to be sorted, please give the worst-case and the average-case running time of the following algorithms: Insertion sort, merge sort, heap sort, and quick

(b) One guy said that he has invented a comparison-based sorting algorithm, called Supersort, with the worst-case running time of O(n). Do you think that Supersort is possible? Please give your reason.

8. Suppose that a 12000-character article is composed of only alphabets I, J, K, L, M, and N, which appear 5400, 1560, 1440, 1920, 1080, and 600 times, respectively. Please draw the Huffman coding trees for fixed-length codeword and variable-length codeword.

(a) How many keys can be held in each node? Please give your calculation.

(b) Please draw the new tree by inserting B.

(c) Please draw the new tree by inserting Q in the tree formed by question (b).

(d) Please draw the new tree by inserting L in the tree formed by question (c).

(e) Please draw the new tree by inserting F in the tree formed by question (d). sort.

(a)Please show the order in which the edges are added to the minimum spanning tree using the Kruskal's algorithm.

(b) Assuming that vertex A is the root, please show the order in which the edges are added to the minimum spanning tree using the Prim's algorithm.

(Notice: In your answer, you can use weights to represent edges.)