(2) The SCAN algorithm

(1)

(1)

3. Two-way insertion sort : Suppose the output sorted sequence is increasing. The two-way insertion sort is a modification of the simple insertion sort (straightforward insertion sort), described as follows. After read the input elements, a separate output array a[0], a[1], a[2], a[n-1] is used to store the sorted sequence. This output array acts as a circular structure, that is, the right position of a[i] is a[i+1] if 0≤ i ≤ n-2, and the right position of a[n-1] is a[0]. The first input element is put into a[0] initially. Once a contiguous group of elements are in the array, room for a new input element is made by shifting all smaller  elements one step to the left or all larger element one step to the right. The choice of left-shift or right-shift to perform depends on which would cause the smallest amount of shifts. Use the following 6 input elements to illustrate how this algorithm works. You have to show the content of the output array after each input element is inserted into the array. 27,35,43, 31,29,33.

(1) The label of each leaf node is a single symbol. The label of each internal node is the concatenation of the labels of its left child and right child.

(2) When two nodes are merged, always set the node of label with less lexical order as the left child, and the other as the right child.

(3) If more than two nodes have the same least frequency, then you have to merge the two that bave the least and the second least label in lexical order. Please draw the full Huffman tree.

(1) The need-to-know principle dictates that programs, users, and even systems should be given just sufficient privileges to perform their tasks. This principle is very critical for system protection, which can prevent the mischievous, intentional violation of an acces ess restriction by a user.

(2) A deadlock situation must arise if any of the following four conditions holds in a computer system: mutual exclusion, hold and wait, no preemplion, and circular wait. Therefore, to vanquish the deadlock, we have to see what conditions cause that deadlock and then try to conquer each of them.

(3) We can realize a dynamic relocation by using a relocation register in memory management. For example, suppose that the CPU asks a logical address of 123 and the relocation register has a value of 1877. Then, the physical address will be 2000.

(4) A trap door may be included in a compiler. Therefore, the compiler would generate the standard object code as well as a trap door. However, this activity can be still found by conducting a very careful search of the source code of the compiled program.

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