Gate2007
Question 1 
P is true and Q is false.
 
P is false and Q is true.
 
Both P and Q are true.
 
Both P and Q are false. 
Question 1 Explanation:
f(x) = x
→ f(x) is continuous for all real values of x
For every value of x, there is corresponding value of f(x).
For x is positive, f(x) is also positive
x is negative, f(x) is positive.
So, f(x) is continuous for all real values of x.
→ f(x) is not differentiable for all real values of x. For x<0, derivative is negative
x>0, derivative is positive.
Here, left derivative and right derivatives are not equal.
→ f(x) is continuous for all real values of x
For every value of x, there is corresponding value of f(x).
For x is positive, f(x) is also positive
x is negative, f(x) is positive.
So, f(x) is continuous for all real values of x.
→ f(x) is not differentiable for all real values of x. For x<0, derivative is negative
x>0, derivative is positive.
Here, left derivative and right derivatives are not equal.
Question 2 
Let S be a set of n elements. The number of ordered pairs in the largest and the smallest equivalence relations on S are:
n and n  
n^{2} and n  
n^{2} and 0  
n and 1 
Question 2 Explanation:
Let us assume a set with 4 elements
S={1,2,3,4}
→ If a set is said to be equivalence, then the set must be
i) Reflexive
ii) Symmetric
iii) Transitive
i) Reflexive Relation: A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.
A = {1,2,3}
R = {(1,1), (2,2), (3,3)} ✔️
R = {(1,1), (2,2)} ❌
R = {(1,1), (2,2), (3,3), (1,2)} ✔️
ii) Symmetric Relation: A relation on a set A is said to be symmetric if (xRy). Then (yRx)∀x,y∈A i.e., if ordered pair (x,y)∈R. Then (y,x)∈R ∀x,y∈A.
A={1,2,3}
R_{1}={(1,2), (2,1)}
R_{2}={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}
Transitive Relation:
A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).
A={1,2,3}
R_{1}={ } ✔️
R_{2}={(1,1)} ✔️
R_{3}={(1,2), (3,1)} ✔️
R_{4}={(1,2), (2,1), (1,1)} ✔️
⇾ A={1,2,3,4}
Largest ordered set is
S×S={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}
⇒ Total = 16 = 4^{2} = n^{2} ✔️
Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}
⇒ Total=4=n ✔️
S={1,2,3,4}
→ If a set is said to be equivalence, then the set must be
i) Reflexive
ii) Symmetric
iii) Transitive
i) Reflexive Relation: A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.
A = {1,2,3}
R = {(1,1), (2,2), (3,3)} ✔️
R = {(1,1), (2,2)} ❌
R = {(1,1), (2,2), (3,3), (1,2)} ✔️
ii) Symmetric Relation: A relation on a set A is said to be symmetric if (xRy). Then (yRx)∀x,y∈A i.e., if ordered pair (x,y)∈R. Then (y,x)∈R ∀x,y∈A.
A={1,2,3}
R_{1}={(1,2), (2,1)}
R_{2}={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}
Transitive Relation:
A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).
A={1,2,3}
R_{1}={ } ✔️
R_{2}={(1,1)} ✔️
R_{3}={(1,2), (3,1)} ✔️
R_{4}={(1,2), (2,1), (1,1)} ✔️
⇾ A={1,2,3,4}
Largest ordered set is
S×S={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}
⇒ Total = 16 = 4^{2} = n^{2} ✔️
Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}
⇒ Total=4=n ✔️
Question 3 
What is the maximum number of different Boolean functions involving n Boolean variables?
n^{2}  
2^{n}  
2^{2}^{n}  
2^{n2} 
Question 3 Explanation:
Each “boolean” variable has two possible values i.e 0 and 1.
Number of variables= n
Number of input combinations is 2^{n}.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 2^{2n}.
Formula: The number of mary functions possible with n kary variables is m^{kn}.
Number of variables= n
Number of input combinations is 2^{n}.
Each “boolean” function has two possible outputs i.e 0 and 1.
Number of boolean functions possible is 2^{2n}.
Formula: The number of mary functions possible with n kary variables is m^{kn}.
Question 4 
Let G be the nonplanar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices  
9 edges and 6 vertices  
10 edges and 5 vertices
 
10 edges and 6 vertices

Question 4 Explanation:
In planar graph, any face (except possibly the outer line) is bounded by atleast three edges and every edge touches atmost two faces.
Using Euler’s formula it states that,
if v ≥ 3 then e ≤ 3v6
where e=edges
v=vertices
Go through the options
i) 9e and 5v ⇒ 9≤3(5)6
⇒ 9≤156
⇒ 9≤9 (It’s satisfies planar graph)
ii) 9e and 6v ⇒ 9≤3(6)6
⇒ 9≤12 (It’s planar graph)
iii) 10e and 5v ⇒ 10≤3(5)6
⇒ 10≤9 (It’s not satisfies planar graph condition)
So, option C is nonplanar graph.
iv) 10e and 6v ⇒ 10≤3(6)6
⇒ 10≤12 (It’s planar graph)
Using Euler’s formula it states that,
if v ≥ 3 then e ≤ 3v6
where e=edges
v=vertices
Go through the options
i) 9e and 5v ⇒ 9≤3(5)6
⇒ 9≤156
⇒ 9≤9 (It’s satisfies planar graph)
ii) 9e and 6v ⇒ 9≤3(6)6
⇒ 9≤12 (It’s planar graph)
iii) 10e and 5v ⇒ 10≤3(5)6
⇒ 10≤9 (It’s not satisfies planar graph condition)
So, option C is nonplanar graph.
iv) 10e and 6v ⇒ 10≤3(6)6
⇒ 10≤12 (It’s planar graph)
Question 5 
1 2 3 4 5 6  
1 3 2 4 5 6  
1 3 2 4 6 5  
3 2 4 1 6 5

Question 5 Explanation:
The process to find topological order is,
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.
Question 6 
Which of the following problems is undecidable?
Membership problem for CFGs.
 
Ambiguity problem for CFGs.
 
Finiteness problem for FSAs.  
Equivalence problem for FSAs.

Question 6 Explanation:
Whether a given CFG is ambiguous, this problem is undecidable. The reason is there is no algorithm exist for this. Remaining all are decidable.
Question 7 
Which of the following is TRUE?
Every subset of a regular set is regular.  
Every finite subset of a nonregular set is regular.
 
The union of two nonregular sets is not regular.
 
Infinite union of finite sets is regular. 
Question 7 Explanation:
If a set is finite then it must be regular , as every language which contains finite elements is regular. Hence, every finite subset of a nonregular set is regular.
Every subset of regular set is regular, is false. For example L = {an bn  n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two nonregular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {a^{n} b^{n}  n ≥ 0} and its complement L^{c} = {a^{m} b^{n}  m ≠ n } U b*a*.
If we take UNION of L and L^{c} , we will get ∑*, which is regular. Hence the UNION of two nonregular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Every subset of regular set is regular, is false. For example L = {an bn  n ≥ 0} is subset of ∑* and L is CFL, whereas ∑* is regular. Hence, every subset of regular set need not be regular.
The union of two nonregular sets is not regular, is also a false statement.
For example, consider two CFL’s.
L = {a^{n} b^{n}  n ≥ 0} and its complement L^{c} = {a^{m} b^{n}  m ≠ n } U b*a*.
If we take UNION of L and L^{c} , we will get ∑*, which is regular. Hence the UNION of two nonregular set may or may not be regular.
The statement, Infinite union of finite sets is regular is also a false statement.
Question 8 
How many 3to8 line decoders with an enable input are needed to construct a 6to64 line decoder without using any other logic gates?
7  
8  
9  
10 
Question 8 Explanation:
Each 3to8 lines decoder has 8 output lines.
Number of 3to8 decoders needed for 64 output lines of 6to64 Decoder is 8.
One more 3to8 lines Decoder is needed to select one of the eight 3to8 Decoders.
So 8+1= 9 decoders are needed.
Number of 3to8 decoders needed for 64 output lines of 6to64 Decoder is 8.
One more 3to8 lines Decoder is needed to select one of the eight 3to8 Decoders.
So 8+1= 9 decoders are needed.
Question 9 
independent of one variable.  
independent of two variables.
 
independent of three variables.  
dependent on all the variables.

Question 9 Explanation:
w and y are not needed to represent the function f. So f is independent of two variables.
Question 10 
Consider a 4way set associative cache consisting of 128 lines with a line size of 64 words. The CPU generates a 20bit address of a word in main memory. The number of bits in the TAG, LINE and WORD fields are respectively:
9, 6, 5
 
7, 7, 6  
7, 5, 8  
9, 5, 6 
Question 10 Explanation:
Cache has 128 lines.
Each line size 64 words, so no. of bits for WORD = 6 bits
Because it is 4way set associative cache, no. of sets in the cache = 128/4 = 32 = 2^{5}
No. of bits for the set number = 5
Because the address is 20bits long, no. of TAG bits = 2056 = 9
Each line size 64 words, so no. of bits for WORD = 6 bits
Because it is 4way set associative cache, no. of sets in the cache = 128/4 = 32 = 2^{5}
No. of bits for the set number = 5
Because the address is 20bits long, no. of TAG bits = 2056 = 9
Question 11 
Consider a disk pack with 16 surfaces, 128 tracks per surface and 256 sectors per track. 512 bytes of data are stored in a bit serial manner in a sector. The capacity of the disk pack and the number of bits required to specify a particular sector in the disk are respectively:
256 Mbyte, 19 bits
 
256 Mbyte, 28 bits
 
512 Mbyte, 20 bits  
64 Gbyte, 28 bit

Question 11 Explanation:
Given that the disk pack has 16 surfaces, 128 tracks per surface, 256 sectors per track and each sector size is 512 bytes.
So the disk pack capacity = 16 * 128 * 256 * 512 bytes = 256 MB
To specify a sector we need the information about surface number, track number and sector number within a track. Surface number needs 4 bits as there are 16 surfaces(2^{4}), track number needs 7 bits as there are 128 tracks(2^{7}) within a surface, within a track the sector number needs 8 bits as there are 256 sectors (2^{8}). Total number bits needed to specify a particular sector = 4+7+8 = 19 bits. Hence option A is the answer.
So the disk pack capacity = 16 * 128 * 256 * 512 bytes = 256 MB
To specify a sector we need the information about surface number, track number and sector number within a track. Surface number needs 4 bits as there are 16 surfaces(2^{4}), track number needs 7 bits as there are 128 tracks(2^{7}) within a surface, within a track the sector number needs 8 bits as there are 256 sectors (2^{8}). Total number bits needed to specify a particular sector = 4+7+8 = 19 bits. Hence option A is the answer.
Question 12 
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:
2^{h}−1  
2^{h−1} – 1  
2^{h+1}– 1  
2^{h+1}

Question 12 Explanation:
img src = "https://pyq.ravindrababuravula.com/wpcontent/uploads/2018/09/51.png">
1,3,7,15,31,...=2^{h+1}  1
1,3,7,15,31,...=2^{h+1}  1
Question 13 
The maximum number of binary trees that can be formed with three unlabeled nodes is:
1  
5  
4  
3 
Question 13 Explanation:
Total number of binary trees possible for n nodes is
C(n)=(2n)!/(n+1)!n!
C(n)=(2(3))!/(3+1)!3!=6×5×4×3×2×1/4×3×2×1×3×2=5
Total no. of possible trees is 5.
Total = 5
Total no. of possible trees is 5.
Total = 5
Question 14 
Which of the following sorting algorithms has the lowest worstcase complexity?
Merge sort
 
Bubble Sort  
Quick Sort
 
Selection Sort 
Question 14 Explanation:
Worst case time complexities are
Merge sort→ O(nlogn)
Bubble sort→ O(n^{2})
Quick sort→ O(n^{2})
Selection sort→ O(n^{2})
Merge sort→ O(nlogn)
Bubble sort→ O(n^{2})
Quick sort→ O(n^{2})
Selection sort→ O(n^{2})
Question 15 
⌈log_{2}n⌉ + 1
 
n  
⌈log_{2}n⌉  
⌊log_{2}n⌋+1

Question 15 Explanation:
Let us consider n=6, then
1<=6 (✔️)
2<=6 (✔️)
4<=6 (✔️)
8<=6 (❌)
4 comparisons required
Option A:
[log n]+1
[log 6]+1
3+1=4 (✔)
Option B:
n=6 (❌)
Option C:
[log n]
[log 6]=3 (❌)
Option D:
[log_{2}n]+1
[log_{2}6]+1=2+1=3 (❌)
1<=6 (✔️)
2<=6 (✔️)
4<=6 (✔️)
8<=6 (❌)
4 comparisons required
Option A:
[log n]+1
[log 6]+1
3+1=4 (✔)
Option B:
n=6 (❌)
Option C:
[log n]
[log 6]=3 (❌)
Option D:
[log_{2}n]+1
[log_{2}6]+1=2+1=3 (❌)
Question 16 
P – 3 Q – 2 R – 1  
P – 1 Q – 2 R – 3
 
P – 2 Q – 3 R – 1
 
P – 1 Q – 3 R – 2

Question 16 Explanation:
Gang Scheduling is a scheduling algorithm for parallel systems that schedules related threads (or) processes to run simultaneously on different processes to run simultaneously on different processes.
Rate Monotonic scheduling is a priority assignment algorithm used in RealTime operating systems (RTOS) with a static priority scheduling class.
Fair scheduling is a process of distributing the CPU usage equally among system users or groups and which is guarantee scheduling process.
Rate Monotonic scheduling is a priority assignment algorithm used in RealTime operating systems (RTOS) with a static priority scheduling class.
Fair scheduling is a process of distributing the CPU usage equally among system users or groups and which is guarantee scheduling process.
Question 17 
Consider the following statements about user level threads and kernel level threads. Which one of the following statements is FALSE?
Context switch time is longer for kernel level threads than for user level threads.  
User level threads do not need any hardware support.
 
Related kernel level threads can be scheduled on different processors in a multiprocessor system.
 
Blocking one kernel level thread blocks all related threads.

Question 17 Explanation:
A) True, because as kernel level threads are managed by OS and kernal maintains lots of data structure.
B) True, because kernel is not involved in it.
C) True
D) Blocking one kernel level thread blocks all related threads is false, because kernel level threads are independent.
B) True, because kernel is not involved in it.
C) True
D) Blocking one kernel level thread blocks all related threads is false, because kernel level threads are independent.
Question 18 
Which one of the following is a topdown parser?
Recursive descent parser.
 
Operator precedence parser.  
An LR(k) parser.
 
An LALR(k) parser.

Question 18 Explanation:
Recursive descent parser is top down parser, while others are bottom up parser.
Question 19 
In Ethernet when Manchester encoding is used, the bit rate is:
Half the baud rate.
 
Twice the baud rate.
 
Same as the baud rate.
 
None of the above.

Question 19 Explanation:
Bit rate is half the baud rate in Manchester encoding as bits are transferred only during a positive transition of the clock.
Question 20 
Which one of the following uses UDP as the transport protocol?
HTTP
 
Telnet
 
DNS
 
SMTP

Question 20 Explanation:
DNS uses the UDP at the transport layer with port number 53 for name resolution.
HTTP, Telnet and SMTP uses TCP.
HTTP, Telnet and SMTP uses TCP.
Question 21 
How many different nonisomorphic Abelian groups of order 4 are there?
2  
3  
4  
5 
Question 21 Explanation:
a*b = 4
a^{2} = 4
a = 2
No. of possible nonisomorphic abelian groups are 2.
a^{2} = 4
a = 2
No. of possible nonisomorphic abelian groups are 2.
Question 22 
Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: “Not every graph is connected”?
¬∀x (Graph (x) ⇒ Connected (x))  
¬∃x (Graph (x) ∧ ¬Connected (x))  
¬∀x (¬Graph (x) ∨ Connected (x))  
∀x (Graph (x) ⇒ ¬Connected (x))

Question 22 Explanation:
Option A:
¬∀x(Graph(x)⇒Connected(x)
¬∀x(Graph(x)∨Connected(x))
≡
equals to option C
Option B:
∃x(Graph(x)∧¬Connected(x))
There exist a graph and which is not connected.
Option C:
∀x(Graph(x)⇒¬Connected (x))
∀x(¬Graph(x)∨¬Connected (x))
For every value of x graph is not connected.
¬∀x(Graph(x)⇒Connected(x)
¬∀x(Graph(x)∨Connected(x))
≡
equals to option C
Option B:
∃x(Graph(x)∧¬Connected(x))
There exist a graph and which is not connected.
Option C:
∀x(Graph(x)⇒¬Connected (x))
∀x(¬Graph(x)∨¬Connected (x))
For every value of x graph is not connected.
Question 23 
Which of the following graphs has an Eulerian circuit?
Any kregular graph where k is an even number.
 
A complete graph on 90 vertices.
 
The complement of a cycle on 25 vertices.
 
None of the above.

Question 23 Explanation:
A necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an “even degree”.
Option C:
A Eulerian circuit with 25 vertices, with degree as 2. In complement graph would have degree such as ‘22’ which is even degree.
Option C:
A Eulerian circuit with 25 vertices, with degree as 2. In complement graph would have degree such as ‘22’ which is even degree.
Question 24 
Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1, 2, 3,….., 20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?
1/2  
1/10  
9!/20!  
None of these

Question 24 Explanation:
1, 2, 3, 4, …….20
→ Total no. of possible even number = 10
→ Here we are not considering odd number.
→ The probability that 2 appears at an earlier position than any other even number is =1/10
→ Total no. of possible even number = 10
→ Here we are not considering odd number.
→ The probability that 2 appears at an earlier position than any other even number is =1/10
Question 25 
5  
7  
2  
1 
Question 25 Explanation:
Eigen value of A[4×4] matrix is 5, 2, 1, 4.
(AλI)^{2}I=0 [a^{2}b^{2}=(a+b)(ab)]
(AλI+I)(AλII)=0
(A(λI)I)(A(λ+I)I=0
Let us assume λ1=k & λ +1=k
λ =k+1 λ =k1
⇓ ⇓
for k=5; λ=4 λ =6
k=2; λ=1 λ =3
k=1; λ=2 λ = 0
k=4; λ=5 λ = 3
So; λ=4,1,2,5,6,3,0,3
Check with the option
Option C = 2
(AλI)^{2}I=0 [a^{2}b^{2}=(a+b)(ab)]
(AλI+I)(AλII)=0
(A(λI)I)(A(λ+I)I=0
Let us assume λ1=k & λ +1=k
λ =k+1 λ =k1
⇓ ⇓
for k=5; λ=4 λ =6
k=2; λ=1 λ =3
k=1; λ=2 λ = 0
k=4; λ=5 λ = 3
So; λ=4,1,2,5,6,3,0,3
Check with the option
Option C = 2
Question 26 
Question 26 Explanation:
π_{4} = refines every partition. So it has to be bottom of poset diagram.
And, neither π_{2} refines π_{3}, nor π_{3} refines π_{2}.
Here, only π_{1} refined by every set, so it has to be at the top.
Finally, option C satisfies all the property.
And, neither π_{2} refines π_{3}, nor π_{3} refines π_{2}.
Here, only π_{1} refined by every set, so it has to be at the top.
Finally, option C satisfies all the property.
Question 27 
{[1,1,0]^{T}, [1,0,1]^{T}} is a basis for the subspace X.  
{[1,1,0]^{T}, [1,0,1]^{T}} is a linearly independent set, but it does not span X and therefore is not a basis of X.
 
X is not a subspace of R^{3}  
None of the above

Question 27 Explanation:
Since, [1,1,0]^{T} and [1,0,1]^{T} are linearly independent set and spans X. So is the basis for subspace X.
Question 28 
1.5
 
√2
 
1.6  
1.4 
Question 28 Explanation:
Given series is
x_{n+1}=x_{n}/2+9/8x_{n} ⟶ (I); x_{0}=0.5
Equation based on NewtonRapson is
x_{n+1}=x_{n}f(x_{n})/f'(x_{n})⟶ (II)
Equate I and II
x_{n}f(x_{n})/f'(x_{n})=x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n})=x_{n}x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n})=x_{n}(4x^{n2}9)/8x_{n}
So, f(x)=4x^{n2}9
4x^{2}9=0
4x^{2}=9
x^{2}=9/4
x=±3/2
x=±1.5
Equation based on NewtonRapson is
x_{n+1}=x_{n}f(x_{n})/f'(x_{n})⟶ (II)
Equate I and II
x_{n}f(x_{n})/f'(x_{n})=x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n})=x_{n}x_{n}/2+9/8x_{n}
x_{n}f(x_{n})/f'(x_{n})=x_{n}(4x^{n2}9)/8x_{n}
So, f(x)=4x^{n2}9
4x^{2}9=0
4x^{2}=9
x^{2}=9/4
x=±3/2
x=±1.5
Question 29 
15 states  
11 states  
10 states  
9 states

Question 29 Explanation:
Given that number of 0’s and 1’s are divisible by 3 and 5, it means that the number of 0’s and 1’s must be divisible by 15. As the LCM of 3 and 5 is 15, so number of 0’s and 1’s are divisible by 3 and 5 is only possible if of 0’s and 1’s are divisible by 15. Also modulo 3 will leave a remainder of 0,1,2 (3 states required) and modulo 5 will leave remainder of 0,1,2,3,4 (5 states required) , so product automata will require (3 × 5=15 states).
Question 30 
The language L = {0^{i}21^{i}  i≥0} over the alphabet {0,1, 2} is:
not recursive.  
is recursive and is a deterministic CFL.
 
is a regular language.
 
is not a deterministic CFL but a CFL.

Question 30 Explanation:
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.
Question 31 
Which of the following languages is regular?
{ww^{R}w ∈ {0,1}^{+}}
 
{ww^{R}xx, w ∈ {0,1}^{+}}
 
{wxw^{R}x, w ∈ {0,1}^{+}}  
{xww^{R}x, w ∈ {0,1}^{+}}

Question 31 Explanation:
The regular expression corresponding to option C is:
0 (0+1)^{+} 0 + 1 (0+1)^{+} 1
Any string which begins and ends with same symbol, can be written in form of “wxw^{r}”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^{r} = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^{r}” and L={wxw^{r}  x,w ϵ {0,1}^{+} } is a regular language.
0 (0+1)^{+} 0 + 1 (0+1)^{+} 1
Any string which begins and ends with same symbol, can be written in form of “wxw^{r}”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and w^{r} = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxw^{r}” and L={wxw^{r}  x,w ϵ {0,1}^{+} } is a regular language.
Question 32 
P only
 
Q and S
 
R and S  
S only

Question 32 Explanation:
(P), (Q), (R) cover all the minterms and are equivalent to f(w,x,y,z) = Σ(0,4,5,7,8,9,13,15).
(S) covers the minterms m_{0}, m_{8}, m_{9}, m_{2}, m_{3}, m_{6}, m_{7}.
(S) is not covering the minterms m_{4}, m_{5}, m_{13}, m_{15}.
Question 33 
Only P and Q are valid.  
Only Q and R are valid.
 
Only P and R are valid.  
All P, Q, R are valid. 
Question 33 Explanation:
P: Y * Z =YZ + Y’Z’
=Y(XY + X’Y’) + Y’(XY+X’Y’)’
=XY+Y’(X ⊕ Y)
=XY+Y’(XY’+X’Y)
=XY+XY’
=X(Y+Y’) =X
Q: X*Z = (XZ + X’Z’)
= X(XY + X’Y’) + X’(XY + X’Y’)’
=XY+X’(X’Y+XY’)
=XY+X’Y
=(X+X’)Y = Y
R: X* Y*Z
= X*X Since P: Y*Z= X
=XX + X’X’
= 1
=Y(XY + X’Y’) + Y’(XY+X’Y’)’
=XY+Y’(X ⊕ Y)
=XY+Y’(XY’+X’Y)
=XY+XY’
=X(Y+Y’) =X
Q: X*Z = (XZ + X’Z’)
= X(XY + X’Y’) + X’(XY + X’Y’)’
=XY+X’(X’Y+XY’)
=XY+X’Y
=(X+X’)Y = Y
R: X* Y*Z
= X*X Since P: Y*Z= X
=XX + X’X’
= 1
Question 34 
Suppose only one multiplexer and one inverter are allowed to be used to implement any Boolean function of n variables. What is the minimum size of the multiplexer needed?
2^{n} line to 1 line  
2^{n+1} line to 1 line
 
2^{n1} line to 1 line
 
2^{n2} line to 1 line 
Question 34 Explanation:
Both true and complement forms of all variables are necessary to implement any function of n variables.
A 2^{n} X 1 multiplexer can implement any function of n variables. As n variables are given to select lines, so that true and complement forms of all variables get generated inside the MUX.
As one inverter is available, we can generate complement of one variable outside of the Multiplexer. And remaining (n1) variables are given to select lines. With this we have true and complement form of all n variables.
So, the answer is 2^{n1} X 1 MUX.
A 2^{n} X 1 multiplexer can implement any function of n variables. As n variables are given to select lines, so that true and complement forms of all variables get generated inside the MUX.
As one inverter is available, we can generate complement of one variable outside of the Multiplexer. And remaining (n1) variables are given to select lines. With this we have true and complement form of all n variables.
So, the answer is 2^{n1} X 1 MUX.
Question 35 
6, 3  
10, 4
 
6, 4  
10, 5

Question 35 Explanation:
Formula: n(n+1)/2 AND gates and n OR gates are needed for an nbit carry look ahead circuit for addition of two binary numbers.
Question 36 
0, 3, 4  
0, 3, 4, 5
 
0, 1, 2, 3, 4
 
0, 1, 2, 3, 4, 5

Question 36 Explanation:
A counter goes through a sequence of states. Given counter resets when A_{1}=A_{3}=1.
Here, initial state is 0000. It goes through 0001,0010,0011,0100 and 0101. When the state is 5(0101) it immediately resets to initial state 0. Here, state 5 is not considered as valid state.
So valid states are 0,1,2,3, and 4 and hence it is a Mod5 counter.
Here, initial state is 0000. It goes through 0001,0010,0011,0100 and 0101. When the state is 5(0101) it immediately resets to initial state 0. Here, state 5 is not considered as valid state.
So valid states are 0,1,2,3, and 4 and hence it is a Mod5 counter.
Question 37 
7  
8  
10  
14 
Question 37 Explanation:
Since operand forwarding is there, by default we consider the operand forwarding from EX stage to EX stage.
So, total no. of clock cycles needed to execute the given 3 instructions is 8.
So, total no. of clock cycles needed to execute the given 3 instructions is 8.
Question 38 
6, 1
 
5, 7
 
3, 2  
1, 5 
Question 38 Explanation:
8 2 3 ^ / 2 3 * + 5 1 * 
After the * is evaluated at the time elements in the stack is 1, 6.
After the * is evaluated at the time elements in the stack is 1, 6.
Question 39 
d e b f g c a
 
e d b g f c a  
e d b f g c a
 
d e f g b c a

Question 39 Explanation:
Inorder: Left root Right
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Question 40 
Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
8, _, _, _, _, _, 10  
1, 8, 10, _, _, _, 3  
1, _, _, _, _, _,3
 
1, 10, 8, _, _, _, 3 
Question 40 Explanation:
Consider a hash table of size 7
Starting index is zero i.e.,
⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Starting index is zero i.e.,
⇾ Given hash function is = (3x+4) mod 3
⇾ Given sequence is = 1, 3, 8, 10
where x = 1 ⟹ (3(1)+4)mod 3 = 0
1 will occupy index 0.
where x = 3 ⟹ (3(3)+4) mod 7 = 6
3 will occupy index 6.
where x = 8 ⟹ (3(8)+4) mod 7 = 0
Index ‘0’ is already occupied then put value(8) at next space (1).
where x = 10 ⟹ (3(10)+4) mod 7 = 6
Index ‘6’ is already occupied then put value(10) at next space (2).
The resultant sequence is (1, 8, 10, __ , __ , __ , 3).
Question 41 
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
Dijkstra’s algorithm starting from S.  
Warshall’s algorithm.
 
Performing a DFS starting from S.  
Performing a BFS starting from S.

Question 41 Explanation:
→ Time Complexity of the Dijkstra’s algorithm : It depends on your implementation of Dijkstra's Algorithm. Simple algorithm is given below with Time complexity of O(V^{2}). There are also some timeefficient Algorithms: Graph represented using adjacency list can be reduced to O(E log V) with the help of binary heap.
→ Time Complexity of the Warshall’s algorithm: O(n^{3}). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
→ Time Complexity of the Warshall’s algorithm: O(n^{3}). Warshall’s algorithm basically we are using to find all pair shortest path.
→ DFS cannot be used for finding shortest paths.
→ Time Complexity for BFS : O(E+V)
Question 42 
5  
7  
9  
18 
Question 42 Explanation:
We need to evaluate f(5)
f(5) = f(3) + 2
f(3) = f(2) + 5 (where r is static and value of r=5)
f(2) = f(1) + 5
f(1) = f(0) + 5
f(0) = 1
⟹ f(5) = 1+5+5+5+2 = 18
f(5) = f(3) + 2
f(3) = f(2) + 5 (where r is static and value of r=5)
f(2) = f(1) + 5
f(1) = f(0) + 5
f(0) = 1
⟹ f(5) = 1+5+5+5+2 = 18
Question 43 
A complete nary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete nary tree. If L = 41, and I = 10, what is the value of n?
3  
4  
5  
6 
Question 43 Explanation:
L = (n1) * I + 1
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n1) * 10 + 1
40 = (n1) * 10
n = 5
L = No. of leaves = 41
I = No. of Internal nodes = 10
41 = (n1) * 10 + 1
40 = (n1) * 10
n = 5
Question 44 
θ (log_{2} n)
 
Ω (n)  
θ (log_{2}log_{2} n)
 
θ(√n)

Question 44 Explanation:
The given code is to calculate the greatest common divisor (GCD) using Euclidean algorithm.
Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)
Then, time complexity is = O(log(a∙b) = O(log(a+b)) = O(log n)
Question 45 
Ω (n^{2})  
θ (nlog_{2} n)
 
θ (log_{2} n)  
θ (log_{2}log_{2} n) 
Question 45 Explanation:
Recurrence relation should be T(n)=T(n^{1/2})+1 where n>2
Solving the Recurrence,
Solving the Recurrence,
Question 46 
the number of nodes in the tree
 
the number of internal nodes in the tree
 
the number of leaf nodes in the tree
 
the height of the tree

Question 46 Explanation:
Let take example,
So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
So from applying algorithm to above tree we got the final value v=3 which is nothing but no. of leaf nodes.
Note that height of the tree is also 3 but it is not correct because in algorithm the part
if ((ptr → leafchild = = NULL) && (ptr → rightchild = = NULL)) value = 1;
Says that if there is only one node the value is 1 which cannot be height of the tree because the tree with one node has height '0'.
Question 47 
Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:
θ(log_{2}n)  
θ(log_{2}log_{2}n)  
θ(n)  
θ(nlog_{2}n)

Question 47 Explanation:
Max heap is the complete binary tree that means each node has either zero children or two children except last level. So in worst case insertion of element is at last level. So, number of comparisons required at each level starting from root is equal to 1+2+4+8+16+ this series is equal to "logn". All the elements are sorted, the binary search which will result in O(loglogn) number of comparisons.
Question 48 
Which of the following is TRUE about formulae in Conjunctive Normal Form?
For any formula, there is a truth assignment for which at least half the clauses evaluate to true.
 
For any formula, there is a truth assignment for which all the clauses evaluate to true.
 
There is a formula such that for each truth assignment, at most onefourth of the clauses evaluate to true.
 
None of the above.

Question 48 Explanation:
For n=2, (means two variables a and b)
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3TRUE=7, FALSE=1 (7/8 ARE TRUE)
(12^{n}) are TRUE.
Looking at options,
Formula: a ∧ b
Truth table:
Conjunctive normal form : (a ∨ b) ∧ (a ∨ ~b) ∧ (~a ∨ b)
Similarly,
For n=1TRUE=1, FALSE=1 (1/2 ARE TRUE)
For n=2TRUE=3, FALSE=1 (3/4 ARE TRUE)
For n=3TRUE=7, FALSE=1 (7/8 ARE TRUE)
(12^{n}) are TRUE.
Looking at options,
Question 49 
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w. Which of the following is FALSE?
There is a minimum spanning tree containing e.
 
If e is not in a minimum spanning tree T, then in the cycle formed by adding e to T, all edges have the same weight.
 
Every minimum spanning tree has an edge of weight w.  
e is present in every minimum spanning tree. 
Question 49 Explanation:
To find minimum Spanning tree(MST), may not be present ‘e’ in every MST graph.
Question 50 
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
At least 2n  c comparisons, for some constant c, are needed.
 
At most 1.5n  2 comparisons are needed.
 
At least nlog_{2}n comparisons are needed.
 
None of the above. 
Question 50 Explanation:
If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.
The time complexity is, T(n) = 2T(n/2) + 2
If n is odd: 3*(n1)/2
If n is even: 1 Initial comparison for initializing min and max, and 3(n2)/2 comparisons for rest of the elements
= 1 + 3*(n2)/2 = 3n/2 2(1.5n2)
Eg: 100 numbers=> (3*100/2)2 ==>148.
Theorem: Every algorithm which finds both the maximum and the minimum element among n distinct numbers must perform atleast ⎡3n/2⎤2 comparisons.
Proof: Let A be an arbitrary algorithm for the problem. By orienting Kn concurrently with the execution with the execution of A according to the rules above (which tell the adversary which orientation to chose when A asks the query Q(x,y)) the adversary will deliver 2 pieces of new information (that is one of x and y is excluded from being the maximum and the other from being the minimum) atmost ⎣n/2⎦times. Thus in order for A to collect the required information A must make atleast 2n2⎣n/2⎦=⎡3n/2⎤2comparisions.
If n is even then initialize min and max as minimum and maximum of the first two elements respectively.
For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.
The time complexity is, T(n) = 2T(n/2) + 2
If n is odd: 3*(n1)/2
If n is even: 1 Initial comparison for initializing min and max, and 3(n2)/2 comparisons for rest of the elements
= 1 + 3*(n2)/2 = 3n/2 2(1.5n2)
Eg: 100 numbers=> (3*100/2)2 ==>148.
Theorem: Every algorithm which finds both the maximum and the minimum element among n distinct numbers must perform atleast ⎡3n/2⎤2 comparisons.
Proof: Let A be an arbitrary algorithm for the problem. By orienting Kn concurrently with the execution with the execution of A according to the rules above (which tell the adversary which orientation to chose when A asks the query Q(x,y)) the adversary will deliver 2 pieces of new information (that is one of x and y is excluded from being the maximum and the other from being the minimum) atmost ⎣n/2⎦times. Thus in order for A to collect the required information A must make atleast 2n2⎣n/2⎦=⎡3n/2⎤2comparisions.
Question 51 
T(n) = O(√n) and T(n) = Ω(√n)
 
T(n) = O(√n) and T(n) = Ω(1)
 
T(n) = O(n) and T(n) = Ω(√n)  
None of the above

Question 51 Explanation:
Here in best case time complexity is omega(1) and in worst case time complexity is O(sqrt(n)).
Question 52 
it is left recursive
 
it is right recursive  
it is ambiguous
 
it is not contextfree 
Question 52 Explanation:
The given grammar is not left recursive and also it is context free (Type 2 grammar), so option A and D is wrong. Being a right recursive grammar is not an issue for LL(1) grammar. So even if given grammar is right recursive, this is not a reason for NOT LL(1).
This grammar has two parse tree for string “ibt ibt aea”.
This grammar has two parse tree for string “ibt ibt aea”.
Question 53 
Both P and Q are true
 
P is true and Q is false
 
P is false and Q is true
 
Both P and Q are false

Question 53 Explanation:
Every regular grammar is LL(1) is false, as the grammar may have left recursion or left factoring or also it is possible that grammar is ambiguous.
For ex: Consider a regular grammar
S>aS  a  ϵ
this grammar is ambiguous as for string "a" two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language acceptor as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
For ex: Consider a regular grammar
S>aS  a  ϵ
this grammar is ambiguous as for string "a" two parse tree is possible.
Hence it is regular but not LL(1).
But every regular set has a language acceptor as DFA , so every regular set must have atleast one grammar which is unambiguous.
Hence, every regular set has LR(1) grammar.
Question 54 
2  
3  
5  
6 
Question 54 Explanation:
We can write the given four instructions using OP and MOV operations as below.
MOV a, R_{1}
ADD b, R_{1}
MOV c, R_{2}
ADD d, R_{2}
SUB e, R_{2}
SUB R_{1}, R_{2}
MOV R_{2}, m
So, from the above total no. of MOV instructions = 3
MOV a, R_{1}
ADD b, R_{1}
MOV c, R_{2}
ADD d, R_{2}
SUB e, R_{2}
SUB R_{1}, R_{2}
MOV R_{2}, m
So, from the above total no. of MOV instructions = 3
Question 55 
5  
15  
40  
55 
Question 55 Explanation:
Waiting time for process P2 = TAT  Execution time
= Completion time  AT  ET
= 55  15  25
= 15
Question 56 
Both P and Q are true, and Q is the reason for P
 
Both P and Q are true, but Q is not the reason for P  
P is false, but Q is true
 
Both P and Q are false

Question 56 Explanation:
⟾ FIFO suffers from Belady Anomaly.
⟾ Belady Anomaly states that when number of page frames. Increases then increase the page fault rate.
P is True:
⟾ Locality of reference states that it’s a phenomenon in which the same values of related storage locations are frequently accessed depending on the memory access pattern.
Q is also True:
⟾ Q is not the reason for P, because Belady Anomaly not depends on the locality of reference.
⟾ Belady Anomaly states that when number of page frames. Increases then increase the page fault rate.
P is True:
⟾ Locality of reference states that it’s a phenomenon in which the same values of related storage locations are frequently accessed depending on the memory access pattern.
Q is also True:
⟾ Q is not the reason for P, because Belady Anomaly not depends on the locality of reference.
Question 57 
P0  
P1
 
P2  
None of the above, since the system is in a deadlock.

Question 57 Explanation:
Given that there are 5 units of each resource type.
543:
System is in safe state
Order of Execution =
P2 will execute last.
543:
System is in safe state
Order of Execution =
P2 will execute last.
Question 58 
It does not ensure mutual exclusion.  
It does not ensure bounded waiting.
 
It requires that processes enter the critical section in strict alternation.
 
It does not prevent deadlocks, but ensures mutual exclusion. 
Question 58 Explanation:
⟶ This satisfies the property of mutual exclusion.
⟶ Here Bounded waiting is also satisfied because there is a count for accessing the critical section i.e, it ensures the ME.
Mutual Exclusion:
⟶ It is a property of concurrency control.
⟶ Which is instituted to prevent race condition.
⟶ A process is executing in a critical section then no other process have access to enter into a critical section.
Bounded waiting:
There may exists a bound or limit, on the number of times other processes are allowed to enter their critical section after a process made request to enter its critical section and before that request is request.
⟶ In the given statement, wants1 and wants2 are initialized to false.
⟶ Two process P1 and P2 are need to access CS.
⟶ If both processes are access at a time they may wait for other process to complete its execution its lead to deadlock.
⟶ If P1 access the CS, then wants1=True (wants may True (or) False). So this says that P2 is not accessing CS and vice versa.
⟶ Here Bounded waiting is also satisfied because there is a count for accessing the critical section i.e, it ensures the ME.
Mutual Exclusion:
⟶ It is a property of concurrency control.
⟶ Which is instituted to prevent race condition.
⟶ A process is executing in a critical section then no other process have access to enter into a critical section.
Bounded waiting:
There may exists a bound or limit, on the number of times other processes are allowed to enter their critical section after a process made request to enter its critical section and before that request is request.
⟶ In the given statement, wants1 and wants2 are initialized to false.
⟶ Two process P1 and P2 are need to access CS.
⟶ If both processes are access at a time they may wait for other process to complete its execution its lead to deadlock.
⟶ If P1 access the CS, then wants1=True (wants may True (or) False). So this says that P2 is not accessing CS and vice versa.
Question 59 
Courses in which all the female students are enrolled.
 
Courses in which a proper subset of female students are enrolled.
 
Courses in which only male students are enrolled.
 
None of the above

Question 59 Explanation:
Option A: It is not result the all the female students who are enrolled. So option A is false.
Option B: Yes, True. It selects the proper subset of female students which are enrolled because in the expression we are performing the cartesian product.
Option C: False. It doesn’t shows (or) display the males students who are enrolled.
Option B: Yes, True. It selects the proper subset of female students which are enrolled because in the expression we are performing the cartesian product.
Option C: False. It doesn’t shows (or) display the males students who are enrolled.
Question 60 
Names of employees with a male supervisor.
 
Names of employees with no immediate male subordinates.  
Names of employees with no immediate female subordinates.  
Names of employees with a female supervisor.

Question 60 Explanation:
The given Tuple Relational calculus produce names of employees with no immediate female subordinates.
Question 61 
Q_{1} is the correct query
 
Q_{2} is the correct query  
Both Q_{1} and Q_{2} produce the same answer  
Neither Q_{1} nor Q_{2} is the correct query 
Question 61 Explanation:
The required output is find the employees who get higher salary than anyone in the department “5”.
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
Question 62 
Which one of the following statements if FALSE?
Any relation with two attributes is in BCNF  
A relation in which every key has only one attribute is in 2NF
 
A prime attribute can be transitively dependent on a key in a 3NF relation  
A prime attribute can be transitively dependent on a key in a BCNF relation 
Question 62 Explanation:
Rules for BCNF is:
i) It is in 3NF.
ii) For any dependency X→ Y
where X is a super key.
iii) Functional dependency has been removed.
Option D is false.
→ Because a prime attribute can’t be transitive dependent on a key in a BCNF relation.
i) It is in 3NF.
ii) For any dependency X→ Y
where X is a super key.
iii) Functional dependency has been removed.
Option D is false.
→ Because a prime attribute can’t be transitive dependent on a key in a BCNF relation.
Question 63 
The order of a leaf node in a B^{+} tree is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?
63  
64  
67  
68 
Question 63 Explanation:
Disk Block size = 1 KBytes = 2^{10} Bytes = 1024 Bytes
Data recorder pointer size, r = 7 bytes
Value size, v = 9 bytes
Disk Block pointer, P = 6 bytes
⇒ Order of leaf be m, then
r*m+v*m+p <= 1024
7m+9m+6 <= 1024
16m <= 1024  6
m <= 63
Data recorder pointer size, r = 7 bytes
Value size, v = 9 bytes
Disk Block pointer, P = 6 bytes
⇒ Order of leaf be m, then
r*m+v*m+p <= 1024
7m+9m+6 <= 1024
16m <= 1024  6
m <= 63
Question 64 
Both S_{1} and S_{2} are conflict serializable.
 
S_{1} is conflict serializable and S_{2} is not conflict serializable.  
S_{1} is not conflict serializable and S_{2} is conflict serializable.
 
Both S_{1} and S_{2} are not conflict serializable.

Question 64 Explanation:
In precedence graph of S_{1} since cycle is formed so not conflict serializable.
But in precedence graph of S_{2} No cycle is formed so it is conflict serializable.
Question 65 
There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that ONLY one station transmits in a given time slot?
np(1p)^{n1}  
(1p)^{n1}  
p(1p)^{n1}
 
1(1p)^{n1} 
Question 65 Explanation:
This question can be solved by binomial distribution,
^{n}C_{1}P^{1}(1p)^{n1}
= nP(1P)^{n1}
^{n}C_{1}P^{1}(1p)^{n1}
= nP(1P)^{n1}
Question 66 
In a token ring network the transmission speed is 10^{7} bps and the propagation speed is 200 metres/μs. The 1bit delay in this network is equivalent to:
500 metres of cable.  
200 metres of cable.
 
20 metres of cable.  
50 metres of cable.

Question 66 Explanation:
T_{t}= L / B => 1/ 10^{7} = 0.1 microsec
Given T_{p}= 200 m / microsec
In, 1 microsec it covers 200m
Therefore, in 0.1 microsec it is 200 * 0.1 = 20 meters
Given T_{p}= 200 m / microsec
In, 1 microsec it covers 200m
Therefore, in 0.1 microsec it is 200 * 0.1 = 20 meters
Question 67 
The address of a class B host is to be split into subnets with a 6bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet?
62 subnets and 262142 hosts.
 
64 subnets and 262142 hosts.
 
62 subnets and 1022 hosts.
 
64 subnets and 1024 hosts.

Question 67 Explanation:
It is a class B address, so there 16bits for NID and 16bits for HID.
From HID, we took 6bits for subnetting.
Then total subnets possible = ( 2^{6} )  2 = 64
Total hosts possible for each subnet = (2^{10})  2 = 1022
From HID, we took 6bits for subnetting.
Then total subnets possible = ( 2^{6} )  2 = 64
Total hosts possible for each subnet = (2^{10})  2 = 1022
Question 68 
The message 11001001 is to be transmitted using the CRC polynomial x^{3}+1 to protect it from errors. The message that should be transmitted is:
11001001000
 
11001001011
 
11001010
 
110010010011

Question 68 Explanation:
CRC polynomial = x^{3}+1 [∵ In data 3zero’s need to be append to data]
= 1001
∴ Data transmitted is: 11001001011
= 1001
∴ Data transmitted is: 11001001011
Question 69 
The distance between two stations M and N is L kilometers. All frames are K bits long. The propagation delay per kilometer is t seconds. Let R bits/second be the channel capacity. Assuming that processing delay is negligible, the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used, is:
⌈log_{2}(2LtR+2K/K)⌉  
⌈log_{2}(2LtR/K)⌉
 
⌈log_{2}(2LtR+K/K)⌉  
⌈log_{2}(2LtR+K/2K)⌉

Question 69 Explanation:
Maximum window size at sender side,
N = (T_{k} + 2T_{p})/T_{k}
T_{p} = l × l sec
T_{k} = K/R sec
So, N = (K/R+2Lt)/(K/R) = K+2LtR/K
Note that when asked for general sliding window protocol (not GBN nor SR) then we do not care about receiver's window size.
So, no. of bits required,
⌈log_{2} K+2LtR/K⌉
N = (T_{k} + 2T_{p})/T_{k}
T_{p} = l × l sec
T_{k} = K/R sec
So, N = (K/R+2Lt)/(K/R) = K+2LtR/K
Note that when asked for general sliding window protocol (not GBN nor SR) then we do not care about receiver's window size.
So, no. of bits required,
⌈log_{2} K+2LtR/K⌉
Question 70 
P – 2 Q – 1 R – 3 S – 5  
P – 1 Q – 4 R – 2 S – 3
 
P – 1 Q – 4 R – 2 S – 5  
P – 2 Q – 4 R – 1 S – 3 
Question 70 Explanation:
SMTP is an application layer protocol used for email transmission.
TCP is a core transport layer protocol.
BGP is a network layer protocol backing the core routing decisions on the Internet.
PPP is a data link layer protocol commonly used in establishing a direct connection between two networking nodes.
TCP is a core transport layer protocol.
BGP is a network layer protocol backing the core routing decisions on the Internet.
PPP is a data link layer protocol commonly used in establishing a direct connection between two networking nodes.
Question 71 
10  
11  
20  
21 
Question 71 Explanation:
Memory reference is R1←M[1000]
which will run 10 times, because the memory location is 10.
R2←M[R3]
M[R3]←R2
For every iteration we have two memory reference such that number of memory references is 10*2 = 20
Total number of memory references = 20+1 = 21
which will run 10 times, because the memory location is 10.
R2←M[R3]
M[R3]←R2
For every iteration we have two memory reference such that number of memory references is 10*2 = 20
Total number of memory references = 20+1 = 21
Question 72 
100  
101  
102  
110 
Question 72 Explanation:
Program can store the memory access results from 2000 to 2010.
→ We are using decrement operator which decrements register value by 1.
→ So it can store 110, 109, 108, ……… 100 at 2010th location.
→ At 2010 it stores 100.
→ We are using decrement operator which decrements register value by 1.
→ So it can store 110, 109, 108, ……… 100 at 2010th location.
→ At 2010 it stores 100.
Question 73 
1005
 
1020
 
1024  
1040

Question 73 Explanation:
Memory is byte addressable, so it requires 1 word or 4 bytes to perform a each operation such that
→ Starts at memory location 1000.
Interrupt occurs during the execution of information “INC R3”.
Then the value of address i.e., 1024 is pushed into the stack.
→ Starts at memory location 1000.
Interrupt occurs during the execution of information “INC R3”.
Then the value of address i.e., 1024 is pushed into the stack.
Question 74 
b*ab*ab*ab*  
(a+b)*
 
b*a(a+b)*  
b*ab*ab* 
Question 74 Explanation:
State q3 is unreachable and state q1 and q2 are equivalent, so we can merge q1 and q2 as one state. The resulting DFA will be:
Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Clearly we can see that the regular expression for DFA is “ b*a (a+b)* ”.
Question 75 
1  
2  
3  
4 
Question 75 Explanation:
The minimum state automaton for problem 74 is:
Question 76 
0, 10, 110, 1110, 11110, 11111
 
11, 10, 011, 010, 001, 000
 
11, 10, 01, 001, 0001, 0000
 
110, 100, 010, 000, 001, 111

Question 76 Explanation:
→ 0, 10, 110, 1110, 11110, 11111
Question 77 
3  
2.1875
 
2.25  
1.9375

Question 77 Explanation:
The Average length =(1*1/2+2*1/4+3*1/8+4*1/16+5*1/32+5*1/32)=1.9375
Question 78 
aaaabb
 
aabbbb
 
aabbab  
abbbba 
Question 78 Explanation:
The string “aabbab” can be derived by following steps:
S > aB [Using S > aB]
> aaBB [Using B > aBB]
> aabB [Using B > b]
> aabbS [Using B > bS]
> aabbaB [Using S > aB]
> aabbab [Using B > b]
S > aB [Using S > aB]
> aaBB [Using B > aBB]
> aabB [Using B > b]
> aabbS [Using B > bS]
> aabbaB [Using S > aB]
> aabbab [Using B > b]
Question 79 
1  
2  
3  
4 
Question 79 Explanation:
There exist two parse tree for the string “aabbab” using LMD (left most derivation)
Question 80 
40  
50  
56  
59 
Question 80 Explanation:
Size of main memory = 2^{16} Bytes
Size of cache = 32×64 = 2^{5} × 2^{6} = 2^{11} = 2048 bytes
⟶ A 50×50 two dimensional array of bytes is stored in main memory i.e., size of array is = 2500 bytes
⟶ Number of page faults = 2500  2048 = 452
⟶ The second array is accessed , No. of page faults = 452*2 = 904
Total = 904+452 =1356
⟹ No. of data cache missed = 56
Size of cache = 32×64 = 2^{5} × 2^{6} = 2^{11} = 2048 bytes
⟶ A 50×50 two dimensional array of bytes is stored in main memory i.e., size of array is = 2500 bytes
⟶ Number of page faults = 2500  2048 = 452
⟶ The second array is accessed , No. of page faults = 452*2 = 904
Total = 904+452 =1356
⟹ No. of data cache missed = 56
Question 81 
line 4 to line 11  
line 4 to line 12  
line 0 to line 7  
line 0 to line 8 
Question 81 Explanation:
Starting address = 1100H
= 0001000100000000
00100 ⇒ starting line address of cache from where array elements will be stored which is '4'.
Total no. of cache lines required to store 50×50 array elements of eac h 1 byte,
= ⌈2500/64⌉ = 40
Since cache line size is 64B and each array element size is 1B. So 64 element at a time can be placed in a cache line.
Now, 40 cache lines required but 32 lines are available. So last 8 blocks or lines requirements will be fulfilled by replacing the 8 blocks from where we started to fill the array elements, i.e., 4 to 11.
Question 82 
7  
8  
9  
10 
Question 82 Explanation:
Given sequence is
1, 2, 1, 3, 7, 4, 5, 6, 3, 1
No. of frames = 3
Using Optimal page replacement,
Total 7 page faults.
1, 2, 1, 3, 7, 4, 5, 6, 3, 1
No. of frames = 3
Using Optimal page replacement,
Total 7 page faults.
Question 83 
0  
1  
2  
3 
Question 83 Explanation:
Given sequence is
1, 2, 1, 3, 7, 4, 5, 6, 3, 1 br> No. of frames = 3 (Using LRU)
No. of page faults with LRU = 9
⟶ In the LRU we replace the page with least recently used page.
Using optimal page replacement
⟶ 1,2,1,3,7,4,5,6,3,1
No. of page faults with optimal = 7
Difference between optimal and LRU = 9  7 = 2
In optimal we replace the page which will occur last in the future.
1, 2, 1, 3, 7, 4, 5, 6, 3, 1 br> No. of frames = 3 (Using LRU)
No. of page faults with LRU = 9
⟶ In the LRU we replace the page with least recently used page.
Using optimal page replacement
⟶ 1,2,1,3,7,4,5,6,3,1
No. of page faults with optimal = 7
Difference between optimal and LRU = 9  7 = 2
In optimal we replace the page which will occur last in the future.
Question 84 
2^{20}
 
2^{10}  
None of the above 
Question 84 Explanation:
At each move, robot can move either 1 unit right, or 1 unit up, and there will be 20 such moves required to reach (10,10) from (0,0). So we have to divide these 20 moves, numbered from 1 to 20, into 2 groups : right group and up group. Right group contains those moves in which we move right, and up group contains those moves in which we move up. Each group contains 10 elements each. So basically, we have to divide 20 things into 2 groups of 10 10 things each, which can be done in 20! / (10!∗10! )=^{20}C_{10} ways.
Question 85 
2^{9}  
2^{19}  
Question 85 Explanation:
Since we are not allowed to traverse from (4,4) to (5,4). So we will subtract all those paths which were passing through (4,4) to (5,4).
To count number of paths passing through (4,4) to (5,4), we find number of paths from (0,0) to (4,4), and then from (5,4) to (10,10).
From (0,0) to (4,4), number of paths = ^{8}C_{4} (found in same way as in previous question).
From (5,4) to (10,10), number of paths = ^{11}C_{5}.
So total number of paths required : ^{20}C_{10}−^{8}C_{4}∗^{11}C_{5}
To count number of paths passing through (4,4) to (5,4), we find number of paths from (0,0) to (4,4), and then from (5,4) to (10,10).
From (0,0) to (4,4), number of paths = ^{8}C_{4} (found in same way as in previous question).
From (5,4) to (10,10), number of paths = ^{11}C_{5}.
So total number of paths required : ^{20}C_{10}−^{8}C_{4}∗^{11}C_{5}
There are 85 questions to complete.