Question 1

I


B 
II

III


D 
IV

Here, part IV is incorrect. “was losing consciousness” shows continuous process of losing consciousness, but he was not in the process, rather he just lost consciousness. So, the correction is ” was losing consciousness ” → ” lost consciousness “.
Thus, IV is the correct choice.
Question 2

knows, will have


B 
knew, had

C 
had known, could have

should have known, would have

Explanation: A)knows, will have //Present ,future B)knew, had //past past c)had known, could have//past perfect,perfect conditional D)should have known, would have //present,future In a Type 3 conditional sentence, the tense in the ‘if’ clause is the past perfect, and the tense in the main clause is the perfect conditional or the perfect continuous conditional.
IF CLAUSE (CONDITION)  MAIN CLAUSE (RESULT) 

If + past perfect  perfect conditional or perfect continuous conditional 
If this thing had happened  that thing would have happened. 
Question 3

sticky


wellconnected


C 
rambling

friendly

Coherent – Adj. Meaning – (of an argument, theory, or policy) logical and consistent. Rambling – Adj. Meaning – (of writing or speech) lengthy and confused or inconsequential. Hence both are opposite to each other.
Question 4

17


37


C 
64

26

Explanation:
Given series is 2,5,10,17,26,37,50,64.
Here total number of terms are 8..i.e. A(1) to A(8).
For the 1st 7 terms, you can observe the relationship
between the terms which is
A(n) = [ A(n1)  {A(n1) + A(n2)} + 2 ] where n >= 3
Now for the 8th term i.e. A(8), this relationship violates.
According to the relationship,
A(8) = [A(7) + {A(7)  A(6)} + 2 ]
= [50 + {50  37} + 2 ]
= 50 + 13 + 2
= 65.
But in the series it is 64. Hence 64 doesn't belong to
the series.
Question 5

1.34


1.74


C 
3.02

D 
3.91

As you can see from each row that the total number of
students in the class are 44.
Now we have to find the total number of marks obtained
by the class.
Marks are given for correct answers only.
No negative or partial marking.
For 1st question total marks obtained are : 2*21 = 42
For 2nd question total marks obtained are : 3*15 = 45
For 3rd question total marks obtained are : 2*23 = 46
hence total marks obtained by the class are = 42+45+46 = 133
Now, Average marks obtained = Total Marks/Total no of students
= 133/44
= 3.02
Hence C is the answer.
Question 6
A dance programme is scheduled for 10.00 a.m. Some students are participating in the programme and they need to come an hour earlier than the start of the event. These students should be accompanied by a parent. Other students and parents should come in time for the programme. The instruction you think that is appropriate for this is

Students should come at 9.00 a.m. and parents should come at 10.00 a.m.


B 
Participating students should come at 9.00 a.m. accompanied by a parent, and other parents and students should come by 10.00 a.m.

C 
Students who are not participating should come by 10.00 a.m. and they should not bring their parents. Participating students should come at 9.00 a.m.

Participating students should come before 9.00 a.m. Parents who accompany them should come at 9.00 a.m. All others should come at 10.00 a.m.

 A is not the appropriate instruction as only the participating students and their parents have to come at 9.00 a.m. and other students along with their parents have to come at 10.00 a.m., while the statement in A says that all students should come at 9.00 a.m. and all the parents should come at 10.00 a.m.
 B is the appropriate instruction and covers all the aspects of the information to be conveyed.
 C is not the appropriate instruction as the non participating students have to come at 10.00 a.m. with their parents, while the statement in B says that these students have to come without their parents.
 D is not the appropriate instruction as it states that the participating students have to come before 9.00 a.m. whereas they have to come at 9.00 a.m.
So B is Correct option.
Question 7

By the beginning of the 20th century, several hypotheses were being proposed, suggesting a paradigm shift in our understanding of the universe. However, the clinching evidence was provided by experimental measurements of the position of a star which was directly behind our sun. Which of the following inference(s) may be drawn from the above passage?
(i) Our understanding of the universe changes based on the positions of stars (ii) Paradigm shifts usually occur at the beginning of centuries (iii) Stars are important objects in the universe (iv) Experimental evidence was important in confirming this paradigm shift
A 
(i), (ii) and (iv)

(iii) only


(i) and (iv)


D 
(iv) only

Explanation:
So, D is the correct choice as only (iv) is the correct statement. Please comment below if you find anything wrong in the above post.
Question 8

A 
increased by 5 %

decreased by 13%


decreased by 20%


D 
decreased by 11%

Suppose original GDP was x then its international
value is x/50.
Now GDP becomes 107*x/100 and its international
value becomes (107x/100)/60= 107x/6000.
The value has decreased by (x/50)(107x/6000).
Percentage approx 10.8% = 11%
Question 9

1:1


B 
2:1

C 
1.5:1

2.5:1

Explanation:
Number of female students in 2011 and 2012 are equal.
Suppose they are x.
Now,
Males students in 2011 = Female students in 2011
= x (as the ratio is 1)
And in 2012, Male students / Female students =
1.5(Given)
Hence Male students in 2012 = 1.5 * Female students
= 1.5 * x
Now ratio of Male students in 2012 to Male students
in 2011 = ( 1.5 * x ) / x
= 1.5 / 1
i.e. 1.5 : 1
Hence C is the answer.
Question 10

1634


1737


C 
3142

3162

Explanation:
Question 11

Consider the following statements:
P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equivalent to Q
Which one of the following about L, M, and N is CORRECT?
Only L is TRUE.


Only M is TRUE.


C 
Only N is TRUE.

D 
L, M and N are TRUE

Explanation:
Let a and b be two proposition
a: Good Mobile phones.
b: Cheap Mobile Phones.
P and Q can be written in logic as
P: a>~b
Q: b>~a.
Truth Table
a b ~a ~b P Q
T T F F F F
T F F T T T
F T T F T T
F F T T T T
it clearly shows P and Q are equivalent.
so option D is Correct
Question 12

A


B


C 
C

D 
D

Explanation:
Let x = {a, b, c} and y = {1, 2}
A Function f maps each element of x to 1 in y.
f(a)=1 , f(b)=1 , f(c) =1
A = {a, b} B = {b, c}

A ]
 f(A u B)  = f({a, b, c}) = 3
 f(A)+f(B) = 2 + 2 = 4 , LHS != RHS.

B ]
f(A ∩ B) = f({b}) = { 1 }
f(A) ∩ f(B) = {1, 1} ∩ {1, 1} = {1, 1}
LHS != RHS

C ]
f(A ∩ B) = f({b}) = { 1 } = 1
min{f(A),f(B)} = min(2,2) = 2
LHS != RHS

D ] In a function a value can be mapped only to one value.
Question 13

A 
3

B 
5

7


9

Explanation:
This is according to Lagrange’s theorem that states that the order of subgroup should divide the order of group. Subgroups of G can be of order 1,3,5 or 15 and according to the conditions and choices, B is the right answer.
Question 14

A 
If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative.

If the trace of the matrix is positive, all its eigenvalues are positive.


C 
If the determinant of the matrix is positive, all its eigenvalues are positive.

If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive.

ANSWER IS A
Question 15

1


B 
2

3


D 
4

Explanation:
Question 16

2


3


C 
4

D 
5

ANSWER IS C
Question 17

A


B


C


D

ANSWER IS B
Question 18

Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output.
f (x, y, a, b) { if (x is 1) y = a; else y = b; } 
Which one of the following digital logic blocks is the most suitable for implementing this function?
Full adder


Priority encoder


C 
Multiplexer

Flipflop

Explanation:
This function can be interpreted as having two inputs a, b and select signal x. Output y will depend on the select signal x. Function will be like (ax+bx’) Its implementation will be like So ans is ( C) .
Question 19

Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency.
P1: Fourstage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns. P2: Fourstage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns. P3: Fivestage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns. P4: Fivestage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock frequency?
P1


P2


C 
P3

P4

Explanation:
Peak clock frequency = 1 / Maximum latency
Maximum of latencies is minimum in P3
Question 20

Let A be a square matrix of size n x n. Consider the following program. What is the expected output?
C = 100 for i = 1 to n do for j = 1 to n do { Temp = A[i][j] + C A[i][j] = A[j][i] A[j][i] = Temp  C } for i = 1 to n do for j = 1 to n do Output(A[i][j]); 
A 
The matrix A itself

Transpose of matrix A


Adding 100 to the upper diagonal elements and subtracting 100 from diagonal elements of A


D 
None of the above

Explanation:
If we take look at the inner statements of first loops, we can notice that the statements swap A[i][j] and A[j][i] for all i and j. Since the loop runs for all elements, every element A[l][m] would be swapped twice, once for i = l and j = m and then for i = m and j = l. Swapping twice means the matrix doesn’t change.
Question 21

6


B 
7

8


D 
9

Explanation:
P(X) = x^{5} + 4x^{3} + 6x + 5
=x ( x^{4} + 4x^{2} + 6 ) +5
=x ( x ( x^{3} + 4x ) + 6 ) + 5
=x ( x ( x ( x^{2} + 4 ) ) + 6 ) + 5
=x ( x ( x (x (x) + 4 ) ) + 6 ) + 5
Let T be a temporary variable to store intermediate results.
1. T = (x) * (x)
2. T = T + 4
3. T = (x) * (T)
4. T = (x) * (T)
5. T = T + 6
6. T = (x) * T
7. T = T + 5
Thus, we need 7 operations if we are to use only one temporary variable.
Question 22

A 
SQPTRWUV

SQPTURWV


SQPTWUVR


D 
SQPTRUWV

Explanation:
Algorithm Inorder(tree)  Use of Recursion
Steps:
1. Traverse the left subtree,
i.e., call Inorder(leftsubtree)
2. Visit the root.
3. Traverse the right subtree,
i.e., call Inorder(rightsubtree)
Understanding this algorithm requires the basic
understanding of Recursion
Therefore, We begin in the above tree with root as
the starting point, which is P.
# Step 1( for node P) :
Traverse the left subtree of node or root P.
So we have node Q on left of P.
> Step 1( for node Q)
Traverse the left subtree of node Q.
So we have node S on left of Q.
* Step 1 (for node S)
Now again traverse the left subtree of node S which is
NULL here.
* Step 2(for node S)
Visit the node S, i.e print node S as the 1st element of
inorder traversal.
* Step 3(for node S)
Traverse the right subtree of node S.
Which is NULL here.
Now move up in the tree to Q which is parent
of S.( Recursion, function of Q called for function of S).
Hence we go back to Q.
> Step 2( for node Q):
Visit the node Q, i.e print node Q as the 2nd
element of inorder traversal.
> Step 3 (for node Q)
Traverse the right subtree of node Q.
Which is NULL here.
Now move up in the tree to P which is parent
of Q.( Recursion, function of P called for function of Q).
Hence we go back to P.
# Step 2(for node P)
Visit the node P, i.e print node S as the 3rd
element of inorder traversal.
# Step 3 (for node P)
Traverse the right subtree of node P.
Node R is at the right of P.
Till now we have printed SQP as the inorder of the tree.
Similarly other elements can be obtained by traversing
the right subtree of P.
The final correct order of Inorder traversal would
be SQPTRWUV.
Question 23

17


18


C 
19

D 
20

Explanation:
So the recursion depth is 19 (including the first node).
Question 24

O(n^{2})


O(nLogn)


Theta(nLogn)


O(n^{3})

ANSWER IS A
Question 25

The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.
a*b*(ba)*a*
2


B 
3

C 
4

5

Explanation:
The string “bab” is the shortest string not acceptable by regular expression.
Question 26

A


B


C


D

ANSWER IS C
Question 27

make parsing and semantic analysis simpler.


B 
improve error recovery and error reporting.

C 
increase the chances of reusing the machineindependent code optimizer in other compilers.

improve the register allocation.

Explanation:
After semantic Analysis, the code is converted into intermediate code which is language independent, the advantage of converting into intermediate code is to improve the performance of code generation and to increase the chances of reusing the machineindependent code optimizer in other compilers.
Question 28

Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. 2) Automatic garbage collection is essential to implement recursion. 3) Dynamic allocation of activation records is essential to implement recursion. 4) Both heap and stack are essential to implement recursion.
A 
1 and 2 only

2 and 3 only


3 and 4 only


D 
1 and 3 only

Explanation:
1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. True, dynamic allocate of memory is required for function call stack as number of calls is not known advance for recursive functions. 2) Automatic garbage collection is essential to implement recursion. False, Automatic garbage collection is not essential. 3) Dynamic allocation of activation records is essential to implement recursion. True, as number of calls or number of activation records is not known advance for recursive functions. 4) Both heap and stack are essential to implement recursion. Heap is not needed for function calls. It is generally used for dynamic memory allocation by user (or programmer). See Memory Layout of C Programs for details.
Question 29

High cohesion and high coupling


B 
High cohesion and low coupling

C 
Low cohesion and high coupling

Low cohesion and low coupling

Explanation:
Coupling is the manner and degree of interdependence between software modules.Cohesion refers to the degree to which the elements of a module belong together. In a good software design, it is always desirable to have less interaction among modules (Low coupling). Advantages of high cohesion (or “strong cohesion”) are: 1) Reduced module complexity (they are simpler, having fewer operations). 2) Increased system maintainability, because logical changes in the domain affect fewer modules, and because changes in one module require fewer changes in other modules. 3) Increased module reusability,because application developers will find the component they need more easily among the cohesive set of operations provided by the module.
Question 30

4


5


c 
6

d 
7

Explanation:
What is a Page fault ? An interrupt that occurs when a program requests data that is not currently in real memory. The interrupt triggers the operating system to fetch the data from a virtual memory and load it into RAM. Now, 4, 7, 6, 1, 7, 6, 1, 2, 7, 2 is the reference string, you can think of it as data requests made by a program. Now the system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy.
[ ]  Initially page frames are empty.i.e. no
process pages in main memory.
[ 4 ]  Now 4 is brought into 1st frame (1st
page fault)
Explanation: Process page 4 was requested by the program, but it was not in the main memory(in form of page frames),which resulted in a page fault, after that process page 4 was brought in the main memory by the operating system.
[ 4 7 ]  Now 7 is brought into 2nd frame
(2nd page fault)  Same explanation.
[ 4 7 6 ]  Now 6 is brought into 3rd frame
(3rd page fault)
[ 1 7 6 ]  Now 1 is brought into 1st frame, as 1st
frame was least recently used(4th page fault).
After this 7, 6 and 1 are were already present in the frames hence no replacements in pages.
[ 1 2 6 ]  Now 2 is brought into 2nd frame, as 2nd
frame was least recently used(5th page fault).
[ 1 2 7 ] Now 7 is brought into 3rd frame, as 3rd frame
was least recently used(6th page fault).
Hence, total number of page faults(also called pf) are 6. Therefore, C is the answer.
Question 31

A 
A

B


C


D 
D

Explanation:
The Relational Algebra expression in the question above, does 4 operations, step by step ( innermost braces first ) .
1. Select those tuples from relation r which satisfies
expression/condition F1, say the result of this
operation is set A.
2. Select those tuples from set A which satisfies
expression/condition F2, say the result of this
operation is set B.
3. Select attrributes set A2 from set B, say the
result of this operation is set C.
4. Select attrributes set A1 from set C, say the
result is set D which is the final result.
Now to optimize this expression, we can combine operations/steps 1 and 2 by AND operator between F1 and F2 condition, like F1 ^ F2, and instead of selecting first attribute set A2, we can directly select attribute set A1 from the result of the combined operation, which is represented by expression in Option A .
Question 32

in all candidate keys of R.


in some candidate key of R.


in a foreign key of R.


only in the primary key of R.

Explanation:
The constituent attributes of a Candidate key or simply the attributes of a candidate key are called the prime attributes. Suppose ABC is one candidate key of a Relation R(ABCDEFGH). Then the attributes A, B and C all are prime attributes. Similarly if ABD is also another candidate key in the same relation R, then D is also the prime attribute. And conversely, an attribute that does not occur in ANY candidate key is called a nonprime attribute.
Question 33

Network layer and Routing


B 
Data Link Layer and Bit synchronization

Transport layer and Endtoend process communication


D 
Medium Access Control sublayer and Channel sharing

Explanation:
1) Yes, Network layer does Rotuing
2) No, Bit synchronization is provided by Physical Layer
3) Yes, Transport layer provides Endtoend process
communication
4) Yes, Medium Access Control sublayer of Data Link Layer provides
Channel sharing.
Question 34

0111110100


B 
0111110101

0111111101


D 
0111111111

Explanation:
Bit Stuffing is used to create framing.
8bit delimiter pattern is 01111110.
The output bitstring after stuffing is 01111100101.
The above highlighted bit is stuffed bit.
So input bitstring must be 0111110101.
Question 35

Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D?
(i) TTL (ii) Checksum (iii) Fragment Offset
(i) only


B 
(i) and (ii) only

(ii) and (iii) only


D 
(i), (ii) and (iii)

Explanation:
All (i), (ii) and (iii) are changed: (i) TTL is decremented at every hop. So TTL is different from orginal value (ii) Since TTL changes, the Checksum of the packet also changes. (iii) A packet is fragmented if it has a size greater than the Maximum Transmission Unit (MTU) of the network. There may be intermediate networks that may change fragment offset by fragmenting the packet.
Question 36

Classless Interdomain Routing (CIDR) receives a packet with address 131.23.151.76. The router’s routing table has the following entries:
Prefix Output Interface Identifier 131.16.0.0/12 3 131.28.0.0/14 5 131.19.0.0/16 2 131.22.0.0/15 1
The identifier of the output interface on which this packet will be forwarded is ______.
A 
1

B 
2

3


5

Explanation:
In this question, we need to find out Netmask for each entry and BITWISE AND with given packet address, whichever equals the Netid, is the ans. Ex. 1st entry in table: 131.16.0.0/12. its MASK is first 12 bits of network(they are all 1) and remaining 20 bits of host(they are all 0). so MASK is 255.240.0.0 AND 131.23.151.76 = 131.16.0.0. Last entry is 131.22.0.0/15 MASK—>255.254.0.0 AND 131.23.151.76 = 131.22.0.0. Two ans coming interfaces 1,3. Longest Prefix Matching is used to decide among two. When one destination address matches more than one forwarding table entry. The most specific of the matching table entries is used as the interface. The interface 1 has the longest matching prefix with the input IP address. Therefore 1 is chosen.
Question 37

128


64


C 
256

512

Explanation:
Wraparound time is nothing but in how many seconds will all the hosts generate all IDs possible. (i.e. TOTAL_IDS / NO. OF IDS PER SEC). Total IDs possible with 50bit is 2^50. One host generating 1000 identifiers per sec. So all hosts will generate 2^32 * 1000 —> 2^32 * 2^10—–> 2^42 unique IDs. If we Divide them, we get answer (i.e. 2^50/2^42=2^8)
Question 38

MF bit: 0, Datagram Length: 1444; Offset: 370


MF bit: 1, Datagram Length: 1424; Offset: 185


MF bit: 1, Datagram Length: 1500; Offset: 37


MF bit: 0, Datagram Length: 1424; Offset: 2960

Explanation:
Number of packet fragments = ⌈ (total size of packet)/(MTU) ⌉
= ⌈ 4404/1500 ⌉
= ⌈ 2.936 ⌉
= 3
So Datagram with data 4404 byte fragmented into 3 fragments.
The first frame carries bytes 0 to 1479 (because MTU is 1500 bytes and HLEN is 20 byte so the total bytes in fragments is maximum 150020=1478). the offset for this datagram is 0/8 = 0. The second fragment carries byte 1480 to 2959. The offset for this datagram is 1480/8 = 185.finally the third fragment carries byte 2960 to 4404.the offset is 370.and for all fragments except last one the M bit is 1.so in the third bit M is 0..
Question 39

Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1: r1(X); r1(Z); w1(X); w1(Z) T2: r2(Y); r2(Z); w2(Z) T3: r3(Y); r3(X); w3(Y) S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z) S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)
Which one of the following statements about the schedules is TRUE?
A 
Only S1 is conflictserializable.

Only S2 is conflictserializable.


C 
Both S1 and S2 are conflictserializable.

Neither S1 nor S2 is conflictserializable.

Explanation:
For conflict serializability of a schedule( which gives same effect as a serial schedule ) we should check for conflict operations, which are ReadWrite, WriteRead and WriteWrite between each pair of transactions, and based on those conflicts we make a precedence graph, if the graph contains a cycle, it’s not a conflict serializable schedule. To make a precedence graph: if Read(X) in Ti followed by Write(X) in Tj ( hence a conflict ), then we draw an edge from Ti to Tj ( Ti > Tj) If we make a precedence graph for S1 and S2 , we would get directed edges for S1 as T2>T1, T2>T3, T3>T1, and for S2 as T2>T1, T2>T3, T3>T1, T1>T2. In S1 there is no cycle, but S2 has a cycle. Hence only S1 is conflict serializable. Note : The serial order for S1 is T2 > T3 > T1.
Question 40

Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation.
employee (empId, empName, empAge) dependent(depId, eId, depName, depAge)
Consider the following relational algebra query: The above query evaluates to the set of empIds of employees whose age is greater than that of
some dependent.


all dependents.


some of his/her dependents


D 
all of his/her dependents.

Explanation:
The below subquery after the subtraction sign produces id’s of those employees who have at least one dependent with age greater than or equal the employee’s age.
When the result of above subquery is subtracted from all employees, we get the employees whose age is greater than all dependents.
Question 41

A 
6

B 
7

8


9

Explanation:
If 6 resources are there then it may be possible that all three process have 2 resources and waiting for 1 more resource. Therefore, all of them will have to wait indefinitely. If 7 resources are there, then atleast one must have 3 resources so deadlock can never occur.
Question 42

An operating system uses shortest remaining time first scheduling algorithm for preemptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):
Process Arrival Time Burst Time P1 0 12 P2 2 4 P3 3 6 P4 8 5
The average waiting time (in milliseconds) of the processes is _________.
4.5


5.0


C 
5.5

D 
6.5

Explanation:
Process Arrival Time Burst Time
P1 0 12
P2 2 4
P3 3 6
P4 8 5
Burst Time – The total time needed by a process from the CPU for its complete execution. Waiting Time – How much time processes spend in the ready queue waiting their turn to get on the CPU Now, The Gantt chart for the above processes is :
P1  0 to 2 milliseconds
P2  2 to 6 milliseconds
P3  6 to 12 milliseconds
P4  12 to 17 milliseconds
P1  17 to 27 milliseconds
Process p1 arrived at time 0, hence cpu started executing it. After 2 units of time P2 arrives and burst time of P2 was 4 units, and the remaining time of the process p1 was 10 units,hence cpu started executing P2, putting P1 in waiting state(Preemptive and Shortest remaining time first scheduling). Due to P1’s highest remaining time it was executed by the cpu in the end.
Now calculating the waiting time of each process:
P1 > 17 2 = 15
P2 > 0
P3 > 6  3 = 3
P4 > 12  8 = 4
Hence total waiting time of all the processes is
= 15+0+3+4=22
Total no of processes = 4
Average waiting time = 22 / 4 = 5.5
Hence C is the answer.
Question 43

120


B 
122

124


D 
118

Explanation:
As both page table and page are in physical memory T(eff) = hit ratio * (TLB access time + Main memory access time) + (1 – hit ratio) * (TLB access time + 2 * main memory time) = 0.6*(10+80) + (10.6)*(10+2*80) = 0.6 * (90) + 0.4 * (170) = 122
Question 44

Consider the basic block given below.
a = b + c c = a + d d = b + c e = d  b a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are
A 
6 and 6

8 and 10


9 and 12


D 
4 and 4

Explanation:
Simplifying the given equations :
d = b + c (given) e = d – b (given) => d = b + c and e = c
e = d – b (given) a = e + b (given) => a = d
Thus, the given DAG has 6 nodes and 6 edges.
Question 45

A 
Deciding if a given contextfree grammar is ambiguous.

Deciding if a given string is generated by a given contextfree grammar.


C 
Deciding if the language generated by a given contextfree grammar is empty.

Deciding if the language generated by a given contextfree grammar is finite.

Explanation:
Context free grammar is not closed under ambiguity.A set is closed under an operation means when we operate an element of that set with that operator we get an element from that set. Here, context free grammar generates a context free language and set of all context free languages is also a set. But, ambiguity is not an operation and hence we can never say that CFG is closed under ambiguity. Thus, problem mentioned in option (A) is undecidable.
Question 46

A 
None of the languages

Only L1


C 
Only L1 and L2

All the three languages

ANSWER IS C
Question 47

50


100


C 
150

D 
200

Explanation:
T(k) is the smallest number of steps needed to move from k to 100. Now, it is given that ‘y’ and ‘z’ are two numbers such that T(9) = 1 + min (T(y), T(z)), i.e., T(9) = 1 + min (Steps from y to 100, Steps from z to 100), where ‘y’ and ‘z’ are two possible values that can be reached from 9. One number that can be reached from 9 is 10, which is the number obtained if we simply move one position right on the number line. Another number is 15, the shortcut path from 9, as given in the question. So, we have two paths from 9, one is 10 and the other is 15. Therefore, the value of y and z is 10 and 15 (either variable may take either of the values). Thus, yz = 150.
Question 48

NPComplete.


B 
solvable in polynomial time by reduction to directed graph reachability.

C 
solvable in constant time since any input instance is satisfiable.

NPhard, but not NPcomplete.

Explanation:
2CNFSAT can be reduced to strongly connected components problem. And strongly connected component has a polynomial time solution. Therefore 2CNFSAT is polynomial time solvable.
Question 49

60


B 
110

210


50

Explanation:
int getSum(node *root, int L, int H)
{
// Base Case
if (root == NULL)
return 0;
if (root>key < L)
return getSum(root>right, L, H);
if (root>key > H)
return getSum(root>left, L, H)
if (root>key >= L && root>key <=H)
return getSum(root>left, L, H) + root>key +
getSum(root>right, L, H);
}
The above always takes O(m + Logn) time. Note that the code first traverses across height to find the node which lies in range. Once such a node is found, it recurs for left and right children. Two recursive calls are made only if the node is in range. So for every node that is in range, we make at most one extra call (here extra call means calling for a node that is not in range).
Question 50

A 
(97 × 97 × 97)/100^{3}

B 
(99 × 98 × 97)/100^{3}

(97 × 96 × 95)/100^{3}


(97 × 96 × 95)/(3! × 100^{3})

Explanation:
Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. (Source: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29).
Probability that the first 3 slots are unfilled after the first 3 insertions =
(probability that first item doesn't go in any of the first 3 slots)*
(probability that second item doesn't go in any of the first 3 slots)*
(probability that third item doesn't go in any of the first 3 slots)
= (97/100) * (97/100) * (97/100)
Question 51

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChildrightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr; struct treeNode { treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) { int value=0; if (tree != NULL) { if (tree>leftMostChild == NULL) value = 1; else value = DoSomething(tree>leftMostChild); value = value + DoSomething(tree>rightSibling); } return (value); } 
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
A 
number of internal nodes in the tree.

height of the tree.


number of nodes without a right sibling in the tree.


D 
number of leaf nodes in the tree.

Explanation:
The function counts leaf nodes for a tree represented using leftMostChildrightSibling representation. Below is function with comments added to demonstrate how function works. 1
Question 52

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.
int ProcessArray( int *listA, int x, int n) { int i, j, k; i = 0; j = n1; do { k = (i+j)/2; if (x <= listA[k]) j = k1; if (listA[k] <= x) i = k+1; } while (i <= j); if (listA[k] == x) return (k); else return 1; } 
Which one of the following statements about the function ProcessArray is CORRECT?
It will run into an infinite loop when x is not in listA.


B 
It is an implementation of binary search.

It will always find the maximum element in listA.


It will return −1 even when x is present in listA.

Explanation:
The function is iterative implementation of Binary Search.
k keeps track of current middle element.
i and j keep track of left and right corners
of current subarray
Question 53

A 
1.5

1.4


C 
1.8

2.5

Explanation:
Each one takes average 1CPI.
In 1st case 80% take 1 clock and 20% take 3 clocks so total time:
p = (.8*1 + .2*3)*2.2=3.08.
q = (.8*1 + 6*.2)*1=2
p/q = 1.54
Question 54

1.26


B 
1.68

C 
2.46

4.52

Explanation:
The question is to find the time taken for, "100 fetch operation and 60 operand red operations and 40 memory operand write operations"/"total number of instructions". Total number of instructions= 100+60+40 =200 Time taken for 100 fetch operations(fetch =read) = 100*((0.9*1)+(0.1*5)) // 1 corresponds to time taken for read // when there is cache hit = 140 ns //0.9 is cache hit rate Time taken for 60 read operations = 60*((0.9*1)+(0.1*5)) = 84ns Time taken for 40 write operations = 40*((0.9*2)+(0.1*10)) = 112 ns // Here 2 and 10 the time taken for write when there is cache // hit and no cahce hit respectively So,the total time taken for 200 operations is = 140+84+112 = 336ns Average time taken = time taken per operation = 336/200 = 1.68 ns
Question 55

001, 010, 011


111, 110, 101


C 
100, 110, 111

D 
100, 011, 001

Explanation:
JK ff truth table—
j  k  Q 
0  0  Q0 
1  0  1 
0  1  0 
1  1  Q0’ 
Initially Q2Q1Q0=000 Present state FF input Next state
Q2  Q1  Q0  J2  K2  J1  K1  J0  K0  Q2  Q1  Q0 
0  0  0  1  0  0  1  0  1  1  0  0 
1  0  0  1  0  1  0  0  1  1  1  0 
1  1  0  0  0  1  0  1  1  1  1  1 
So ans is ( C) .
Question 56

I Only


II Only


C 
Both I and II

D 
Neither I or II

ANSWER IS C
Question 57

A


B


C


D

ANSWER IS A
Question 58

0.5


B 
0.25

0.225


0.125

Explanation:
Hence max(P(A)*P(B)) = 1/4.
We can think of this problem as flipping a coin, it has two mutually exclusive events ( head and tail , as both can’t occur simultaneously). And sample space S = { head, tail } Now, lets say event A and B are getting a “head” and “tail” respectively. Hence, S = A U B. Therefore, P(A) = 1/2 and P(B) = 1/2. And, P(A).P(B) = 1 /4 = 0.25. Hence option B is the correct choice.
Question 59

There are two elements x, y in a group (G,∗) such that every element in the group can be written as a product of some number of x’s and y’s in some order. It is known that
x ∗ x = y ∗ y = x ∗ y ∗ x ∗ y = y ∗ x ∗ y ∗ x = e
where e is the identity element. The maximum number of elements in such a group is __________.
2


3


C 
4

D 
5

Explanation:
x * x = e, x is its own inverse
y * y = e, y is its own inverse
(x*y) * (x* y) = e, x*y is its own inverse
(y*x) * (y*x) = e, y*x is its own inverse
also x*x*e = e*e can be rewritten as follows
x*y*y*x = e*y*y*e = e, (Since y *y = e)
(x*y) * (y*x) = e shows that (x *y) and (y *x)
are each other’s inverse and we already know that
(x*y) and (y*x) are inverse of its own.
As per (G,*) to be group any element should have
only one inverse element (unique)
This implies x*y = y*x (is one element)
So the elements of such group are 4 which are
{x, y, e, x*y}.
See following definition of group from wikipedia. A group is a set, G, together with an operation • (called the group law of G) that combines any two elements a and b to form another element, denoted a • b or ab. To qualify as a group, the set and operation, (G, •), must satisfy four requirements known as the group axioms:[5] Closure For all a, b in G, the result of the operation, a • b, is also in G.b[›] Associativity For all a, b and c in G, (a • b) • c = a • (b • c). Identity element There exists an element e in G, such that for every element a in G, the equation e • a = a • e = a holds. Such an element is unique (see below), and thus one speaks of the identity element. Inverse element For each a in G, there exists an element b in G such that a • b = b • a = e, where e is the identity element. Source:
Question 60

floor(n/k)


ceil(n/k)


C 
nk

D 
nk+1

Explanation:
Each component will have n/k vertices (pigeonhole principle). Hence, for each component there will be (n/k)1 edges. Since there are k components, total number of edges= k*((n/k)1) = nk.
Question 61
Let d denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with d ≥ 3, which one of the following is TRUE?

A 
In any planar embedding, the number of faces is at least n/2 + 2

In any planar embedding, the number of faces is less than n/2 + 2


C 
There is a planar embedding in which the number of faces is less than n/2 + 2

There is a planar embedding in which the number of faces is at most n/(d+1)

Explanation:
Euler's formula for planar graphs:
v − e + f = 2.
v => Number of vertices
e => Number of edges
f => Number of faces
Since degree of every vertex is at least 3,
below is true from handshaking lemma (Sum of
degrees is twice the number of edges)
3v >= 2e
3v/2 >= e
Putting these values in Euler's formula.
v  3v/2 + f >= 2
f >= v/2 + 2
Question 62

Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements:
P. For each such function it must be the case that for every i, f(i) = i. Q. For each such function it must be the case that for some i, f(i) = i. R. Each such function must be onto.
Which one of the following is CORRECT?
P, Q and R are true


B 
Only Q and R are true

C 
Only P and Q are true

Only R is true

Explanation:
This kind of functions are called identity functions. We assume f(i) = k. So, f(k) = i. Now, since the values of ‘ i ‘ and ‘ j ‘ would be same for atleast some values if the domain and co – domain intersect, which is true for the given question, Q is definitely true. But this might not happen for all the values of ‘ i ‘, hence, P is not always true. Now, ‘ i ‘ ranges from 0 to 2014, so, it takes 2015 possible values. From the definition of a function, we know that for each input to the function, we have a unique output. Also, in the given question, domain and co – domain are exactly same. Therefore, the function is onto and hence, R is definitely true. Thus, the correct option is B.
Question 63

A


B


C


D 
D

Explanation:
(A) Note that (p ∧ ~q) ≡ ~(p > q). So it means rainy day to cold implication is false for all days. Which means nonrainy days are cold. (B) For all days, if day is not rainy, then it is cold [NonRainy days are cold] (C) There exist some days for which not rainy implies cold. [Some nonrainy days are cold] (D) Note that (p ∧ ~q) ≡ ~(p > q). So it means rainy day to cold implication is false for some days. Which means not all rainy days are cold.
Question 64

Consider the following relational schema:
employee(empId, empName, empDept) customer(custId, custName, salesRepId, rating)
salesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?
SELECT empName FROM employee E WHERE NOT EXISTS (SELECT custId FROM customer C WHERE C.salesRepId = E.empId AND C.rating <> ’GOOD’);
A 
Names of all the employees with at least one of their customers having a ‘GOOD’ rating.

Names of all the employees with at most one of their customers having a ‘GOOD’ rating.


Names of all the employees with none of their customers having a ‘GOOD’ rating.


D 
Names of all the employees with all their customers having a ‘GOOD’ rating.

Explanation:
If any employee has received rating other than 'good' from some customer,
then there will be some rows returned by the inner query.
And not exists will return false so that employee won't be printed
only those employees which have got rating good from all their
customers will be printed.
Question 65

Let X denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary constants. Consider the following Boolean expression for F over two variables P and Q:
F(P, Q) = ( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )
The equivalent expression for F is
P + Q


B 
(P + Q)’

P X Q


D 
(P X Q)’

Explanation:
We need to simplify the above expression. As the given operation is XOR, we shall see property of XOR. Let A and B be boolean variable. In A XOR B, the result is 1 if both the bits/inputs are different, else 0. Now,
( ( 1 X P) X (P X Q) ) X ( (P X Q) X (Q X 0) )
( P' X P X Q ) X ( P X Q X Q ) ( as 1 X P = P' and Q X 0 = Q )
(1 X Q) X ( P X 0) ( as P' X P = 1 , and Q X Q = 0 )
Q' X P ( as 1 X Q = Q' and P X 0 = P )
PQ + P'Q' ( XOR Expansion, A X B = AB' + A'B )
This is the final simplified expression.
Now we need to check for the options.
If we simplify option D expression.
( P X Q )' = ( PQ' + P'Q )' ( XOR Expansion, A X B = AB' + A'B )
((PQ')'.(P'Q)') ( De Morgan's law )
( P'+ Q).(P + Q') ( De Morgan's law )
P'P + PQ + P'Q' + QQ'
PQ + P'Q' ( as PP' = 0 and QQ' = 0 )
Hence both the equations are same. Therefore Option D.
source: geeksforgeeks