(a) (5%)

(b) (5%)

7. (10%) Suppose that the preorder sequence of a binary tree is ABCDEFGH, and the inorder sequence is ABDAFGHE. What is the postorder sequence of the binary tree ?

8. (15%) In the hash method, suppose that a rehash function hi(x)-(5i+x) mod 13 is applied sequentially when a new element is inserted into the hash table, but a hash colision occurs. In other words, h1( ) is applied for the first time; h2( ) is applied if a hash collision occurs; h3( ) is applied if a hash collision occurs again; and so on. What is the content of the hash table after the elements 35, 22, 9, 24, 16, 19, 3, are inserted sequentially into an empty hash table of size 13, indexed as 0 through 12 ?

(a) (5%) Please give the definition of an AVL binary search tree.

(b) (5%) Assume that the initial AVL tree is empty. Please draw the AVL tree after the numbers 8, 9, 6, 3 and 2 are inserted into the tree sequentially.

(c) (5%) Please draw the AVL tree after the number 5 is inserted into the above AVL obtained in (b).

(1) Except for the process state, what are the six components in a process control block? (6%)

(2) Please define interrupt latency and dispatch latency. (4%)

(3) As compared with processes, will or will not context switching among multiple threads incur less overhead? Why or why not? (4%)

(4) According to POSIX threads, what are the three procedures involved in a mutex and how to use them? (6%)

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

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

108年 - 108 國立中山大學_碩士班招生考試_資工系(甲組#105764

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

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

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

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

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

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

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