CS GATE 2016 PAPER 01 - Online Test
Q1. 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.
Q2. Archimseedes said, “Give me a lever long enough and a fulcrum on which to place it, and I
will move the world.”
The sentence above is an example of a ________ statement.
Answer : Option A
Explaination / Solution:
No Explaination.
Q3. 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+
Q4. Consider the transition diagram of a PDA given below with input alphabet Σ = {a, b} and
stack alphabet Γ = {X , Z}. Z is the initial stack symbol. Let L denote the language accepted
by the PDA.
Which one of the following is TRUE?
Answer : Option D
Explaination / Solution:
No Explaination.
Q5. If f(x) = 2x7 + 3x - 5 which of the following is a factor of f(x)?
Answer : Option B
Explaination / Solution:
from the option (b0 substitute x=1 in
2x7 + 3x - 5 = 0
2(1)7 + 3(1) - 5 = 0
5-5 = 0
So (x - 1) is a factor of f (x)
Q6. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently. Which one of the following statements is CORRECT (n refers to the
number of items in the queue)?
Answer : Option A
Explaination / Solution:
No Explaination.
Q7. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
Answer : Option D
Explaination / Solution:
Merge sort θ(n log n) in all the cases
Quick sort θ(n log n) best case and θ(n2) worst cases
Insertion sort θ(n)best case R θ(n2) worst case
Q8. Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
Answer : Option A
Explaination / Solution:
No Explaination.
Q9. The following function computes the maximum value contained in an integer array p[ ] of size
n (n >= 1).
int max(int *p, int n) {
int a=0, b=n-1;
while ( _________ ) {
if (p[a] <= p[b]) { a = a+1; }
else { b = b-1; }
}
return p[a];
}
The missing loop condition is
Answer : Option D
Explaination / Solution:
When a=b then P[a] will have the maximum value of the array
Q10. What will be the output of the following pseudo-code when parameters are passed by
reference and dynamic scoping is assumed?
a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}
Answer : Option D
Explaination / Solution:
Dynamic scoping looks for the definition of free variable in the reverse order of calling
sequence.
