Gate-2008

Question 1
 
A
1
B
-1
C
D
-∞
       Engineering Mathematics        alculus
Question 1 Explanation: 
Question 2
If P, Q, R are subsets of the universal set U, then (P∩Q∩R) ∪ (Pc∩Q∩R) ∪ Q∪ Rc is
A
Qc ∪ Rc
B
P ∪ Qc ∪ Rc
C
Pc ∪ Qc ∪ Rc
D
U
       Engineering Mathematics        Sets And Relations
Question 2 Explanation: 
Given, (P∩Q∩R)∪(Pc∩Q∩R)∪Qc∪Rc
It can be written as the p.q.r + p'.q.r +q'+r'
=> (p+p').q.r + q' +r'
=> q.r +(q'+r')
=> q.r + q'+r' = 1 i.e U
Question 3
 
A
0
B
either 0 or 1
C
one of 0, 1 or -1
D
any real number
       Engineering Mathematics        Linear Algebra
Question 3 Explanation: 
The conjugate matrix [A|B] is
When a-5=0, then rank(A)=rank[A|B]<3,
So infinite number of solutions.
But, it is given that the given system has unique solution i.e., rank(A)-rank[A|B]=3 will be retain only if a-5≠0.
Question 4
In the IEEE floating point representation, the hexadecimal value 0×00000000 corresponds to
A
the normalized value 2-127
B
the normalized value 2-126
C
the normalized value +0
D
the special value +0
       Digital Logic Design        Number System
Question 4 Explanation: 
Value is ±0 if M=0 and E=0.
Question 5
       
A
B
C
D
       Digital Logic Design        K Map
Question 5 Explanation: 
Question 6
A
decimal 10
B
decimal 11
C
decimal 10 and 11
D
any value >2
       Digital Logic Design        Number System
Question 6 Explanation: 

Any value of r will satisfy the above equation. But the radix should be greater than 2 because the 121 has 2. So r >2 is correct.
Question 7
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
A
θ(n)
B
θ(m)
C
θ(m+n)
D
θ(mn)
       Data Structures        Graphs
Question 7 Explanation: 
To find the number of connected components using either BFS or DFS time complexity is θ(m+n).
Suppose if we are using Adjacency matrix means it takes θ(n2).
Question 8
 
A
Σm(4,6)
B
Σm(4,8)
C
Σm(6,8)
D
Σm(4,6,8)
       Data Structures        Canonical Normal Form
Question 8 Explanation: 
f= f1* f2 + f3
f1*f2 is intersection of minterms of f1 and f2
f= (f1*f2) + f3 is union of minterms of (f1*f2) and f3
Σm(1,6,8,15)= Σm(4,5,6,7,8) * f2 + Σm(1,6,15)
Options A, B and D have minterm m4 which result in Σm(1,4,6,15), Σm(1,4,6,8, 15) and Σm(1,4,6,8, 15)respectively and they are not equal to f.
Option C : If f2= Σm(6,8)
RHS: Σm(4,5,6,7,8) * Σm(6,8) + Σm(1,6,15)
=Σm(6,8) + Σm(1,6,15)
= Σm(1,6,8,15)
= f= LHS
Question 9
Which of the following is true for the language {ap|p is a prime} ?  
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free, but accepted by a Turing machine
       Theory of Computation        Identify Class Language
Question 9 Explanation: 
Finding prime number cannot be done by FA or PDA , so it cannot be regular or CFL. This language can be recognized by LBA , hence it can be accepted by Turing Machine.
Question 10
     
A
I and II
B
I and IV
C
II and III
D
II and IV
       Theory of Computation        Decidability And Undecidability
Question 10 Explanation: 
The intersection of two regular languages is always a regular language (by closure property of regular language) and testing infiniteness of regular language is decidable. Hence statement I is decidable.
Statement IV is also decidable, we need to check that whether the given grammar satisfies the CFG rule (TYPE 2 grammar productions).
But statements II and III are undecidable, as there doesn’t exist any algorithm to check whether a given context-free language is regular and whether two push-down automata accept the same language.
Question 11
Which of the following describes a handle (as applicable to LR-parsing) appropriately?
A
It is the position in a sentential form where the next shift or reduce operation will occur.
B
It is non-terminal whose production will be used for reduction in the next step.
C
It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur.
D
It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
       Compiler Design        Parsers
Question 11 Explanation: 
A handle is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found.
Question 12
Some code optimizations are carried out on the intermediate code because
A
They enhance the portability of the compiler to other target processors
B
Program analysis is more accurate on intermediate code than on machine code
C
The information from dataflow analysis cannot otherwise be used for optimization
D
The information from the front end cannot otherwise be used for optimization
       Compiler Design        Compilers
Question 12 Explanation: 
The code-optimization on intermediate code generation will always enhance the portability of the compiler to target processors. The main reason behind this is, as the intermediate code is independent of the target processor on which the code will be executed, so the compiler is able to optimize the intermediate code more conveniently without bothering the underlying architecture of target processor.
Question 13
A
regular
B
context-free
C
context-sensitive
D
recursive
       Theory of Computation        Recursive and Recursively Enumerable Language
Question 13 Explanation: 
If L is recursive enumerable, then it implies that there exist a Turing Machine (lets say M1) which always HALT for the strings which is in L.
If are recursively enumerable, then it implies that there exist a Turing Machine (lets say M2) which always HALT for the strings which is NOT in L(as L is complement of Since we can combine both Turing machines (M1 and M2) and obtain a new Turing Machine (say M3) which always HALT for the strings if it is in L and also if it is not in L. This implies that L must be recursive.
Question 14
What is the maximum size of data that the application layer can pass on to the TCP layer below?
A
Any size
B
216 bytes-size of TCP header
C
216 bytes
D
1500 bytes
       Computer Networks        Application Layer Protocol
Question 14 Explanation: 
Application Layer - Any size
Transport Layer - 65515 byte
Network layer - 65535 byte
Data link layer - 1500 byte
Question 15
A
I only
B
II only
C
III only
D
III and IV only
       Database Management System        Relational Calculus
Question 15 Explanation: 
Demorgan law:
∀xP(x)≡∼∃x(∼P(x))
∼∀x(∼P(x))≡∃x(P(x))
Given: ∀t ∈ r(P(t))------ (1)
As per Demorgan law
(1) ⇒ ∼∃t ∈ r(∼P(t))
which is option (III).
Question 16
A clustering index is defined on the fields which are of type
A
non-key and ordering
B
non-key and non-ordering
C
key and ordering
D
key and non-ordering
       Database Management System        Indexing
Question 16 Explanation: 
Create index files, fields could be non-key attributes and which are in ordered form so as to form clusters easily.
Question 17
Which of the following system calls results in the sending of SYN packets?
A
socket
B
bind
C
listen
D
connect
       Computer Networks        Socket
Question 17 Explanation: 
When connect( ) is called by client, following three way handshake happens to establish the connection in TCP.
1) The client requests a connection by sending a SYN (synchronize) message to the server.
2) The server acknowledges this request by sending SYN-ACK back to the client.
3) The client responds with an ACK, and the connection is established.
Question 18
 
A
x = 3, y = 4, z = 2
B
x = 6, y = 5, z = 3
C
x = 6, y = 3, z = 5
D
x = 5, y = 4, z = 5
       Programming       C Program
Question 18 Explanation: 
Required final output value of a=4.
→ We can directly eliminate the options B & C, because none of the variable can assign a value 4.
→ Given explanation is
a=(x>y)?((x>z)?x:z):((y>z)?y:z)
Option A:
x=3; y=4; z=2
a=(3>4)?⇒No
Then evaluate second expression⇒(4>2)?Yes
⇒a=y
a=4 (True)
Option D:
x=5; y=4; z=5
a=(5>4)⇒Yes
Then evaluate first expression ⇒ (5>5)? No
⇒ a=z ⇒ a=5 (Not true)
⇒Answer is Option A.
Question 19
 
A
MNOPQR
B
NQMPOR
C
QMNPRO
D
QMNPOR
       Data Structures        Graphs
Question 19 Explanation: 

Check with the options:
Option A: MNOPQR
→ If queue starts with M then neighbour nodes are {N,Q,R}.
→If Q starts with M then string is not matching with neighbour nodes.
So, option A is wrong.
Option B: NQMPOR
→ Neighbours of N is ⇒ {Q,M,O}
String is not matched with neighbours.
So, option B is wrong.
Question 20
The data blocks of a very large file in the Unix file system are allocated using  
A
contiguous allocation
B
linked allocation
C
indexed allocation
D
an extension of indexed allocation
       Operating Systems        File System
Question 20 Explanation: 
An Unix file system can utilizes an extension of indexed allocation. Because it uses direct blocks, single indirect blocks, double indirect blocks and triple indirect blocks.
Question 21
     
A
1000e
B
1000
C
100e
D
100
       Engineering Mathematics        Trapezidal Rule
Question 21 Explanation: 
Trapezoidal rule error is En=(b-a)3/ 12N2 f''(c)
The given, Maximum error: 1/3×10-6
Then |En|<1/3×10-6
Upper bound b=z,
Lower bound a=1
⇒ Finally,

Answer is Option A.
Question 22
 
A
square of R
B
reciprocal of R
C
square root of R
D
logarithm of R
       Engineering Mathematics        Newton Raphson Method
Question 22 Explanation: 
The given expression is
xn+1=1/2(xn+R/xn)
It can be written as
xn+1=xn-((xn)2-R)/2xn
It computes square root R.
Correct option is C.
Question 23
Which of the following statements is true for every planar graph on n vertices?
A
The graph is connected
B
The graph is Eulerian
C
The graph has a vertex-cover of size at most 3n/4
D
The graph has an independent set of size at least n/3
       Engineering Mathematics        Graph Theory
Question 23 Explanation: 
Lets do with elimination method,
(A) Consider the following disconnected graph which is planar.

So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K4 graph. It has independent set size 1 which is less than 4/3.

So false.
Hence, option (C) is correct.
Question 24
   
A
P = Q - k
B
P = Q + k
C
P = Q
D
P = Q +2 k
       Engineering Mathematics        Permutation and Combination
Question 24 Explanation: 

P=1+3+5+7+...+(2k-1)
=(2-1)+(4-1)+(6-1)+(8-1)+...+(2k-1)
=(2+4+6+8+...+2k)+(-1+-1+-1+k times)
=Q-(1+1+...+k times)
=Q-k
Question 25
A point on a curve is said to be an extremum if it is a local minimum or a local maximum. The number of distinct extrema for the curve 3x4 - 16x3 + 24x2 + 37 is
A
0
B
1
C
2
D
3
       Engineering Mathematics        Calculus
Question 25 Explanation: 
f(x)=3x4-16x3+24x2+37
f’(x)=12x3+48x2+48x=0 12x(x2-4x+4)=0 x=0; (x-2)2=0
x=2
f’’(x)=36x2-96x+48
f ”(0)=48
f ”(2)=36(4)-96(2)+48
=144-192+48
=0
At x=2, we can’t apply the second derivative test.
f’(1)=12; f’(3)=36, on either side of 2 there is no sign change then this is neither minimum or maximum.
Finally, we have only one Extremum i.e., x=0.
Question 26
 
A
B
C
D
       Digital Logic Design        Boolean Algebra
Question 26 Explanation: 
Question 27
Aishwarya studies either computer science or mathematics everyday. If she studies computer science on a day, then the probability that she studies mathematics the next day is 0.6. If she studies mathematics on a day, then the probability that she studies computer science the next day is 0.4. Given that Aishwarya studies computer science on Monday, what is the probability that she studies computer science on Wednesday?
A
0.24
B
0.36
C
0.4
D
0.6
       Engineering Mathematics        Probability
Question 27 Explanation: 
→ Aishwarya studied CS on Monday. Then we have two possibilities to she study computer science on wednesday.
(i) She study Mathematics on Tuesday and computer science on wednesday.
⇒ 0.6×0.4
⇒ 0.24
(ii) She study computer science on Tuesday and computer science on wednesday.
⇒ 0.4×0.4
⇒ 0.16
→ The probability that she study computer science on wednesday is
0.24+0.16=0.40
Question 28
       
A
one
B
two
C
three
D
four
       Engineering Mathematics        Linear Algebra
Question 28 Explanation: 




Answer: We have only one matrix with eigen value 1.
Question 29
Let X be a random variable following normal distribution with mean +1 and variance 4. Let Y be another normal variable with mean -1 and variance unknown. If P(X ≤ -1) = P(Y ≥ 2), the standard deviation of Y is
A
3
B
2
C
√2
D
1
       Engineering Mathematics        Probability
Question 29 Explanation: 
P(X ≤ -1) = P(Y ≥ 2)
We can compare their values using standard normal distributions.

The above equation satisfies when σy will be equal to 3.
Question 30
 
A
(∀x fsa(x)) ⇒ (∃y pda(y) ∧ equivalent(x,y))
B
∼∀y(∃x fsa(x) ⇒ pda(y) ∧ equivalent(x,y))
C
∀x ∃y(fsa(x) ∧ pda(y) ∧ equivalent(x,y))
D
∀x ∃y(fsa(y)∧ pda(x) ∧ equivalent(x,y))
       Engineering Mathematics        Propositional Logic
Question 30 Explanation: 
Go through the options.
Option A:
If everything is a FSA. Then there exists an equivalent PDA for everything.
Option B:
Not for the case Y, if there exists a FSA then it can have equivalent PDA.
Option C:
Everything is a PDA and consists equivalent PDA.
Option D:
Everything is a PDA and has exist an equivalent FSA. In option A we are getting the equivalent of a and b.
So answer is option A.
Question 31
       
A
Only I and II
B
Only I, II and III
C
Only I, II and IV
D
All of I, II, III and IV
       Engineering Mathematics        Propositional
Question 31 Explanation: 
I. P∨∼Q (✔️)
II. ∼(∼P∧Q)⇒(P∨∼Q)≡I (✔️)
III. (P×Q)∨(P×∼Q)∨(∼P×∼Q)
P∧(Q∨∼Q)∨(∼P∧∼Q)
P∨(∼P×∼Q)
(P∨∼P)×(P∨∼Q)
(P∨∼Q)≡I=II (✔️)
IV. (P×Q)∨(P∧∼Q)∨(∼P×Q)
P×(Q∨∼Q)∨(∼P∧Q)
P∨(∼P×Q)
(P∨∼P)×(P∨Q)
(P∨Q)≠I (❌)
So I≡II≡III (✔️)
Question 32
For a magnetic disk with concentric circular tracks, the seek latency is not linearly proportional to the seek distance due to
A
non-uniform distribution of requests
B
arm starting and stopping inertia
C
higher capacity of tracks on the periphery of the platter
D
use of unfair arm scheduling policies
       Computer Organization        Secondary Storage
Question 32 Explanation: 
No such direct relation exists between latency and seek distance.
The order in which the sectors are read from disks has tremendous impact on performance. This is mainly because of seek time if request for sector are random.
So (d) is appropriate answer because it causes random access of sectors.
Question 33
   
A
I only
B
II only
C
III Only
D
II and III only
       Computer Organization        Addressing Modes
Question 33 Explanation: 
I : Self relocating code always takes some address in memory. So auto-increment mode is not used for self relocating code. Hence this statement is wrong.
II. An additional ALU is not necessary for auto-increment. So this statement is wrong.
III. In auto-increment addressing mode the address where next data block to be stored is generated automatically depending upon the size of single data item required to store. This is based on pointer arithmetic. So this statement is true.
Hence option C is the answer.
Question 34
A
I only
B
II only
C
I and II only
D
I, II and III only
       Computer Organization        Machine Instruction
Question 34 Explanation: 
RFE is a privileged instruction that is performed explicitly by the Operating System to switch from kernel mode to user mode at the end of handling an exception. Hence it has to be a trap. We know when a trap/interrupt is in execution, till its completion all other trap/interrupts will not be allowed to execute. So option D is correct answer.
Question 35
 
A
IV only
B
I and IV only
C
I, III and IV only
D
I, II, III and IV
       Computer Organization        Cache Memory
Question 35 Explanation: 
Inclusion property: in this the presence of an address in a given level of the memory system guarantees that the address is present in all lower levels of the memory system.
1st is not always correct as data need not to be exactly same at the same point of time and so write back policy can be used in this instead of write through policy.
2nd is not needed when talking only about L1 and L2, as whether L2 is write through will have impact on any memory higher than L2, not on L1.
For 3rd, associativity can be equal also, so it need not be true.
For 4th statement, L2 cache has to be as large as L1 cache. In most cases L2 cache will be generally larger than L1 cache, but we will never have an L2 cache smaller than L1 cache. So only 4th statement is necessarily true. Hence option A is the answer.
Question 36
 
A
I and II only
B
I and III only
C
II and III only
D
I, II and III
       Computer Organization        Pipelining
Question 36 Explanation: 
I - False Bypassing can't handle all RAW hazard, consider when any instruction depends on the result of LOAD instruction, now LOAD updates register value at Memory Access Stage (MA), so data will not be available directly on Execute stage.
II - True, register renaming can eliminate all WAR Hazard.
III- If the 3rd statement says "Control hazard penalties can be completely eliminated by dynamic branch prediction", then it is false, but it is only given that "Control hazard penalties can be eliminated by dynamic branch prediction". So we can't say that this statement is false. In all the given options we don't have any option which says only statement I is false, so the next better choice is considering both statements I and III as false. Hence option B is the answer.
Question 37
A
I only
B
II only
C
III only
D
I, II and III
       Computer Organization        Run Time Environments
Question 37 Explanation: 
I is true because when we make a function call there are some input registers and some output registers. If function F() is calling function G(), we can make the caller function F()'s output registers the same as the called procedure G()'s input registers this is done using overlapping register windows.This will reduce the memory accesses so that F()'s output need not be put into memory for G() to access again from memory.
II is false as register saves and restores would still be required for each and every variable.
III is also false as instruction fetch is not affected by memory access using multiple register windows.
Question 38
In an instruction execution pipeline, the earliest that the data TLB (Translation Lookaside Buffer) can be accessed is
A
Before effective address calculation has started
B
During effective address calculation
C
After effective address calculation has completed
D
After data cache lookup has completed
       Computer Organization        Virtual Memory
Question 38 Explanation: 
TLB is a mini page table and it contains the frequently accessed page table entries. Because logical address is effective address, only after we calculate what is the effective address we can access the TLB. Hence option C is the correct answer.
Question 39
 
A
f(n) = O(g(n)); g(n) = O(h(n))
B
f(n) = Ω(g(n)); g(n) = O(h(n))
C
g(n) = O(f(n)); h(n) = O(f(n))
D
h(n) = O(f(n)); g(n) = Ω(f(n))
       Algorithms        Time Complexity
Question 39 Explanation: 
When we want to find asymptotically bigger/smaller functions, we have to follow basically 2 steps:
1. Check whether the function if polynomial time or exponential time.
2. Group them into polynomial functions and exponential function. The exponential functions are always bigger than polynomial functions.
As per the above 3 functions, the g(n) is greater than others. f(n) greater than h(n). So, the order of growth h(n) < f(n) < g(n).
Note: For computing, take always big number.
Question 40
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
A
θ(n)
B
θ(logn)
C
θ(log*n)
D
θ(1)
       Algorithms        Time Complexity
Question 40 Explanation: 
The Best way to find out whether an integer appears more than n/2 times in a sorted array(Ascending Order) of n integers, would be binary search approach.
1. The First occurrence of an element can be found out in O(log(n))time using divide and conquer technique,lets say it is i.
2. The Last occurrence of an element can be found out in O(log(n)) time using divide and conquer technique,lets say it is j.
3. Now number of occurrence of that element(count) is (j-i+1).
Overall time complexity = log n +log n +1 = O(logn)
Program:
/* If x is present in arr[low...high] then returns the index of first occurrence of x, otherwise returns -1 */
int binarySearch(int arr[], int low, int high, int x){
if (high >= low) {
int mid = (low + high)/2; /*low + (high - low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x */
if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) )
return mid;
else if (x > arr[mid]
) return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid -1), x);
}
return -1;
}
Note: The code finds out the first occurrence of the element in the array and checks if the element at (n/2+1)th position is same(as the array is sorted). Takes O(logn) time.
Question 41
A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?
A
3
B
4
C
5
D
6
       Database Management System        B Tree
Question 41 Explanation: 
Let's take 10 successive key values,
{1,2,3,...,10} which can cause maximum possi ble splits.
1, 2, 3 →

4 →

5 →

6 →

7 →

8 →

9 →

10 →
Question 42
G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
A
For every subset of k vertices, the induced subgraph has at most 2k–2 edges
B
The minimum cut in G has at least two edges
C
There are two edge-disjoint paths between every pair to vertices
D
There are two vertex-disjoint paths between every pair of vertices
       Data Structures        Graphs
Question 42 Explanation: 
→ In Spanning tree n nodes require n-1 edges. The above question they mentioned 2 disjoint spanning trees. So, it requires n-1 + n-1 =2n-2 edges. Except option D everything is correct.
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
Question 43
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then
A
T(n) ≤ 2T(n/5) + n
B
T(n) ≤ T(n/5) + T(4n/5) + n
C
T(n) ≤ 2T(4n/5) + n
D
T(n) ≤ 2T(n/2) + n
       Algorithms       Sorting
Question 43 Explanation: 
For the case where n/5 elements are in one subset, T(n/5) comparisons are needed for the first subset with n/5 elements, T(4n/5) is for the rest 4n/5 elements, and n is for finding the pivot. If there are more than n/5 elements in one set then other set will have less than 4n/5 elements and time complexity will be less than T(n/5) + T(4n/5) + n because recursion tree will be more balanced.
Question 44
A
Q solves the subset-sum problem in polynomial time when the input is encoded in unary
B
Q solves the subset-sum problem in polynomial time when the input is encoded in binary
C
The subset sum problem belongs to the class NP
D
The subset sum problem is NP-hard
       Algorithms       P-NP
Question 44 Explanation: 
Suppose the input is encoded in binary format. If W is an exponential in terms of the input length of W and O(nW) also becomes exponential in terms of the input lengths. Q is not a polynomial time algorithm.
Note: As per Present GATE syllabus , the above concept is not required.
Question 45
 
A
only vertex a
B
only vertices a, e, f, g, h
C
only vertices a, b, c, d
D
all the vertices
       Algorithms       Shortest Path
Question 45 Explanation: 
The single source shortest path algorithm(Dijkstra’s) is not work correctly for negative edge weights and negative weight cycle. But as per the above graph it works correct. It gives from shortest path between ‘a’ vertex to all other vertex. The Dijkstra’s algorithm will follow greedy strategy.
A-B ⇒ 1
A-C⇒ 1+2=3
A-E⇒ 1-3 =-2
A-F⇒ 1 -3 +2 =0
A-G⇒ 1 -3 +2 +3 =3
A-C ⇒1 +2 =3
A-H⇒ 1+2 -5 =-2
Question 46
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
A
θ(log n)
B
θ(n)
C
θ(nlog n)
D
None of the above, as the tree cannot be uniquely determined
       Data Structures        Binary Search Tree
Question 46 Explanation: 
Last element in post order is the root of tree- find this element in inorder-log n time. Now as in quick sort consider this as pivot and split the post order array into 2. All elements smaller than pivot goes to left and all elements larger than pivot goes to right and suppose we have k elements smaller than pivot, these elements will be same in both in-order as well as post order. Now, we already got the root, now left child is the left split and right child is the right split.
T(n) = T(k) + T(n-k-1) + logn
In worst case T(n) = O(nlogn), when k=0
But searching for an element in the in-order traversal of given BST can be done in O(1) because we have n elements from 1...n so there is no need to search an element- if last element in post order is say 5 we take it as root and since 4 elements are split the post order array into two (first 4 elements), (6th element onward) and solve recursively. Time complexity for this would be
T(n) = T(k) + T(n-k-1)+O(1)
Which gives T(n) = O(n)
since we know that all elements must be traversed at least once T(n) = θ(n)
Question 47
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
A
θ(log n)
B
θ(n)
C
θ(nlog n)
D
θ(n2)
       Data Structures        Heap Tree
Question 47 Explanation: 
Inserting an element into binary(either max or min) heap takes O(logn) for all cases, but in question they clearly mentioned that n elements and inserting one by one n elements, so it takes 2n time. So, O(n).
Note: We can also insert all the elements once, there will be no difference on time complexity.
Question 48
Which of the following statements is false?
A
Every NFA can be converted to an equivalent DFA
B
Every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine
C
Every regular language is also a context-free language
D
Every subset of a recursively enumerable set is recursive
       Theory of Computation        Recursive And Recursively Enumerable Languages
Question 48 Explanation: 
Every NFA can be converted into DFA (as there exist a standard procedure to convert NFA into DFA). Also, every non-deterministic Turing machine can be converted to an equivalent deterministic Turing machine. Every regular language is also a CFL , since if a language can be recognized by Finite automata, then it must also be recognize by PDA (as PDA is more powerful than FA). But every subset of recursively enumerable need not be recursive.
Question 49
 
A
B
C
D
       Theory of Computation        Finite Automata
Question 49 Explanation: 
The product automata will have states {11, 12, 21, 22} and “11” is inItial state and “22” is final state. By comparison we can easily infer that state {11, 12, 21, 22} is renamed as {P, Q, S, R}, wheresP is initial state (state “11”) and R is final state (state “22”).
Lets rename table Z (for sake of clarity)

And Table Y (same as given in question)

The product automata will have states { One1, One2, Two1, Two2} Where One1 is P , Two2 is R and One2 is Q and Two1 is S.
The transition table for Z × Y is given below:

NOTE: LAST TWO ROWS DOESN’T MATCH WITH OPTION A. BUT IF THE ASSUMPTION IN QUESTION SUCH AS STATE “11” IS P AND STATE “22” IS R, HOLDS, THEN THE ONLY OPTION MATCHES WITH PRODUCT AUTOMATA IS OPTION A, AS (FIRST ROW) , P (ON “a”) -> S AND P (ON “b”) -> R, IS THE ONLY OPTION MATCHING WITH OPTION A.
Question 50

 
A
I, II, III and IV
B
II, III and IV only
C
I, III and IV only
D
I, II and IV only
       Theory of Computation        Context Free Grammar
Question 50 Explanation: 
Every left recursive grammar can be converted to a right-recursive grammar and vice-versa, the conversion of a left recursive grammar into right recursive is also known as eliminating left recursion from the grammar. Statement III is also true, as this is the standard definition of regular grammar (TYPE 3 grammar). Statement IV is also true, as in CNF the only productions allowed are of type:
A-> BC
A-> a // where “a” is any terminal and B, C are any variables.
When we draw the parse tree for the grammar in CNF, it will always have at most two childs in every step, so it always results binary tree.
But statement II is false, as if the language contains empty string then we cannot remove every epsilon production from the CFG, since at least one production (mainly S → ϵ) must be there in order to derive empty string in language.
Question 51
 
A
E - P, F - R, G - Q, H - S
B
E - R, F - P, G - S, H - Q
C
E - R, F - P, G - Q, H - S
D
E - P, F - R, G - S, H - Q
       Theory of Computation        Match The Following
Question 51 Explanation: 
The grammar in S {X →bXb | cXc | ϵ} derives all even length Palindromes, So H matches with S.
F matches with P, Number of formal parameters in the declaration…. matches with {L={ an bm c n dm | m,n >=1}
Since, an bm corresponds to formal parameter (if n=2 and m=1, and “a” is int type and “b”is float type, then it means (int,int,float)) and cn dm corresponds to actual parameter used in function.
Similarly other two can also be argued by their reasons, but with F matches with P and H matches with S implies that option C is the only correct option.
Question 52
A
P-2, Q-1, R-3, S-4
B
P-1, Q-3, R-2, S-4
C
P-1, Q-2, R-3, S-4
D
P-3, Q-2, R-1, S-4
       Theory of Computation        Finite Automata
Question 52 Explanation: 
The NFA represented by P, accepts string “00” and then at final state (other than initial state) we have self loop of “1” , so we conclude that it must accept the string of the form of -> ϵ + 0 X* 01*, where X is regular expression (01*1 + 00 ) {resolving the loop at middle state}. It matches with statement 1.
Similarly, The NFA represented by Q, has the form of -> ϵ + 0X*0, where X is regular expression (10*1 + 00 ) {resolving the loop at middle state}. It matches with statement 2.
The NFA represented by R, has the form of -> ϵ + 0X*1, where X is regular expression (10*1 + 01 ) {resolving the loop at middle state}. It matches with statement 3.
The NFA represented by S, accepts string “01” and then at final state (other than initial state) we have self loop of “0” , so we conclude that it must accept the string of the form of -> ϵ + 0X* 10*, where X is regular expression (10*1 + 10 ) {resolving the loop at middle state}. It matches with statement 4.
Question 53
 
A
I and IV only
B
I and III only
C
I only
D
IV only
       Theory of Computation        Regular Languages
Question 53 Explanation: 
Statement I represents a regular language whose regular expression is a* (bb)*. Also it doesn’t require any comparison between “a” and “b” , so it can be recognized by DFA and hence regular.
Statement II and III represent CFL, as it requires comparison between number of a’s and b’s.
Statement IV is also regular, and its regular expression is (a+b)* c (a+b)*.
Question 54
 
A
II and V only
B
I, III and IV only
C
I, II and V only
D
II, III and V only
       Compiler Design        Run Time Environments
Question 54 Explanation: 
II. Multilevel access link (or display) arrangement is needed to arrange Activation Records only if the programming language being implemented has nesting of procedures and functions.
V. PL’s which permits a function to return a function as its result cannot be implemented with a stack-based storage allocation scheme for activation records.
II & V are True.
Question 55
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if
A
the SLR(1) parser for G has S-R conflicts
B
the LR(1) parser for G has S-R conflicts
C
the LR(0) parser for G has S-R conflicts
D
the LALR(1) parser for G has reduce-reduce conflicts
       Compiler Design        Parsrs
Question 55 Explanation: 
LALR(1) parser is obtained by minimising the LR(1) parser and hence they both uses LR(1) items. Now consider if LR(1) parser has SR conflict, for ex:
Consider a state in LR(1) parser:
S-> x.yA, a
A-> x. , y
This has both shift and reduce conflict on symbol “y”.
Since LR(1) already has SR conflict , so resulting LALR(1) (after merging) will also have SR conflict.
Now if LR(1) doesn’t have SR conflict then it is guaranteed that the LALR(1) will never have SR conflict. The reason behind this is, as we merge those state only which has same set of canonical items except look ahead and the LR(1) canonical items has DFA (means from one state to other state the transition is from unique symbol) , so after merging also we will never see any shift conflict, only reduce-reduce may occur.
Hence An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if the LR(1) parser for G has S-R conflicts.
Question 56
In the slow start phase of the TCP congestion control algorithm, the size of the congestion window
A
does not increase
B
increases linearly
C
increases quadratically
D
increases exponentially
       Computer Networks        TCP
Question 56 Explanation: 
In slow start phase, window size will grow exponentially. when the threshold is reached and congestion avoidance phase begins. In congestion avoidance phase, the window is increased linearly.
Question 57
If a class B network on the Internet has a subnet mask of 255.255.248.0, what is the maximum number of hosts per subnet?
A
1022
B
1023
C
2046
D
2047
       Computer Networks        IP Addresses
Question 57 Explanation: 
255.255.248.0 can be written as 11111111.11111111.11111000.00000000
Number of bits assigned for host id is the number of zeros in subnet mask. Here 11 bits are used.
for host id so maximum possible hosts are= 211 -2=2046
Question 58
A computer on a 10Mbps network is regulated by a token bucket. The token bucket is filled at a rate of 2Mbps. It is initially filled to capacity with 16Megabits. What is the maximum duration for which the computer can transmit at the full 10Mbps?
A
1.6 seconds
B
2 seconds
C
5 seconds
D
8 seconds
       Computer Networks        Tocken Bucket
Question 58 Explanation: 
Duration = C/x-y, where C is the initial capacity, x is outgoing rate and y is incoming rate.
Question 59

A client process P needs to make a TCP connection to a server process S. Consider the following situation: the server process S executes a socket (), a bind () and a listen () system call in that order, following which it is preempted. Subsequently, the client process P executes a socket () system call followed by connect () system call to connect to the server process S. The server process has not executed any accept() system call. Which one of the following events could take place?

A
connect ( ) system call returns successfully
B
connect ( ) system call blocks
C
connect ( ) system call returns an error
D
connect ( ) system call results in a core dump
       Computer Networks        Sockets
Question 59 Explanation: 
Connect() System call is not blocking system call but it blocks until connection is established or rejected. If accept() is not executed at server then connection will be rejected and an error statement is returned.
Question 60
A
18
B
19
C
21
D
22
       Programming       C Program
Question 60 Explanation: 
f(c,b,a)
f(c,&c,&(&c))=f(4,4,4)
c is 4, b is a pointer pointing address of a, a is a pointer to pointer of c. Hence both b and c are pointing to same memory address i.e., a.
Hence whatever increment operation happens in f, it happens/ reflects on same value i.e., a.
**ppz+=1;
z=**ppz; //z=5
These steps update it to 5 and stored in z.
*py+=2; //changes c to 7, x is unchanged.
y=*py; //y=7
It updates to 7 and stored in y.
x+=3 //x is incremented by 3.
returns x+y+z=7+7+5=19
Question 61
A
?1 is (getchar( ) != ’\n’)
?2 is getchar(c);
B
?1 is (c = getchar( ) ) != ’\n’)
?2 is getchar(c);
C
?1 is (c != ’\n’)
?2 is putchar(c);
D
?1 is ((c = getchar()) != ’\n’)
?2 is putchar(c);
       Programming       C Program
Question 61 Explanation: 
void reverse(void)
{
int c;
if(?1) reverse( );
?2
}
main( )
{
printf(“Enter Text”);
printf(“\n”);
reverse( );
printf(“\n”);
}
We can simply eliminate A & B for ?2.
& Hence
?1 is ((c=getchar( )) != ‘\n’)
?2 is putchar(c);
Question 62
A
1,2,3,4,5,6,7
B
2,1,4,3,6,5,7
C
1,3,2,5,4,7,6
D
2,3,4,5,6,7,1
       Data Structures        Linked List
Question 62 Explanation: 
The given list is 1,2,3,4,5,6,7.
After 1st Iteration: 2,1,3,4,5,6,7
2nd Iteration: 2,1,4,3,5,6,7
3rd Iteration: 2,1,4,3,6,5,7
After each exchange is done, it starts from unchanged elements due to p=q⟶next;
‘p’ pointing to Null & q pointing to 7.
Hence 2,1,4,3,6,5,7.
Question 63
 
A
0 and 0
B
0 and 1
C
1 and 0
D
1 and 1
       Operating Systems        Process Synchronization
Question 63 Explanation: 
xb must be 1 because both P(s) operation and V(s) operation perform Pb(xb) first. So if xb=0, then all the process performing these operations will be blocked.
Yb must be '0' initially, because if Yb is '1' initially then two process can be in critical section at the same time.
So answer is Option (C).
Question 64
Which of the following statements about synchronous and asynchronous I/O is NOT true?
A
An ISR is invoked on completion of I/O in synchronous I/O but not in asynchronous I/O
B
In both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is invoked after completion of the I/O
C
A process making a synchronous I/O call waits until I/O is complete, but a process making an asynchronous I/O call does not wait for completion of the I/O
D
In the case of synchronous I/O, the process waiting for the completion of I/O is woken up by the ISR that is invoked after the completion of I/O
       Operating Systems        IO Handling
Question 64 Explanation: 
Synchronous I/O mean that some flow of execution (such as a process or thread) is waiting for the operation to complete. Asynchronous I/O means that nothing is waiting for the operation to complete and the completion of the operation itself causes something to happen.
Synchronous I/O -- some execution vehicle (like a process or thread) that initiates the I/O also waits for the I/O to complete (and perhaps completes it). When the I/O completes, that same execution vehicle goes on to do something else, perhaps using the results of the I/O.
Asynchronous I/O -- no execution vehicle waits for the I/O to complete. When the I/O completes, whatever execution vehicle happens to complete the I/O may arrange for later things to happen.
Option B is not true, because both synchronous and asynchronous I/O, an ISR (Interrupt Service Routine) is not invoked after completion of the I/O.
Question 65
Which of the following is NOT true of deadlock prevention and deadlock avoidance schemes?
A
In deadlock prevention, the request for resources is always granted if the resulting state is safe
B
In deadlock avoidance, the request for resources is always granted if the result state is safe
C
Deadlock avoidance is less restrictive than deadlock prevention
D
Deadlock avoidance requires knowledge of resource requirements a priori
       Operating Systems        Deadlock
Question 65 Explanation: 
Deadlock prevention scheme handles deadlock by making sure that one of the four necessary conditions don't occur. So, it may be the case that a resource request might be rejected even if the resulting state is safe. Hence, option (A) is false.
Question 66
 
A
n
B
(2n) - 1
C
2n
D
(2n+1) - 1
       Operating Systems        System Calls
Question 66 Explanation: 
Fork is a system call, implements in kernel.
It is a operation where process creates a copy of itself.

1,3,7,15,31,... ⇒ 2n-1
Question 67
 
A
20, 20 and 20
B
24, 24 and 24
C
24, 24 and 20
D
25, 25 and 24
       Operating Systems        Virtual Memory
Question 67 Explanation: 
Virtual address size = 32 bits
From the question we can see the below info:
Physical address size = 36 bits
Physical memory size = 236 bytes
Page frame size = 4K bytes = 212 bytes
No. of bits for offset = 12
No. of bits required to access physical memory frame = 36 – 12 = 24
So in third level of page table, 24 bits are required to access an entry.
In second level page table entry -- 9 bits of virtual address are used to access second level page table entry and size of pages in second level is 4 bytes.
So size of second level page table is (29)*4 = 211 bytes. It means there are (236)/(211) possible locations to store this page table. Therefore the second page table requires 25 bits to address it. the first page table needs 25 bits.
Answer - D
First level
Question 68
 
A
Only I and II
B
Only I and III
C
Only I, II and III
D
Only I, III and IV
       Database Management System        Relational Algebra
Question 68 Explanation: 
Natural join is based on the common columns of the two tables.
We have two common columns in 'R' and 'S' which are 'P' and 'Q'.
(I) Both P and Q are used while doing the join, i.e., both P and Q are used to filter.
(II) Q is not used here for filtering. Natural join is done on all P's from R and all P's from S. So different from option (I).
(III) Through venn diagram it can be proved that A∩B = A - (A-B).
So through above formula we can say that (III) and (IV) are equivalent.
So finally (I), (III) and (IV) are equivalent.
Question 69
 
A
Both Book and Collection are in BCNF
B
Both Book and Collection are in 3NF only
C
Book is in 2NF and Collection is in 3NF
D
Both Book and Collection are in 2NF only
       Database Management System        Normalization
Question 69 Explanation: 
Given that
Book(Title, Author, Catalog_no, Publisher, Year, Price)
Collection(Title, Author, Catalog_no)
I) Title Author ⟶ Catalog_no ⟶ BCNR
II) Catalog_no ⟶ Title, Author, Publisher, Year ⟶ 3NF
III) Publisher Title Year ⟶Price ⟶ 2NF Book’s in 2NF
Collection is in 3NF.
Question 70
Consider a file of 16384 records. Each record is 32 bytes long and its key field is of size 6 bytes. The file is ordered on a non-key field, and the file organization is unspanned. The file is stored in a file system with block size 1024 bytes, and the size of a block pointer is 10 bytes. If the secondary index is built on the key field of the file, and a multi-level index scheme is used to store the secondary index, the number of first-level and second-level blocks in the multi-level index are respectively
A
8 and 0
B
128 and 6
C
256 and 4
D
512 and 5
       Database Management System        Indexing
Question 70 Explanation: 
Total no. of records in a file = 16384
Record size = 32 bytes
Key size = 6 bytes
Block pointer size = 10 bytes
Block size of file system = 1024 bytes
Record (or) index entry size = 10+6 = 16 bytes
In first level no. of blocks =No. of records in a file/Block size=16384 * 16/1024=256
In second level, it have = 256*16 entries
In second level, no. of blocks =No. of entries/Block size =256*16/1024=4
Question 71
A
32Kbits
B
34Kbits
C
64Kbits
D
68Kbits
       Computer Organization        Cache Memory
Question 71 Explanation: 
It is given that cache size = 64KB
Block size = 16 Bytes = 24 Bytes, so block offset = 4 bits
Number of blocks in the cache = 64KB / 16B = 4K
It is 2-way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 211
So, we need 11-bits for set indexing.
Since the address is 32 bits long, number of tag bits = 32−11−4 = 17
Total size of the tag directory = No. of tag bits ×Number of cache blocks =17×4K
=68 Kbits
Question 72
A
ARR [0] [4]
B
ARR [4] [0]
C
ARR [0] [5]
D
ARR [5] [0]
       Computer Organization        Cache Memory
Question 72 Explanation: 
It is given that cache size = 64KB
Block size = 16 Bytes
Number of blocks in the cache = 64KB / 16B = 4K
It is 2-way set associative cache, so each set contains 2 blocks.
So, number of sets = 4K / 2 = 2K = 211
Each element size = 8B and size of each block = 16 B
No. of elements in one block = 16/8 = 2 We know no. of elements in one row of the array = 1024. So, no. of blocks for one row of the array = 1024/2 = 512
We know there are 211 sets, and each set has two blocks.
For any element to share the same cache index as ARR[0][0], it has to belong to the same set.
ARR[0][0] belongs to set-0. The next element that belongs to set-0 will have block number 2048 because 2048 mod 211 = 0.
Block number 2048 will be from row number 2048/512 = 4, because each row has 512 blocks we divide the block number with 512 to get the row number.
From the given options ARR[4][0] will have the same cache index as ARR[0][0].
Question 73
A
0%
B
25%
C
50%
D
75%
       Computer Organization        Cache Memory
Question 73 Explanation: 
Block size = 16B and it is given that double size is 8B, so one element = 8B.
So in one block 2 elements will be stored.
To store 1024×1024 elements no. of blocks needed = 1024×1024/2 = 220/2 = 219.
In each block the first element will be a miss and second element will be a hit because on every miss that entire block is brought into the cache. So, there will be 219 hits and 219 misses. Total no. of references = no. of elements in the array = 220
⇒hit ratio = No. of hits / Total no. of references
=219/220 = 1/2 = 0.5
=0.5×100=50%
Question 74
A
θ(n) and θ(n)
B
θ(2n) and θ(n)
C
θ(n) and θ(2n)
D
θ(2n) and θ(2n)
       Algorithms        Time Complexity
Question 74 Explanation: 
Time complexity of f1 is given by
T(n) = T(n-1) + T(n-2) (multiplication by 2 and 3 won't affect complexity as it is a constant time operation)
T(0) = T(1) = 1
The recurrence is similar to fibonacci series. The time complexity is O(2n)
T(n) = T(n-1) + T(n-2) + c
T(0) = 1
T(n-1) ≈ T(n-2)
But in reality, T(n-1) > T(n-2)
So to find upper bound the expression will be
T(n) = 2T(n-1) + c
= 4T(n-2) + 3c
= 8T(n-3) +7c
= 2kT(n-k) + (2k-1)c
n-k=0 ⇒ k = n
T(n) = 2nT(0) + (2n-1)c
= 2n +(2n-1)c
⇒ T(n) = O(2n)
The time required for f2 is O(n) (because it consists of only one loop).
Question 75
A
1661 and 1640
B
59 and 59
C
1640 and 1640
D
1640 and 1661
       Programming       C Program
Question 75 Explanation: 
Both functions perform same operation, so output is same, means either (B) or (C) is correct.
f1(2) = 2*f1(1) + 3*f1(0) = 2
f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
f1(4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3*7 = 40 + 21 = 61
We can skip after this as the only remaining choice is (C).
f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
f1(8) = 2*f1(7) + 3*f1(6) = 2*547 + 3*182 = 1094 + 546 = 1640
Question 76
A
The instruction following the conditional branch instruction in memory is executed.
B
The first instruction in the fall through path is executed.
C
The first instruction in the taken path is executed.
D
The branch takes longer to execute than any other instruction.
       Computer Organization        Pipelining
Question 76 Explanation: 
In order to avoid the pipeline delay due to conditional branch instruction, a suitable instruction is placed below the conditional branch instruction such that the instruction will be executed irrespective of whether branch is taken or not and won't affect the program behaviour. Hence option A is the answer.
Question 77
 
A
I1
B
I2
C
I3
D
I4
       Computer Organization        Pipelining
Question 77 Explanation: 
It is the method to maximize the use of the pipeline by finding and executing an instruction that can be safely executed whether the branch is taken or not. So, when a branch instruction is encountered, the hardware puts the instruction following the branch into the pipe and begins executing it. Here we do not need to worry about whether the branch is taken or not, as we do not need to clear the pipe because no matter whether the branch is taken or not, we know the instruction is safe to execute.
From the given set of instructions I3 is updating R1, and the branch condition is based on the value of R1 so I3 can’t be executed in the delay slot.
Instruction I1 is updating the value of R2 and R2 is used in I3. So I1 also can’t be executed in the delay slot.
Instruction I2 is updating R4, and at the memory location represented by R4 the value of R1 is stored. So if I2 is executed in the delay slot then the memory location where R1 is to be stored as part of I4 will be in a wrong place. Hence between I2 and I4, I2 can’t be executed after I4. Hence I2 can’t be executed in the delay slot.
Instruction I4 can be executed in the delay slot as this is storing the value of R1 in a memory location and executing this in the delay slot will have no effect. Hence option D is the answer.
Question 78
 
A
xn = 2xn-1
B
xn = x⌊n/2⌋+1
C
xn = x⌊n/2⌋+n
D
xn = xn-1+xn-2
       Algorithms        Recurrence
Question 78 Explanation: 
xn = number of binary strings of length contains non-consecutive 0’s.
Let us consider n=1
Possible binary strings: 0, 1
x1 = 2
⇒ n = 2; binary strings not containing consecutive zero’s
11,01,10
x2 = 3
⇒ For n=3, then possible strings are

⇒ For n=4; then possible strings are
Question 79
   
A
5
B
7
C
8
D
16
       Algorithms        Reccurrence
Question 79 Explanation: 
Asked for no. of binary strings of length 5 contains non-consecutive zeros.
Case 1: When string contains no zero,
1 1 1 1 1
No. of ways = 1
Case 2: When string contains only one zero
× 1 × 1 × 1 × 1 ×
It can be placed any of the five places above shown with cross mark.
So no. of ways = 5C1 = 5
Case 3: When string contains only two zero's.
× 1 × 1 × 1 ×
The two zero's can be placed any of the four places above shown with cross marks,
So no. of ways = 4C2 = 6
Case 4: When string contains only three zero's.
× 1 × 1 ×
The three zero's can be placed at any of the three places above shown with cross marks.
So no. of ways = 3C3 = 1
Four zero's and five zero's cannot be placed in the string because whatever you try to put it in the length of string 5, the two consecutive zero will come. So therefore total no. of ways possible.
= 1+5+6+1
= 13
None of the given option is correct.
Question 80
   
A
X[i, j] = X[i - 1, j] ∨ X[i, j - ai]
B
X[i, j] = X[i - 1, j] ∨ X[i - 1, j - ai]
C
X[i, j] = X[i - 1, j] ∧ X[i, j - ai]
D
X[i, j] = X[i - 1, j] ∧ X[i -1, j - ai]
       Algorithms        Dynamic Programming
Question 80 Explanation: 
X[I, j] (2 <= i <= n and ai <= j <= W) is true if any of the following is true.
1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true.
2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j.
Question 81
A
X[1, W]
B
X[n, 0]
C
X[n, W]
D
X[n-1, n]
       Algorithms        Dynamic Programming
Question 81 Explanation: 
The last row and last column given the value is 1 then subset of whose elements sum to W.
Note: As per present GATE syllabus, this concept is not required.
Question 82
A
2
B
3
C
4
D
5
       Database Management System        ER Model
Question 82 Explanation: 
➝ M, P are entities so they require individual tables.
➝ Here N is a Weak entity, but it need to modify the primary key of P such as P1
M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
➝ Relationship set has its own attribute, then no need to create a separate table.
➝ Finally we require 3 minimum tables to represent M,P,N,R1,R2.
Question 83
A
{M1, M2, M3, P1}
B
{M1, P1, N1, N2}
C
{M1, P1, N1}
D
{M1, P1}
       Database Management System        ER Model
Question 83 Explanation: 
Possible set of attributes is
For M = {M1, M2, M3, P1}
P = {P1, P2}
N = {N1, N2, P1}
Question 84
A
Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
B
Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
C
Y is [2 2 2 2 2 2 2 2 2 2] and x > 2
D
Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 and x is even
       Algorithms        Binary Search
Question 84 Explanation: 
This program doesn’t work for the cases where element to be searched is the last element of Y[ ] or greater than the last element (or maximum element) in Y[ ]. In such case, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes same/ equal to or greater than j. So while condition never becomes false.
Question 85
A
Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1;
B
Change line 6 to: if (Y[k] < x) i = k - 1; else j = k+1;
C
Change line 6 to: if (Y[k] <= x) i = k; else j = k;
D
Change line 7 to: } while ((Y[k] == x) && (i < j));
       Algorithms        Binary Search
Question 85 Explanation: 
f(int Y[10], int x)
{
int i,j,k;
i=0;j=9;
do
{
k=(i+j)/2;
if(Y[k] i=k+1;
else
j=k-1;
} while (Y[k]!=x && i if (Y[k]= =x)
printf(“x is in the array”);
else
printf(“x is not in the array”);
}
There are 85 questions to complete.