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

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

試卷資訊

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

選擇題 (0)

申論題 (23)

1.[Sorting: ]

Please prove that any comparison-based sorting algorithm requires O(n Ign) computation time in the worst case, where n is the number of objects to be sorted.

(1) From the viewpoint of an operating system, please give practical applications of using a stack, queue, and linked list.

(2) Given a prefix expression "+ + (2)x(3) (4)x +x (5)(6) (7) (8)", please convert it to the infix expression and calculate the result.

(3) What is the assumption of simple uniform hashing? Under this assumption, given a hash table with m slots that stores n elements, what is the expected time taken by an unsuccessful search when the hash collisions are resolved by chaining?

(4) Please explain the property of a binary search tree.

3.[Graph: ]
You are given the adjacency matrix of an undirected graph:

Starting fom node S, please eanswer the tollowing giestions.

(1) Please give the five properties of a binomial tree. (5%)

(2) Consider a Fibonacci heap as follows: The number in each node indicates its key value. Suppose that we decrease key 48 to 17 and then decrease key 37 to 7. Please show the final result of the revised heap.

(3) Why does a B-tree can help reduce the cost of disk access?

(1) Please explain the five states of a process.

(2) What is the risk of terminating a single thread by calling the exit0 procedure in a multi- threading program?

(3) Except for CPU utilization and throughput, please explain the three criteria to measure the performance of a process scheduling algorithm.

(1) Except for single-level and two-level directories, what are the three popular schemes to define the logical structure of directories?

(2) Suppose that the range of a disk's cylinders is [1, 200] and the disk head currently stops at 5. Let the disk queue contain the requests of blocks on cylinders {99, 187, 39, 124,14, 131, 65, 70}. Please show how the disk head moves in the SSTF, SCAN, C-SCAN, and C- LOOK disk scheduling schemes.

(3) What is a component unit of the distributed file system?

(1) Let the time to search the TLB and to access memory is 25 ns and 95 ns, respectively. Supposing that the TLB has 80% hit ratio, what is the effective memory-access time? Notice that you have to give the calculation.

(2) Please explain both external and internal fragmentation in memory allocation.

(3) From the viewpoint of a process, what is thrashing?

(4) What is memory-mapped I/O? Why do we need it?

(5) Why can virtual memory speed up process creation?

(1) Please explain the three synchronization mechanisms for threads to access a shared data item in UNIX systems.

(2) Suppose that three processes P1, P2, and P3 respectively have timestamps 17, 25, and 30, and P2 currently holds a resource requested by both P1 and P3. Please give the results of wait-die and wound-wait schemes used to handle deadlocks.

(3) Please explain how the two-phase locking protocol works to check the correctness of a non- serial schedule for atomic transactions.