lvy>試卷(2022/01/21)

中山◆資工◆作業系統與資料結構題庫  下載題庫

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

【非選題】
1.

1.Let us consider a set of processes as follows, where they have arrived in the order of P1, P2, P3, P4, and P5 all at time 0:

【題組】(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).

【非選題】
2.【題組】(b) Calculate the turnaround time of each process in the four scheduling algorithms.

【非選題】
3.(c) Which of the algorithms results in the minimum average waiting time? Note that you should give your calculation.

【非選題】
4.2.(a) What are the four conditions to result in a deadlock? Please detail each condition in your answer.

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

【非選題】
6.

3.In virtual-memory management, demand paging plays an important role.

【題組】(a) Please explain what is demand paging?

【非選題】
7.【題組】(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.

【非選題】
8.【題組】(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.

【非選題】
9.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.

【非選題】
10.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.

【非選題】
11.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.

【非選題】
12.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

【非選題】
13.(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.

【非選題】
14.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.

【非選題】
15.

9. Consider a B-tree as follows, where the minimum degree t for this B-tree is three.

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

【非選題】
16.【題組】(b) Please draw the new tree by inserting B.

【非選題】
17.【題組】(c) Please draw the new tree by inserting Q in the tree formed by question (b).

【非選題】
18.【題組】(d) Please draw the new tree by inserting L in the tree formed by question (c).

【非選題】
19.【題組】(e) Please draw the new tree by inserting F in the tree formed by question (d). sort.

【非選題】
20.

10. Consider the adjacency matrix of an undirected graph as follows:

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

【非選題】
21.【題組】(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.)