CS GATE 2012 - Online Test
Q1. Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected
graph, then the number of bounded faces in any embedding of G on the plane is equal to
Answer : Option D
Explaination / Solution:
We have the relation V-E+F=2, by this we will get the total number of faces, F = 7. Out of 7 faces one is an unbounded face, so total 6 bounded faces.
Q2. The worst case running time to search for an element in a balanced binary search tree with
n2n elements is
Answer : Option C
Explaination / Solution:
The worst case search time in a balanced BST on ‘x’ nodes is logx. So, if x = n2n , then log(n2n) = logn + log(2n) = logn + n = θ(n)
Q3. Assuming P ≠ NP, which of the following is TRUE?
Answer : Option B
Explaination / Solution:
If P!=NP, then it implies that no NP-Complete problem can be solved in polynomialtime
which implies that the set P and the set NPC are disjoint.
Q4. The height of a tree is defined as the number of edges on the longest path in the tree. The
function shown in the pseudocode below is invoked as height (root) to compute the height of
a binary tree rooted at the tree pointer root.
int height (treeptr n)
{ if (n== NULL) return -1;
if (n → left == NULL)
if (n → right ==NULL) return 0;
else return BI ; // Box 1
else {h1 = height (n → left);
if (n → right == NULL) return (1+ h1);
else {h2 = height (n → right);
return B2 ; // Box 2
}
}
}
The appropriate expressions for the two boxes B1 and B2 are
Answer : Option A
Explaination / Solution:
No Explaination.
Q5. Consider an instance of TCP’s Additive Increase Multiplicative decrease (AIMD) algorithm
where the window size at the start of the slow start phase is 2 MSS and the threshold at the
start of the first transmission is 8 MSS. Assume that a timeout occurs during the fifth
transmission. Find the congestion window size at the end of the tenth transmission.
Answer : Option C
Explaination / Solution:
Given, initial threshold = 8
Time = 1, during 1st transmission,Congestion window size = 2 (slow start phase)
Time = 2, congestion window size = 4 (double the no. of acknowledgments)
Time = 3, congestion window size = 8 (Threshold meet)
Time = 4, congestion window size = 9, after threshold (increase by one Additive increase)
Time = 5, transmits 10 MSS, but time out occurs congestion window size = 10
Hence threshold = (Congestion window size)/2 = 10/2 = 5
Time = 6, transmits 2
Time = 7, transmits 4
Time = 8, transmits 5 (threshold is 5)
Time = 9, transmits 6, after threshold (increase by one Additive increase)
Time = 10, transmits 7
∴ During 10th transmission, it transmits 7 segments hence at the end of the tenth transmission the size of congestion window is 7 MSS.
Q6. Consider the virtual page reference string
1,2,3,2,4,1,3,2,4,1
on a demand paged virtual memory system running on a computer system that has main
memory size of 3 page frames which are initially empty. Let LRU, FIFO and OPTIMAL
denote the number of page faults under the corresponding page replacement policy. Then
Answer : Option B
Explaination / Solution:
FIFO
1 1 1 4 4 4
2 2 2 1 1 → (6) faults
3 3 3 2
Optimal
1 1 1 1 1
2 2 4 4 → (5) faults
3 3 2
LRU
1 1 1 4 4 4 2 2 2
2 2 2 2 3 3 3 1 → (9) faults
3 3 1 1 1 4 4
Optimal < FIFO < LRU
Q7. Consider the directed graph shown in the figure below. There are multiple shortest paths
between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm?
Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly
shorter path to v is discovered.
Answer : Option D
Explaination / Solution:
No Explaination.
Q8. A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort
algorithm. The worst case running time of this computation is
Answer : Option B
Explaination / Solution:
The height of the recursion tree using merge sort is logn and n2
comparisons are done at each
level, where at most n pairs of strings are compared at each level and n comparisons are
required to compare any two strings, So the worst case running time is O(n2 log n)
Q9. Consider the program given below, in a block-structured pseudo-language with lexical
scoping and nesting of procedures permitted
Program main;
Var . . .
Procedure A1;
Var ….
Call A2;
End A1
Procedure A2;
Var . . .
Procedure A21;
Var . . .
Call A1;
End A21
Call A21;
End A2
Call A1;
End main.
Consider the calling chain: Main → A1 → A2 → A21 → A1
The correct set of activation records along with their access links is given by
Answer : Option D
Explaination / Solution:
Access link is defined as link to activation record of closest lexically enclosing block in
program text, so the closest enclosing blocks respectively for A1 ,A2 and A21 are main ,
main and A2
Q10. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n
elements. Assume that the insertion and deletion operations are carried out using REAR and
FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions
to detect queue full and queue empty are
Answer : Option A
Explaination / Solution:
The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is satisfied which is false
The counter example for the condition full : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false
The counter example for the condition empty : (REAR+1)mod n = FRONT is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
The counter example for the condition empty : (FRONT+1)mod n =REAR is
Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here
