GATE 2005
Question 1 
What does the following Cstatement declare?
int ( * f) (int * ) ;
A function that takes an integer pointer as argument and returns an integer.  
A function that takes an integer as argument and returns an integer pointer.  
A pointer to a function that takes an integer pointer as argument and returns an integer.  
A function that takes an integer pointer as argument and returns a function pointer. 
→ A pointer to a function which takes integer as a pointer and return an integer value.
Question 2 
An Abstract Data Type (ADT) is:
Same as an abstract class  
A data type that cannot be instantiated
 
A data type type for which only the operations defined on it can be used, but none else  
All of the above 
Question 3 
A common property of logic programming languages and functional languages is:
both are procedural languages  
both are based on λcalculus  
both are declarative  
both use Hornclauses 
Question 4 
Which one of the following are essential features of an objectoriented programming language?
 (i) Abstraction and encapsulation
(ii) Strictlytypedness
(iii) Typesafe property coupled with subtype rule
(iv) Polymorphism in the presence of inheritance
(i) and (ii) only  
(i) and (iv) only  
(i), (ii) and (iv) only  
(i), (iii) and (iv) only 
Question 5 
A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
An array of 50 numbers  
An array of 100 numbers  
An array of 500 numbers  
A dynamically allocated array of 550 numbers 
→ Then using array of 50 numbers is the best way to store the frequencies.
Question 6 
An undirected graph C has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) diagonal elements are 0's and (ii) nondiagonal elements are l's. Which one of the following is TRUE?
Graph G has no minimum spanning tree (MST)
 
Graph G has a unique MST of cost n1  
Graph G has multiple distinct MSTs, each of cost n1  
Graph G has multiple spanning trees of different costs 
Since the weights of every edge is 1 so there are different MST's are possible with same cost, i.e., (n1).
Question 7 
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be:
O(n)  
O(n log n)  
O(n^{3/2})  
O(n^{3}) 
For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R^{+} such that x R^{+} y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.
To find the transitive closure of given relation, we can represent the given relation by the graph such that if x R y then there should be directed edge between x and y in a graph. For this graph, we have to apply modified Floyd_Warshall Algorithm to find the transitive closure of the graph.
The time complexity of this algorithm is O(V3) where V is the number of vertices in the given graph. You can take here V as the number of elements is set i.e., N. Therefore time complexity for the given question is O(n^{3}).
Question 8 
Let A, B and C be nonempty sets and let X = (A  B)  C and Y = (A  C)  (B  C). Which one of the following is TRUE?
X = Y  
X ⊂ Y  
Y ⊂ X  
None of these 
B = {1, 3, 4, 5}
C = {2, 4, 5, 6}
X = (A  B)  C
X = {2, 6}  {2, 4, 5, 6}
= ∅
Y = (A  C)  (B  C)
= {1, 3}  { 1, 3}
= ∅
X = Y
X = (A  B)  C
= (1, 5)  (5, 7, 4, 3)
= (1)
Y = (A  C)  (B  C)
= (1, 4)  (2, 4)
= (1)
X = Y
Question 9 
The following is the Hasse diagram of the poset [{a,b,c,d,e},<]
The poset is
not a lattice  
a lattice but not a distributive lattice  
a distributive lattice but not a Boolean algebra  
a Boolean algebra 
But it is not distributed because for some element there are more than one complement. Moreover if it is not distributive then it can't be boolean.
Question 10 
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
6  
8  
9  
13 
F = E  V + 2 [From Euler's formula i.e., F + V  E = 2]
F = 19  13 +2
F = 8
Question 11 
Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
12  
8  
Less than 8  
More than 12

Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices  Minimum cover of vertex G
= 20  8
= 12
Question 12 
Let f(x) be the continuous probability density function of a random variable X. The probability that a < X ≤ b, is:
f(b  a)
 
f(b)  f(a)  
Then the probablity be area of the corresponding curve i.e.,
Question 13 
The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses of 4 and 7 are respectively:
3 and 13  
2 and 11  
4 and 13  
8 and 14 
Inverse of 4 = m; Inverse of 7 = n
(4×m)%15=1; (7*n)%15=1
Option A: m=3 n=13
12%15≠1 (✖️) 91%15=1 (✔️)
Option B: m=2 n=11
8%15≠1 (✖️) 11%15≠1 (✖️)
Option C: m=4 n=13
16%15=1(✔️) 91%15=1 (✔️)
Option D: m=8 n=14
120%15≠1(✖️) 98%15≠1(✖️)
Question 14 
The grammar A → AA  (A)  ε is not suitable for predictiveparsing because the grammar is:
ambiguous  
leftrecursive  
rightrecursive  
an operatorgrammar 
It have A → AA has left recursion.
Question 15 
Consider the following circuit.
Which one of the following is TRUE?
f is independent of X
 
f is independent of Y  
f is independent of Z  
None of X, Y, Z is redundant 
= ((X’+Y) YZ)’
= (X’YZ + YZ)’
= ((X’+1) YZ)’
= (YZ)’
Question 16 
The range of integers that can be represented by an n bit 2's complement number system is:
 2^{n1} to (2^{n1}  1)  
 (2^{n1}  1) to (2^{n1}  1)  
 2^{n1} to 2^{n1}
 
 (2^{n1} + 1) to (2^{n1}  1) 
The smallest (negative) n bit number is 100..0 (i.e., 1 followed by n1 zeros) which is equal to  2^{n1}.
1000...00
0111...11 < 1’s complement
1000..00 < 2’s complement
=  2^{n1}
Question 17 
The hexadecimal representation of 657_{8} is
1AF  
D78  
D71  
32F 
Make 3 zeros on the left side so that the number of bits is multiple of 4.
= (0001 1010 1111)_{2}
= (1 A F)_{16}
Question 18 
The switching expression corresponding to f(A, B, C, D) = Σ (1, 4, 5, 9, 11, 12) is:
BC'D' + A'C'D + AB'D  
ABC' + ACD + B'C'D  
ACD' + A'BC' + AC'D'  
A'BD + ACD' + BCD' 
f(A,B,C,D) = A'C'D + BC'D' + AB'D
Question 19 
Which one of the following is true for a CPU having a single interrupt request line and a single interrupt grant line?
Neither vectored interrupt nor multiple interrupting devices are possible.
 
Vectored interrupts are not possible but multiple interrupting devices are possible.
 
Vectored interrupts and multiple interrupting devices are both possible.
 
Vectored interrupt is possible but multiple interrupting devices are not possible. 
Also for vectored Interrupts it is always possible if we implement in daisy chain mechanism.
Question 20 
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instructions privileged. In a CPU with memory mapped I/O, there is no explicit I/O instruction. Which one of the following is true for a CPU with memory mapped I/O?
I/O protection is ensured by operating system routine(s)
 
I/O protection is ensured by a hardware trap  
I/O protection is ensured during system configuration
 
I/O protection is not possible 
Question 21 
What is the swap space in the disk used for?
Saving temporary html pages
 
Saving process data
 
Storing the superblock  
Storing device drivers

→ The interchange of data between a virtual memory and a real memory is called as swapping and space on a disk as 'swap space'.
→ Swap space in the disk can be used for saving process data.
Question 22 
Increasing the RAM of a computer typically improves performance because:
Virtual memory increases  
Larger RAMs are faster  
Fewer page faults occur  
Fewer segmentation faults occur 
→ Such as if RAM size increases, then no. of page entries increases, then no. of page faults decreases.
Question 23 
Packets of the same session may be routed through different paths in:
TCP, but not UDP  
TCP and UDP  
UDP, but not TCP  
Neither TCP nor UDP 
Question 24 
The address resolution protocol (ARP) is used for:
Finding the IP address from the DNS  
Finding the IP address of the default gateway  
Finding the IP address that corresponds to a MAC address  
Finding the MAC address that corresponds to an IP address

Question 25 
The maximum window size for data transmission using the selective reject protocol with nbit frame sequence numbers is:
2^{n}  
2^{n1}  
2^{n}  1  
2^{n2} 
For Goback N, the maximum window size can be 2^{n}  1.
Question 26 
In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges. Why is the spanning tree algorithm used for bridgerouting?
For shortest path routing between LANs  
For avoiding loops in the routing paths
 
For fault tolerance  
For minimizing collisions 
Question 27 
An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be:
255.255.0.0  
255.255.64.0  
255.255.128.0  
255.255.252.0 
Question 28 
Which one of the following is a key factor for preferring B^{+} trees to binary search trees for indexing database relations?
Database relations have a large number of records  
Database relations are sorted on the primary key  
B^{+} trees require less memory than binary search trees
 
Data transfer from disks is in blocks 
Thus, the data can be transferred through blocks in B^{+} trees. This can be used for indexing the database relations.
Question 29 
Which one of the following statements about normal forms is FALSE?
BCNF is stricter than 3NF  
Lossless, dependencypreserving decomposition into 3NF is always possible
 
Lossless, dependencypreserving decomposition into BCNF is always possible  
Any relation with two attributes is in BCNF 
Option B: Lossless, dependency preserving decomposition into 3NF is always possible.
Option C: It is false.
It is not possible to have dependency preserving in BCNF decomposition.
→ Let take an example, 3NF can't be decomposed into BCNF.
Option D: It is true.
Let consider two attributes (X, Y).
If (X→Y), X is a candidate key. It is in BCNF and viceversa.
Question 30 
Let r be a relation instance with schema R = (A, B, C, D). We define r_{1} = Π_{A,B,C}(R) and r_{2} = Π_{A,D}(R). Let s = r_{1}*r_{2} where * denotes natural join. Given that the decomposition of r into r_{1} and r_{2} is lossy, which one of the following is TRUE?
s ⊂ r  
r ∪ s = r  
r ⊂ s  
r * s = s

Table r: R(A, B, C, D)
Table r_{1}: Π_{A,B,C}(R)
Table r_{2}: Π_{A,D}(R)
S = r_{1} * r_{2} (* denotes natural join)
Table S:
Table r ⊂ Table S
⇒ r ⊂ S
Question 31 
Consider the following Cprogram:
void foo(int n, int sum) { int k = 0, j = 0; if (n == 0) return; k = n % 10; j = n / 10; sum = sum + k; foo(j, sum); printf ("%d,", k); } int main () { int a = 2048, sum = 0; foo(a, sum); printf ("%d\n", sum); }
What does the above program print?
8, 4, 0, 2, 14
 
8, 4, 0, 2, 0  
2, 0, 4, 8, 14  
2, 0, 4, 8, 0 
⇒ foo (a, sum) = foo (2048,0)
⇒ n == 2048
⇒ k = n%10 = 2048%10 = 8
⇒ j = n/10 = 2048/10 = 204
Sum = Sum+k = 0+8 = 8
foo(j, sum) = foo(204, 8)
⇒ n=204
k = n%10 = 204%10 = 4
j = n/10 = 204/10 = 20
sum = sum+k = 12+0 = 12
foo(j, sum) =foo(2,12)
⇒ n=2
k = n%10 = 2%10 = 2
j = n/10 = 2/10 = 0
sum = 14
foo(0,14) ⇒ n==0
printf("%d", k) ⇒ k = 2, 0, 4, 8
After foo( ) statement one more printf statement is there then if print 0 after all digits of n.
2, 0, 4, 8, 0.
Question 32 
Consider the following Cprogram:
double foo (double); /* Line 1 */ int main() { double da, db; // input da db = foo(da); } double foo(double a) { return a; }
The above code compiled without any error or warning. If Line 1 is deleted, the above code will show:
no compile warning or error  
some compilerwarnings not leading to unintended results  
some compilerwarnings due to typemismatch eventually leading to unintended results  
compiler errors 
Question 33 
Postorder traversal of a given binary search tree T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?
9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95  
9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29  
29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95  
95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29 
Question 34 
A PriorityQueue is implemented as a MaxHeap. Initially, it has 5 elements. The levelorder traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The levelorder traversal of the heap after the insertion of the elements is:
10, 8, 7, 5, 3, 2, 1  
10, 8, 7, 2, 3, 1, 5  
10, 8, 7, 1, 2, 3, 5  
10, 8, 7, 3, 2, 1, 5

Insert → 1 into heap structure
Insert → 7 into heap structure
Here, violating Maxheap property. So perform heapify operation.
The final sequence is 10, 8, 7, 3, 2, 1, 5.
Question 35 
How many distinct binary search trees can be created out of 4 distinct keys?
5  
14  
24  
42 
(or)
t(0)=1
t(1)=1
t(4) = t(0)t(3) + t(1)t(2) + t(2)t(1) + t(3)t(0)
= 5+2+2+5
= 14
(or)
^{8}C_{4} / 5 = 14
Question 36 
In a complete kary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:
nk  
(n  1) k + 1  
n (k  1) + 1  
n (k  1) 
Leaves = total nodes  internal nodes
= nk+1n
= n(k1)+1
Question 37 
Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?
T(n) = O(n^{2})  
T(n) = θ(n log n)  
T(n) = Ω(n^{2})
 
T(n) = O(n log n) 
a=2, b=2, k=1, p=0.
The recurrence relation result will be O(n logn).
Question 38 
Let G(V,E) be an undirected graph with positive edge weights. Dijkstra's single source shortest path algorithm can be implemented using the binary heap data structure with time complexity:
O(V^{2})  
O(E+VlogV)  
O(VlogV)  
O((E+V)logV) 
In worst case graph will be a complete graph i.e total edges = v(v1)/2 where v is no. of vertices.
E<=v^{2}
Time Complexity of Dijkstra's algorithms is:
1. With Adjacency List and Priority queue: O((v+e) log v) ⇒ O(e log v)
2. With matrix and Priority queue: O(v^{2} + e log v)
3. With Fibonacci Heap and adjacency list : O(e + v log v)
Question 39 
Suppose there are ⌈log n⌉ sorted lists of ⌊n/log n⌋ elements each. The time complexity of producing a sorted list of all these elements is: (Hint: Use a heap data structure)
O(nlog log n)  
θ(nlog n)  
Ω(nlog n)  
Ω(n^{3/2}) 
P = log n
Q = n/log n
∴ Putting values we get,
O(n log log n)
Question 40 
Let P, Q and R be three atomic prepositional assertions. Let X denote (P ∨ Q) → R and Y denote (P → R) ∨ (Q → R). Which one of the following is a tautology?
X ≡ Y  
X → Y  
Y → X  
¬Y → X 
⇒ ∼(P∨Q) ∨ R
⇒ (∼P∧∼Q) ∨ R
⇒ (∼P∨R) × (∼Q∨R)
⇒ (P→R) ∧ (Q→R)
Option B: X→Y
[(P→R) × (Q→R)] → [(P→R) ∨ (Q→R)]
∼[(P→R) × (Q→R) ∨ (P→R) ∨ (Q→R)]
[∼(P→R) ∨ ∼(Q→R)] ∨ [(P→R) ∨ (Q→R)]
[∼(P→R) ∨ (P→R)] ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] ∨ [∼(Q→R) ∨ (Q→R)]
T ∨ [∼(P→R) ∨ (Q→R)] ∨ [(Q→R) ∨ (P→R)] V T
T (✔️)
Question 41 
What is the first order predicate calculus statement equivalent to the following?
Every teacher is liked by some student
∀(x) [teacher(x) → ∃ (y) [student(y) → likes (y, x)]]  
∀(x) [teacher(x) → ∃ (y) [student(y) ∧ likes (y, x)]]  
∃(y) ∀(x) [teacher(x) → [student(y) ∧ likes (y, x)]]  
∀(x) [teacher(x) ∧ ∃ (y)[student(y) → likes (y, x)]] 
Option B: If x is a teacher, then there exists some y, who is a student and like x. (✔️)
Option C: There exists a student who likes all teachers.
Option D: If x is a teacher and then there exists some y, if y is a student then y likes x.
Question 42 
Let R and S be any two equivalence relations on a nonempty set A. Which one of the following statements is TRUE?
R∪S, R∩S are both equivalence relations.  
R∪S is an equivalence relation.  
R∩S is an equivalence relation.  
Neither R∪S nor R∩S is an equivalence relation. 
Let (a,b) present in R and (b,c) present in S and (a,c) is not present in either of them. Then R∪S will contain (a,b) and (b,c) but not (a,c) and hence not transitive.
And equivalence relation must satisfy 3 property:
(i) Reflexive
(ii) Symmetric
(iii) Transitive
But as we have seen that for R∪S, Transitivity is not satisfied.
Question 43 
Let f: B → C and g: A → B be two functions and let h = f∘g. Given that h is an onto function. Which one of the following is TRUE?
f and g should both be onto functions
 
f should be onto but g need not be onto  
g should be onto but f need not be onto  
both f and g need not be onto 
f: B→C and g: A→B are two functions.
h = f∘g = f(g(x))
→ If his onto function, that means for every value in C, there must be value in A.
→ Here, we are mapping C to A using B, that means for every value in C there is a value in B then f is onto function.
→ But g may (or) may not be the onto function i.e., so values in B which may doesn't map with A.
Question 44 
What is the minimum number of ordered pairs of nonnegative numbers that should be chosen to ensure that there are two pairs (a,b) and (c,d) in the chosen set such that
a ≡ c mod 3 and b ≡ d mod 5
4  
6  
16  
24 
That means a = 0,1,2 ⇒ 3
b = dmod5
That means b = 0,1,2,3,4 ⇒ 4
→ Total no. of order pairs = 3 * 5 = 15
→ Ordered pair (c,d) has 1 combination.
Then total no. of combinations = 15+1 = 16
Question 45 
Consider three decision problems P_{1}, P_{2} and P_{3}. It is known that P_{1} is decidable and P_{2} is undecidable. Which one of the following is TRUE?
P_{3} is decidable if P_{1} is reducible to P_{3}
 
P_{3} is undecidable if P_{3} is reducible to P_{2}  
P_{3} is undecidable if P_{2} is reducible to P_{3}  
P_{3} is decidable if P_{3} is reducible to P_{2}'s complement

Option B: If P_{3} is reducible to P_{2}, then P_{3} cannot be harder than P_{2}. But P_{2} being undecidable, this can't say P_{3} is undecidable.
Option C: If P_{2} is reducible to P_{3}, then P_{3} is atleast as hard as P_{2}. Since, P_{2} is undecidable. This means P_{3} is also undecidable.
Question 46 
Consider the set H of all 3 × 3 matrices of the type
a f e 0 b d 0 0 c
where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication operation, the set H is
a group  
a monoid but not a group
 
a semi group but not a monoid  
neither a group nor a semi group

The algebraic structure is a group because the given matrix can have inverse and the inverse is nonsingular.
Question 47 
Which one of the following graphs is NOT planar?
G_{1}  
G_{2}  
G_{3}  
G_{4} 
which is planar
G_{3} can also be drawn as
which is planar
G_{4} can also be drawn as
which is planar
But G_{1} cannot be drawn as planar graph.
Hence, option (A) is the answer.
Question 48 
Consider the following system of equations in three real variables x_{l}, x_{2} and x_{3}
2x_{l}  x_{2} + 3x_{3} = 1 3x_{l} 2x_{2} + 5x_{3} = 2 x_{l} + 4x_{2} + x_{3} = 3
This system of equations has
no solution  
a unique solution  
more than one but a finite number of solutions  
an infinite number of solutions

2(2  20) +1(3 + 5) + 3(12  2)
= 44 + 8 + 30
= 6 ≠ 0
→ A ≠ 0, we have Unique Solution.
Question 49 
What are the eigenvalues of the following 2 × 2 matrix?
2 1 4 5
1 and 1  
1 and 6  
2 and 5  
4 and 1 
A = (2  λ)(5  λ)  (4) = 0
10  7λ+ λ^{2}  4 = 0
λ^{2}  7λ + 6 = 0
λ^{2}  6λ  λ + 6 = 0
(λ  6) 1(λ  6) = 0
λ = 1 (or) 6
Question 50 
Let , where x<1. What is g(i)?
i  
i+1  
2i  
2^{i} 
Put g(i) = i+1
S = 1 + 2x + 3x^{2} + 4x^{3} + .....
Sx = 1x + 2x^{2} + 3x^{3} + 4x^{4} + ......
S  Sx = 1 + x + x^{2} + x^{3} + .....
[Sum of infinite series in GP with ratio < 1 is a/1r]
S  Sx = 1/(1x)
S(1x) = 1/(1x)
S = 1/(1x)^{2}
Question 51 
Box P has 2 red balls and 3 blue balls and box Q has 3 red balls and 1 blue ball. A ball is selected as follows:
(i) Select a box (ii) Choose a ball from the selected box such that each ball in the box is equally likely to be chosen. The probabilities of selecting boxes P and Q are (1/3) and (2/3), respectively.
Given that a ball selected in the above process is a red ball, the probability that it came from the box P is
4/19  
5/19  
2/9  
19/30 
Q → 3 red, 1 blue
The probability of selecting a red ball is
(1/3)(2/5) + (2/3)(3/4)
2/15 + 1/2 = 19/30
The probability of selecting a red ball from P
(1/3) * (2/5) = 2/15
→ The colour of ball is selected is to be red and that is taken from the box P.
⇒ Probability of selecting a red ball from P/Probability of selecting a red ball
⇒ (2/15)/(19/30)
⇒ 4/19
Question 52 
A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is:
1/2^{n}  
1  1/n  
1/n!  
1(1/2^{n}) 
Hence Probability = (2^{n}  1) /2^{n} = 1  1/2^{n}
Question 53 
Consider the machine M:
The language recognized by M is:
{w ∈ {a, b}*  every a in w is followed by exactly two b's}  
{w ∈ {a, b}* every a in w is followed by at least two b’}  
{w ∈ {a, b}* w contains the substring 'abb'}  
{w ∈ {a, b}* w does not contain 'aa' as a substring} 
Ex: abbbb, abbb...
Option B: It is True. If a string is to be accepted by given machine then it have atleast two b's.
Option C: It is false. Ex: abba. It contains 'abb' as a substring but not accepted by given machine.
Option D: It is false. Ex: abbab. It is not accepted by TM. It doesn't have 'aa' as a substring but not accepting.
Question 54 
Let N_{f} and N_{p} denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let D_{f} and D_{p} denote the classes of languages accepted by deterministic finite automata and deterministic pushdown automata, respectively. Which one of the following is TRUE?
D_{f} ⊂ N_{f} and D_{p} ⊂ N_{p}
 
D_{f} ⊂ N_{f} and D_{p} = N_{p}  
D_{f} = N_{f} and D_{p} = N_{p}  
D_{f} = N_{f} and D_{p} ⊂ N_{p} 
So D_{f} = N_{f}
NPDA can accept more languages than DPDA.
D_{p} ⊂ N_{p}
Question 55 
Consider the languages:
L_{1} = {a^{n}b^{n}c^{m} n,m > 0} and L_{2} = {a^{n}b^{m}c^{m} n,m > 0}
Which one of the following statements is FALSE?
L_{1} ∩ L_{2} is a contextfree language  
L_{1} ∪ L_{2} is a contextfree language  
L_{1} and L_{2} are contextfree languages  
L_{1} ∩ L_{2} is a context sensitive language 
CFL is not closed under Intersection.
L_{1} = {a^{n}b^{n}c^{m}  n>0 & m>0}
L_{2} = {a^{m}b^{n}c^{n}  n>0 & m>0}
L_{3} = L_{1} ∩ L_{2}
={a^{n}b^{n}c^{n}  n>0} It is not contextfree.
Question 56 
Let L_{1} be a recursive language, and let L_{2} be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
But, recursive enumerable languages are not closed under complementation.
If L_{1} is recursive, then L_{1}', is also recursive.
If L_{2} is recursive enumerable, then L_{2}', is not recursive enumerable language.
Question 57 
Consider the languages:
L_{1} = {ww^{R} w ∈ {0,1}*} L_{2} = {w#w^{R}  w ∈ {0,1}*}, where # is a special symbol L_{3} = {ww  w ∈ (0, 1)*}
Which one of the following is TRUE?
L_{1} is a deterministic CFL
 
L_{2} is a deterministic CFL  
L_{3} is a CFL, but not a deterministic CFL  
L_{3} is a deterministic CFL 
→ Given L_{1} is CFL but not DCFL.
→ Because, we can't predict where w ends and where it reverse is starts.
→ L_{2} = {w#w^{R}  w ∈ (0,1)*}
→ Given L_{2} is CFL and also DCFL.
→ The string w and w^{R} are separated by special symbol '#'.
→ L_{3} = {ww  w ∈ (0,1)*}
This is not even a CFL. This can be proved by using pumping lemma. So, L_{2} is DCFL. (✔️)
Question 58 
Consider the following two problems on undirected graphs:
 α: Given G(V,E), does G have an independent set of size V4?
β: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE?
α is in P and β is NPcomplete  
α is NPcomplete and β is in P  
Both α and β are NPcomplete  
Both α and β are in P

Question 59 
Consider the grammar:
E → E + n  E × n  n
For a sentence n + n × n, the handles in the rightsentential form of the reduction are:
n, E + n and E + n × n  
n, E + n and E + E × n
 
n, n + n and n + n × n  
n, E + n and E × n 
→ E + E * n {Applying E → E * n}
→ E + n * n {Applying E → n}
→ n + n * n {Applying E → n}
We use n, E+n, E×n reductions to get a sentence n+n*n.
Question 60 
Consider the grammar:
S → (S)  a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n_{1}, n_{2} and n_{3} respectively. The following relationship holds good:
n_{1} < n_{2} < n_{3}  
n_{1} = n_{3} < n_{2}  
n_{1} = n_{2} = n_{3}  
n_{1} ≥ n_{3} ≥ n_{2} 
→ LR(1) be the states of LR(1) items.
→ LR(0) items never be greater than LR(1) items then SLR(1) = LALR(1) < LR(1)
n_{1} = (n_{3}) < (n_{2})
Question 61 
Consider line number 3 of the following Cprogram.
int main ( ) { /* Line 1 */ int I, N; /* Line 2 */ fro (I = 0, I < N, I++); /* Line 3 */ }
Identify the compiler's response about this line while creating the objectmodule:
No compilation error
 
Only a lexical error  
Only syntactic errors  
Both lexical and syntactic errors 
Question 62 
Consider the following circuit involving a positive edge triggered D FF.
Consider the following timing diagram. Let A_{i} represent the logic level on the line A in the ith clock period.
Let A' represent the complement of A. The correct output sequence on Y over the clock periods 1 through 5 is
A_{0} A_{1} A_{1}' A_{3} A_{4}  
A_{0} A_{1} A_{2}' A_{3} A_{4}  
A_{1} A_{2} A_{2}' A_{3} A_{4}  
A_{1} A_{2}' A_{3} A_{4} A_{5}' 
Input will be accepted by the flipflop after the cycle gets finished, because +ve edge is occurring at the end of the clock cycle only.
Question 63 
The following diagram represents a finite state machine which takes as input a binary number from the least significant bit.
Which one of the following is TRUE?
It computes 1's complement of the input number  
It computes 2's complement of the input number  
It increments the input number  
It decrements the input number

Input = 1000
Output = 1111
The FSM, doesn't change until the first 1 come
I/p = 1000
1's complement = 0111
2's complement = 0111

1000 = I/p

It results 2's complement.
Question 64 
Consider the following circuit.
The flipflops are positive edge triggered D FFs. Each state is designated as a two bit string Q_{0}Q_{1}. Let the initial state be 00. The state transition sequence is:
Question 65 
Consider a three word machine instruction
ADD A[R0], @B
The first operand (destination) "A[R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand).
The number of memory cycles needed during the execution cycle of the instruction is
3  
4  
5  
6 
1 → To get 1^{st} operand from memory address (Read).
1 → To get 2^{nd} operand Address (Read).
1 → To get 2^{nd} operand from the address given by previous memory (Read).
1 → To store first operand (Write).
3R + 1W = 4
Question 66 
Match each of the high level language statements given on the left hand side with the most natural addressing mode from those listed on the right hand side.
(1) A[1] = B[J]; (a) Indirect addressing (2) while [*A++]; (b) Indexed addressing (3) int temp = *x; (c) Auto increment
(1, c), (2, b), (3, a)  
(1, a), (2, c), (3, b)  
(1, b), (2, c), (3, a)  
(1, a), (2, b), (3, c) 
Here using the Index.
(b) while [*A++]; Auto increment.
The memory is increments automatically.
(c) int temp = *x; Indirect Addressing.
Here temp is assigned to integer type of Address contained in x.
Question 67 
Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively.
10, 17  
10, 22  
15, 17  
5, 17 
So indexing requires 10 bits.
No. of offset bit required to access 32 byte block = 5
So, No. of TAG bits = 32  10  5 = 17
Question 68 
A 5 stage pipelined CPU has the following sequence of stages:
IF — Instruction fetch from instruction memory. RD — Instruction decode and register read. EX — Execute: ALU operation for data and address computation. MA — Data memory access  for write access, the register read at RD stage is used. WB — Register write back.
Consider the following sequence of instructions:
I_{1} : L R0, 1oc1; R0 <= M[1oc1] I_{2} : A R0, R0 1; R0 <= R0 + R0 I_{3} : S R2, R0 1; R2 <= R2  R0 Let each stage take one clock cycle.
What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I_{1}?
8  
10  
12  
15 
If we don't use operator forwarding:
Total clock cycles = 8/11
There is no '11' in option.
Then no. of cycles = 8
Question 69 
A device with data transfer rate 10 KB/sec is connected to a CPU. Data is transferred bytewise. Let the interrupt overhead be 4 μsec. The byte transfer time between the device interfaces register and CPU or memory is negligible. What is the minimum performance gain of operating the device under interrupt mode over operating it under programcontrolled mode?
15  
25  
35  
45 
In 1 sec it transfer 10 KB of data = 10 × 10^{3} B = 10^{4}B
Data interrupt overhead = 4μsec = 4×10^{6} sec
Transferring 10KB overhead = 4×10^{6}×10^{4}sec
Performance gain = 1/(4×10^{6}×10^{4}) = 10^{2}/4 = 25
Question 70 
Consider a disk drive with the following specifications:
16 surfaces, 512 tracks/surface, 512 sectors/track, 1 KB/sector, rotation speed 3000 rpm. The disk is operated in cycle stealing mode whereby whenever one byte word is ready it is sent to memory; similarly, for writing, the disk interface reads a 4 byte word from the memory in each DMA cycle. Memory cycle time is 40 nsec. The maximum percentage of time that the CPU gets blocked during DMA operation is:
10  
25  
40  
50 
It reads 512 * 1024 B in one rotation.
Time taken to read 4B = 153ns
(153) for 4 is approximately = 160
Percentage CPU get blocked = 40*100/160 = 25
Question 71 
Suppose n processes, P_{1}, …., P_{n} share m identical resource units, which can be reserved and released one at a time. The maximum resource requirement of process P_{i} is s_{i}, where s_{i}>0. Which one of the following is a sufficient condition for ensuring that deadlock does not occur?
If the deadlock will never occur in the corresponding process then the following condition be true.
Question 72 
Consider the following code fragment:
if (fork() == 0) { a = a + 5; printf(“%d, %d\n”, a, &a); } else { a = a – 5; printf(“%d, %d\n”, a, &a); }
Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?
u = x + 10 and v = y
 
u = x + 10 and v is ≠ y  
u + 10 = x and v = y  
u + 10 = x and v ≠ y 
u = a  5; v be address of a
a = u + 5;
x, y values printed by child process.
x = a + 5; y be the address of a
x = u + 5 + 5; v = y
x = u + 10
Question 73 
In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is:
4  
6  
7  
9 
Packet size have minimum header overhead.
Question 74 
Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48bit jamming signal is 46.4 μs. The minimum frame size is:
94  
416  
464  
512 
Round trip propagation delay is RTT = 2*T_{p}
Minimum frame size of Ethernet can be found by using formula T_{t} = 2*T_{p}
Let L is minimum frame size. Then L / 10Mbps = 46.4 μs
L = 464 Kbits
It has nothing to do with jamming signal.
Question 75 
Let E_{1} and E_{2} be two entities in an E/R diagram with simple singlevalued attributes. R_{1} and R_{2} are two relationships between E_{1} and E_{2}, where R_{1} is onetomany and R_{2} is manytomany. R_{1} and R_{2} do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model?
2  
3  
4  
5 
R_{1} is one to many.
R_{2} is many to many.
→ E_{1} and E_{2} have separate table because they need to store multiple values.
→ R_{2} also have separate table by considering Primary keys E_{1} and E_{2} as foreign keys.
→ R_{1} is converted to many side table i.e., E_{2} as Primary key and E_{1} as Foreign key.
So, totally we need 3 tables to store the value.
Question 76 
The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with ondelete cascade.
A C  2 4 3 4 4 3 5 2 7 2 9 5 6 4
The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:
(3,4) and (6,4)  
(5,2) and (7,2)  
(5,2), (7,2) and (9,5)
 
(3,4), (4,3) and (6,4) 
Totally (5,2), (7,2), (9,5) are also deleted.
Question 77 
select title from book as B where (select count(*) from book as T where T.price > B.price) < 5
Titles of the four most expensive books
 
Title of the fifth most inexpensive book  
Title of the fifth most expensive book
 
Titles of the five most expensive books 
The where clause of outer query will be true for 5 most expensive books.
Question 78 
Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold: {A → B, BC → D, E → C, D → A}. What are the candidate keys of R?
AE, BE  
AE, BE, DE  
AEH, BEH, BCH  
AEH, BEH, DEH 
So only option (D) contains E and H as part of candidate key.
Question 79 
Consider the following data path of a CPU.
The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation  the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.
The instruction "add R0, R1" has the register transfer interpretation R0 <= R0+R1. The minimum number of clock cycles needed for execution cycle of this instruction is:
2  
3  
4  
5 
1 cycle → Load PC to MAR
1 cycle → Fetch memory and load to PC

3 cycles

Question 80 
Consider the following data path of a CPU.
The, ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation  the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR.
The instruction "call Rn, sub" is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is
Rn <= PC + 1; PC <= M[PC];
The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:
2  
3  
4  
5 
1 cycle → Load PC to MAR
1 cycle → Fetch memory and load to PC

3 cycles

Question 81 
Consider the following Cfunction:
double foo (int n) { int i; double sum; if (n == 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo(i); return sum; } }
The space complexity of the above function is:
O(1)  
O(n)  
O(n!)  
O(n^{n}) 
Time complexity is O(2^{n}).
foo(n) = foo(n1) + foo(n2) + ... + 1
foo(n1) = foo(n2) + foo(n3) + ...
=> foo(n) = 2*foo(n1), foo(0) = 1
=> foo(n) is in O(2^{n}) [By recursion tree method you can solve it].
Question 82 
Consider the following Cfunction:
double foo (int n) { int i; double sum; if (n == 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo(i); return sum; } }
Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:
O(1)  
O(n)  
O(n^{2})
 
O(n!) 
Question 83 
Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
The edge e must definitely belong to:
the minimum weighted spanning tree of G
 
the weighted shortest path from s to t
 
each path from s to t  
the weighted longest path from s to t 
Question 84 
Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X, Y] be a partition of V such that s ∈ X and t ∈ Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
a path from s to t in the minimum weighted spanning tree
 
a weighted shortest path from s to t  
an Euler walk from s to t  
a Hamiltonian path from s to t 
Minimum congestion is the edge with maximum weight among all other edges included in the path.
Now suppose shortest path from A→B is 6, but in MST, we have A→C→B(A→C=4, C→B=3), then along the path in MST, we have minimum congestion i.e., 4.
Question 85 
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val E '+' E E^{(1)}.val = E^{(2)}.val + E>sup>(3).val E '×' E E^{(1)}.val = E^{(2)}.val × E^{(3)}.val
The above grammar and the semantic rules are fed to a yacc tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
It detects recursion and eliminates recursion
 
It detects reducereduce conflict, and resolves
 
It detects shiftreduce conflict, and resolves the conflict in favor of a shift over a reduce action  
It detects shiftreduce conflict, and resolves the conflict in favor of a reduce over a shift action

Question 86 
Consider the following expression grammar. The semantic rules for expression calculation are stated next to each grammar production.
E → number E.val = number. val E '+' E E^{(1)}.val = E^{(2)}.val + E>sup>(3).val E '×' E E^{(1)}.val = E^{(2)}.val × E^{(3)}.val
Assume the conflicts in Part (a) of this question are resolved and an LALR(1) parser is generated for parsing arithmetic expressions as per the given grammar. Consider an expression 3 × 2 + 1. What precedence and associativity properties does the generated parser realize?
Equal precedence and left associativity; expression is evaluated to 7
 
Equal precedence and right associativity; expression is evaluated to 9  
Precedence of '×' is higher than that of '+', and both operators are left associative; expression is evaluated to 7  
Precedence of '+' is higher than that of '×', and both operators are left associative; expression is evaluated to 9 
Hence, the answer is 9 and right associative.
Question 87 
We are given 9 tasks T_{1}, T_{2}.... T_{9}. The execution of each task requires one unit of time. We can execute one task at a time. Each task T_{i} has a profit P_{i} and a deadline d_{i} Profit P_{i} is earned if the task is completed before the end of the d_{i}^{th} unit of time.
Task T_{1} T_{2} T_{3} T_{4} T_{5} T_{6} T_{7} T_{8} T_{9} Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3
Are all tasks completed in the schedule that gives maximum profit?
All tasks are completed  
T_{1} and T_{6} are left out
 
T_{1} and T_{8} are left out  
T_{4} and _{6} are left out 
T_{3} T_{9} T_{7} T_{2} T_{4} T_{5} T_{8} T_{1} T_{6}
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T_{3} to T_{6}, upto their maximum deadline possible.
So T_{4} and T_{6} are left out.
Question 88 
We are given 9 tasks T_{1}, T_{2}.... T_{9}. The execution of each task requires one unit of time. We can execute one task at a time. Each task T_{i} has a profit P_{i} and a deadline d_{i} Profit P_{i} is earned if the task is completed before the end of the d_{i}^{th} unit of time.
Task T_{1} T_{2} T_{3} T_{4} T_{5} T_{6} T_{7} T_{8} T_{9} Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3
What is the maximum profit earned?
147  
165  
167  
175 
30+25+23+20+18+16+15 = 147
Question 89 
Consider the following floating point format.
Mantissa is a pure fraction in signmagnitude form.
The decimal number 0.239 × 2^{13} has the following hexadecimal representation (without normalization and rounding off:
0D 24  
0D 4D  
4D 0D  
4D 3D 
Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)_{2}
Bias = 64. So biased exponent is 13+64 = 77= (1001101)_{2}
0.239 × 2^{13} = 0 1001101 00111101
= 0100 1101 0011 1101
= 4 D 3 D
Question 90 
Consider the following floating point format.
Mantissa is a pure fraction in signmagnitude form.
The normalized representation for the above format is specified as follows. The mantissa has an implicit 1 preceding the binary (radix) point. Assume that only 0's are padded in while shifting a field. The normalized representation of the above number (0.239 × 2^{13}) is
0A 20  
11 34  
4D D0
 
4A E8 
Convert 0.239 to binary
0.239 * 2 = 0.478
0.478 * 2 = 0.956
0.956 * 2 = 1.912
0.912 * 2 = 1.824
0.824 * 2 = 1.648
0.648 * 2 = 1.296
0.296 * 2 = 0.512
0.512 * 2 = 1.024
Mantissa = (0. 00111101)_{2}
0.239 × 2^{13} = 1.11101000 x 2^{10} < Normalized Mantissa
Bias = 64. So biased exponent is 10+64 = 74 = (1001010)_{2}
0.239 × 2^{13} = 0 1001010 11101000
= 0100 1010 1110 1000
= (4 A E 8)_{16}