Question 1

**Which of the following options is the closest in meaning to the phrase underlined in the sentence below?**

It is fascinating to see life forms

It is fascinating to see life forms

__cope with__varied environmental conditions.A : Adopt to

B : Adapt to

C : Adept in

D : Accept with

.

Correct answer is : B

Question 2

**Choose the most appropriate word from the options given below to complete the following sentence.**

He could not understand the judges awarding her the first prize, because he thought that her performance was quite ___________________.

He could not understand the judges awarding her the first prize, because he thought that her performance was quite ___________________.

A : Superb

B : Medium

C : Mediocre

D : Exhilarating

.

Correct answer is : C

Question 3

**In a press meet on the recent scam, the minister said, “The buck stops here”. What did the minister convey by the statement?**

A : He wants all the money

B : He will return the money

C : He will assume final responsibility

D : He will resist all enquiries

.

Correct answer is : C

Question 4

**If (z+ 1/z)**

^{2}= 98 ,compute (z^{2}+ 1/z^{2}).

Correct answer is : 96

Solution :

z

^{2}+ 1/z

^{2}+ 2z.(1/z) = 98 => z

^{2}+ 1/z

^{2}= 96

Question 5

**The roots of ax**

^{2}+ bx + c = 0 are real and positive a, b and c are real. Then ax^{2}+ b |x| + c = 0 hasA : No roots

B : 2 real roots

C : 3 real roots

D : 4 real roots

.

Correct answer is : D

Question 6

**The Palghat Gap (or Palakkad Gap), a region about 30 km wide in the southern part of the Western Ghats in India, is lower than the hilly terrain to its north and south. The exact reasons for the formation of this gap are not clear. It results in the neighbouring regions of Tamil Nadu getting more rainfall from the South West monsoon and the neighbouring regions of Kerala having higher summer temperatures.**

What can be inferred from this passage?

What can be inferred from this passage?

A : The Palghat gap is caused by high rainfall and high temperatures in southern Tamil Nadu and Kerala

B : The regions in Tamil Nadu and Kerala that are near the Palghat Gap are low–lying

C : The low terrain of the Palghat Gap has a significant impact on weather patterns in neighbouring part

D : Higher summer temperatures result in higher rainfall near the Palghat Gap area

.

Correct answer is : C

Question 7

**Geneticists say that they are very close to confirming the genetic roots of psychiatric illnesses such as depression and schizophrenia, and consequently, that doctors will be able to eradicate these diseases through early identification and gene therapy.**

On which of the following assumptions does the statement above rely?

On which of the following assumptions does the statement above rely?

A : Strategies are now available for eliminating psychiatric illnesses

B : Certain psychiatric illnesses have a genetic basis

C : All human diseases can be traced back to genes and how they are expressed

D : In the future, genetics will become the only relevant field for identifying psychiatric illnesses

.

Correct answer is : B

Question 8

**Round–trip tickets to a tourist destination are eligible for a discount of 10% on the total fare. In addition, groups of 4 or more get a discount of 5% on the total fare. If the one way single person fare is Rs 100, a group of 5 tourists purchasing round–trip tickets will be charged Rs ___________**

.

Correct answer is : 850

Solution :

One way force =100 , Two way fare per person=200

5 persons=1000/- Total discount applicable=10+5=15%

Discount amount = 15 * 1000/100 = 150

Amount to be paid=1000-150=850

Question 9

**In a survey, 300 respondents were asked whether they own a vehicle or not. If yes, they were further asked to mention whether they own a car or scooter or both. Their responses are tabulated below. What percent of respondents do not own a scooter?**

.

Correct answer is : 48

Solution :

Total respondents=300 Those who don’t have scooter

Men= 40+20=60 84 Women =34+ 50=84/144

%= 144/300*100 = 48%

Question 10

**When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created with these lines? _______________________**

.

Correct answer is : 6

Solution :

We have a point say X and 4 sides say P,Q,R and S. A plane is formed by combination of 2 sides and center X. So

^{4}C

_{2}= 6

Question 11

**Consider the statement:**

“Not all that glitters is gold”

Predicate glitters (x) is true if x glitters and predicate gold (x) is true if x is gold. Which one of the following logical formulae represents the above statement?

“Not all that glitters is gold”

Predicate glitters (x) is true if x glitters and predicate gold (x) is true if x is gold. Which one of the following logical formulae represents the above statement?

A : ∀x glitter (x) => ¬gold(x)

B : ∀xgold(x) => glitter(x)

C : ∃xgold(x) ∧ ¬ glitter(x)

D : ∃ glitter(x) ∧ ¬ gold(x)

.

Correct answer is : D

Solution :

It means “It is false that every glitter is gold” or “some glitters are not gold”. Then we can say “atleast one glitter object is not gold”.

Question 12

**Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .**

.

Correct answer is : 0.25

Solution :

The smaller sticks, therefore, will range in length from almost 0 meters up to a maximum of 0.5 meters, with each length equally possible.

Thus, the average length will be about 0.25 meters, or about a quarter of the stick.

Question 13

**Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?**

A : G

_{1}= (V,E

_{1}) where E

_{1}= { (u,v) | (u,v) ∉ E }

B : G

_{2}= (V,E

_{2}) where E

_{2}= { (u,v) | (v,u) ∈ E }

C : G

_{3}= (V,E

_{3}) where E

_{1}= { (u,v) | there is a path of length <=2 from

D : G

_{4}= (V

_{4},E) where V

_{4}is the set of vertices in G which are not isol

.

Correct answer is : B

Question 14

**Consider the following system of equations:**

3x + 2y= 1

4x +7z=1

x + y + z = 3

x - 2y + 7z = 0

The number of solutions for this system is __________________

3x + 2y= 1

4x +7z=1

x + y + z = 3

x - 2y + 7z = 0

The number of solutions for this system is __________________

.

Correct answer is : 1

Question 15

**The value of the dot product of the eigenvectors corresponding to any pair of different eigen values of a 4-by-4 symmetric positive definite matrix is ______________.**

.

Correct answer is : 0

Solution :

( The eigen vectors corresponding to distinct eigen values of real symmetric matrix are orthogonal)

Question 16

**Let the function given below where θ = ∈ [ π/6 , π/2] and f'(θ) denote the derivative of f with respect to θ . Which of the following statement is / are TRUE?**

(I) There exists θ ∈ (π/6 ,&pi/;3) such that f'(θ) = 0

(I) There exists θ ∈ (π/6 ,π/3) such that f'(θ) ≠ 0

(I) There exists θ ∈ (π/6 ,&pi/;3) such that f'(θ) = 0

(I) There exists θ ∈ (π/6 ,π/3) such that f'(θ) ≠ 0

A : I only

B : II only

C : Both I and II

D : Neither I and II

.

Correct answer is : C

Solution :

By mean value theorem

Question 17

**Consider the following Boolean expression for F:**

F(P,Q,R,S) = PQ + P'QR + P`QR`S

The minimal sum-of products form of F is

F(P,Q,R,S) = PQ + P'QR + P`QR`S

The minimal sum-of products form of F is

A : PQ+ QR + QS

B : P +Q + R + S

C : P` +Q` + R` + S`

D : P'R + (PR)`S + P

.

Correct answer is : A

Solution :

PQ + P`QR + P`QR`S

=PQ +P`Q( R+ R`S)

=PQ+P`Q((R+R`)(R+S)) [because A+BC = (A+B)(A+C)]

=PQ+P`Q(R+S) [because R+R`=1]

=Q(P+P`(R+S))

Q((P+P`)(P+R+S))

=Q(P+R+S)

=PQ+QR+QS

Question 18

**The base (or radix) of the number system such that the following equation holds is____________.**

312/20 = 13.1

312/20 = 13.1

.

Correct answer is : 5

Solution :

Let the base be x and if we convert it into decimal equivalent we get the following equation :

(3x

^{2}+ x + 2) / 2x = x + 3 + 1/x

Solving which we get 3x

^{2}+ x + 2 = 2x

^{2}+ 6x + 2

solve the above equation and get x = 5

Question 19

**A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________.**

.

Correct answer is : 16383

Solution :

1 Word = 32 bits

Each instruction has 32 bits

To support 45 instructions, opcode must contain 6-bits

Register operand1 requires 6 bits, since the total registers are 64.

Register operand 2 also requires 6 bits

Opcode(6) | Reg opd 1(6) | Reg opd 2(6) | immediate opnd(14) |

14-bits are left over for immediate Operand Using 14-bits, we can give maximum 16383, Since 2

^{14}= 16384

Question 20

**Consider the following program in C language:**

# include

main ()

{

int i;

int * pi =&i;

scanf( "%d", pi );

printf( "%d \ n", i+5) ;

}

Which one of the following statements is TRUE?

# include

main ()

{

int i;

int * pi =&i;

scanf( "%d", pi );

printf( "%d \ n", i+5) ;

}

Which one of the following statements is TRUE?

A : Compilation fails.

B : Execution results in a run-time error.

C : On execution, the value printed is 5 more than the address of variable i.

D : On execution, the value printed is 5 more than the integer value entered.

.

Correct answer is : D

Solution :

pi contains the address of i. So scanf("%d",pi) places the value entered in console into variable i.e So printf("%d\n",i+5),prints 5 more than the value entered in console.

Question 21

**Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?**

A : θ (n)

B : θ (n+m)

C : θ (n

^{2})

D : θ (m

^{2})

.

Correct answer is : C

Solution :

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V

^{2})

Question 22

**Consider rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having exactly 4 nodes is O(n**

^{a}log n^{b}). Then the value of a + 10b is_______.

Correct answer is : 1

Solution :

int print_subtrees_size_4(node *n)

{

int size=0;

if(node==null)

return 0;

size=print_subtrees_size_4(node->left)+print_subtrees_size_4(node->right)+1;

if(size==4)

printf("this is a subtree of size 4");

return size;

}

The above function on taking input the root of a binary tree prints all the subtrees of size 4 in O(n) time

Question 23

**Consider the directed graph given below.**

Which one of the following is TRUE?

Note: Edge is from R to Q

Which one of the following is TRUE?

Note: Edge is from R to Q

A : The graph does not have any topological ordering

B : Both PQRS and SRQP are topological orderings

C : Both PSRQ and SPRQ are topological orderings.

D : PSRQ is the only topological ordering.

.

Correct answer is : C

Solution :

Topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. Topological ordering is possible iff graph has no directed cycles.

(A) As the given graph doesn’t contain any directed cycles, it has at least one topological ordering. So option (A) is false

(B) PQRS cannot be topological ordering because S should come before R in the ordering as there is a directed edge from S to R and Q

Question 24

**Let P be a quick sort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?**

A : t1=5

B : t1 < t2

C : t1 > t2

D : t1 = t2

.

Correct answer is : C

Solution :

Partition algorithm for quick sort

Partition (A,P,q) //A [P,.....]

x <- A [P[ // pivot A= [P]

i <-P

for j= P + 1 to q

do if A [j] <= x

then i <- i + 1

exchange A [i] <-> A [j]

exchange A [P] <-> A [i]

return i [returning where pivot element is there after partitioning]

Recursively call the above algorithm for the two sub arrays [elements before and after pivot element] to complete the sorting.

Question 25

**Which one of the following is TRUE?**

A : The language L = { a

^{n}b

^{n}| n >= 0} is regular.

B : The language L = { a

^{n}| n is prime } is regular.

C : The language L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} } is regular.

D : The language L ={ww | w ∈ ∑* with ∑ = {0,1} } is regular

.

Correct answer is : C

Solution :

(A) { a

^{n}b

^{n}| n >= 0} is a CFL but not regular, it requires memory for the representati

(B) L = { a

^{n}| n is prime } is neither regular nor CFL

(C) L = { w | w has 3k +1b's for some k ∈ N with ∑ = {a,b} }

is a regular language, since the total count of b’s are multiple of 3 plus one. The regular expression is a * ba *(a *ba *ba * ba *)*+(a * ba * ba * ba *)*a * ba *

L ={ww | w ∈ ∑* with ∑ = {0,1} } is neither regular nor CFL

Question 26

**Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?**

A : { q

_{0},q

_{1},q

_{2}}

B : { q

_{0},q

_{1}}

C : { q

_{0},q

_{1},q

_{2},q

_{3}}

D : { q

_{3}}

.

Correct answer is : A

Solution :

d(q0 ,0011) = d(q0 ,011)

=d(q0,11)

=d({q0,q1},1)

=d(q0,1) U d(q1,1)

={q0,q1} U {q2}

{q0,q1,q2}

Question 27

**Which one of the following is FALSE?**

A : A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end

B : Available expression analysis can be used for common subexpression elimination.

C : Live variable analysis can be used for dead code elimination

D : x = 4*5 -> x = 20 is an example of common subexpression elimination

.

Correct answer is : D

Solution :

x = 4 × 5 => x = 20 is not an example of common sub-expression but it is constant folding. In constant folding expression consisting of constants will be replaced by their final value at compile time, rather than doing the calculation in run-time.

Question 28

**Match the following**

A : 1-a, 2-b, 3-c, 4-d

B : 1-d, 2-a, 3-b, 4-c

C : 1-d, 2-b, 3-a, 4-c

D : 1-c, 2-a, 3-b, 4-d

.

Correct answer is : B

Solution :

The main drawback of the waterfall model is the difficulty of accommodating change after the process is underway. One phase has to be complete before moving onto the next phase. Inflexible partitioning of the project into distinct stages in waterfall model makes it difficult to respond to changing customer requirements

Evolutionary software models are iterative. They are characterized in manner that enables the software engineers to develop increasingly more complete version of software.

Question 29

**Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.**

.

Correct answer is : 3

Solution :

Request for cylinder is served after serving 3 requests (100,105 and 110)

Question 30

**Which one of the following is FALSE?**

A : User level threads are not scheduled by the kernel.

B : When a user level thread is blocked, all other threads of its process are blocked.

C : Context switching between user level threads is faster than context switching between kernel level threads

D : Kernel level threads cannot share the code segment.

.

Correct answer is : D

Solution :

User threads are supported above the kernel and a managed without kernel support. The thread function library to implement user level threads usually runs on top of the system in user mode. Thus these threads with in a process are invisible to the operating system. Since the kernel is unaware of the existence of such threads; when one user level thread is blocked in the kernel all other threads of its process are blocked. So options (A) and (B) are true

(C) Kernel-level threads require a context switch, which involves changing a large set of processor registers that define the current memory map and permissions. It also evicts some or all of the processor cache. User-level threads just require a small amount of bookkeeping within one kernel thread or process.

Question 31

**Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies**

{{E,F}-> {G}

{F}-> {I, J}

{E,H}->{K,L}

{K}->{M}

{L}->{N} }

on R. What is the key for R?

{{E,F}-> {G}

{F}-> {I, J}

{E,H}->{K,L}

{K}->{M}

{L}->{N} }

on R. What is the key for R?

A : {E.F}

B : {E.F,H}

C : {E.F,H,K,L}

D : {E}

.

Correct answer is : B

Solution :

R(EFGHI,JKLMN)

F = {

EF->G

F->IJ

EH->KL

K->M

L->N

}

(EF)

^{+}= EFGIJ, E&F + = Together functionally derive GIJ and if we observe given FDs, H can’t be determined by any other attributes. So H must be part of all the (candidate) keys. H along with E determines K and L, K & L functionally determine M and N respectively.

(EFH)

^{+}= EFGIJHKLMN

EFH is the only candidate for key.

Question 32

**Given the following statements:**

S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL

S2: Given the table R(a,b,c) where a and b together form the primary key, the following is a valid table definition.

CREATE TABLE S (

a INTEGER,

d INTEGER,

e INTEGER,

PRIMARY KEY (d),

FOREIGN KEY (a) references R)

Which one of the following statements is CORRECT?

S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL

S2: Given the table R(a,b,c) where a and b together form the primary key, the following is a valid table definition.

CREATE TABLE S (

a INTEGER,

d INTEGER,

e INTEGER,

PRIMARY KEY (d),

FOREIGN KEY (a) references R)

Which one of the following statements is CORRECT?

A : S1 is TRUE and S2 is a FALSE

B : Both S1 and S2 are TRUE

C : S1 is FALSE and S2 is a TRUE

D : Both S1 and S2 are FALSE

.

Correct answer is : D

Solution :

Check assertions are not sufficient to replace foreign key. Foreign key declaration may have cascade delete which is not possible by just check insertion.

Foreign key in one table should uniquely identifies a row of other table. In above table definition, table S has a foreign key that refers to field a of R. The field a in table R doesnt uniquely identify a row in table R.

Question 33

**Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links**

[S1] The computational overhead in link state protocols is higher than in distance vector protocols.

[S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol.

[S3] After a topology change, a link state protocol will converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2, and S3?

[S1] The computational overhead in link state protocols is higher than in distance vector protocols.

[S2] A distance vector protocol (with split horizon) avoids persistent routing loops, but not a link state protocol.

[S3] After a topology change, a link state protocol will converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2, and S3?

A : S1, S2, and S3 are all true

B : S1, S2, and S3 are all false.

C : S1 and S2 are true, but S3 is false

D : S1 and S3 are true, but S2 is false.

.

Correct answer is : D

Solution :

The DV rely on the info from directly connected neighbours in order to calculate and accumulate route information. DV require very little overhead as compared to LS. LS uses data from whole link for generating the routing table so huge overhead is there.

S3 is also true as Distance Vector protocol has count to infinity problem and converges slower.

S2 is false. In distance vector protocol, split horizon with poison reverse reduces the chance of forming loops and uses a maximum number of hops to counter the 'count-to-infinity' problem. These measures avoid the formation of routing loops in some, but not all, cases

Question 34

**Which one of the following are used to generate a message digest by the network security protocols?**

(P) RSA

(Q)SHA - I

(R) DES

(S) MD5

(P) RSA

(Q)SHA - I

(R) DES

(S) MD5

A : P and R only

B : Q and R only

C : Q and S only

D : R and S only

.

Correct answer is : C

Solution :

RSA and DES are for Encryption where MD5 and SHA – 1 are used to generate Message Digest.

Question 35

**Identify the correct order in which the following actions take place in an interaction between a web browser and a web server.**

1. The web browser requests a webpage using HTTP.

2. The web browser establishes a TCP connection with the web server.

3. The web server sends the requested webpage using HTTP.

4. The web browser resolves the domain name using DNS.

1. The web browser requests a webpage using HTTP.

2. The web browser establishes a TCP connection with the web server.

3. The web server sends the requested webpage using HTTP.

4. The web browser resolves the domain name using DNS.

A : 4,2,1,3

B : 1,2,3,4

C : 4,1,2,3

D : 2,4,1,3

.

Correct answer is : A

Solution :

First of all the browser must now know what IP to connect to. For this purpose browser takes help of Domain name system (DNS) servers which are used for resolving hostnames to IP addresses. As browser is an HTTP client and as HTTP is based on the TCP/IP protocols, first it establishes a TCP connection with the web server and requests a webpage using HTTP, and then the web server sends the requested webpage using HTTP. Hence the order is 4,2,1,3

Question 36

**Consider a token ring network with a length of 2km having 10 stations including a monitoring station. The propagation speed of the signal is 2 x 108 m/s and the token transmission time is ignored. If each station is allowed to hold the token for 2 microsec, the minimum time for which the monitoring station should wait (in microsec) before assuming that the token is lost is _______.**

.

Correct answer is : 30

Solution :

Given Length (d) = 2 Km

No. of Stations (m) = 10 Propagation Speed (v) = 2 × 10

^{8}m/s

THT = 2?s

So, Max. TRT = T

_{P}in the Ring + No. of Active Stations * THT

=10 × 10

^{-6}+ 10 × 2 × 10

^{-6}

=30 s

Question 37

**Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2kB. The time taken (in msec) by the TCP connection to get back to 32KB congestion window is ______**

.

Correct answer is : 1100 to 1300

Solution :

Given that at the time of Time Out, Congestion Window Size is 32KB and RTT = 100ms When Time Out occurs, for the next round of Slow Start, Threshold = (size of Cwnd) / 2 It means Threshold = 16KB

Slow Start 2KB

1RTT

4KB

2RTT

8KB

3RTT

16KB ----------- Threshold reaches. So Additive Increase Starts

4RTT

18KB

5RTT

20KB

6RTT

22KB

7RTT

24KB

8RTT

26KB

9RTT

28KB

10RTT

30KB

11RTT

32KB

So, Total no. of RTTs = 11

Question 38

**Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.**

.

Correct answer is : 5

Solution :

Given L =1KB

B= 1.5Mbps

T

_{p}=50ms

η = 60%

Efficiency formula for SR protocol is

η = W/(1+2a)= 60/100

T

_{x}= L/B = 8000/1.5 * 10

^{6}= 5.3 ms

a= T

_{p}/T

_{x}=50/5.3 = 500/53 = 9.43

=60/100 = W/19.86 => W= 11.9 ≅ 12

W = 2

^{n-1}= 12 => 2

^{n}= 24 ≅ = 2

^{5}=> n=5

Question 39

**Consider the following four schedules due to three transactions (indicted by the subscript) using read and write on a data item x, denoted r (x) and w (x) respectively. Which one of them is conflict serializable?**

A : r1 (x) ; r2 (x) ; w1 (x) ; r3(x) ; w2 (x)

B : r2 (x) ; r1 (x) ; w2 (x) ; r3(x) ; w1 (x)

C : r3 (x) ; r2 (x) ; r1 (x) ; w2(x) ; w1 (x)

D : r2 (x) ; w2 (x) ; r3 (x) ; r1(x) ; w1 (x)

.

Correct answer is : D

Solution :

If there is a cycle in precedence graph, then the schedule is not conflict serializable.

Question 40

**Given the following two statements:**

S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF

S2 : AB->C, D -> E, E->C is a minimal cover for the set of functional dependencies AB->C, D -> E, AB -> E,E -> C Which one of the following is CORRECT?

S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF

S2 : AB->C, D -> E, E->C is a minimal cover for the set of functional dependencies AB->C, D -> E, AB -> E,E -> C Which one of the following is CORRECT?

A : S1 is TRUE and S2 is FALSE.

B : Both S1 and S2 are TRUE.

C : S1 is FALSE and S2 is TRUE.

D : Both S1 and S2 are FALSE.

.

Correct answer is : A

Question 41

**An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.**

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z

REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z

REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z

Which one of the following is TRUE?

A : Only REQ1 can be permitted.

B : Only REQ2 can be permitted.

C : Both REQ1 and REQ2 can be permitted.

D : Neither REQ1 and REQ2 can be permitted.

.

Correct answer is : B

Question 42

**Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds**

Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ____________________.

Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ____________________.

Process Name Arrival Time Execution Time A 0 6 B 3 2 c 5 4 D 7 6 E 10 3

.

Correct answer is : 7.2

Solution :

Average turn around time = (8-0)+(5-3)+(12-5)+(21-7)+(15-10)/5 = 36/5 = 7.2ms

Question 43

**Assume that there are 3 page frames which are initially empty. If the page reference string 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is ___________**

.

Correct answer is : 7

Question 44

**A canonical set of items is given below**

s -> L.> R

Q -> R.

On input symbol < the set has

s -> L.> R

Q -> R.

On input symbol < the set has

A : a shift-reduce conflict and a reduce-reduce conflict.

B : a shift-reduce conflict but not a reduce-reduce conflict

C : a reduce-reduce conflict but not a shift-reduce conflict.

D : neither a shift-reduce nor a reduce-reduce conflict.

.

Correct answer is : D

Solution :

From the diagram, we can see that there is no shift- reduce or reduce-reduce conflict.

Question 45

**Let L be a language and L` be its complement. Which of the following is NOT a viable possibility?**

A : Neither L nor L` is recursively enumerable (r.e.).

B : One of L and L` is r.e. but not recursive; the other is not r.e.

C : Both L and L` are r.e. but not recursive.

D : Both L and L` are recursive.

.

Correct answer is : C

Solution :

Recursive languages are closed under complement.

If a language L is recursive enumerable but not recursive then its complement is not a recursive enumerable, so both L and L' are recursive enumerable but not recursive is not a viable possibility.

Question 46

**Which of the regular expressions given below represent the following DFA?**

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

A : I and II only

B : I and III only

C : II and III only

D : I, II and III

.

Correct answer is : B

Solution :

Given DFA will accept all the strings over e ={0,1} which are ending with 1.

0*1(1+ 00*1)* and(0 +1)*1, are the regular expressions for ending with 1.

Question 47

**There are 5 bags labelled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is ___.**

.

Correct answer is : 12

Solution :

Let the weight of coins in the respective bags (1 through 5) be a,b,c,d and e-each of which can take one of two values namely 10 or 11 (gm).

Now, the given information on total weight can be expressed as the following equation:

1.a+2.b+4.c+8.d+16.e = 323

a must be odd => a = 11

The equation then becomes: 11+2.b+4.c+8.d+16.e = 323

=>2.b+4.c+8.d+16.e = 312

=>b+2.c+4.d+8.e = 156

b must be even b = 10

The equation then becomes: 10+2.c+4.d+8.e = 156

=>2.c+4.d+8.e = 146

=> c+2.d+4.e = 73

c must be odd c = 11

The equation now becomes: 11+2.d+4.e = 73

=>2.d+4.e = 62

=>d+2.e = 31

e = 11 and e = 10

Therefore, bags labelled 1, 3 and 4 contain 11 gm coins => Required Product = 1*3*4* = 12.

Question 48

**Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?**

A : B :

C : D :

.

Correct answer is : D

Solution :

The most important open question in complexity theory is whether the P = NP , which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems ( since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.

Question 49

**The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.**

.

Correct answer is : 148

Solution :

To find minimum and maximum element out of n numbers, we need to have at least (3n/2-2) comparisons.

Question 50

**Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are**

A : 3,0 and 1

B : 3,3 and 3

C : 4,0 and 1

D : 3,0 and 2

.

Correct answer is : A

Solution :

Maximum&minimum chain lengths are 3&0 respectively

Average chain length = 0+3+1+1+0+1+2+0+1/9 = 1

Question 51

**Consider the following C function in which size is the number of elements in the array E:**

int MyX(int *E, unsigned int size)

{

int Y = 0;

int Z;

int i, j, k;

for(i = 0; i < size; i++)

Y = Y + E[i];

for(i = 0; i < size; i++)

for(j = i; j < size; j++)

{

Z = 0;

for(k = i; k <= j; k++)

Z = Z + E[k];

if (Z > Y)

Y = Z;

}

return Y;

}

The value returned by the function MyX is the

int MyX(int *E, unsigned int size)

{

int Y = 0;

int Z;

int i, j, k;

for(i = 0; i < size; i++)

Y = Y + E[i];

for(i = 0; i < size; i++)

for(j = i; j < size; j++)

{

Z = 0;

for(k = i; k <= j; k++)

Z = Z + E[k];

if (Z > Y)

Y = Z;

}

return Y;

}

The value returned by the function MyX is the

A : maximum possible sum of elements in any sub-array of array E.

B : maximum element in any sub-array of array E.

C : sum of the maximum elements in all possible sub-arrays of array E.

D : the sum of all the elements in the array E.

.

Correct answer is : A

Question 52

**Consider the following pseudo code. What is the total number of multiplications to be performed?**

D= 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3

D= 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3

A : Half of the product of the 3 consecutive integers

B : One-third of the product of the 3 consecutive integers.

C : One-sixth of the product of the 3 consecutive integers.

D : None of the above.

.

Correct answer is : C

Question 53

**Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6- stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.**

.

Correct answer is : 4

Solution :

For 6 stages, non- pipelining takes 6 cycles.

There were 2 stall cycles for pipelining for 25% of the instructions

So pipeline time = (1+25/100*2) = 3/2 =1.5

Speed up = Non - pipeline time/pipeline time = 6/1.5 =4

Question 54

**An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A >= k exercising least-recently-used replacement policy?**

A : n/N

B : 1//N

C : 1/A

D : k/n

.

Correct answer is : A

Question 55

**Consider the 4-to-1 multiplexer with two lines S1 and S0 given below.**

The minimal sum of-products form of the Boolean expression for the output F of the multiplexer is

The minimal sum of-products form of the Boolean expression for the output F of the multiplexer is

A : P`Q+ QR + PQ`R

B : P`Q + P`QR` + PQR` + PQ`R

C : P`QR + P`QR` + QR` + PQ`R

D : PQR`

.

Correct answer is : A

Solution :

Hence the minimized expression is P`Q + QR` + PQ`R

Question 56

**The function f(x) = x sin x satisfies the following equation. f"(x) + f(x) +tcosx = 0. The value of t is______.**

.

Correct answer is : -2

Solution :

Given f "(x) +f (x)+ t cos x =0

and f(x)= xsin x

f '(x)= x cos x + sin x

f "(x)= x(- sin x) + cos x + cos x

= 2cos x - xsin x

= 2cos x - f(x)

2cos x - f(x)+ f(x) +t cos x = 0

=> 2cos x= -t cos x=> t= -2

Question 57

**A function f(x) is continuous the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) = 1. Which one of the following statements must be true?**

A : There exists a y in the interval (0,1) such that f(y) = f(y + 1)

B : For every y in the interval (0,1), f(y) = f(2 - y)

C : The maximum value of the function in the interval (0.2) is 1

D : There exists a y in the interval (0,1) such that f(y) =f(2 – y)

.

Correct answer is : A

Solution :

Define g(x) =f(x)-f(x+1) in [0,1]. g(0) is negative and g(1) is positive. By intermediate value

theorem there is y€(0,1) such that g(y)=0

That is f(y) =f(y+1).

Thus answer is (a)

Question 58

**Four fair six-sided dice are rolled. The probability that the sum of the results being 22is X/1296.The value of X is ______________.**

.

Correct answer is : 10

Solution :

22 occurred in following ways

6 6 6 4 -> 4 ways

6 6 5 5 -> 6 ways

Required probability = 6+4/2296 = 10/2296 => x=10

Question 59

**A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1- pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)}and the set of all 3-pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10- pennants is ______________.**

.

Correct answer is : 89

Solution :

No twos: 11111111111=> pennant

Single two: 211111111 => 9!/8!1! = 9 pennants

Two twos: 22111111 => 8!/6!.2! = 28

Three twos: 2221111 => 7!/3!.4! = 35

Four twos: 222211 => 6!/4!.2! = 15

Five twos: 22222 =>1

Total = 89 pennants.

Question 60

**Let S denote the set of all functions f:{0,1}**

^{4}-> {01} . Denote by N the number of functions from S to the set {0,1}. The value of log_{2}log_{2}N is______..

Correct answer is : 16

Solution :

The number of functions from A to B where size of A = |A| and size of B = |B| is |B||A|

{0,1}

^{4}= {0,1} X {0,1} X {0,1}X {0.1} = 16

|S| = 2

^{16}

N=2

^{|S|}

loglogN= loglog 2

^{|S|}= log |S| = log 2

^{16}=16

Question 61

**Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {i, f): 1 <= i <= 12, 1 <= j <= 12}. There is an edge between (a,b) and (c,d) if |a - c| <= 1 and |b - d| <= 1 The number of edges in the graph is _____________.**

.

Correct answer is : 506

Solution :

The graph formed by the description contains 4 vertices of degree 3 and 40verices of degree 5 and 100 vertices of degree 8.

According to sum of the degrees theorem 4*3+40*5+100*8 = 2|E|

|E| = 1012/2 = 506

Question 62

**An ordered n-tuple (d1,d2,…,dn) with d1 >= d2 >= .... >= dn is called graphic if there exists a simple undirected graph with n vertices having degrees d1,d2,.......dn respectively. Which of the following 6-tuples is NOT graphic?**

A : (1, 1, 1, 1, 1, 1)

B : (2, 2, 2, 2, 2, 2)

C : (3, 3, 3, 1, 0, 0)

D : ( 3, 2, 1, 1, 1, 0)

.

Correct answer is : C

Solution :

According to havel-hakimi theorem

(1,1,1,1,1,1) is graphic iff<1,1,1,1,0> is graphic

(0,1,1,1,1) is graphic iff (0,1,1,0) is graphic

(0,0,1,1) is graphic iff (0,0,0) is graphic

Since (0,0,0) is graphic (1,1,1,1,1,1) is also graphic.

(The process is always finding maximum degree and removing it from degree sequence, subtract 1 from each degree for d times from right to left where d is maximum degree)

(2,2,2,2,2,2) is graphic iff (2,2,22-1,2-1) = (2,2,2,1,1) is graphic

(1,1,2,2,2

Question 63

**Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?**

A : ((p <-> q) ∧ r) V (p ∧ q ∧ ~ r)

B : (~ (p <-> q) ∧ r) V (p ∧ q ∧ ~ r)

C : ((p -> q) ∧ r) V (p ∧ q ∧ ~ r)

D : (~ (p <-> q) ∧ r) ∧ (p ∧ q ∧ ~ r)

.

Correct answer is : B

Solution :

P = T q=F and r=T

Option A will become false

Option C will become false.

Option D is always false.

Question 64

**Given the following schema:**

employees(emp-id, first-name, last-name, hire-date, dept-id, salary)

departments(dept-id, dept-name, manager-id, location-id)

You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:

SQL>SELECT last-name, hire-date

FROM employees

WHERE (dept-id, hire-date) IN

(SELECT dept-id, MAX(hire-date)

FROM employees JOIN departments USING(dept-id)

WHERE location-id = 1700

GROUP BY dept-id);

What is the outcome?

employees(emp-id, first-name, last-name, hire-date, dept-id, salary)

departments(dept-id, dept-name, manager-id, location-id)

You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:

SQL>SELECT last-name, hire-date

FROM employees

WHERE (dept-id, hire-date) IN

(SELECT dept-id, MAX(hire-date)

FROM employees JOIN departments USING(dept-id)

WHERE location-id = 1700

GROUP BY dept-id);

What is the outcome?

A : It executes but does not give the correct result.

B : It executes and gives the correct result.

C : It generates an error because of pairwise comparison.

D : It generates an error because the GROUP BY clause cannot be used with table joins in a sub-query.

.

Correct answer is : B

Question 65

**Consider two processors P1 and P2 executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P2 takes 25% less time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on P1. If the clock frequency of P1 is 1GHz, then the clock frequency of P2 (in GHz) is _________.**

.

Correct answer is : 1.6

Solution :

1 cycle time for p1= 10

^{9}/1GH = 1n.s

Assume 1 p takes 5 cycles for a program then p2 takes 20% more, means, 6 cycles. p2 Takes 25% less time, means, if p1 takes 5 n.s, then p2 takes 3.75 n.s. Assume p2 clock frequency is x GHz.

p2 Taken 6 cycles , so 6 * 10

^{9}/ x GH = 3.75 => x=1.6

## Prepjunkie

Home . Contact . About . Disclaimer

Prepjunkie© 2015

Picture Palace Tilak Road Mussoorie, Uttarakhand

contactus@prepjunkie.com

About Prepjunkie PrepJunkie provides comprehensive guidance for entrance exams with well thought of solutions for selected questions, notes, books & much more.