Gate2003
Question 1 
X^{y}  
e^{x}  
ln(1+x)
 
X^{x}

Question 1 Explanation:
P = P * (x/i)
S = S+P
Iteration 1:
P=1; i=1; S=1
P=x
S=1+x
Iteration 2:
P=x; S=1+x; i=2
P = x * x/2 = x^{2}/2
Iteration 3:
P=x^{2}/2; S=1+x+x^{2}/2; i=3
P = (x^{2}/2)(x/3) = x^{3}/6
S = 1 + x + x^{2}/2 + x^{3}/6
Continue upto n Then f( ) returns:
S = 1 + x/1 + x^{2}/2⋅1 + x^{3}/3⋅2 + ...
= 1 + x/1! + x^{2}/2! + x^{3}/3! + ... + x^{n}/n!
= e^{x}
S = S+P
Iteration 1:
P=1; i=1; S=1
P=x
S=1+x
Iteration 2:
P=x; S=1+x; i=2
P = x * x/2 = x^{2}/2
Iteration 3:
P=x^{2}/2; S=1+x+x^{2}/2; i=3
P = (x^{2}/2)(x/3) = x^{3}/6
S = 1 + x + x^{2}/2 + x^{3}/6
Continue upto n Then f( ) returns:
S = 1 + x/1 + x^{2}/2⋅1 + x^{3}/3⋅2 + ...
= 1 + x/1! + x^{2}/2! + x^{3}/3! + ... + x^{n}/n!
= e^{x}
Question 2 
I, II, and IV only  
II, III, and IV only  
II and IV only
 
IV only 
Question 2 Explanation:
i) A[2] can be consider as a pointer and this will not give any compiletime error.
ii) A[2][3] This results an integer, no error will come.
iii) B[1] is a base address of an array. This will not be changed it will result a compile time error.
iv) B[2][3] This also results an integer. No error will come.
ii) A[2][3] This results an integer, no error will come.
iii) B[1] is a base address of an array. This will not be changed it will result a compile time error.
iv) B[2][3] This also results an integer. No error will come.
Question 3 
Question 3 Explanation:
P(A)=1, P(B)=1/2
P(A/B) = P(A∩B)/P(B)
= P(A)⋅P(B)/P(B) (consider P(A), P(B) are two independent events)
= 1
P(B/A) = P(B∩A)/P(A)
= P(B)⋅P(A)/P(A)
= 1/2
P(A/B) = P(A∩B)/P(B)
= P(A)⋅P(B)/P(B) (consider P(A), P(B) are two independent events)
= 1
P(B/A) = P(B∩A)/P(A)
= P(B)⋅P(A)/P(A)
= 1/2
Question 4 
Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?
2  
30  
56  
256 
Question 4 Explanation:
A can have sequence of 8 distinct integers which are sorted in ascending order.
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 8 elements from total of 8 = ^{8}C_{3}
= 8!/3!5!
= 8 * 7
= 56
→ If we are pick 3 elements from 8 sequence integers then remaining 5 elements are already in ascending order. After merging these elements then it gives A.
→ No. of possibilities of choosing 8 elements from total of 8 = ^{8}C_{3}
= 8!/3!5!
= 8 * 7
= 56
Question 5 
n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
Question 5 Explanation:
The possibilities to attend party is
i) Both husband and wife comes
ii) Only wife comes
iii) Both are not come
The no. of different gatherings possible at party is
= 3 * 3 * 3 * 3 * ... n times
= 3^{n}
i) Both husband and wife comes
ii) Only wife comes
iii) Both are not come
The no. of different gatherings possible at party is
= 3 * 3 * 3 * 3 * ... n times
= 3^{n}
Question 6 
n – k + 1  
n – k  
n – k – 1
 
n – k – 2

Question 6 Explanation:
A binary search tree consists of n distinct elements. Let consider on left subtree, it consists of (k1) elements. Then right subtree consists of (nk) elements. From this we c an write recursive function as T(k1)*(nk) i.e.,
Question 7 
Consider the set Σ* of all strings over the alphabet Σ = {0, 1}. Σ* with the concatenation operator for strings
does not form a group
 
forms a noncommutative group
 
does not have a right identity element
 
forms a group if the empty string is removed from Σ*

Question 7 Explanation:
In the concatenation '∊' is the identity element. And given one is not a group because no element has inverse element.
→ To perform concatenation with the given set can result a Monoid and it follows the property of closure, associativity and consists of identity element.
→ To perform concatenation with the given set can result a Monoid and it follows the property of closure, associativity and consists of identity element.
Question 8 
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
k and n  
k – 1 and k + 1  
k – 1 and n – 1
 
k + 1 and n – k

Question 8 Explanation:
While a vertex is removed from a graph then that can be itself be forms a new component. The minimum number of components is k1.
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components.
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components.
Question 9 
Assuming all numbers are in 2’s complement representation, which of the following numbers is divisible by 11111011?
11100111  
11100100
 
11010111
 
11011011

Question 9 Explanation:
Given: Binary numbers = 11111011
MSB bit is '1' then all numbers are negative
1's complement = 00000100
2's complement = 00000100 + 00000001 = 00000101 = 5
(A) 11100111  (25)_{10}
(B) 11100100  (28)_{10 (C) 11010111  (41)10 (D) 11011011  (37)10 Answer: Option A (25 is divisible by 5)}
MSB bit is '1' then all numbers are negative
1's complement = 00000100
2's complement = 00000100 + 00000001 = 00000101 = 5
(A) 11100111  (25)_{10}
(B) 11100100  (28)_{10 (C) 11010111  (41)10 (D) 11011011  (37)10 Answer: Option A (25 is divisible by 5)}
Question 10 
I and II only
 
II and III only
 
III only
 
All the three

Question 10 Explanation:
I is belongs to the Data hazard.
II is belongs to the Control hazard.
III is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
II is belongs to the Control hazard.
III is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
Question 11 
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
Θ (1)
 
Θ (log n)  
Θ (n)
 
Θ (n^{2}) 
Question 11 Explanation:
Each bit in Multiplier is ANDed with a bit in Multiplicand which produce n nbit numbers. The multiplication takes n units of time. The n nbit numbers are added by using (n1) nbit adders. The time taken by (n1) nbit adders is k*(n1) units.
The total time is n+knk = Θ(n)
The total time is n+knk = Θ(n)
Question 12 
Ram and Shyam have been asked to show that a certain problem Π is NPcomplete. Ram shows a polynomial time reduction from the 3SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3SAT. Which of the following can be inferred from these reductions?
Π is NPhard but not NPcomplete
 
Π is in NP, but is not NPcomplete
 
Π is NPcomplete
 
Π is neither NPhard, nor in NP

Question 12 Explanation:
Note: As per Present syllabus, it is not required.
Question 13 
L is recursive
 
L is recursively enumerable but not recursive  
L is not recursively enumerable
 
Whether L is recursive or not will be known after we find out if P = NP

Question 13 Explanation:
Here, we have two possibilities, whether
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is recular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
P = NP (or) P != NP
→ If P=NP then L=(0+1)* which is recular, then it is recursive.
→ If P!=NP then L becomes ɸ which is also regular, then it is recursive.
So, finally L is recursive.
Question 14 
The regular expression 0*(10*)* denotes the same set as
(1*0)*1*
 
0+(0+10)*
 
(0+1)*10(0+1)*  
None of the above

Question 14 Explanation:
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
Option (B) and (C) doesn't generate 11.
Question 15 
If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
L is necessarily finite
 
L is regular but not necessarily finite
 
L is context free but not necessarily regular  
L is recursive but not necessarily context free 
Question 15 Explanation:
The given language L is to be recursively enumerable. The TM which accepts the language which is in lexicographic order. If the language is not in lexicograhic order which is not accepted by TM.
The give 'L' is recursive but not necessarily context free.
The give 'L' is recursive but not necessarily context free.
Question 16 
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
Removing left recursion alone
 
Factoring the grammar alone  
Removing left recursion and factoring the grammar  
None of the above 
Question 16 Explanation:
Left recursion removing (or) factoring the given grammar are not sufficient to convert an arbitrary CFG to an LL(1) grammar.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
To convert an arbitrary CFG to an LL(1) grammar we need to remove the left recursion and as well as left factoring without that we cannot convert.
Question 17 
Assume that the SLR parser for a grammar G has n_{1} states and the LALR parser for G has n_{2} states. The relationship between n_{1} and n_{2} is
n_{1} is necessarily less than n_{2}  
n_{1} is necessarily equal to n_{2}
 
n_{1} is necessarily greater than n_{2}
 
None of the above

Question 17 Explanation:
No. of states in SLR and LALR are equal and no. of states in SLR and LALR are less than or equal to LR(1).
Question 18 
In a bottomup evaluation of a syntax directed definition, inherited attributes can
always be evaluated
 
be evaluated only if the definition is Lattributed
 
be evaluated only if the definition has synthesized attributes
 
never be evaluated

Question 18 Explanation:
LAttributed grammar can able to inherits either inherited attributes (or) synthesized attributes.
LAttributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parsetree.
LAttributed definitions are a class of syntax directed definitions whose attributes can be evaluated by a single traversal of the parsetree.
Question 19 
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder traversal sequence of the resultant tree?
7 5 1 0 3 2 4 6 8 9  
0 2 4 3 1 6 5 9 8 7  
0 1 2 3 4 5 6 7 8 9
 
9 8 6 4 2 3 0 1 5 7

Question 19 Explanation:
Inorder: 0 1 2 3 4 5 6 7 8 9
Question 20 
I and II
 
I and III  
II and III
 
I, II, and III 
Question 20 Explanation:
Which is true by considering leading ordered term present in polynomial expression.
2^{n}×2^{n} can't be written as Θ(2^{n})
So, this is False.
Question 21 
I, II and IV only  
I and IV only  
II, III and IV only  
I, III and IV only

Question 21 Explanation:
I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
Question 22 
The usual Θ(n^{2}) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
remain Θ(n^{2})
 
become Θ(n (log n)^{2})
 
become Θ(n log n)
 
become Θ(n)

Question 22 Explanation:
While using Insertion sort to sort array by using linear search then time complexity = Θ(n^{2})
Instaed, linear search use binary search then (log n) will be the worst case time complexity of binary search and performing n swaps to place an element in right position for the corresponding n elements
i.e., n×(logn+n)
Θ((n×logn)+n^{2})
Θ(n^{2})
Remains same.
Instaed, linear search use binary search then (log n) will be the worst case time complexity of binary search and performing n swaps to place an element in right position for the corresponding n elements
i.e., n×(logn+n)
Θ((n×logn)+n^{2})
Θ(n^{2})
Remains same.
Question 23 
In a heap with n elements with the smallest element at the root, the 7^{th} smallest element can be found in time
Θ(n log n)
 
Θ(n)  
Θ(log n)
 
Θ(1)

Question 23 Explanation:
The 7^{th} smallest elements can be present in any of 7 levels. Then total possible elements can be present is seven levels is
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^{th} smallest element in Θ(1) time.
1 + 2 + 4 + 6 + 8 + 16 + 32
Which is constant then we can find the 7^{th} smallest element in Θ(1) time.
Question 24 
Which of the following statements is FALSE?
In statically typed languages, each variable in a program has a fixed type  
In untyped languages, values do not have any types  
In dynamically typed languages, variables have no types  
In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program

Question 24 Explanation:
Dynamic typed languages are those languages in which variable must necessarily be defined before they are used. Then dynamic typed languages have types.
Question 25 
Using a larger block size in a fixed block size file system leads to
better disk throughput but poorer disk space utilization
 
better disk throughput and better disk space utilization  
poorer disk throughput but better disk space utilization  
poorer disk throughput and poorer disk space utilization

Question 25 Explanation:
While using a larger block size means that contains less number of blocks then that results better throughput. This can be implemented in a fixed block size then the space utilization is not upto the mark. So the statement results better disk throughput but poorer disk space utilization.
Question 26 
In a system with 32 bit virtual addresses and 1KB page size, use of onelevel page tables for virtual to physical address translation is not practical because of
the large amount of internal fragmentation  
the large amount of external fragmentation
 
the large memory overhead in maintaining page tables  
the large computation overhead in the translation process

Question 26 Explanation:
Page size = 1KB
Virtual address = 32 bit = 2^{32}
No. of page level entries = 2^{32} / 2^{10}
= 2^{22}
= 4M (Too large size)
Virtual address = 32 bit = 2^{32}
No. of page level entries = 2^{32} / 2^{10}
= 2^{22}
= 4M (Too large size)
Question 27 
Which of the following assertions is FALSE about the Internet Protocol (IP)?
It is possible for a computer to have multiple IP addresses
 
IP packets from the same source to the same destination can take different routes in the network
 
IP ensures that a packet is discarded if it is unable to reach its destination within a given number of hops
 
The packet source cannot set the route of an outgoing packets; the route is determined only by the routing tables in the routers on the way

Question 27 Explanation:
Because in strict source routing or loose source routing path is set by the source not by router and main task of router is to check outgoing path with the help of forwarding table inside it.
Question 28 
Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?
Recovery from packet losses
 
Detection of duplicate packets  
Packet delivery in the correct order  
End to end connectivity 
Question 28 Explanation:
End to end connectivity is the required functionality provided by Transport protocol.
Question 29 
Which of the following scenarios may lead to an irrecoverable error in a database system?
A transaction writes a data item after it is read by an uncommitted transaction  
A transaction reads a data item after it is read by an uncommitted transaction  
A transaction reads a data item after it is written by a committed transaction
 
A transaction reads a data item after it is written by an uncommitted transaction

Question 29 Explanation:
Irrecoverable error occurs when a transaction reads a data item after it is written by uncommitted transaction.
Question 30 
Question 30 Explanation:
If we want to get distinct elements then we need to perform cross product in between the relations r_{1},
r_{2}, .... r_{m}.
Question 31 
Let (S, ≤) be a partial order with two minimal elements a and b, and a maximum element c. Let P: S → {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) ⇒ P(y) for all x, y ∈ S satisfying x≤y, where ⇒ stands for logical implication. Which of the following statements CANNOT be true?
P(x) = True for all x ∈ S such that x ≠ b
 
P(x) = False for all x ∈ S such that x ≠ a and x ≠ c  
P(x) = False for all x ∈ S such that b ≤ x and x ≠ c  
P(x) = False for all x ∈ S such that a ≤ x and b ≤ x

Question 31 Explanation:
c is the maximum element.
a or b the minimal element in set.
P(a) = True for all x ∈ S such that a ≤ x and b ≤ x.
Option D is False.
a or b the minimal element in set.
P(a) = True for all x ∈ S such that a ≤ x and b ≤ x.
Option D is False.
Question 32 
Which of the following is a valid first order formula? (Here α and β are first order formulae with x as their only free variable)
((∀x)[α] ⇒ (∀x)[β]) ⇒ (∀x)[α⇒β]
 
(∀x)[α] ⇒ (∃x)[α ∧ β]  
((∀x)[α ∨ β] ⇒ (∃x)[α] ⇒ (∀x)[α]
 
(∀x)[α ⇒ β] ⇒ ((∀x)[α] ⇒ (∀x)[β])

Question 32 Explanation:
Option D is valid.
Here, α, β are holding values of x. Then and RHS saying that α holding the value of x and β is holding value of x.
Then LHS ⇒ RHS.
Here, α, β are holding values of x. Then and RHS saying that α holding the value of x and β is holding value of x.
Then LHS ⇒ RHS.
Question 33 
I_{1} satisfies α, I_{2} does not  
I_{2} satisfies α, I_{1} does not
 
Neither I_{2} nor I_{1} satisfies α
 
Both I_{1} and I_{2} satisfy α

Question 33 Explanation:
Given that:
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Q_{yy}]] ⇒(∀x)[¬Px]
Q_{yy} is always true, because y divide y, then ¬Q_{yy} is false.
∀x[(P(x) ⇔ ∀y [Qxy ⇔ False]]
∀y [Qxy ⇔ False] can be written as ∀y[¬axy]
⇒(∀x)[P(x) ⇔ ∀y[¬Qxy]]
Here, ¬Qxy says that y doesnot divides x, which is not always be true.
For example, if x=y then it is false then ∀y[¬Qxy] is not true for all values of y.
⇒(∀x)[P(x) ⇔ False]
⇒(∀x)[¬P(x) = RHS]
LHS = RHS
⇒ Irrespective of x, whether x is prime of composite number I_{1} and I_{2} satisfies α.
(∀x)[Px ⇔ (∀y)[Qxy ⇔ ¬Q_{yy}]] ⇒(∀x)[¬Px]
Q_{yy} is always true, because y divide y, then ¬Q_{yy} is false.
∀x[(P(x) ⇔ ∀y [Qxy ⇔ False]]
∀y [Qxy ⇔ False] can be written as ∀y[¬axy]
⇒(∀x)[P(x) ⇔ ∀y[¬Qxy]]
Here, ¬Qxy says that y doesnot divides x, which is not always be true.
For example, if x=y then it is false then ∀y[¬Qxy] is not true for all values of y.
⇒(∀x)[P(x) ⇔ False]
⇒(∀x)[¬P(x) = RHS]
LHS = RHS
⇒ Irrespective of x, whether x is prime of composite number I_{1} and I_{2} satisfies α.
Question 34 
m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where k is a natural number ≥1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?
Question 34 Explanation:
Since we want at least k balls in each bag, so first we put kn balls into bags, k balls in each bag. Now we are left with m  kn balls, and we have to put them into n bags such that each bag may receive 0 or more balls. So applying theorem 2 of stars and bars with m  nk stars and n bars, we get number of ways to be
. So option (B) is correct
. So option (B) is correct
Question 35 
Question 35 Explanation:
Considering floor value for square root of numbers.
Successive root number of numbers are in the series 3, 5, 7, ... like 3 numbers from 1... 4, 5 numbers 59 and so on.
Question 36 
How many perfect matching are there in a complete graph of 6 vertices?
15  
24  
30  
60 
Question 36 Explanation:
We have formula to find no. of perfect matchings in complete graphs of 2n vertices,
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
Question 37 
g(h(D)) ⊆ D
 
g(h(D)) ⊇ D
 
g(h(D)) ∩ D = ɸ
 
g(h(D)) ∩ (B—D) ≠ ɸ 
Question 37 Explanation:
f: A→B ba an injective (onetoone)
→ g: 2^{A}→2^{B} be also one to one function and g(C) = f(x)x∈C}, for all subsets C of A.
The range of this function is n(2^{A}).
→ h: 2^{B}→2^{A} it is not a one to one function and given h(D) = {xx∈A, f(x)∈D}, for all subsets D of B.
The range of this function is also n(2^{A}).
→ The function g(h(D)) also have the range n(2^{A}) that implies n(A)≤n(B), i.e., n(2^{A}) is less than n(2^{B}).
Then this result is g(h(D))⊆D.
→ g: 2^{A}→2^{B} be also one to one function and g(C) = f(x)x∈C}, for all subsets C of A.
The range of this function is n(2^{A}).
→ h: 2^{B}→2^{A} it is not a one to one function and given h(D) = {xx∈A, f(x)∈D}, for all subsets D of B.
The range of this function is also n(2^{A}).
→ The function g(h(D)) also have the range n(2^{A}) that implies n(A)≤n(B), i.e., n(2^{A}) is less than n(2^{B}).
Then this result is g(h(D))⊆D.
Question 38 
0  
1  
2  
3 
Question 38 Explanation:
Total possible values = 3^{2} = 9 i.e., (a,a), (b,b), (c,c), (a,b), (a,c), (b,a), (b,c), (c,a), (c,b)
In those (x, y) = (b,c) & (c,b) are the possible solution for the corresponding equations.
(x, y) = (b,c) ⇒ (a*b)+(a*c) ⇒ (b*b)+(c*c)
⇒ (b) + (c) ⇒ c + b
⇒ c (✔️) ⇒ c (✔️)
(x,y) = (c,b) ⇒ (a*c)+(a*b) ⇒ (b*c)+(c*b)
⇒ c+b ⇒ a+c
⇒ c (✔️) ⇒ c (✔️)
In those (x, y) = (b,c) & (c,b) are the possible solution for the corresponding equations.
(x, y) = (b,c) ⇒ (a*b)+(a*c) ⇒ (b*b)+(c*c)
⇒ (b) + (c) ⇒ c + b
⇒ c (✔️) ⇒ c (✔️)
(x,y) = (c,b) ⇒ (a*c)+(a*b) ⇒ (b*c)+(c*b)
⇒ c+b ⇒ a+c
⇒ c (✔️) ⇒ c (✔️)
Question 39 
2^{7}3^{7}5^{7}
 
2^{8}3^{8}5^{8}
 
2^{9}3^{9}5^{9}  
2^{10}5^{10}7^{10}

Question 39 Explanation:
The answers can have only three possibilities of sequences i.e., "a", "a", "a", and there is no multiplies of 7 and 9. So eliminates option A & C.
And f(S) = 2^{3} = 8
So answer is 2^{8}3^{8}5^{8}.
And f(S) = 2^{3} = 8
So answer is 2^{8}3^{8}5^{8}.
Question 40 
3  
4  
5  
6 
Question 40 Explanation:
The minimum degree of G = min_{v∈V} {degree(v)}
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  6
0 ≤ 6 (Not satisfied)
And which is inconsistent.
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  6
0 ≤ 6 (Not satisfied)
And which is inconsistent.
Question 41 
0  
1  
2  
infinitely many

Question 41 Explanation:
This is in the form AX = B
⇒ R(AB) < n [If we want infinitely many solution]
then 1+5α = 0
5α = 1
α = 1/5 There is only one value of α. System can have infinitely many solutions.
Question 42 
1.3, 0.6, and 0.6 respectively
 
0.6, 0.6, and 1.3 respectively
 
1.3, 1.3, and 0.6 respectively
 
1.3, 0.6, and 1.3 respectively 
Question 42 Explanation:
Note: Out of syllabus.
Question 43 
2^{40}
 
2^{9}
 
2^{22}  
2^{31} 
Question 43 Explanation:
Largest gap will be in between two most largest numbers.
The largest number is 1.111111111× 2^{6231} = (2−2^{−9})×2^{31}
Second largest number is 1.111111110×2^{6231} = (2−2^{8})×2^{31}
Difference = (2−2^{−9})×2^{31}  (2−2^{8})×2^{31}
= (2^{8}−2^{−9}) ×2^{31}
= 2^{−9}×2^{31}
= 2^{22}
The largest number is 1.111111111× 2^{6231} = (2−2^{−9})×2^{31}
Second largest number is 1.111111110×2^{6231} = (2−2^{8})×2^{31}
Difference = (2−2^{−9})×2^{31}  (2−2^{8})×2^{31}
= (2^{8}−2^{−9}) ×2^{31}
= 2^{−9}×2^{31}
= 2^{22}
Question 44 
5  
6  
7  
8 
Question 44 Explanation:
Let q is the initial state.
q_{0} ← Number of zeros is one more than number of ones.
q_{1} ← Number of ones is one more than number of zeros.
q_{00} ← Number of zeros is two more than number of ones.
q_{11} ← Number of ones is two more than number of zeros.
q_{0} ← Number of zeros is one more than number of ones.
q_{1} ← Number of ones is one more than number of zeros.
q_{00} ← Number of zeros is two more than number of ones.
q_{11} ← Number of ones is two more than number of zeros.
Question 45 
(11, 9)  
(9, 13)  
(9, 10)  
(11, 11) 
Question 45 Explanation:
For SOP,
⇒ w'y' + z'wx' + xyz'
Total 8 literals are there.
For POS,
⇒ (z' + w')(z' + y')(w' + x')(x + z + w)
Total 9 literals are there.
⇒ w'y' + z'wx' + xyz'
Total 8 literals are there.
For POS,
⇒ (z' + w')(z' + y')(w' + x')(x + z + w)
Total 9 literals are there.
Question 46 
A + B, and A – B, but not A + 1  
A + B, and A + 1, but not A – B  
A + B, but not A – B or A + 1  
A + B, and A – B, and A + 1

Question 46 Explanation:
The circuits performs
1) A+B when K=0 and C_{0} = 0. It is binary adder which performs addition of two binary numbers.
2) A  B = A+ B' + 1 when K=1 and C_{0} = 1 ;
Here XOR gates produce B' if K=1. Since 1⊕b= b'.
"1" in (A+B+1) is coming from C_{0}.
Note: 2's complement of B is (B'+1). 3) A+1 when B=0, K=0, C_{0}= 1.
Increments A.
1) A+B when K=0 and C_{0} = 0. It is binary adder which performs addition of two binary numbers.
2) A  B = A+ B' + 1 when K=1 and C_{0} = 1 ;
Here XOR gates produce B' if K=1. Since 1⊕b= b'.
"1" in (A+B+1) is coming from C_{0}.
Note: 2's complement of B is (B'+1). 3) A+1 when B=0, K=0, C_{0}= 1.
Increments A.
Question 47 
1  
2  
3  
4 
Question 47 Explanation:
⇒ a will always be equal to A.
Question 48 
the number of 0 bits in A_{0}
 
the number of 1 bits in A_{0}
 
A_{0}  
8 
Question 48 Explanation:
B is to be increments when a is moved to carry.
The code is counting the number of 1 bits in A_{0}
The code is counting the number of 1 bits in A_{0}
Question 49 
RRC A, #1
 
NOP ; no operation
 
LRC A, #1 ; left rotate A through carry flag by one bit  
ADD A, #1

Question 49 Explanation:
Initially, the 8 bits will be,
a_{7}, a_{6}, a_{5, a4, a3 , a2, a1, a0 Now right rotate it once, C0, a7, a6, a5, a4, a3 , a2, a1, now a0 is the new carry. Now again right rotate it, a0C0, a7, a6, a5, a4, a3 , a2 ⁞ So after 8 rotations, a6, a5, a4, a3 , a2, a1, a0C0 and carry is a7 Now, one more rotation will restore the original value of A0. Hence, answer is Option (A). }
a_{7}, a_{6}, a_{5, a4, a3 , a2, a1, a0 Now right rotate it once, C0, a7, a6, a5, a4, a3 , a2, a1, now a0 is the new carry. Now again right rotate it, a0C0, a7, a6, a5, a4, a3 , a2 ⁞ So after 8 rotations, a6, a5, a4, a3 , a2, a1, a0C0 and carry is a7 Now, one more rotation will restore the original value of A0. Hence, answer is Option (A). }
Question 50 
1  
5  
7  
8 
Question 50 Explanation:
There are possible: 7 strings
Question 51 
G is not ambiguous
 
There exist x, y ∈ L(G) such that xy ∉ L(G)
 
There is a deterministic pushdown automaton that accepts L(G)  
We can find a deterministic finite state automaton that accepts L(G)

Question 51 Explanation:
a) False
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
We can derive ϵ with more than one parse tree,
So ambiguous.
b) False
Let take x=aabb and y=ab then xy=aabbab we can produce it,
c) True
Because the language generated is no. of a's = no' of b's. So DPDA exist for this language.
d) Not possible.
Infinite memory needed to count 'a' for no. of 'b'.
Question 52 
L_{1} ∈ P and L_{2} is finite  
L_{1} ∈ NP and L_{2} ∈ P
 
L_{1} is undecidable and L_{2} is decidable
 
L_{1} is recursively enumerable and L_{2} is recursive 
Question 52 Explanation:
L_{1} is polynomial time reducible to L_{2}.
Now if L_{2} is decidable then L_{1} should also be decidable. Hence, option (c) is wrong.
Now if L_{2} is decidable then L_{1} should also be decidable. Hence, option (c) is wrong.
Question 53 
M does not halt on any string in (0+1)^{+}
 
M does not halt on any string in (00+1)*  
M halts on all strings ending in a 0
 
M halts on all strings ending in a 1

Question 53 Explanation:
Try for any string, it will not Halt for any string other than ϵ. Hence, option (A) is correct.
Question 55 
L_{1} = {0,1}*  L
 
L_{1} = {0,1}*
 
L_{1} ⊆ L  
L_{1} = L

Question 55 Explanation:
As in the question said,
As in above NFA language,
L_{1} is {0,1}*.
As in above NFA language,
L_{1} is {0,1}*.
Question 56 
{S'→e S} and {S'→ε}
 
{S'→e S} and { }  
{S'→ε} and {S'→ε}  
{S'→e S, S'→ε} and {S'→ε}

Question 56 Explanation:
First(S) = {1,a}
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.
Hence, option (D) is correct.
First(S') = {e,ε}
First(E) = {b}
Follow(S') = {e,$}
Only when 'First' contains ε, we need to consider FOLLOW for getting the parse table entry.
Hence, option (D) is correct.
Question 57 
LL(1)
 
SLR(1) but not LL(1)
 
LALR(1) but not SLR(1)
 
LR(1) but not LALR(1)

Question 57 Explanation:
Hence, it is LL(1).
Question 58 
9 + 5 + 2
 
9 5 + 2 +  
9 5 2 + +
 
+ + 9 5 2 
Question 58 Explanation:
Now traverse the tree and whatever comes first to print, just print it.
Answer will be 9 5 + 2 +.
Question 59 
X = Y + Z
 
t_{1} = Y + Z; X = t_{1}  
t_{1}= Y; t_{2} = t_{1} + Z; X = t_{2}  
t_{1} = Y; t_{2} = Z; t_{3} = t_{1} + t_{2}; X = t_{3}

Question 59 Explanation:
Question 60 
A program consists of two modules executed sequentially. Let f_{1}(t) and f_{2}(t) respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by
Question 60 Explanation:
f_{1}(t) and f_{2}(t) are executed sequentially.
→ They representing the probability density functions of time taken to execute.
→ f_{1} can be executed in 'x' time.
f_{2} can be executed in 'tx' time.
→ The probability density function =
→ They representing the probability density functions of time taken to execute.
→ f_{1} can be executed in 'x' time.
f_{2} can be executed in 'tx' time.
→ The probability density function =
Question 61 
Question 61 Explanation:
Probability of inverse (a_{i}, a_{j}(i
Probability of expected no. of inversions = (1/2) × (n(n1)/2) = n(n1)/4
Question 62 
Θ(n^{2})  
Θ(n log n)
 
Θ(n^{1.5})  
Θ(n) 
Question 62 Explanation:
Here the inputs are to be restricted to 1...n with atmost 'n' inversions. Then the worst case time complexity of inversion sort reduces to Θ(n).
Question 63 
A heap can be used but not a balanced binary search tree  
A balanced binary search tree can be used but not a heap  
Both balanced binary search tree and heap can be used  
Neither balanced binary search tree nor heap can be used 
Question 63 Explanation:
→ In heap deletion takes O(log n).
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).
Question 64 
Let S be a stack of size n ≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥1, define the stacklife of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stacklife of an element of this stack is
n(X + Y)  
3Y + 2X
 
n(X + Y)  X
 
Y + 2X 
Question 64 Explanation:
Life time of last element present in the stack = Y
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
Question 65 
None of the above 
Question 65 Explanation:
Given Tree is
Insert G at root level:
Insert G at root level:
Question 66 
The cube root of a natural number n is defined as the largest natural number m such that m^{3}≤n. The complexity of computing the cube root of n (n is represented in binary notation) is
O(n) but not O(n^{0.5})
 
O(n^{0.5} but not O((log n)^{k}) for any constant k>0
 
O((log n)^{k}) for some constant k>0, but not O((log log n)^{m}) for any constant m>0  
O((log log n)^{k}) for some constant k>0.5, but not O((log log n)^{0.5}) 
Question 66 Explanation:
Time complexity to search using binary search is O(log n). The cube root involves to serach again O(log n) times in worst case. So time taken to find cube root is O(log^{2}n) ... (I)
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) ... (II)
From (I), option A and B False
From (II), option D False.
The time complexity is never less than O(log n) because to represent a binary search will takes O(log n) ... (II)
From (I), option A and B False
From (II), option D False.
Question 67 
The number of edges in the shortest paths from v_{1} to all vertices of G  
G_{1} is connected
 
V_{1} forms a clique in G  
G_{1} is a tree

Question 67 Explanation:
Calculate the minimum weight of the graph by using single source shortest path, if the weight of the graph is 0 then G is Connected, then that is the shortest path. In case the weight of the graph is not 0 then the graph G is disconnected.
Question 69 
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “a_{s} b_{s} c_{s} a_{e} d_{s} c_{e} e_{s} f_{s} b_{e} d_{e} g_{s} e_{e} f_{e} h_{s} g_{e} h_{e}”. Here, x_{s} denotes the starting time and x_{e} denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
3  
4  
5  
6 
Question 69 Explanation:
Given order is “a_{s} b_{s} c_{s} a_{e} d_{s} c_{e} e_{s} f_{s} b_{e} d_{e} g_{s} e_{e} f_{e} h_{s} g_{e} h_{e}”
Where x_{s}→Starting time, x_{e}→ Ending time.
R_{1}→for a
R_{2}→for b
R_{3}→for c
a_{e}, R_{1} is free
R_{1}→for d
c_{e}, R_{3} is free
R_{3}→for e
R_{4}→for f
b_{e}, R_{2} is free
d_{e}, R_{1} is free
R_{1}→for g
e_{e}, R_{3} is free
f_{e}, R_{4} is free
R_{2}→for h
g_{e}, R_{1} is free
h_{e}, R_{2} is free
Here, total we used is: R_{1}, R_{2}, R_{3}, R_{4}.
Therefore, total no. of rooms we required = 4(minimum).
Where x_{s}→Starting time, x_{e}→ Ending time.
R_{1}→for a
R_{2}→for b
R_{3}→for c
a_{e}, R_{1} is free
R_{1}→for d
c_{e}, R_{3} is free
R_{3}→for e
R_{4}→for f
b_{e}, R_{2} is free
d_{e}, R_{1} is free
R_{1}→for g
e_{e}, R_{3} is free
f_{e}, R_{4} is free
R_{2}→for h
g_{e}, R_{1} is free
h_{e}, R_{2} is free
Here, total we used is: R_{1}, R_{2}, R_{3}, R_{4}.
Therefore, total no. of rooms we required = 4(minimum).
Question 70 
A[j,k] ≤ n  
If A[j,j] ≥ n  1, then G has a Hamiltonian cycle
 
If there exists a path from j to k, A[j,k] contains the longest path length from j to k  
If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges

Question 70 Explanation:
Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.
Question 71 
(∀x) [(∃y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ ¬(∃x)[B(x,x)]  
(∀x) [(∀y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ ¬(∃x)[B(x,x)]  
(∀x) [(∃y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∨ ¬(∃x)[B(x,x)]  
(∀x) [(∀y) [B(x,y) ∧ C(y)] ⇒ A(x)] ∧ (∃x)[B(x,x)] 
Question 71 Explanation:
Note: This is not in gate syllabus. Please ignore this question.
Question 72 
((P ∨ R) ∧ (Q ∨ ¬R)) ⇒ (P ∨ Q) is logically valid  
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R)) is logically valid
 
(P ∨ Q) is satisfiable if and only if (P∨R) ∧ (Q∨¬R) is satisfiable  
(P ∨ Q) ⇒ FALSE if and only if both P and Q are unsatisfiable

Question 72 Explanation:
(P ∨ Q) ⇒ ((P ∨ R) ∧ (Q ∨ ¬R))
It is may be True (or) False depending on values. So this is not valid.
It is may be True (or) False depending on values. So this is not valid.
Question 73 
115, 220  
25, 220
 
25, 15  
115, 105

Question 73 Explanation:
P(i+j)
P(100+5) = P(105)
→void P(105)
{
int i=10;
print (x+10); ⇒ 105+10=115 prints
i=200;
j = 20;
print (x); ⇒ x=105 prints
}
115, 105 prints
P(100+5) = P(105)
→void P(105)
{
int i=10;
print (x+10); ⇒ 105+10=115 prints
i=200;
j = 20;
print (x); ⇒ x=105 prints
}
115, 105 prints
Question 74 
115, 220  
25, 220
 
25, 15
 
115, 105

Question 74 Explanation:
In dynamic,
In void P(x)
{ int i = 10;
print(x + 10); ⇒ 105+10=115 prints
print (x); ⇒ print x=220;
In void P(x)
{ int i = 10;
print(x + 10); ⇒ 105+10=115 prints
print (x); ⇒ print x=220;
Question 75 
1 2 1  
2 1 1  
2 1 2
 
2 2 2 
Question 75 Explanation:
Because of using dynamic binding it results a values such as 2 2 2.
Note: The given question is not in the present syllabus
Note: The given question is not in the present syllabus
Question 76 
Which of the following is NOT an advantage of using shared, dynamically linked libraries as opposed to using statically linked libraries?
Smaller sizes of executable files
 
Lesser overall page fault rate in the system
 
Faster program startup
 
Existing programs need not be relinked to take advantage of newer versions of libraries 
Question 76 Explanation:
Dynamic link libraries takes more time in program setup (in loading and linking phase to set up the global offset table and load and link the required libraries).
Question 77 
A uniprocessor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?
First come first served scheduling
 
Shortest remaining time first scheduling
 
Static priority scheduling with different priorities for the two processes  
Round robin scheduling with a time quantum of 5 ms

Question 77 Explanation:
We have two processes P and Q. These process have 10ms CPU burst time and 90ms I/O bursts.
(i) FCFS:
010: Process 1 can execute
1020: Process 2 can execute
100110: Process 1 Terminate
110120: Process 2 Terminate
CPU utilization = 20/100 [In every 100ms it utilizes]
=20%
(ii) SRTF: can process P and Q same as FCFS
then CPU utilization = 20%
(iii) Round robin: with TQ5
05: Process P_{1}
510: Process P_{2}
1015: Process P_{1}
1520: Process P_{2}
105110: Process P_{1}
110115: Process P_{2}
CPU utilization = 20/105 = 19.5
(i) FCFS:
010: Process 1 can execute
1020: Process 2 can execute
100110: Process 1 Terminate
110120: Process 2 Terminate
CPU utilization = 20/100 [In every 100ms it utilizes]
=20%
(ii) SRTF: can process P and Q same as FCFS
then CPU utilization = 20%
(iii) Round robin: with TQ5
05: Process P_{1}
510: Process P_{2}
1015: Process P_{1}
1520: Process P_{2}
105110: Process P_{1}
110115: Process P_{2}
CPU utilization = 20/105 = 19.5
Question 78 
1.5 ns  
2 ns  
3 ns
 
4 ns 
Question 78 Explanation:
The possibilities are = (TLB Hit * Cache Hit) + (TLB Hit * Cache Miss)
(TLB Miss * Cache Hit) + (TLB Miss * Cache Miss)
= (0.96*0.9*2)+(0.96*0.1+12)
(0.04*0.9*2)+(0.04*0.1*32)
= 3.8
= 4 (approximately)
(TLB Miss * Cache Hit) + (TLB Miss * Cache Miss)
= (0.96*0.9*2)+(0.96*0.1+12)
(0.04*0.9*2)+(0.04*0.1*32)
= 3.8
= 4 (approximately)
Question 79 
8 KB  
12 KB
 
16 KB  
20 KB 
Question 79 Explanation:
Breakup of given addresses into bit form:
32bits are broken up as 10bits (L2)  10bits (L1)  12bits (offset)
First code page:
0x00000000 = 0000 0000 00  00 0000 0000  0000 0000 0000
So next code page will start from
0x00001000 = 0000 0000 00  00 0000 0001  0000 0000 0000
First data page:
0x00400000 = 0000 0000 01  00 0000 0000  0000 0000 0000
So next data page will start from
0x00401000 = 0000 0000 01  00 0000 0001  0000 0000 0000
Only one stack page:
0xFFFFF000 = 1111 1111 11  11 1111 1111  0000 0000 0000
Now, for second level page table, we will just require 1 Page
which will contain following 3 distinct entries i.e. 0000 0000 00, 0000 0000 01, 1111 1111 11.
Now, for each of these distinct entries, we will have 11 page in Level1.
Hence, we will have in total 4 pages and page size = 2^{12} = 4KB.
Therefore, Memory required to store page table = 4*4KB = 16KB.
32bits are broken up as 10bits (L2)  10bits (L1)  12bits (offset)
First code page:
0x00000000 = 0000 0000 00  00 0000 0000  0000 0000 0000
So next code page will start from
0x00001000 = 0000 0000 00  00 0000 0001  0000 0000 0000
First data page:
0x00400000 = 0000 0000 01  00 0000 0000  0000 0000 0000
So next data page will start from
0x00401000 = 0000 0000 01  00 0000 0001  0000 0000 0000
Only one stack page:
0xFFFFF000 = 1111 1111 11  11 1111 1111  0000 0000 0000
Now, for second level page table, we will just require 1 Page
which will contain following 3 distinct entries i.e. 0000 0000 00, 0000 0000 01, 1111 1111 11.
Now, for each of these distinct entries, we will have 11 page in Level1.
Hence, we will have in total 4 pages and page size = 2^{12} = 4KB.
Therefore, Memory required to store page table = 4*4KB = 16KB.
Question 80 
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
 
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
 
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1  
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S initially 1, and T initially 0

Question 80 Explanation:
Option B is correct.
Process P_{1} will be executed first and then Process P_{2} can be executed next.
At the process P: W=P(S)
X=V(T)
At the process Q: Y=P(T)
Z=V(S)
Here, S=1, T=0 then the process P executes first and then Q, and both can run on process alternate way start with P.
Process P_{1} will be executed first and then Process P_{2} can be executed next.
At the process P: W=P(S)
X=V(T)
At the process Q: Y=P(T)
Z=V(S)
Here, S=1, T=0 then the process P executes first and then Q, and both can run on process alternate way start with P.
Question 81 
P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1  
P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1  
P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1
 
V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1 
Question 81 Explanation:
Here to print the required output only one semaphore is enough, if we initialize two at a time then they will run concurrently and leads the processing error.
Question 82 
The subnet mask for a particular network is 255.255.31.0. Which of the following pairs of IP addresses could belong to this network?
172.57.88.62 and 172.56.87.233
 
10.35.28.2 and 10.35.29.4
 
191.203.31.87 and 191.234.31.88  
128.8.129.43 and 128.8.161.55 
Question 82 Explanation:
To find whether hosts belong to same network or not , we have to find their net id, if net id is same then hosts belong to same network and net id can be find by ANDing subnet mask and IP address.
128.8.129.43 (Bitwise AND) 255.255.31.0 = 128.8.1.0
128.8.161.55 (Bitwise AND) 255.255.31.0 = 128.8.1.0
128.8.129.43 (Bitwise AND) 255.255.31.0 = 128.8.1.0
128.8.161.55 (Bitwise AND) 255.255.31.0 = 128.8.1.0
Question 83 
A 2km long broadcast LAN has 10^{7} bps bandwidth and uses CSMA/CD. The signal travels along the wire at 2×10^{8} m/s. What is the minimum packet size that can be used on this network?
50 bytes
 
100 bytes
 
200 bytes
 
None of the above

Question 83 Explanation:
Minimum packet size for a CSMA/CD LAN is the frame which cover whole RTT(round trip time). i.e. T_{t}=2T_{p}
d= 2 km = 2 x 10^{3} m, v = 2 x 10^{8} m/s, B= 10^{7}
T_{p}= d / v = 2 x 10^{3} /(2 x 10^{8} ) seconds= 10^{5} seconds
Let L bits be minimum size of frame, then T_{t}=t L / B = L / 10^{7} seconds
Now, T_{t}=2T_{p}
L/10^{7} = 2 x 10^{5} = 200 bits = (200 / 8) bytes = 25 bytes
d= 2 km = 2 x 10^{3} m, v = 2 x 10^{8} m/s, B= 10^{7}
T_{p}= d / v = 2 x 10^{3} /(2 x 10^{8} ) seconds= 10^{5} seconds
Let L bits be minimum size of frame, then T_{t}=t L / B = L / 10^{7} seconds
Now, T_{t}=2T_{p}
L/10^{7} = 2 x 10^{5} = 200 bits = (200 / 8) bytes = 25 bytes
Question 84 
Host A is sending data to host B over a full duplex link. A and B are using the sliding window protocol for flow control. The send and receive window sizes are 5 packets each. Data packets (sent only from A to B) are all 1000 bytes long and the transmission time for such a packet is 50 µs Acknowledgement packets (sent only from B to A) are very small and require negligible transmission time. The propagation delay over the link is 200 µs. What is the maximum achievable throughput in this communication?
7.69 × 10^{6} bps
 
11.11 × 10^{6} bps
 
12.33 × 10^{6} bps  
15.00 × 10^{6} bps

Question 84 Explanation:
Given, T_{t}= 50 μs, T_{p} = 200 μs, L= 1000 bytes, N= 5,
Transmission rate , T_{t} = L / B.W
Therefore, B.W. = L / T_{t} = 1000 bytes/ 50 μs = 8000 bits / 50 μs=160 Mbps
Efficiency = N / 1 + 2a, where a = T_{p} / T_{t}
Efficiency = 5 * 50 / (50+400)=250/450=5/9
Maximum achievable throughput= Efficiency * B.W = (5/9)*160 Mbps = 88.88 Mbps = = 11.11 x 10^{6} bytes per second
*Actual option should be in bytes per second.
Transmission rate , T_{t} = L / B.W
Therefore, B.W. = L / T_{t} = 1000 bytes/ 50 μs = 8000 bits / 50 μs=160 Mbps
Efficiency = N / 1 + 2a, where a = T_{p} / T_{t}
Efficiency = 5 * 50 / (50+400)=250/450=5/9
Maximum achievable throughput= Efficiency * B.W = (5/9)*160 Mbps = 88.88 Mbps = = 11.11 x 10^{6} bytes per second
*Actual option should be in bytes per second.
Question 85 
in second normal form but not in third normal form  
in third normal form but not in BCNF  
in BCNF
 
in none of the above

Question 85 Explanation:
Three FD's are valid from the above set of FD's for the given relation.
Date_of_Birth → Age
Name → Roll_number
Roll_number → Name
Candidate keys for the above are:
(Date_of_Birth, Name) and (Date_of_Birth, Roll_number)
Clearly, there is a partial dependency,
Date_of_Birth → Age
So, it is only in 1NF.
Date_of_Birth → Age
Name → Roll_number
Roll_number → Name
Candidate keys for the above are:
(Date_of_Birth, Name) and (Date_of_Birth, Roll_number)
Clearly, there is a partial dependency,
Date_of_Birth → Age
So, it is only in 1NF.
Question 86 
Names of students who have got an A grade in all courses taught by Korth
 
Names of students who have got an A grade in all courses
 
Names of students who have got an A grade in at least one of the courses taught by Korth
 
in none of the above 
Question 86 Explanation:
The query results a names of students who got an A grade in at least one of the courses taught by korth.
Question 87 
The schedule is serializable as T2; T3; T1
 
The schedule is serializable as T2; T1; T3  
The schedule is serializable as T3; T2; T1
 
The schedule is not serializable

Question 87 Explanation:
Precedence graph:
Cycle formed so not serializable.
Cycle formed so not serializable.
Question 88 
{mm ≤ n, (∃i)[m=i!]}
 
{mm ≤ n, (∃i)[m=i^{2}]}
 
{mm ≤ n, m is prime}
 
{ } 
Question 88 Explanation:
Take n=4, so Two log_n=4
Now Trace the code,
for (k=3; k<=n; k++)
A[k]=0; // A[3]=0
A[4]=0
for (k=2; k<=Two log_n; k++)
for(j=k+1; j<=n; j++)
A[j] = A[j] // (j%k); // A[3] = 0 // I=1
A[4] = 0 // I=1
for (j=3; j<=n; j++)
if (!A[j]) printf("%d", j);
// if (!1) means if (0), so printf will never execute
Hence, Option (D) is the answer.
Now Trace the code,
for (k=3; k<=n; k++)
A[k]=0; // A[3]=0
A[4]=0
for (k=2; k<=Two log_n; k++)
for(j=k+1; j<=n; j++)
A[j] = A[j] // (j%k); // A[3] = 0 // I=1
A[4] = 0 // I=1
for (j=3; j<=n; j++)
if (!A[j]) printf("%d", j);
// if (!1) means if (0), so printf will never execute
Hence, Option (D) is the answer.
Question 89 
12 7 6
 
22 12 11
 
14 6 6
 
7 6 6 
Question 89 Explanation:
In main function x=5; it is global array
p(&x) it goes to P( ) function
y=5
x=5+2=7;
Q(x)
z=7
z=7+5=12(Print+z→I)
comes to P( )
*y=71=6
x=7(Print x→II)
comes to main ( ),
print x=*y=6 (print x→III)
Output: 12 7 6
p(&x) it goes to P( ) function
y=5
x=5+2=7;
Q(x)
z=7
z=7+5=12(Print+z→I)
comes to P( )
*y=71=6
x=7(Print x→II)
comes to main ( ),
print x=*y=6 (print x→III)
Output: 12 7 6
Question 90 
the list is empty or has exactly one element  
the elements in the list are sorted in nondecreasing order of data value
 
the elements in the list are sorted in nonincreasing order of data value
 
not all elements in the list have the same data value

Question 90 Explanation:
It return a value '1' when the elements in the list are presented in sorted order and nondecreasing order of data value.
There are 90 questions to complete.