CS GATE 2013 - Online Test

Q1. Were you a bird, you ___________ in the sky
Answer : Option A
Explaination / Solution:
No Explaination.


Q2. Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
Answer : Option C
Explaination / Solution:

Q: Sum of degrees of all vertices = 2 × (number of edges)

Q3.
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P. 
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP. 
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
Answer : Option A
Explaination / Solution:

1. Cycle detection using DFS: O(V + E) = O(V2)and it is polynomial problem 
2. Every P-problem is NP(since P ⊂ NP)
3. NP-complete ∈ NP
Hence, NP-complete can be solved in non-deterministic polynomial time

Q4. 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)

Q5. 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.


Q6. In the following truth table, V = 1 if and only if the input is valid

What function does the truth table represent?  
Answer : Option A
Explaination / Solution:

4 to 2 priority encoder.

Q7.
 Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter
MultiDequeue (Q) {
m = k
while (Q is not empty) and (m > 0) {
Dequeue (Q)
m = m - 1
}
}
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue? 

Answer : Option A
Explaination / Solution:
No Explaination.


Q8. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
Answer : Option D
Explaination / Solution:

Pr eorder :30,20,10,15,25,23,39,35,42 
Inorder :10,15,20,23,25,30,35,39,42


Q9. What is the return value of f (p,p) if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.
int f (int & x, int c) {
c = c - 1;
if (c = 0) return 1;
x = x + 1;
return f (x,c)* x;
}
Answer : Option B
Explaination / Solution:



Q10. A certain computation generates two arrays a and b such that a[i] = f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < n. Suppose this computation is decomposed into two concurrent processes X and Y such that X computes the array a and Y computes the array b. The processes employ two binary semaphores R and S, both initialized to zero. The array a is shared by the two processes. The structures of the processes are shown below.
Pr ocess X;                                              Pr ocess Y;
private i;                                                   private i;
   for(i = 0; i<n; i++){                                      for(i = 0; i<n; i++){
        a[i] = f(i);                                                      EntryY(R, S);
           ExitX(R, S);                                                    b[i] = g(a[i]);
}                                                                  }
Which one of the following represents the CORRECT implementations of ExitX and EntryY? 

Answer : Option C
Explaination / Solution:

For computing both the array a[] and b[], first element a[i] should be computed using which b[i] can be computed. So process X and Y should run in strict alteration manner, starting with X. This requirement meets with implementation of ExitX and EntryY given in option C.