Computer Science Engineering - Online Test
Q1. A computer system has an L1 cache, an L2 cache, and a main memory unit
connected as shown below. The block size in L1 cache is 4 words. The block size
in L2 cache is 16 words. The memory access times are 2 nanoseconds.
20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory
unit respectively.
When there is a miss in L1 cache and a hit in L2 cache, a block is transferred
from L2 cache to L1 cache. What is the time taken for this transfer?
Answer : Option D
Explaination / Solution:
No Explaination.
Q2. Consider a network with 6 routers R1 to R6 connected with links having
weights as shown in the following diagram
All the routers use the distance vector based routing algorithm to update their
routing tables. Each router starts with its routing table initialized to contain an
entry for each neighbour with the weight of the respective connecting link.
After all the routing tables stabilize, how many links in the network will never
be used for carrying any data?
Answer : Option C
Explaination / Solution:
No Explaination.
Q3. Which one of the following regular expressions represents the language: the set of all binary
strings having two consecutive 0s and two consecutive 1s?
Answer : Option B
Explaination / Solution:
(a) contains 00 & 11 consecutively which is not the required condition.
(c) Doesn’t guaranty that both 00 & 11 will be present in the string.
(d) Says string should start with 11 & ends with 00 or vice versa.
Q4. Consider a database that has the relation schemas EMP(EmpId, EmpName, DepId). And
DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation
EMP. Consider the following queries on the database expressed in tuple relational calculus.
Which of the above queries are safe?
Answer : Option D
Explaination / Solution:
Query which generates infinite number of tuples is called unsafe query. In the given question
all the given queries generate finite number of tuples.
Q5. A computer system has an L1 cache, an L2 cache, and a main memory unit
connected as shown below. The block size in L1 cache is 4 words. The block size
in L2 cache is 16 words. The memory access times are 2 nanoseconds.
20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory
unit respectively.
When there is a miss in both L1 cache and L2 cache, first a block is transferred
from main memory to L2 cache, and then a block is transferred from L2 cache to
L1 cache. What is the total time taken for these transfers?
Answer : Option B
Explaination / Solution:
No Explaination.
Q6. Which one of the following is the tightest upper bound that represents the time complexity of
inserting an object into a binary search tree of n nodes?
Answer : Option C
Explaination / Solution:
For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)
Q7. Consider a network with 6 routers R1 to R6 connected with links having
weights as shown in the following diagram
Suppose the weights of all unused links in the previous question are changed
to 2 and the distance vector algorithm is used again until all routing tables
stabilize. How many links will now remain unused?
Answer : Option C
Explaination / Solution:
No Explaination.
Q8. Consider the following context-free grammars:
G1: S → aS|B, B → b|bB
G2: S → aA|bB, A → aA|B|ε , B → bB|ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
Answer : Option D
Explaination / Solution:
Lagrange’s generated by G1 = a*b+
Lagrange’s generated by G2 = a+b*\b+
Q9. In a database system, unique time stamps are assigned to each transaction using Lamport’s
logical clock . Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting
lock on the same resource R. The following algorithm is used to prevent deadlocks in the
database system assuming that a killed transaction is restarted with the same timestamp.
if TS(T2) < TS(T1) then
T1 is killed
else T2 waits.
Assume any transactions that is not killed terminates eventually. Which of the following is
TRUE about the database system that uses the above algorithm to prevent deadlocks?
Answer : Option A
Explaination / Solution:
Elder kills younger and youngers waits on elder. So both are not waiting for each other. Hence
no deadlock and there won’t be any starvation as well because the transaction who got killed
will be starting with same time stamp.
Q10. Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?
Answer : Option B
Explaination / Solution:
No Explaination.
