CS GATE 2011 - Online Test
Q1. Consider the following table of arrival time and burst time for three processes P0,
P1 and P2.
Process Arrival time Burst Time
P0 0 ms 9 ms
P1 1 ms 4ms
P2 2 ms 9ms
The pre-emptive shortest job first scheduling algorithm is used. Scheduling is
carried out only at arrival or completion of processes. What is the average
waiting time for the three processes?
Answer : Option A
Explaination / Solution:
Average waiting time = (4+11)/3 = 5 ms
Q2. Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑ . Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?
Answer : Option B
Explaination / Solution:
7 ↓ 3 ↑ 4 ↑ 3 ↓ 2
7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative
7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2
(7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative
Q3. We are given a set of n distinct elements and an unlabeled binary tree with n
nodes. In how many ways can we populate the tree with the given set so that it
becomes a binary search tree?
Answer : Option D
Explaination / Solution:
No Explaination.
Q4. Consider evaluating the following expression tree on a machine with load-store
architecture in which memory can be accessed only through load and store
instructions. The variables a, b, c, d and e are initially stored in memory. The
binary operators used in this expression tree can be evaluated by the machine
only when the operands are in registers. The instructions produce result only in a
register. If no intermediate results can be stored in memory, what is the
minimum number of registers needed to evaluate this expression?
Answer : Option D
Explaination / Solution:
Total 3 Registers are required minimum
Q5. Choose the word from the options given below that is most nearly opposite in
meaning to the given word: Amalgamate
Answer : Option B
Explaination / Solution:
Amalgamate means combine or unite to form one organization or structure. So
the best option here is split. Separate on the other hand, although a close
synonym, it is too general to be the best antonym in the given question while
Merge is the synonym; Collect is not related.
Q6. An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1, v2,....vn . Two
nodes vi, vj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is
assigned a weight i + j. A sample graph with n = 4 is shown below
What will be the cost of the minimum spanning tree (MST) of such a graph with n
nodes?
Answer : Option B
Explaination / Solution:
No Explaination.
Q7. Which of the following options is the closest in the meaning to the word below:
Inexplicable
Answer : Option A
Explaination / Solution:
Inexplicable means not explicable; that cannot be explained, understood, or
accounted for. So the best synonym here is incomprehensible.
Q8. An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1, v2,....vn . Two nodes vi, vj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
The length of the path from v5 to v6 in the MST of previous question with n = 10
is
Answer : Option C
Explaination / Solution:
12 + 8 + 4 + 3 + 6 + 10 = 31
Q9. Consider a network with five nodes, N1 to N5, as shown below
The net work uses a Distance Vector Routing protocol. Once the routes have
stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4)
N2 : (1, 0, 6, 7, 3)
N3 : (7, 6, 0, 2, 6)
N4 : (8, 7, 2, 0, 4)
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to
nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric
and the cost is identical in both directions. In each round, all nodes exchange
their distance vectors with their respective neighbors. Then all nodes update their
distance vectors. In between two rounds, any change in cost of a link will cause
the two incident nodes to change only that entry in their distance vectors
The cost of link N2-N3 reduces to 2 in (both directions). After the next round of
updates, what will be the new distance vector at node, N3?
Answer : Option A
Explaination / Solution:
Q10. Consider a network with five nodes, N1 to N5, as shown below
The net work uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4)
N2 : (1, 0, 6, 7, 3)
N3 : (7, 6, 0, 2, 6)
N4 : (8, 7, 2, 0, 4)
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors
After the update in the previous question, the link N1-N2 goes down. N2 will
reflect this change immediately in its distance vector as cost, ∞ . After the NEXT
ROUND of update, what will be the cost to N1 in the distance vector of N3?
Answer : Option C
Explaination / Solution:
N3 has neighbors N2 and N4
N2 has made entry ∞
N4 has the distance of 8 to N1
N3 has the distance of 2 to N4
So 2 + 8 = 10
