ISRO-2017 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
A
{n,1}
B
{n, n}
C
{n2, 1}
D
{1, n2}
       Engineering-Mathematics       Sets-And Relation
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.
Question 2
Consider the set of integers I. Let D denote “divides with an integer quotient” (e.g. 4D8 but 4D7). Then D is
A
Reflexive, not symmetric, transitive
B
Not reflexive, not antisymmetric, transitive
C
Reflexive, antisymmetric, transitive
D
Not reflexive, not antisymmetric, not transitive
       Engineering-Mathematics       Set-Theory
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.
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
A
1
B
1/21
C
0
D
0.5
       Engineering-Mathematics       Probability
Question 3 Explanation: 
Given data,
Step-1: 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.
Step-2: 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.
Step-3: As per the above constraints, total 19 Red balls it means odd number.
→ Among 19 only 18 will be discarded.
Step-3: 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
A
α = -6, β = -1/2
B
α = 2, β = -1/2
C
α = 2, β = 1/2
D
α = -6, β =1/2
       Engineering-Mathematics       Calculus
Question 4 Explanation: 
Given data,
Step-1: x= -1 and x=2
f(x) = α log |x| + β x2 + x
f'(x)= α/x + 2βx + 1 = 0
Step-2: for extreme points f'(x)=0
α/x + 2βx + 1=0
Step-3: 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) = log|x| 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
A
[-1, 0]
B
[-1, 0)
C
[-∞, 0]
D
[-∞,1]
       Engineering-Mathematics       Set-Theory
Question 5 Explanation: 
Given data,
Step-1: f(x) = log|x| and given range is [-∞ to +∞]
g(x) = sin(x) and given range is [-1,1]
Step-2: Given 2 variables are A and B
A= f(g(x))
= log|g(x)|
= log|sin(x)|
So, we will get A range is [-∞ ,0]
Step-3: B= g(f(x))
= sin(f(x))
= sin(log|x|)
So, we will get B range is [-1, 1]
Step-4: Common in both A and B is A∩B
A∩B = [-1, 0]
Key point: Ranges [ -1 ≤ sin(x) ≤ 1 and -∞ ≤ log|x| ≤ ∞ ]
Question 6
The proposition (P⇒Q)⋀(Q⇒P) is a
A
tautology
B
contradiction
C
contingency
D
absurdity
       Engineering-Mathematics       Propositional-Logic
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
A
¬∃(x) [ T(x) ⋀ ¬P(x) ]
B
¬∃(x) [ T(x) ⋁ ¬P(x) ]
C
¬∃(x) [ ¬T(x) ⋀ ¬P(x) ]
D
¬∃(x) [ T(x) ⋀ P(x) ]
       Engineering-Mathematics       Calculus
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”.
Question 8
The number of elements in the power set of { {1,2}, {2,1,1}, {2,1,1,2} } is
A
3
B
8
C
4
D
2
       Engineering-Mathematics       Set-Theory
Question 8 Explanation: 
Given data,
Step-1: Total number of elements in power set of given set with ‘n’ elements = 2n
Example: {1,2}
{{∅},{1},{2},{1,2}} → Total 4 possibilities.
Step-2: 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 23 =8.
Step-3: 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
A
injective and surjective
B
surjective but not injective
C
injective but not surjective
D
neither injective nor surjective
       Engineering-Mathematics       Calculus
Question 9 Explanation: 
Question 10
A
2/5
B
2
C
3
D
5/2
       Engineering-Mathematics       Vectors
Question 10 Explanation: 
Given data,
Step-1: It is clearly showing that two vectors are perpendicular. If two vectors are perpendicular
we are using dot product is zero. a.b =0
Step-2: Calculating dot product is “i is multiplied with i” and “j is multiplied with coefficient of j”
Step-3: we can write like this,
= (2i+λj+k).(i-2j+3k)=0
= 2-2λ+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
A
6
B
5
C
4
D
3
       Database-Management-System       SQL
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
A
Linear hashing
B
Extendible hashing
C
B+ Tree
D
Bit-mapped hashing
       Database-Management-System       B-and-B+-Trees
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 low-cardinality 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 B-tree indexes for columns whose data is frequently updated: consequently, they are more often employed in read-only 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
A
which is written in C++
B
which requires an intermediate layer
C
which communicates through Java sockets
D
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 vendor-specific 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 application-to-database connection; this can facilitate debugging.

Disadvantages Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.

Type-1 driver (or) JDBC-ODBC bridge driver
Type-2 driver (or) Native-API driver
Type-3 driver (or) Network Protocol driver
Type-4 driver (or) Thin driver
Question 14
Consider the recurrence equation
T(n) = 2T(n-1), if n>0
= 1, otherwise
Then T(n) is (in big O order)
A
O(n)
B
O(2n)
C
O(1)
D
O(log n)
       Algorithms       Time-Complexity
Question 14 Explanation: 
Question 15

The complexity of the program is
A
O(log n)
B
O(n2)
C
O(n2 log n)
D
O(n log n)
       Programming       Control Flow
Question 15 Explanation: 
Question 16
Match the following and choose the correct Solution for the order A, B, C, D
A
r, s, p, q
B
r, p, s, q
C
q, s, p, r
D
s, p, q, r
       Algorithms       Dynamic-Programming-and-Sorting
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
Question 17
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
A
Set of strings with 2 a’s and 2 b’s
B
Set of strings with 2 a’s 2 b’s followed by b
C
Set of strings with 2 a’s followed by b’s which is a multiple of 3
D
Set of strings with even number of a’s followed by odd number of b’s
       Theory-of-Computation       Regular-Expression
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.
Question 18
Consider the grammar with productions S → aSb | SS | ϵ This grammar is
A
not context-free, not linear
B
not context-free, linear
C
context-free, not linear
D
context-free, linear
       Theory-of-Computation       Context-Free-Language
Question 18 Explanation: 
Linear grammar means regular grammar which is in the form of A→ Ba | b (or) A→ aB|b
and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*
V → set of terminals and T → set of non-terminals
It is clearly seen that given grammar is not linear but context-free.
Question 19
Identify the language generated by the following grammar
S -> AB
A -> aAb|ϵ
B -> bB| b
A
{ambn | n>=m, m>0}
B
{ambn | n>=m, m>=0}
C
{ambn | n>m, m>0}
D
{ambn | n>m, m>=0}
       Theory-of-Computation       Languages-and-Grammars
Question 19 Explanation: 
The language generated by given grammar is - L={b,bb,abb,abbb,ababb}
Hence it is ambn | n>m, m>=0
Question 20
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
A
L1 ∩ L2 is context-free
B
L3 ∩ L1 is recursive
C
L1 ∪ L2 is context-free
D
L1 ∩ L2 ∩ L3 is recursively enumerable
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language
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 L1 ∩ L2 is a deterministic CFL.
→ Option B is false, as L3 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, L1 ∪ L2 is deterministic context free, hence it is also context free.
→ Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 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 = {ap| p is a prime}.
Then which of the following is true?
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free but accepted by a Turing Machine
       Theory-of-Computation       Context-Free-Language
Question 21 Explanation: 
L = {ap | p is a prime}
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 = {anbnambm | m, n>=0}
B = {anbnambn | m, n>=0}
C = {ambn | m≠2n,m, n>=0}
A
A and B only
B
A and C only
C
B and C only
D
C only
Question 1 Explanation: 
Statement-A: 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.
Statement-B: When last 'b' i.e., bn after am comes as input then top of the stack will contain am
So we can't compare an with anbn. Hence it is not CFL
Statement-C: It is a CFL
Question 2
Let S be an NP-complete 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?
A
R is NP-complete
B
R is NP-hard
C
Q is NP-complete
D
Q is NP-hard
Question 2 Explanation: 
NP-Hard- if it can be solved in polynomial time then all NP-Complete 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
A
14
B
12
C
336
D
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.
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?
A
Encryption : X’s private key followed by Y’s private key. Decryption : X’s public key followed by Y’s public key.
B
Encryption : X’s private key followed by Y’s public key; Decryption : X’s public key followed by Y’s private key
C
Encryption : X’s private key followed by Y’s public key; Decryption : Y’s private key followed by X’s public key.
D
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) SHA-256
(Q) AES
(R) DES
(S) MD5
A
P and S only
B
P and Q only
C
R and S only
D
P and R only
Question 5 Explanation: 
To generate a message digest by the network security protocols we need SHA and MD5.
→ SHA-256 and SHA-512 are novel hash functions computed with 32-bit and 64-bit 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 message-digest algorithm is a widely used hash function producing a 128-bit 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 non-cryptographic 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
A
220
B
224
C
214
D
221
Question 6 Explanation: 
→ IP address belonging to class C are assigned to small-sized 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:
221 = 2097152 network address
28 – 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 CIDR-based 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?
A
245.248.136.0/21 and 245.248.128.0/22
B
245.248.128.0/21 and 245.248.128.0/22
C
245.248.132.0/22 and 245.248.132.0/21
D
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?
A
Network layer – 4 times, Data link layer – 4 times
B
Network layer – 4 times, Data link layer – 6 times
C
Network layer – 2 times, Data link layer – 4 times
D
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 ,
Question 9
Generally TCP is reliable and UDP is not reliable. DNS which has to be reliable uses UDP because
A
UDP is slower
B
DNS servers has to keep connections
C
DNS requests are generally very small and fit well within UDP segments
D
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.
Question 10
Consider the set of activities related to e-mail
A : Send an e-mail from a mail client to mail server
B : Download e-mail headers from mail box and retrieve mails from server to a cache
C : Checking e-mail through a web browser
The application level protocol used for each activity in the same sequence is
A
SMTP, HTTPS, IMAP
B
SMTP, POP, IMAP
C
SMTP, IMAP, HTTPS
D
SMTP, IMAP, POP
E
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.
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?
A
5
B
10
C
40
D
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=?
Step-1: First we have to find transmission time
Transmission time= Frame size/bandwidth
= 32*8/(64) ms
= 4 ms
Step-2: 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
A
20, 7
B
19, 8
C
20, 8
D
21, 9
Question 12 Explanation: 
2-way 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 2-way set-associative cache
= 2^9 /2 = 2^8 sets => 8 set bits
Now, because it is set-associative 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
A
16384
B
512
C
2048
D
1024
Question 13 Explanation: 
→ Access A in row major order.
→ No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×210B / 128B = 215 / 27 = 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
A
–232 to 232
B
–231 to 232-1
C
–231 to 231-1
D
–231-1 to 232-1
Question 14 Explanation: 
Range of ‘n’ bit 2’s complement binary number is always –2(n-1) to 2(n-1)-1.
Question 15
Let M = 11111010 and N = 00001010 be two 8 bit two’s complement number. Their product in two’s complement is
A
11000100
B
10011100
C
10100101
D
11010101
Question 15 Explanation: 
A = 1111 1010 = -610 [2's complement number]
B = 0000 1010 = 1010 [2's complement number]
A×B = -6×10 = - 6010
⇒ -6010 = 101111002
= 110000112 (1's complement)
= 110001002 (2's complement)
Question 16
For a pipelines CPU with a single ALU, consider the following:
  1. The j + 1st instruction uses the result of jth instruction as an operand
  2. Conditional jump instruction
  3. jth and j + 1st instructions require ALU at the same time
Which one of the above causes a hazard?
A
A and B only
B
B and C only
C
B only
D
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.
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?
A
Smaller block size incurs lower cache miss penalty
B
Smaller block size implies better spatial locality
C
Smaller block size implies smaller cache tag
D
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?
A
Immediate addressing
B
Register addressing
C
Register Indirect addressing
D
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.
Question 19
A sorting technique is called stable if
A
If it takes O(n log n) time
B
It uses divide and conquer technique
C
Relative order of occurrence of non-distinct elements is maintained
D
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.
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)
A
q, r, p
B
p, q, r
C
q, p, r
D
r, q, p
Question 20 Explanation: 
Heap Construction → O(n)
Hash table construction→ O(n2)
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
A
i+j
B
j+i(i-1)/2
C
i+j-1
D
i+j(j-1)/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, ith row contains i number of non-zero elements. Before ith row there are (i-1) rows, (1 to i-1) and in total these rows has 1+2+3......+(i-1) = i(i-1)/2 elements.
Now at ith row, the jth 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(i-1)/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?
A
7, 8, 9, 5, 6
B
5, 9, 6, 7, 8
C
7, 8, 9, 6, 5
D
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.
Question 23
Quick sort is run on 2 inputs shown below to sort in ascending order
A.     1, 2, 3……n
B.     n, n-1, n-2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
A
C1>C2
B
C1=C2
C
C1
D
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(n2)
→ 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?
A
61, 52, 14, 17, 40, 43
B
10, 65, 31, 48, 37, 43
C
81, 61, 52, 14, 41, 43
D
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
A
Y
B
C
C
M
D
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

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 in-order traversal of the resultant binary search tree is
A
9, 8, 6, 4, 2, 3, 0, 1, 5, 7
B
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
C
0, 2, 4, 3, 1, 6, 5, 9, 8, 7
D
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 Max-heap. 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
A
10, 8, 7, 5, 3, 2, 1
B
10, 8, 7, 2, 3, 1, 5
C
10, 8, 7, 1, 2, 3, 5
D
10, 8, 7, 3, 2, 1, 5
Question 27 Explanation: 
Max-Heap has 5 elements:

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
A
3
B
1
C
2
D
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
A
cannot have more than 19 nodes
B
has exactly 19 nodes
C
has exactly 17 nodes
D
has exactly 20 nodes
Question 29 Explanation: 
→ If every non-leaf 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
Question 30
What is the maximum height of any AVL tree with 7 nodes? Assume that height of tree with single node is 0.
A
2
B
3
C
4
D
5
Question 30 Explanation: 
The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2h-1=7
h=3
Question 31
Which one of the following property is correct for a red-black tree?
A
Every simple path from a node to a descendant leaf contains the same number of black nodes
B
If a node is red, then one children is red and another is black
C
If a node is red, then both its children are red
D
Every leaf node (sentinel node) is red
Question 31 Explanation: 
→ It could be from a binary search tree. The red-black 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 self-balancing 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
A
e d b g f c a
B
e d b f g c a
C
d e b f g c a
D
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
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?
A
Both M and N are true and N is the reason for M
B
Both M and N are true and N is not the reason for M
C
Both M and N are false
D
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.
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
A
1
B
2
C
3
D
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
A
n2
B
2n+1 -1
C
2n
D
2n -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,... ⇒ 2n-1
Question 36
Consider the following scheduling

Matching the table in the order A, B, C gives
A
t, u, s
B
s, t, u
C
u, s, t
D
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 Real-Time 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?
A
96
B
100
C
97
D
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.
Question 38
Which of the following is false?
A
User level threads are not scheduled by the kernel
B
Context switching between user level threads is faster than context switching between kernel level threads
C
When a user thread is blocked all other threads of its processes are blocked
D
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?
  1. Abstraction and encapsulation
  2. Strictly-typed
  3. Type-safe property coupled with sub-type rule
  4. Polymorphism in the presence of inheritance
A
A and B only
B
A, D and B only
C
A and D only
D
A, C and D only
Question 39 Explanation: 

Question 40
Which languages necessarily need heap allocation in the run time environment?
A
Those that support recursion
B
Those that use dynamic scoping
C
Those that use global variables
D
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.
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
A
The code contains loop invariant computation
B
There is scope of common subexpression elimination in this code
C
There is scope of strength reduction in this code
D
There is scope of dead code elimination in this code
Question 41 Explanation: 
→ 4*j is a common sub-expression. 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.
Question 42
Consider the following table

Matching A, B, C, D in the same order gives :
A
p, q, r, s
B
q, r, s, p
C
r, s, q, p
D
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.
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
A
0
B
13
C
18
D
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 .
Question 44
We consider the addition of two 2’s complement numbers bn-1bn-2…b0 and an-1an-2…a0. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by cn-1cn-2…c0 and the carry-out by cout. Which one of the following options correctly identifies the overflow condition?
A
B
C
D
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.
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
A
89
B
90
C
91
D
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
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
A
9
B
8
C
0
D
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.
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) Three-input gates that output (A.B)+C for the inputs A, B and C.
A
a and d
B
b and c
C
c
D
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.
Question 48
Consider the following :

Matching A, B, C, D in the same order gives.
A
r, p, s, q
B
p, r, q, s
C
s, r, q, p
D
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
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
A
Regression
B
Decision Tree
C
Clustering
D
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 non-similar objects to other groups.
Association Rules: It uses if-then reasoning method using the support-confidence 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?
A
Each dimension is represented by a single dimensional table
B
Maintenance efforts are less
C
Dimension tables are normalised
D
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.
Question 51
Which of the following is not true with respect to deadlock prevention and deadlock avoidance schemes?
A
In deadlock prevention, the request for resources is always granted if resulting state is safe
B
In deadlock avoidance, the request for resources is always granted, if the resulting state is safe
C
Deadlock avoidance requires knowledge of resource requirements a priori
D
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.
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?
A
190
B
238
C
233
D
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
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
A
SI
B
IT
C
TI
D
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.
Question 54
If C is a skew-symmetric matrix of order n and X is n * 1 column matrix, then XTCX is a
A
scalar matrix
B
null matrix
C
unit matrix
D
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 AT = -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
A
16
B
18
C
17
D
19
Question 55 Explanation: 
Block diagram of Carry look-ahead 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 Carry-lookahead generators. Carry-lookahead 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
A
-3.0
B
-1.0
C
-4.0
D
-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 Boyce-Codd Normal Form. Then Faculty is
A
Not in 3NF, in BCNF
B
In 3NF, not in BCNF
C
In 3NF, in BCNF
D
Not in 3NF, not in BCNF
Question 57 Explanation: 
Possible FD’S for given instance are:
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
A
the index is only hash and clustered
B
the index is only B+tree and clustered
C
index can be hash or B+ tree and clustered or non-clustered
D
index can be hash or B+ tree and clustered
There are 58 questions to complete.