ISRO2017 December
Question 1 
Suppose A is a finite set with n elements. The number of elements and the rank of the largest equivalence relation on A is
{n,1}  
{n, n}  
{n^{2}, 1}  
{1, n^{2}} 
Question 1 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)} It is false.
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}
R1={(1,2), (2,1)}
R2={(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}
R1={ }
R2={(1,1)}
R3={(1,2), (3,1)}
R4={(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 = 42 = n2
Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}
⇒ Total=4=n
Note: In question, they are clearly mentioned that Rank of an Equivalence relation is equal to the number of induced Equivalence classes. Since we have maximum number of ordered pairs(which are reflexive, symmetric and transitive ) in largest Equivalence relation, its rank is always 1.
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)} It is false.
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}
R1={(1,2), (2,1)}
R2={(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}
R1={ }
R2={(1,1)}
R3={(1,2), (3,1)}
R4={(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 = 42 = n2
Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}
⇒ Total=4=n
Note: In question, they are clearly mentioned that Rank of an Equivalence relation is equal to the number of induced Equivalence classes. Since we have maximum number of ordered pairs(which are reflexive, symmetric and transitive ) in largest Equivalence relation, its rank is always 1.
Question 2 
Consider the set of integers I. Let D denote “divides with an integer quotient” (e.g. 4D8 but 4D7). Then D is
Reflexive, not symmetric, transitive  
Not reflexive, not antisymmetric, transitive  
Reflexive, antisymmetric, transitive  
Not reflexive, not antisymmetric, not transitive 
Question 2 Explanation:
Reflexive Relation:
A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.
Example: 4 D 8, 4 D 12, 4 D16, 4 D20…….(Here, D means divide)
8 D 16, 8 D 24……….
In this example, we didn’t get 4D4. So, it is not reflexive.
AntiSymmetric Relation:
For all x ∈ I, R(x,y) and R(y,x) then x=y is antisymmetric. We can easily make a violation as R(2,2) and R(2,2) are not antisymmetric.
It is violating. So, not antisymmetric relation.
Transitive relation:
A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).
Example: 4D8, 4D12, 4D16, 4D20…….(Here, D means divide)
8D16, 8D24……….
{ 4D8, 8D16, 1D16}. So, it is satisfied.
A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.
Example: 4 D 8, 4 D 12, 4 D16, 4 D20…….(Here, D means divide)
8 D 16, 8 D 24……….
In this example, we didn’t get 4D4. So, it is not reflexive.
AntiSymmetric Relation:
For all x ∈ I, R(x,y) and R(y,x) then x=y is antisymmetric. We can easily make a violation as R(2,2) and R(2,2) are not antisymmetric.
It is violating. So, not antisymmetric relation.
Transitive relation:
A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).
Example: 4D8, 4D12, 4D16, 4D20…….(Here, D means divide)
8D16, 8D24……….
{ 4D8, 8D16, 1D16}. So, it is satisfied.
Question 3 
A bag contains 19 red balls and 19 black balls. Two balls are removed at a time repeatedly and discarded if they are of the same colour, but if they are different, black ball is discarded and red ball is returned to the bag. The probability that this process will terminate with one red ball is
1  
1/21  
0  
0.5 
Question 3 Explanation:
Given data,
Step1: Bag contains 19 Red(R) and 19 Blue(B) balls.
BB (or) RR happen we are discarded.
If we get BR (or) RB then B is discarded and R is returned.
Step2: There are some conditions that,
→ If black balls will either come with black then both black balls are discarder.
→ If it will come with red then only black balls will be discarded.
→ Suppose 2 red balls will come together means we are discarding both red balls.
Step3: As per the above constraints, total 19 Red balls it means odd number.
→ Among 19 only 18 will be discarded.
Step3: Final content of bag at second last trail will be either R,B (or) R,R,R and finally in last
trail bag will left with one red ball in both the cases.
Step1: Bag contains 19 Red(R) and 19 Blue(B) balls.
BB (or) RR happen we are discarded.
If we get BR (or) RB then B is discarded and R is returned.
Step2: There are some conditions that,
→ If black balls will either come with black then both black balls are discarder.
→ If it will come with red then only black balls will be discarded.
→ Suppose 2 red balls will come together means we are discarding both red balls.
Step3: As per the above constraints, total 19 Red balls it means odd number.
→ Among 19 only 18 will be discarded.
Step3: Final content of bag at second last trail will be either R,B (or) R,R,R and finally in last
trail bag will left with one red ball in both the cases.
Question 4 
If x = 1 and x = 2 are extreme points of f(x) = α log x + βx2 + x then
α = 6, β = 1/2  
α = 2, β = 1/2  
α = 2, β = 1/2  
α = 6, β =1/2 
Question 4 Explanation:
Given data,
Step1: x= 1 and x=2
f(x) = α log x + β x2 + x
f'(x)= α/x + 2βx + 1 = 0
Step2: for extreme points f'(x)=0
α/x + 2βx + 1=0
Step3: For x= 1 then we will get α+2β= 1 → (i)
For x= 2: then we will get α+8β= 2 → (ii)
from (i) and (ii) we can get the value of α=2 and β= 1/2
Step1: x= 1 and x=2
f(x) = α log x + β x2 + x
f'(x)= α/x + 2βx + 1 = 0
Step2: for extreme points f'(x)=0
α/x + 2βx + 1=0
Step3: For x= 1 then we will get α+2β= 1 → (i)
For x= 2: then we will get α+8β= 2 → (ii)
from (i) and (ii) we can get the value of α=2 and β= 1/2
Question 5 
Let f(x) = logx and g(x) = sin x . If A is the range of f(g(x)) and B is the range of g(f(x)) then A ∩ B is
[1, 0]  
[1, 0)  
[∞, 0]  
[∞,1] 
Question 5 Explanation:
Given data,
Step1: f(x) = logx and given range is [∞ to +∞]
g(x) = sin(x) and given range is [1,1]
Step2: Given 2 variables are A and B
A= f(g(x))
= logg(x)
= logsin(x)
So, we will get A range is [∞ ,0]
Step3: B= g(f(x))
= sin(f(x))
= sin(logx)
So, we will get B range is [1, 1]
Step4: Common in both A and B is A∩B
A∩B = [1, 0]
Key point: Ranges [ 1 ≤ sin(x) ≤ 1 and ∞ ≤ logx ≤ ∞ ]
Step1: f(x) = logx and given range is [∞ to +∞]
g(x) = sin(x) and given range is [1,1]
Step2: Given 2 variables are A and B
A= f(g(x))
= logg(x)
= logsin(x)
So, we will get A range is [∞ ,0]
Step3: B= g(f(x))
= sin(f(x))
= sin(logx)
So, we will get B range is [1, 1]
Step4: Common in both A and B is A∩B
A∩B = [1, 0]
Key point: Ranges [ 1 ≤ sin(x) ≤ 1 and ∞ ≤ logx ≤ ∞ ]
Question 6 
The proposition (P⇒Q)⋀(Q⇒P) is a
tautology  
contradiction  
contingency  
absurdity 
Question 6 Explanation:
A proposition that is neither a tautology nor a contradiction is called a contingency.
Question 7 
If T(x) denotes x is a trigonometric function, P(x) denotes x is a periodic function and C(x) denotes x is a continuous function then the statement “It is not the case that some trigonometric functions are not periodic” can be logically represented as
¬∃(x) [ T(x) ⋀ ¬P(x) ]  
¬∃(x) [ T(x) ⋁ ¬P(x) ]  
¬∃(x) [ ¬T(x) ⋀ ¬P(x) ]  
¬∃(x) [ T(x) ⋀ P(x) ] 
Question 7 Explanation:
Option A implies "It is not the case that some trigonometric functions are not periodic”.
Hence it is correct .
Option B implies "It is not the case that some are trigonometric functions or they are not periodic”.
Option C implies "It is not the case that some of not trigonometric functions are not periodic”.
Option D implies "It is not the case that some trigonometric functions are periodic”.
Hence it is correct .
Option B implies "It is not the case that some are trigonometric functions or they are not periodic”.
Option C implies "It is not the case that some of not trigonometric functions are not periodic”.
Option D implies "It is not the case that some trigonometric functions are periodic”.
Question 8 
The number of elements in the power set of { {1,2}, {2,1,1}, {2,1,1,2} } is
3  
8  
4  
2 
Question 8 Explanation:
Given data,
Step1: Total number of elements in power set of given set with ‘n’ elements = 2^{n}
Example: {1,2}
{{∅},{1},{2},{1,2}} → Total 4 possibilities.
Step2: The given set in question contains 3 elements({1,2},{2,1,1}, {2,1,1,2} }. So, number of elements in power set of given set is 2^{3} =8.
Step3: The power set is {{∅},{X}} or {{∅},{1,2}}.
Step1: Total number of elements in power set of given set with ‘n’ elements = 2^{n}
Example: {1,2}
{{∅},{1},{2},{1,2}} → Total 4 possibilities.
Step2: The given set in question contains 3 elements({1,2},{2,1,1}, {2,1,1,2} }. So, number of elements in power set of given set is 2^{3} =8.
Step3: The power set is {{∅},{X}} or {{∅},{1,2}}.
Question 9 
The function f: [0,3]→[1,29] defined by f(x) = 2x3 – 15x2 + 36x + 1 is
injective and surjective  
surjective but not injective  
injective but not surjective  
neither injective nor surjective 
Question 9 Explanation:
Question 10 
2/5  
2  
3  
5/2 
Question 10 Explanation:
Given data,
Step1: It is clearly showing that two vectors are perpendicular. If two vectors are perpendicular
we are using dot product is zero. a.b =0
Step2: Calculating dot product is “i is multiplied with i” and “j is multiplied with coefficient of j”
Step3: we can write like this,
= (2i+λj+k).(i2j+3k)=0
= 22λ+3 =0
2λ = 5
λ=5/2
Step1: It is clearly showing that two vectors are perpendicular. If two vectors are perpendicular
we are using dot product is zero. a.b =0
Step2: Calculating dot product is “i is multiplied with i” and “j is multiplied with coefficient of j”
Step3: we can write like this,
= (2i+λj+k).(i2j+3k)=0
= 22λ+3 =0
2λ = 5
λ=5/2
Question 11 
Consider the schema
Sailors(sid, sname, rating, age) with the following data
For the query
SELECT S.rating, AVG(S.age) AS average FROM Sailors S
Where S.age >= 18
GROUP BY S.rating
HAVING 1 < (SELECT COUNT(*) FROM Sailors S2 where S.rating = S2.rating)
The number of rows returned is
Sailors(sid, sname, rating, age) with the following data
For the query
SELECT S.rating, AVG(S.age) AS average FROM Sailors S
Where S.age >= 18
GROUP BY S.rating
HAVING 1 < (SELECT COUNT(*) FROM Sailors S2 where S.rating = S2.rating)
The number of rows returned is
6  
5  
4  
3 
Question 11 Explanation:
Question 12 
Consider a table that describes the customers :
Customers(custid, name, gender, rating)
The rating value is an integer in the range 1 to 5 and only two values (male and female) are recorded for gender. Consider the query “how many male customers have a rating of 5”? The best indexing mechanism appropriate for the query is
Linear hashing  
Extendible hashing  
B+ Tree  
Bitmapped hashing 
Question 12 Explanation:
→ A bitmap index is a special kind of database index that uses bitmaps.
→ Bitmap indexes have traditionally been considered to work well for lowcardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data.
→ The extreme case of low cardinality is Boolean data (e.g., does a resident in a city have internet access?), which has two values, True and False.
→ Bitmap indexes use bit arrays (commonly called bitmaps) and Solution queries by performing bitwise logical operations on these bitmaps. Bitmap indexes have a significant space and performance advantage over other structures for query of such data.
→ Their drawback is they are less efficient than the traditional Btree indexes for columns whose data is frequently updated: consequently, they are more often employed in readonly systems that are specialized for fast query  e.g., data warehouses, and generally unsuitable for online transaction processing applications.
→ Bitmap indexes have traditionally been considered to work well for lowcardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data.
→ The extreme case of low cardinality is Boolean data (e.g., does a resident in a city have internet access?), which has two values, True and False.
→ Bitmap indexes use bit arrays (commonly called bitmaps) and Solution queries by performing bitwise logical operations on these bitmaps. Bitmap indexes have a significant space and performance advantage over other structures for query of such data.
→ Their drawback is they are less efficient than the traditional Btree indexes for columns whose data is frequently updated: consequently, they are more often employed in readonly systems that are specialized for fast query  e.g., data warehouses, and generally unsuitable for online transaction processing applications.
Question 13 
Type 4 JDBC driver is a driver
which is written in C++  
which requires an intermediate layer  
which communicates through Java sockets  
which translates JDBC function calls into API not native to DBMS 
Question 13 Explanation:
The JDBC type 4 driver, also known as the Direct to Database Pure Java Driver, is a database driver implementation that converts JDBC calls directly into a vendorspecific database protocol.
Written completely in Java, type 4 drivers are thus platform independent. They install inside the Java Virtual Machine of the client. This provides better performance than the type 1 and type 2 drivers as it does not have the overhead of conversion of calls into ODBC or database API calls. Unlike the type 3 drivers, it does not need associated software to work.
As the database protocol is vendor specific, the JDBC client requires separate drivers, usually vendor supplied, to connect to different types of databases.
Advantages Completely implemented in Java to achieve platform independence.
These drivers don't translate the requests into an intermediary format (such as ODBC).
The client application connects directly to the database server. No translation or middleware layers are used, improving performance.
The JVM can manage all aspects of the applicationtodatabase connection; this can facilitate debugging.
Disadvantages Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.
Type1 driver (or) JDBCODBC bridge driver
Type2 driver (or) NativeAPI driver
Type3 driver (or) Network Protocol driver
Type4 driver (or) Thin driver
Written completely in Java, type 4 drivers are thus platform independent. They install inside the Java Virtual Machine of the client. This provides better performance than the type 1 and type 2 drivers as it does not have the overhead of conversion of calls into ODBC or database API calls. Unlike the type 3 drivers, it does not need associated software to work.
As the database protocol is vendor specific, the JDBC client requires separate drivers, usually vendor supplied, to connect to different types of databases.
Advantages Completely implemented in Java to achieve platform independence.
These drivers don't translate the requests into an intermediary format (such as ODBC).
The client application connects directly to the database server. No translation or middleware layers are used, improving performance.
The JVM can manage all aspects of the applicationtodatabase connection; this can facilitate debugging.
Disadvantages Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.
Type1 driver (or) JDBCODBC bridge driver
Type2 driver (or) NativeAPI driver
Type3 driver (or) Network Protocol driver
Type4 driver (or) Thin driver
Question 14 
Consider the recurrence equation
T(n) = 2T(n1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
T(n) = 2T(n1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
O(n)  
O(2  
O(1)  
O(log n) 
Question 14 Explanation:
Question 15 
The complexity of the program is
O(log n)  
O(n^{2})  
O(n^{2} log n)  
O(n log n) 
Question 15 Explanation:
Question 16 
Match the following and choose the correct Solution for the order A, B, C, D
r, s, p, q  
r, p, s, q  
q, s, p, r  
s, p, q, r 
Question 16 Explanation:
Strassen matrix multiplication→ Divide and conquer
Insertion sort→ Decrease and Conquer
Gaussian Elimination→ Transform and Conquer
Floyd Shortest path algorithm→ Dynamic programming
Insertion sort→ Decrease and Conquer
Gaussian Elimination→ Transform and Conquer
Floyd Shortest path algorithm→ Dynamic programming
Question 17 
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
Set of strings with 2 a’s and 2 b’s  
Set of strings with 2 a’s 2 b’s followed by b  
Set of strings with 2 a’s followed by b’s which is a multiple of 3  
Set of strings with even number of a’s followed by odd number of b’s 
Question 17 Explanation:
→ Given expression denotes language that accepts set of all strings with even number of a’s followed by the odd number of b’s.
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.
Question 18 
Consider the grammar with productions
S → aSb  SS  ϵ
This grammar is
not contextfree, not linear  
not contextfree, linear  
contextfree, not linear  
contextfree, linear 
Question 18 Explanation:
Linear grammar means regular grammar which is in the form of A→ Ba  b (or) A→ aBb
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of nonterminals
It is clearly seen that given grammar is not linear but contextfree.
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of nonterminals
It is clearly seen that given grammar is not linear but contextfree.
Question 19 
Identify the language generated by the following grammar
S > AB
A > aAbϵ
B > bB b
S > AB
A > aAbϵ
B > bB b
{a^{m}b^{n}  n>=m, m>0}  
{a^{m}b^{n}  n>=m, m>=0}  
{a^{m}b^{n}  n>m, m>0}  
{a^{m}b^{n}  n>m, m>=0} 
Question 19 Explanation:
The language generated by given grammar is  L={b,bb,abb,abbb,ababb}
Hence it is a^{m}b^{n}  n>m, m>=0
Hence it is a^{m}b^{n}  n>m, m>=0
Question 20 
Let L_{1} be regular language, L_{2} be a deterministic context free language and L_{3} a recursively enumerable language, but not recursive. Which one of the following statements is false?
L_{1} ∩ L_{2} is contextfree  
L_{3} ∩ L_{1} is recursive  
L_{1} ∪ L_{2} is contextfree  
L_{1} ∩ L_{2} ∩ L_{3} is recursively enumerable 
Question 20 Explanation:
→ Option A is true, as by closure property (R is a regular language and L is any language)
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
→ Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.
→ Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
→ Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
L ∩ R = L ( i.e. L Intersection R is same type as L )
So L_{1} ∩ L_{2} is a deterministic CFL.
→ Option B is false, as L_{3} is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.
→ Option C is true, as by closure property (R is a regular language and L is any language)
L U R = L ( i.e. L UNION R is same type as L )
So, L_{1} ∪ L_{2} is deterministic context free, hence it is also context free.
→ Option D is true, as L_{1} ∩ L_{2} is DCFL and DCFL ∩ L_{3} is equivalent to DCFL ∩ Recursive enumerable.
As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.
Question 21 
Let L = {a^{p} p is a prime}.
Then which of the following is true?
Then which of the following is true?
It is not accepted by a Turing Machine  
It is regular but not contextfree  
It is contextfree but not regular  
It is neither regular nor contextfree but accepted by a Turing Machine 
Question 21 Explanation:
L = {a^{p}  p is a prime}
L can only be accepted by a Turing machine
L can only be accepted by a Turing machine
There are 21 questions to complete.
ISRO DEC 2017 22 Soon
Question 1 
Which of the following are context free?
A = {a^{n}b^{n}a^{m}b^{m } m, n>=0}
B = {a^{n}b^{n}a^{m}b^{n}  m, n>=0}
C = {a^{m}b^{n}  m≠2n,m, n>=0}
A = {a^{n}b^{n}a^{m}b^{m } m, n>=0}
B = {a^{n}b^{n}a^{m}b^{n}  m, n>=0}
C = {a^{m}b^{n}  m≠2n,m, n>=0}
A and B only  
A and C only  
B and C only  
C only 
Question 1 Explanation:
StatementA: When 'a' will comes as input. We will push it on the top of stack and when 'b' will comes as input after 'a' we will pop one 'a' for each 'b'.
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
StatementB: When last 'b' i.e., b^{n} after a^{m} comes as input then top of the stack will contain a^{m}
So we can't compare a^{n} with a^{n}b^{n}. Hence it is not CFL
StatementC: It is a CFL
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
StatementB: When last 'b' i.e., b^{n} after a^{m} comes as input then top of the stack will contain a^{m}
So we can't compare a^{n} with a^{n}b^{n}. Hence it is not CFL
StatementC: It is a CFL
Question 2 
Let S be an NPcomplete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
R is NPcomplete  
R is NPhard  
Q is NPcomplete  
Q is NPhard 
Question 2 Explanation:
NPHard if it can be solved in polynomial time then all NPComplete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.
Question 3 
The number of structurally different possible binary trees with 4 nodes is
14  
12  
336  
168 
Question 3 Explanation:
Finding number of binary tree, we are using catalan numbers formula
Here, n=4.
Total number of binary trees are 14.
Here, n=4.
Total number of binary trees are 14.
Question 4 
Using public key cryptography, X adds a digital signature σ to a message M, encrypts (M,σ) and sends it to Y, where it is decrypted. Which one of the following sequence of keys is used for operations?
Encryption : X’s private key followed by Y’s private key. Decryption : X’s public key followed by Y’s public key.  
Encryption : X’s private key followed by Y’s public key; Decryption : X’s public key followed by Y’s private key  
Encryption : X’s private key followed by Y’s public key; Decryption : Y’s private key followed by X’s public key.  
Encryption : X’s public key followed by Y’s private key; Decryption : Y’s public key followed by X’s private key. 
Question 4 Explanation:
Encryption: Source has to encrypt with its private key for forming Digital signature for Authentication. Source has to encrypt the (M, σ) with Y’s public key to send it confidentially. Decryption: Destination Y has to decrypt first with its private key, then decrypt using source public key.
Question 5 
Which of the following are used to generate a message digest by the network security protocols?
(P) SHA256
(Q) AES
(R) DES
(S) MD5
(P) SHA256
(Q) AES
(R) DES
(S) MD5
P and S only  
P and Q only  
R and S only  
P and R only 
Question 5 Explanation:
To generate a message digest by the network security protocols we need SHA and MD5.
→ SHA256 and SHA512 are novel hash functions computed with 32bit and 64bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds.
→ The MD5 messagedigest algorithm is a widely used hash function producing a 128bit hash value. Although MD5 was initially designed to be used as a cryptographic hash function, it has been found to suffer from extensive vulnerabilities. It can still be used as a checksum to verify data integrity, but only against unintentional corruption. It remains suitable for other noncryptographic purposes, for example for determining the partition for a particular key in a partitioned database.
→ SHA256 and SHA512 are novel hash functions computed with 32bit and 64bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds.
→ The MD5 messagedigest algorithm is a widely used hash function producing a 128bit hash value. Although MD5 was initially designed to be used as a cryptographic hash function, it has been found to suffer from extensive vulnerabilities. It can still be used as a checksum to verify data integrity, but only against unintentional corruption. It remains suitable for other noncryptographic purposes, for example for determining the partition for a particular key in a partitioned database.
Question 6 
In the IPv4 addressing format, the number of networks allowed under Class C addresses is
2^{20}  
2^{24}  
2^{14}  
2^{21} 
Question 6 Explanation:
→ IP address belonging to class C are assigned to smallsized networks.
The network ID is 24 bits long.
The host ID is 8 bits long.
→ The higher order bits of the first octet of IP addresses of class C are always set to 110. The remaining 21 bits are used to determine network ID.
→ The 8 bits of host ID is used to determine the host in any network. The default subnet mask for class C is 255.255.255.x. Class C has a total of:
2^{21} = 2097152 network address
2^{8} – 2 = 254 host address
IP addresses belonging to class C ranges from 192.0.0.x – 223.255.255.x.
The network ID is 24 bits long.
The host ID is 8 bits long.
→ The higher order bits of the first octet of IP addresses of class C are always set to 110. The remaining 21 bits are used to determine network ID.
→ The 8 bits of host ID is used to determine the host in any network. The default subnet mask for class C is 255.255.255.x. Class C has a total of:
2^{21} = 2097152 network address
2^{8} – 2 = 254 host address
IP addresses belonging to class C ranges from 192.0.0.x – 223.255.255.x.
Question 7 
An Internet Service Provider (ISP) has the following chunk of CIDRbased IP addresses available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to Organization A, and a quarter to Organization B, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to A and B?
245.248.136.0/21 and 245.248.128.0/22  
245.248.128.0/21 and 245.248.128.0/22  
245.248.132.0/22 and 245.248.132.0/21  
245.248.136.0/24 and 245.248.132.0/21 
Question 7 Explanation:
Question 8 
Assume that Source S and Destination D are connected through an intermediate router R. How many times a packet has to visit the network layer and data link layer during a transmission from S to D?
Network layer – 4 times, Data link layer – 4 times  
Network layer – 4 times, Data link layer – 6 times  
Network layer – 2 times, Data link layer – 4 times  
Network layer – 3 times, Data link layer – 4 times 
Question 8 Explanation:
Source and destination are hosts. The hosts have all layers but routers have only 3 layers
i.e physical,data link and network layer. The purpose of routers is to just pass on the packet between hosts or networks.
Therefore ,
Therefore ,
Question 9 
Generally TCP is reliable and UDP is not reliable. DNS which has to be reliable uses UDP because
UDP is slower  
DNS servers has to keep connections  
DNS requests are generally very small and fit well within UDP segments  
None of these 
Question 9 Explanation:
→ UDP is cheap.
→ UDP itself is not reliable, but higher level protocols  as DNS  may maintain reliability, e.g. by repeating the UDP datagram in the case of no response.
→ But the last is not the case for DNS. DNS itself uses sometimes besides UDP (as its primary protocol) the reliable Transmission Control Protocol (TCP).
→ The last is used when the response data size exceeds 512 bytes, and for tasks which require the reliable delivery (e.g. zone transfers).
→ UDP is much faster. TCP is slow as it requires 3 way handshake. The load on DNS servers is also an important factor. DNS servers (since they use UDP) don’t have keep connections.
→ DNS requests are generally very small and fit well within UDP segments.
→ UDP is not reliable, but reliability can added on application layer. An application can use UDP and can be reliable by using timeout and resend at application layer.
→ UDP itself is not reliable, but higher level protocols  as DNS  may maintain reliability, e.g. by repeating the UDP datagram in the case of no response.
→ But the last is not the case for DNS. DNS itself uses sometimes besides UDP (as its primary protocol) the reliable Transmission Control Protocol (TCP).
→ The last is used when the response data size exceeds 512 bytes, and for tasks which require the reliable delivery (e.g. zone transfers).
→ UDP is much faster. TCP is slow as it requires 3 way handshake. The load on DNS servers is also an important factor. DNS servers (since they use UDP) don’t have keep connections.
→ DNS requests are generally very small and fit well within UDP segments.
→ UDP is not reliable, but reliability can added on application layer. An application can use UDP and can be reliable by using timeout and resend at application layer.
Question 10 
Consider the set of activities related to email
A : Send an email from a mail client to mail server
B : Download email headers from mail box and retrieve mails from server to a cache
C : Checking email through a web browser
The application level protocol used for each activity in the same sequence is
A : Send an email from a mail client to mail server
B : Download email headers from mail box and retrieve mails from server to a cache
C : Checking email through a web browser
The application level protocol used for each activity in the same sequence is
SMTP, HTTPS, IMAP  
SMTP, POP, IMAP  
SMTP, IMAP, HTTPS  
SMTP, IMAP, POP  
None of the above 
Question 10 Explanation:
→ SMTP is used for connecting to outbound servers to send email while POP3 and IMAP are used to connect to incoming servers to retrieve messages.
→ POP download email headers from mailbox and retrieve mails from servers to a cache.
→ HTTPS checking email through a web browser.
→ POP download email headers from mailbox and retrieve mails from servers to a cache.
→ HTTPS checking email through a web browser.
Question 11 
Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip time delay between A and B is 40 ms and the bottleneck bandwidth on the path A and B is 64 kbps. What is the optimal window size that A should use?
5  
10  
40  
80 
Question 11 Explanation:
Given data,
 Round trip delay between A and B = 40ms
 Station A using frame size = 32 bytes. 32 bytes=32*8 bits
 Bottleneck bandwidth on the path A and B = 64kbps
 Window size=?
Step1: First we have to find transmission time
Transmission time= Frame size/bandwidth
= 32*8/(64) ms
= 4 ms
Step2: We have to find window size.
Standard Utilization formula is = n/(1+2a)
where ‘a’ is Propagation time / transmission time
= n/(1+2a)
= n/(1+40/4)
= n/11
Maximum utilization is ‘n’ = 11
 Round trip delay between A and B = 40ms
 Station A using frame size = 32 bytes. 32 bytes=32*8 bits
 Bottleneck bandwidth on the path A and B = 64kbps
 Window size=?
Step1: First we have to find transmission time
Transmission time= Frame size/bandwidth
= 32*8/(64) ms
= 4 ms
Step2: We have to find window size.
Standard Utilization formula is = n/(1+2a)
where ‘a’ is Propagation time / transmission time
= n/(1+2a)
= n/(1+40/4)
= n/11
Maximum utilization is ‘n’ = 11
Question 12 
A two way set associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The physical address space is 4 GB. The number of bits in the TAG, SET fields are
20, 7  
19, 8  
20, 8  
21, 9 
Question 12 Explanation:
2way set associative it means 2 cache lines in one set
Physical Address =4GB
Cache Size =16KB
Block Size = 8 words = 8* 32 bits = 256 bits = 32 Bytes  because 1 word =32 bits
No.of cache lines /blocks = 16KB/ 32 B = 2^14/ 2^5= 2^9 i.e 512 lines
No of sets = No of cache lines / 2  because it is 2way setassociative cache
= 2^9 /2 = 2^8 sets => 8 set bits
Now, because it is setassociative cache memory physical address generated by CPU is divided into 3 parts  first part indicate number of tag bits.
Second part indicates no of bits required to address each set.
Third part indicates  no. of bits for block offset.
Let suppose tag bits = X
Therefore , we get
X+8+5 = 32 => X= 19 are the tag bits
Physical Address =4GB
Cache Size =16KB
Block Size = 8 words = 8* 32 bits = 256 bits = 32 Bytes  because 1 word =32 bits
No.of cache lines /blocks = 16KB/ 32 B = 2^14/ 2^5= 2^9 i.e 512 lines
No of sets = No of cache lines / 2  because it is 2way setassociative cache
= 2^9 /2 = 2^8 sets => 8 set bits
Now, because it is setassociative cache memory physical address generated by CPU is divided into 3 parts  first part indicate number of tag bits.
Second part indicates no of bits required to address each set.
Third part indicates  no. of bits for block offset.
Let suppose tag bits = X
Therefore , we get
X+8+5 = 32 => X= 19 are the tag bits
Question 13 
A CPU has a 32 KB direct mapped cache with 128 byte block size. Suppose A is a 2 dimensional array of size 512×512 with elements that occupy 8 bytes each. Consider the code segment
for (i =0; i < 512; i++)
{
for (j =0; j < 512; j++)
{
x += A[i][j];
}
}
Assuming that array is stored in order A[0][0], A[0][1], A[0][2]……, the number of cache misses is
for (i =0; i < 512; i++)
{
for (j =0; j < 512; j++)
{
x += A[i][j];
}
}
Assuming that array is stored in order A[0][0], A[0][1], A[0][2]……, the number of cache misses is
16384  
512  
2048  
1024 
Question 13 Explanation:
→ Access A in row major order.
→ No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
→ No. of array elements in each block = Block size / Element size = 128B / 8B =16
→ Total misses for (P1)=Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256=16384
→ No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
→ No. of array elements in each block = Block size / Element size = 128B / 8B =16
→ Total misses for (P1)=Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256=16384
Question 14 
A computer with 32 bit word size uses 2s complement to represent numbers. The range of integers that can be represented by this computer is
–2^{32} to 2^{32}  
–2^{31} to 2^{32}1  
–2^{31} to 2^{31}1  
–2^{31}1 to 2^{32}1 
Question 14 Explanation:
Range of ‘n’ bit 2’s complement binary number is always –2^{(n1)} to 2^{(n1)}1.
Question 15 
Let M = 11111010 and N = 00001010 be two 8 bit two’s complement number. Their product in two’s complement is
11000100  
10011100  
10100101  
11010101 
Question 15 Explanation:
A = 1111 1010 = 6_{10} [2's complement number]
B = 0000 1010 = 10_{10} [2's complement number]
A×B = 6×10 =  60_{10}
⇒ 60_{10} = 10111100_{2}
= 11000011_{2} (1's complement)
= 11000100_{2} (2's complement)
B = 0000 1010 = 10_{10} [2's complement number]
A×B = 6×10 =  60_{10}
⇒ 60_{10} = 10111100_{2}
= 11000011_{2} (1's complement)
= 11000100_{2} (2's complement)
Question 16 
For a pipelines CPU with a single ALU, consider the following:
 The j + 1st instruction uses the result of jth instruction as an operand
 Conditional jump instruction
 jth and j + 1st instructions require ALU at the same time
A and B only  
B and C only  
B only  
A , B and C 
Question 16 Explanation:
A is belongs to the Data hazard.
B is belongs to the Control hazard.
C is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
B is belongs to the Control hazard.
C is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
Question 17 
In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?
Smaller block size incurs lower cache miss penalty  
Smaller block size implies better spatial locality  
Smaller block size implies smaller cache tag  
Smaller block size implies lower cache hit time 
Question 17 Explanation:
When a cache block size is smaller, it could accommodate more number of blocks, it improves the hit ratio for cache, so the miss penalty for cache will be lowered.
Question 18 
Consider an instruction of the type LW R1, 20(R2) which during execution reads a 32 bit word from memory and stores it in a 32 bit register R1. The effective address of the memory location is obtained by adding a constant 20 and contents of R2. Which of the following best reflects the addressing mode implemented by this instruction for operand in memory?
Immediate addressing
 
Register addressing  
Register Indirect addressing  
Indexed addressing 
Question 18 Explanation:
Here 20 will act as base and content of R2 will be index.
→ Addresses have two parts: the number of an index register and a constant. The address of the operand is the sum of the constant and the contents of the index register. It contains indexed (direct) addressing, indexed immediate addressing and indexed indirect addressing.
→ Addresses have two parts: the number of an index register and a constant. The address of the operand is the sum of the constant and the contents of the index register. It contains indexed (direct) addressing, indexed immediate addressing and indexed indirect addressing.
Question 19 
A sorting technique is called stable if
If it takes O(n log n) time  
It uses divide and conquer technique  
Relative order of occurrence of nondistinct elements is maintained  
It takes O(n) space 
Question 19 Explanation:
→ Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values).
→ That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
→ That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
Question 20 
Match the following and choose the correct Solution in the order A, B, C
(Bounds given may or may not be asymptotically tight)
q, r, p  
p, q, r  
q, p, r  
r, q, p 
Question 20 Explanation:
Heap Construction → O(n)
Hash table construction→ O(n^{2})
AVL tree construction → O(logn)
Hash table construction→ O(n^{2})
AVL tree construction → O(logn)
Question 21 
In a compact one dimensional array representation for lower triangular matrix (all elements above diagonal are zero) of size n x n, non zero elements of each row are stored one after another, starting from first row, the index of (i, j)th element in this new representation is
i+j  
j+i(i1)/2
 
i+j1  
i+j(j1)/2 
Question 21 Explanation:
Though not mentioned in question, from options it is clear that array index starts from 1 and not 0. If we assume array index starting from 1 then, i^{th} row contains i number of nonzero elements. Before i^{th} row there are (i1) rows, (1 to i1) and in total these rows has 1+2+3......+(i1) = i(i1)/2 elements.
Now at i^{th} row, the j^{th} element will be at j position.
So the index of (i, j)^{th} element of lower triangular matrix in this new representation is
j = i(i1)/2
Now at i^{th} row, the j^{th} element will be at j position.
So the index of (i, j)^{th} element of lower triangular matrix in this new representation is
j = i(i1)/2
Question 22 
Which of the following permutation can be obtained in the same order using a stack assuming that input is the sequence 5, 6, 7, 8, 9 in that order?
7, 8, 9, 5, 6  
5, 9, 6, 7, 8  
7, 8, 9, 6, 5  
9, 8, 7, 5, 6 
Question 22 Explanation:
Push 5 Push 6 Push 7 Pop 7 Push 8 Pop 8 Push 9 Pop 9 Pop 6 Pop 5.
→ Remaining options are not possible.
→ Remaining options are not possible.
Question 23 
Quick sort is run on 2 inputs shown below to sort in ascending order
A. 1, 2, 3……n
B. n, n1, n2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
A. 1, 2, 3……n
B. n, n1, n2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
C1>C2  
C1=C2  
C1  
Cannot say anything for arbitrary n 
Question 23 Explanation:
→ The above question is clearly specifying quicksort worst case complexity.
→ Elements are already sorted order it gives worst case complexity O(n^{2})
→ If all elements are having same weight, it performs worst case complexity.
→ Elements are already sorted order it gives worst case complexity O(n^{2})
→ If all elements are having same weight, it performs worst case complexity.
Question 24 
A binary search tree is used to locate the number 43. Which one of the following probe sequence is not possible?
61, 52, 14, 17, 40, 43  
10, 65, 31, 48, 37, 43  
81, 61, 52, 14, 41, 43  
17, 77, 27, 66, 18, 43 
Question 24 Explanation:
Question 25 
The characters of the string K R P C S N Y T J M are inserted into a hash table of size 10 using hash function
h(x) = ((ord(x)  ord(A) + 1)) mod 10
If linear probing is used to resolve collisions, then the following insertion causes collision
h(x) = ((ord(x)  ord(A) + 1)) mod 10
If linear probing is used to resolve collisions, then the following insertion causes collision
Y  
C  
M  
P

Question 25 Explanation:
Given information,
Hash table size=10 and index starts from 0 to 9.
String=K R P C S N Y T J M
hash function = h(x) = ((ord(x) – ord(A) + 1)) mod 10
Hash table size=10 and index starts from 0 to 9.
String=K R P C S N Y T J M
hash function = h(x) = ((ord(x) – ord(A) + 1)) mod 10
Question 26 
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 reversal ordering on natural numbers i.e. 9 is assumed to be smallest and 0 is assumed to be largest. The inorder traversal of the resultant binary search tree is
9, 8, 6, 4, 2, 3, 0, 1, 5, 7  
0, 1, 2, 3, 4, 5, 6, 7, 8, 9  
0, 2, 4, 3, 1, 6, 5, 9, 8, 7  
9, 8, 7, 6, 5, 4, 3, 2, 1, 0 
Question 26 Explanation:
In order: 0 1 2 3 4 5 6 7 8 9
Question 27 
A priority queue is implemented as a Maxheap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements ‘1’ and ‘7’ are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is
10, 8, 7, 5, 3, 2, 1  
10, 8, 7, 2, 3, 1, 5  
10, 8, 7, 1, 2, 3, 5  
10, 8, 7, 3, 2, 1, 5 
Question 27 Explanation:
MaxHeap has 5 elements:
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 28 
The minimum number of stacks needed to implement a queue is
3  
1  
2  
4 
Question 28 Explanation:
Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.
Question 29 
A strictly binary tree with 10 leaves
cannot have more than 19 nodes  
has exactly 19 nodes  
has exactly 17 nodes  
has exactly 20 nodes 
Question 29 Explanation:
→ If every nonleaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.
→ A strictly binary tree with N leaves always contains 2N – 1 nodes.
(2*10)1 =19
→ A strictly binary tree with N leaves always contains 2N – 1 nodes.
(2*10)1 =19
Question 30 
What is the maximum height of any AVL tree with 7 nodes? Assume that height of tree with single node is 0.
2  
3  
4  
5 
Question 30 Explanation:
The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2^{h}1=7
h=3
2^{h}1=7
h=3
Question 31 
Which one of the following property is correct for a redblack tree?
Every simple path from a node to a descendant leaf contains the same number of black nodes  
If a node is red, then one children is red and another is black  
If a node is red, then both its children are red  
Every leaf node (sentinel node) is red 
Question 31 Explanation:
→ It could be from a binary search tree. The redblack tree tracks every simple path from a node to a descendant leaf that has the same number of black nodes.
→ A red black tree is a kind of selfbalancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node.
→ These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
→ Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case.
→ When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
→ The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
→ A red black tree is a kind of selfbalancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node.
→ These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
→ Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case.
→ When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
→ The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
Question 32 
The in order and pre order traversal of a binary tree are
d b e a f c g
and
a b d e c f g
respectively. The post order traversal of a binary tree is
d b e a f c g
and
a b d e c f g
respectively. The post order traversal of a binary tree is
e d b g f c a  
e d b f g c a  
d e b f g c a  
d e f g b c a 
Question 32 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 33 
A virtual memory system uses FIFO page replacement policy and allocates a fixed number of frames to the process. Consider the following statements
M : Increasing the number of page frames allocated to a process sometimes increases the page fault rate
N : Some programs do not exhibit locality of reference
Which one of the following is true?
M : Increasing the number of page frames allocated to a process sometimes increases the page fault rate
N : Some programs do not exhibit locality of reference
Which one of the following is true?
Both M and N are true and N is the reason for M  
Both M and N are true and N is not the reason for M  
Both M and N are false  
M is false, but N is true 
Question 33 Explanation:
→ FIFO suffers from Belady Anomaly.
→ Belady Anomaly states that when number of page frames. Increases then increase the page fault rate.
M 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.
N 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.
M 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.
N is also True:
→ Q is not the reason for P, because Belady Anomaly not depends on the locality of reference.
Question 34 
Consider three CPU intensive processes, which require 10, 20, 30 units and arrive at times 0, 2, 6 respectively. How many context switches are needed if shortest remaining time first is implemented? Context switch at 0 is included but context switch at end is ignored
1  
2  
3  
4 
Question 34 Explanation:
Total no.of context switches is 2.
Question 35 
A process executes the following code
for (i = 0; i < n; i++) fork( );
The total number of child processes created are
n^{2}  
2^{n+1} 1  
2^{n}  
2^{n} 1 
Question 35 Explanation:
Fork is a system call, implements in kernel.
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
Question 36 
Consider the following scheduling
Matching the table in the order A, B, C gives
Matching the table in the order A, B, C gives
t, u, s  
s, t, u  
u, s, t  
u, t, s 
Question 36 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 37 
A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 50 distinct pages in some order and then accesses the same 50 pages in reverse order. How many page faults will occur?
96  
100  
97  
92 
Question 37 Explanation:
The first 100 accesses causes 100 page faults.
Page 1 …….. Page 100 causes 100 faults.
Now, when they are accesses in reverse order page 100, 99, 98, 97 are already present. So we get 96 page faults. So, total of 196 page faults.
Page 1 …….. Page 100 causes 100 faults.
Now, when they are accesses in reverse order page 100, 99, 98, 97 are already present. So we get 96 page faults. So, total of 196 page faults.
Question 38 
Which of the following is false?
User level threads are not scheduled by the kernel  
Context switching between user level threads is faster than context switching between kernel level threads  
When a user thread is blocked all other threads of its processes are blocked  
Kernel level threads cannot utilize multiprocessor systems by splitting threads on different processors or cores 
Question 38 Explanation:
All are true except “Kernel level threads shares the code segment.”
Question 39 
Which one of the following are essential features of object oriented language?
 Abstraction and encapsulation
 Strictlytyped
 Typesafe property coupled with subtype rule
 Polymorphism in the presence of inheritance
A and B only  
A, D and B only  
A and D only  
A, C and D only 
Question 39 Explanation:
Question 40 
Which languages necessarily need heap allocation in the run time environment?
Those that support recursion  
Those that use dynamic scoping  
Those that use global variables  
Those that allow dynamic data structures 
Question 40 Explanation:
→ Dynamic memory is allocated on the heap by the system.
→ So the languages which allow dynamic data structure require heap allocation at runtime.
→ So the languages which allow dynamic data structure require heap allocation at runtime.
Question 41 
Consider the code segment
int i, j, x, y, m, n;
n=20;
for (i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i % 2)
{
x + = ((4*j) + 5*i);
y += (7 + 4*j);
}
}
m = x + y;
Which one of the following is false
int i, j, x, y, m, n;
n=20;
for (i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i % 2)
{
x + = ((4*j) + 5*i);
y += (7 + 4*j);
}
}
m = x + y;
Which one of the following is false
The code contains loop invariant computation  
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code  
There is scope of dead code elimination in this code 
Question 41 Explanation:
→ 4*j is a common subexpression. So there is a scope of elimination. So B is correct.
→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 42 
Consider the following table
Matching A, B, C, D in the same order gives :
Matching A, B, C, D in the same order gives :
p, q, r, s  
q, r, s, p  
r, s, q, p  
r, s, p, q 
Question 42 Explanation:
Activation Records:
An activation record is another name for Stack Frame. It's the data structure that composes a call stack. It is generally composed of:
1)Locals to the callee
2)Return address to the caller
3)Parameters of the callee
The Call Stack is thus composed of any number of activation records that get added to the stack as new subroutines are added, and removed from the stack (usually) as they return.
The actual structure and order of elements is platform and even implementation defined.
Assembler :
A computer program which translates assembly language to machine language.
It maintains a location counter to assign storage addresses to each instruction of our program.
Reference counter :
→ Reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource.
→ Tracks for each object, counts the number of references made by it and when the count reaches zero, the object becomes inaccessible and gets destroyed.
A linking loader generally performs the reallocation of code.
An activation record is another name for Stack Frame. It's the data structure that composes a call stack. It is generally composed of:
1)Locals to the callee
2)Return address to the caller
3)Parameters of the callee
The Call Stack is thus composed of any number of activation records that get added to the stack as new subroutines are added, and removed from the stack (usually) as they return.
The actual structure and order of elements is platform and even implementation defined.
Assembler :
A computer program which translates assembly language to machine language.
It maintains a location counter to assign storage addresses to each instruction of our program.
Reference counter :
→ Reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource.
→ Tracks for each object, counts the number of references made by it and when the count reaches zero, the object becomes inaccessible and gets destroyed.
A linking loader generally performs the reallocation of code.
Question 43 
A counting semaphore was initialised to 7. Then 20 P (wait) operations and x V (signal) operations were completed on this semaphore. If the final value of semaphore is 5, then the value x will be
0  
13  
18  
5 
Question 43 Explanation:
Counting semaphore value is 7
After 20 P operations value of semaphore = 7 – 20 = 13
After ‘x’ V operations value of S=5, So 13 + xV = 5 and S = 18 .
After 20 P operations value of semaphore = 7 – 20 = 13
After ‘x’ V operations value of S=5, So 13 + xV = 5 and S = 18 .
Question 44 
We consider the addition of two 2’s complement numbers b_{n1}b_{n2}…b_{0} and a_{n1}a_{n2}…a_{0}. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by c_{n1}c_{n2}…c_{0} and the carryout by c_{out}. Which one of the following options correctly identifies the overflow condition?
Question 44 Explanation:
There is an overflow if
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
Question 45 
Consider the function
int fun(x: integer)
{
If x > 100
then
fun = x – 10;
else
fun = fun(fun(x + 11));
}
For the input x = 95, the function will return
int fun(x: integer)
{
If x > 100
then
fun = x – 10;
else
fun = fun(fun(x + 11));
}
For the input x = 95, the function will return
89  
90  
91  
92 
Question 45 Explanation:
Value returned by
fun(95) = fun(fun(106))
= fun(96)
= fun(fun(107))
= fun(97)
= fun(fun(108))
= fun(98)
= fun(fun(109))
= fun(99)
= fun(110)
= fun(100)
= fun(fun(111))
= fun(101)
= 91
fun(95) = fun(fun(106))
= fun(96)
= fun(fun(107))
= fun(97)
= fun(fun(108))
= fun(98)
= fun(fun(109))
= fun(99)
= fun(110)
= fun(100)
= fun(fun(111))
= fun(101)
= 91
Question 46 
Consider the function
int func(int num)
{
int count = 0;
while(num)
{
count++;
num >>= 1;
}
return(count) ;
}
For func(435) the value returned is
int func(int num)
{
int count = 0;
while(num)
{
count++;
num >>= 1;
}
return(count) ;
}
For func(435) the value returned is
9  
8  
0  
10 
Question 46 Explanation:
func (435)
count = 0 Shift right of 1, which means the number gets half.
while (num)
{
Shift left of 1, which means, the number gets doubled.
count++;
num>>=1;
}
return (count); 435/2 = 217/2 = 108/2 = 54/2 = 27/2 = 13/2 = 6/2 = 3/2 = 1/2 = 0
Count: 1, 2, 3, 4, 5, 6, 7, 8, 9. Χ
(or)
(435)_{10} = (110110011)_{2}
The given program counts total number of bits in binary representation and fails when while (num) becomes all zeroes.
count = 0 Shift right of 1, which means the number gets half.
while (num)
{
Shift left of 1, which means, the number gets doubled.
count++;
num>>=1;
}
return (count); 435/2 = 217/2 = 108/2 = 54/2 = 27/2 = 13/2 = 6/2 = 3/2 = 1/2 = 0
Count: 1, 2, 3, 4, 5, 6, 7, 8, 9. Χ
(or)
(435)_{10} = (110110011)_{2}
The given program counts total number of bits in binary representation and fails when while (num) becomes all zeroes.
Question 47 
Which of the following set of components is sufficient to implement any arbitrary Boolean function?
a) XOR gates, NOT gates
b) 2 to 1 multiplexers
c) AND gates, XOR gate
d) Threeinput gates that output (A.B)+C for the inputs A, B and C.
a) XOR gates, NOT gates
b) 2 to 1 multiplexers
c) AND gates, XOR gate
d) Threeinput gates that output (A.B)+C for the inputs A, B and C.
a and d  
b and c  
c  
All a, b, c and d 
Question 47 Explanation:
(A) XOR and NOT gates can only make XOR and XNOR which are not functionally complete.
(B) 2×1 multiplexer is functionally complete provided we have external 1 and 0 available.
(C) XOR can be used to make a NOT gate (a⊕1=a') and (AND, NOT) is functionally complete. Again this required external 1.
(D) We cannot derive NOT gate here. So not functionally complete.
Hence, options (B) and (C) are true provided external 1 and 0 are available.
(B) 2×1 multiplexer is functionally complete provided we have external 1 and 0 available.
(C) XOR can be used to make a NOT gate (a⊕1=a') and (AND, NOT) is functionally complete. Again this required external 1.
(D) We cannot derive NOT gate here. So not functionally complete.
Hence, options (B) and (C) are true provided external 1 and 0 are available.
Question 48 
Consider the following :
Matching A, B, C, D in the same order gives.
Matching A, B, C, D in the same order gives.
r, p, s, q  
p, r, q, s  
s, r, q, p  
q, r, s, p 
Question 48 Explanation:
White box testing→ Condition Coverage
Black box testing→ Equivalence Class partitioning
Volume Testing→ Performance testing
Beta Testing→ System testing
Black box testing→ Equivalence Class partitioning
Volume Testing→ Performance testing
Beta Testing→ System testing
Question 49 
Consider the results of a medical experiment that aims to predict whether someone is going to develop myopia based on some physical measurements and heredity. In this case, the input dataset consists of the person’s medical characteristics and the target variable is binary: 1 for those who are likely to develop myopia and 0 for those who aren’t. This can be best classified as
Regression  
Decision Tree  
Clustering  
Association Rules 
Question 49 Explanation:
Regression: It is a statistical analysis which is used to establish relation between a response and a predictor variable. It is mainly used in finance related applications.
Decision Tree: Decision tree is a computational method which works on descriptive data and records the observations of each object to reach to a result.
Clustering: It is a method of grouping more similar objects in a group and the nonsimilar objects to other groups.
Association Rules: It uses ifthen reasoning method using the supportconfidence technique to give a result.
According to the question Decision Tree is the most suitable technique that can be used to get best result of the experiment.
Decision Tree: Decision tree is a computational method which works on descriptive data and records the observations of each object to reach to a result.
Clustering: It is a method of grouping more similar objects in a group and the nonsimilar objects to other groups.
Association Rules: It uses ifthen reasoning method using the supportconfidence technique to give a result.
According to the question Decision Tree is the most suitable technique that can be used to get best result of the experiment.
Question 50 
Which of the following related to snowflake schema is true?
Each dimension is represented by a single dimensional table  
Maintenance efforts are less  
Dimension tables are normalised  
It is not an extension of star schema 
Question 50 Explanation:
→ A snowflake schema is a logical arrangement of tables in a multidimensional database such that the entity relationship diagram resembles a snowflake shape.
→ The snowflake schema is represented by centralized fact tables which are connected to multiple dimensions.
→ "Snowflaking" is a method of normalizing the dimension tables in a star schema.
→ When it is completely normalized along all the dimension tables, the resultant structure resembles a snowflake with the fact table in the middle.
→ The principle behind snowflaking is normalization of the dimension tables by removing low cardinality attributes and forming separate tables.
→ The snowflake schema is represented by centralized fact tables which are connected to multiple dimensions.
→ "Snowflaking" is a method of normalizing the dimension tables in a star schema.
→ When it is completely normalized along all the dimension tables, the resultant structure resembles a snowflake with the fact table in the middle.
→ The principle behind snowflaking is normalization of the dimension tables by removing low cardinality attributes and forming separate tables.
Question 51 
Which of the following is not true with respect to deadlock prevention and deadlock avoidance schemes?
In deadlock prevention, the request for resources is always granted if resulting state is safe  
In deadlock avoidance, the request for resources is always granted, if the resulting state is safe  
Deadlock avoidance requires knowledge of resource requirements a priori  
Deadlock prevention is more restrictive than deadlock avoidance 
Question 51 Explanation:
False: In deadlock prevention, the request for resources is always granted if resulting state is safe
→ Deadlock prevention algorithms are used in concurrent programming when multiple processes must acquire more than one shared resource.
→ A deadlock prevention algorithm organizes resource usage by each process to ensure that at least one process is always able to get all the resources it needs.
→ Deadlock prevention algorithms are used in concurrent programming when multiple processes must acquire more than one shared resource.
→ A deadlock prevention algorithm organizes resource usage by each process to ensure that at least one process is always able to get all the resources it needs.
Question 52 
Consider a disk sequence with 100 cylinders. The request to access the cylinder occur in the following sequence :
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 2 ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
190  
238  
233  
276 
Question 52 Explanation:
The given sequence is
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 2 ms to move from one cylinder to adjacent one
⇒ (16*2)+(14*2)+(1*2)+(4*2)+(5*2)+(3*2)+(1*2)+(2*2)+(2*2)+(71*2)
⇒ 32+28+2+8+10+6+2+4+4+142
⇒ 238 ms
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 2 ms to move from one cylinder to adjacent one
⇒ (16*2)+(14*2)+(1*2)+(4*2)+(5*2)+(3*2)+(1*2)+(2*2)+(2*2)+(71*2)
⇒ 32+28+2+8+10+6+2+4+4+142
⇒ 238 ms
Question 53 
Consider the following C function
#include <stdio.h>
int main(void)
{
char c[ ] = "ICRBCSIT17";
char *p=c;
printf("%s", c+2[p] – 6[p] – 1);
return 0;
}
The output of the program is
#include <stdio.h>
int main(void)
{
char c[ ] = "ICRBCSIT17";
char *p=c;
printf("%s", c+2[p] – 6[p] – 1);
return 0;
}
The output of the program is
SI  
IT  
TI  
17 
Question 53 Explanation:
String is “ICRBCSIT17” and index numbers starts from 0.
Pointer(p) is pointing to character array c[ ].
Index location 2[p] =’R’ and 6[p] =’I’
‘R’‘I’ = 9 and c+2[p]–6[p]–1
= c+9–1
= c+8
It will print 17.
Pointer(p) is pointing to character array c[ ].
Index location 2[p] =’R’ and 6[p] =’I’
‘R’‘I’ = 9 and c+2[p]–6[p]–1
= c+9–1
= c+8
It will print 17.
Question 54 
If C is a skewsymmetric matrix of order n and X is n * 1 column matrix, then X^{T}CX is a
scalar matrix  
null matrix  
unit matrix  
matrix will all elements 1 
Question 54 Explanation:
→ A skew symmetric(or antisymmetric or anti metric) matrix is a square matrix whose transpose equals its negative. It satisfies the condition A^{T} = A
Question 55 
A 32 bit adder is formed by cascading 4 bit CLA adder. The gate delays (latency) for getting the sum bits is
16  
18  
17  
19 
Question 55 Explanation:
Block diagram of Carry lookahead adder(CLA) is shown in below figure. All the data inputs A and B are available and Pi and Gi are computed simultaneously for all the CLAs.
The carry propagates the through the Carrylookahead generators. Carrylookahead generator which produces carry takes 2 Units of time.
So time delay= (3 units for carry C1 of CLA1)+ (7 * 2 units for carries C2 to C7 of CLA2 to CLA7)+ (3 Units for carry and also sum of CLA8).
Note: For CLAs 1 to 7, it takes an extra 1 unit of time to produce Sum which overlaps with time required for carrie's of next CLAs.
The carry propagates the through the Carrylookahead generators. Carrylookahead generator which produces carry takes 2 Units of time.
So time delay= (3 units for carry C1 of CLA1)+ (7 * 2 units for carries C2 to C7 of CLA2 to CLA7)+ (3 Units for carry and also sum of CLA8).
Note: For CLAs 1 to 7, it takes an extra 1 unit of time to produce Sum which overlaps with time required for carrie's of next CLAs.
Question 56 
In IEEE floating point representation, the hexadecimal number 0xC0000000 corresponds to
3.0  
1.0  
4.0  
2.0 
Question 56 Explanation:
Given number 0xC0000000 is in Hexadecimal format.
Question 57 
Consider the following table : Faculty (facName, dept, office, rank, dateHired)
(Assume that no faculty member within a single department has same name. Each faculty member has only one office identified in office. 3NF refers to third normal form and BCNF refers to BoyceCodd Normal Form. Then Faculty is
(Assume that no faculty member within a single department has same name. Each faculty member has only one office identified in office. 3NF refers to third normal form and BCNF refers to BoyceCodd Normal Form. Then Faculty is
Not in 3NF, in BCNF  
In 3NF, not in BCNF  
In 3NF, in BCNF  
Not in 3NF, not in BCNF 
Question 57 Explanation:
Possible FD’S for given instance are:
FacName ➝ dept,office
FacName ➝ dept,office
Question 58 
Consider the following query :
SELECT E.eno, COUNT(*)
FROM Employees E
GROUP BY E.eno
If an index on eno is available, the query can be Solutioned by scanning only the index if
SELECT E.eno, COUNT(*)
FROM Employees E
GROUP BY E.eno
If an index on eno is available, the query can be Solutioned by scanning only the index if
the index is only hash and clustered
 
the index is only B+tree and clustered  
index can be hash or B+ tree and clustered or nonclustered  
index can be hash or B+ tree and clustered 
There are 58 questions to complete.