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

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

試卷資訊

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

選擇題 (0)

申論題 (18)

1. (10%) What would be the output of the following C program? (Note that the line numbers are for reference only.)

(a) (2%) FCFS

(b) (2%) LOOK

(c) (2%) C-LOOK

(d) (2%) SCAN

(e) (2%) C-SCAN

3. (10%) A computer whose processes have 2048 pages in their address spaces keeps its page tables in memory. The overhead required for reading a word from the page table is 500 nsec. To reduce this overhead, the computer has a TLB, which holds 32 (page, frame) pairs and can do a lookup in 50 nsec. What hit rate is needed to reduce the mean overhead to 150 nsec or less, assuming that TLB is looked up first before the page table is read?

(a) (5%) What would be the size of the smallest file allowed in bytes?

(b) (5%) What would be the size of the largest fle allowed in bytes?

(a) (5%)

(b) (5%)

(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, h₁( ) is applied for the first time; h₂( ) is applied if a hash collision occurs; h₃( ) 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).