110年 - 110 國立臺灣科技大學_碩士班招生試題_資訊工程系：資訊工程概論#100775

(a) For the register values shown above, what is the value of $t2 for the following sequence of instructions? (5%)
sll $t2, $t0, 44
or $t2, $t2, $t1

(b) For the register values shown above, what is the value of St2 for the following sequence of instructions? (5%)
sll $t2, $t0, 4
andi $t2, $t2, -1

2. Consider the following instruction:
Instruction: AND Rd,Rs,Rt
Interpretation: Reg[Rd] = Reg[Rs] AND Reg[Rt]
What are the values of control signals generated by the control in the following for the above instruction? (10%)

(a) What is the cache block size (in words)? (4%)

(b) How many entries does the cache have? (4%)

(c) What is the ratio between total bits required for such a cache implementation over the data storage bits? (5%) Offset

(a)Write down the RAID levels of the following schemes. (I) Mirrored disks, (ii) non-redundant striping, (iii) bit-interleaved parity, and (iv) block-interleaved distributed parity. (4%)

(b) CPU scheduling decides which process in the queue is to be allocated the CPU. FCFS (first-come, first-served), SJF (shortest-job-first), Priority, and RR (round- robin) are four basic scheduling algorithms. Which one(s) of them could result in starvation? (4%)

(c) A deadlock situation can occur if four necessary conditions hold simultaneously. Which one(s) of the following belongs to these conditions? (i) Mutual execution, (li) hold and wait, (ili) critical section, (iv) circular wait, and (v) equal allocation. (5%)

(d) Consider a system consisting of 11 resources of the same type, being shared by n processes. Each process may need at most 3 of these resources at the same time. What is the maximum value of n that keeps the system deadlock free? Explain your answer to receive full credit. (7%)

(a) Use the first-fit algorithm to place processes of size 220 KB, 420 KB, 120 KB, 380 KB, and 90 KB (in order). Which one(s) will be placed in the partition of 500 KB? Which one(s) will be placed in the partition of 300 KB? (7%)

(b) Now use the best-fit algorithm to place the above processes. Which one(s) will be placed in the partition of 500 KB? Which one(s) will be placed in the partition of 300 KB? (7%)

(a) Give the prefix expression for the following expression. (3%)
A*(B+C)/D-E

(b) What is the post-order traversal of the following tree? (4%)

(c) What is the minimum and maximum number of nodes in a complete binary tree of height h? (6%)

(d) Draw the binary min heap that results from inserting 12, 9, 14, 16, 4, 17, 6, 8, 2 in that order into an initially empty binary heap. Draw the final tree. (10%)

(e) Remove the first two smallest values from the heap created in (d) and reconstruct the min heap. Draw the resulting tree. (5%)

7. Given a hash function as follows:
The size of the hash table is 7.
Linear probing is used to resolve collisions.
The hash function used is H(k) = k mod 7
Suppose that the hash table is initially empty. What values will be in the hash table after the following sequence of insertions?
15,26,29,19,8
Draw the contents of the hash table as shown below. (5%)

110年 - 110 國立臺灣科技大學_碩士班招生試題_資訊工程系：資訊工程概論#100775

試卷資訊

選擇題 (0)

申論題 (18)