Question 1

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

India is a post-colonial country because

India is a post-colonial country because

A : it was a former British colony

B : Indian Information Technology professionals have colonized the world

C : India does not follow any colonial practices

D : India has helped other countries gain freedom

.

Correct answer is : A

Question 2

**Who ___________ was coming to see us this evening?**

A : you said

B : did you say

C : did you say that

D : had you said

.

Correct answer is : B

Question 3

**Match the columns.**

A : 1:S, 2:P, 3:Q, 4:R

B : 1:P, 2:Q, 3:R, 4:S

C : 1:Q, 2:R, 3:S, 4:P

D : 1:S, 2:P, 3:R, 4:Q

.

Correct answer is : A

Question 4

**What is the average of all multiples of 10 from 2 to 198?**

A : 90

B : 100

C : 110

D : 120

.

Correct answer is : B

Question 5

**The value of 12 + 12 + 12 +............**

A : 3.464

B : 3.932

C : 4.000

D : 4.444

.

Correct answer is : C

Question 6

**The old city of Koenigsberg, which had a German majority population before World War 2, is now called Kaliningrad. After the events of the war, Kaliningrad is now a Russian territory and has a predominantly Russian population. It is bordered by the Baltic Sea on the north and the countries of Poland to the south and west and Lithuania to the east respectively. Which of the statements below can be inferred from this passage?**

A : Kaliningrad was historically Russian in its ethnic make up

B : Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia

C : Koenigsberg was renamed Kaliningrad, as that was its original Russian name

D : Poland and Lithuania are on the route from Kaliningrad to the rest of Russia

.

Correct answer is : B

Question 7

**The number of people diagnosed with dengue fever (contracted from the bite of a mosquito) in north India is twice the number diagnosed last year. Municipal authorities have concluded that measures to control the mosquito population have failed in this region.**

Which one of the following statements, if true, does not contradict this conclusion?

Which one of the following statements, if true, does not contradict this conclusion?

A : A high proportion of the affected population has returned from neighbouring countries where dengue i

B : More cases of dengue are now reported because of an increase in the Municipal Office’s administrativ

C : Many more cases of dengue are being diagnosed this year since the introduction of a new and effectiv

D : The number of people with malarial fever (also contracted from mosquito bites) has increased this ye

.

Correct answer is : D

Question 8

**If x is real and |x**

^{2}- 2x + 3| = 11, then possible values of |-x^{3}+ x^{2}- x| includeA : 2,4

B : 2,14

C : 4,52

D : 14,52

.

Correct answer is : D

Solution :

|x

^{2}- 2x +3 = 11

=> (x-4)(x+2) = 0 => x=4,x=-2

Values of | -x

^{3}+ x

^{2}-x |

For x = 4

Value = 52

for x=-2

Value = 14

Question 9

**The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students doubled in 2009, by what percent did the number of male students increase in 2009?**

.

Correct answer is : 140

Question 10

**At what time between 6 a.m. and 7 a.m will the minute hand and hour hand of a clock make an angle closest to 60°?**

A : 6:22 a. m.

B : 6:27 a. m.

C : 6:38 a. m.

D : 6:45 a. m.

.

Correct answer is : A

Solution :

Speed of the Hour hand = ( 360 degree ) / ( 12 * 60 minutes )

= 0.5 degree / minute.

Speed of the minute hand = ( 360 degree ) / ( 60 minutes )

= 6 degree / minute.

At 6 am, hour hand will point vertically downward to 6 in the clock, and minute hand will point vertically upward to 12 in the clock. ( Hence they are opposite with a gap of 180 degree between them). Now after t minutes , The angle between these two hands will be either of the below two:

(180 - 6t) + 0.5t, when the minute hand is behind the hour hand or,

6t - (180 + 0.5t), when the minute hand is ahead of hour hand,

Now the the question asks for angle of 60 degree.

Hence,

(180 - 6t) + 0.5t = 60 , we get t = 21.8 minute

and

6t - ( 180 + 0.5t ) = 60, we get t = 48 minutes

Question 11

**The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by p Then 100p= _____________.**

.

Correct answer is : 11.85 - 11.95

Solution :

p= P [at least three computers are working]

=P (3 or 4 computers working)

= (4C3) * (6C1) / 10C4 + 4C4 / 10C4 = 5/42

100p=11.9

Question 12

**Each of the nine words in the sentence ”The quick brown fox jumps over the lazy dog” is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is _____________. (The answer should be rounded to one decimal place.**

.

Correct answer is : 3.8889

Question 13

**The maximum number of edges in a bipartite graph on 12 vertices is __________________________.**

.

Correct answer is : 36

Solution :

The number of edges in a bipartite graph on n-vertices is atmost n

^{2}/4

The maximum number of edges in a bipartite graph on 12 –vertices is n

^{2}/4 = 12*12 /4 = 36

Question 14

**If the matrix A is such that**

Then the determinant of A is equal to ________.

Then the determinant of A is equal to ________.

.

Correct answer is : 0

Solution :

|A| = 0

Question 15

**A non-zero polynomial f(x) of degree 3 has roots at x = 1,x = 2 and x = 3. Which one of the following must be TRUE?**

A : f(0) f(4) < 0

B : f(0) f(4) > 0

C : f(0) + f(4) > 0

D : f(0) + f(4) < 0

.

Correct answer is : A

Solution :

Since, the roots of f(x) = 0 i.e., x = 1, 2, 3 lies between 0 and 4 and f(x) is of degree 3

f(0) and f(4) are of opposite signs

f(0).f(4)<0.

Question 16

**The dual of a Boolean function F( x1,x2,...........xn,+,.,` ) written as F**

^{D}, is the same expression as that of F with + and . swapped. F is said to be self-dual if F = F^{D}. The number of self-dual functions with n Boolean variables isA : 2

^{n}

B : 2

^{n-1}

C : 2

^{2n}

D : 2

^{2n-1}

.

Correct answer is : D

Solution :

A function F is self dual if it has equal number of minterms and maxterms, also mutually exclusive terms should not be included.

The number of mutually exclusive terms (pair wise) is 2

^{n}/2 = 2

^{n-1}

Number of functions possible by taking any of the one term from the above mentioned mutually exclusive pair is 2

^{2n-1}.

Question 17

**Let k = 2**

^{n}. A circuit is built by giving the output of an n-bit binary counter as input to an nto- 2^{n}bit decoder. This circuit is equivalent to aA : k-bit binary up counter.

B : k-bit binary down counter.

C : k-bit ring counter.

D : k-bit Johnson counter.

.

Correct answer is : C

Solution :

In case of decoder output, single output will be 1 and remaining will be zero at a time. The output that is high will give the count of the ring counter at that time.

Question 18

**Consider the equation (123)**

_{5}= (x8)_{y}with x and y as unknown. The number of possible solutions is _____ ..

Correct answer is : 3

Solution :

(123)

_{5}= (x8)

_{y}

Converting both sides to decimal:

25 +10 +3 = xy+ 8

xy +8=38 => xy=30

x=1 , y=30

or , x=2 , y=15 or x=3 , y=10

Total number of solutions: 3

Question 19

**A 4-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 size of the physical address space is 4 GB. The number of bits for the TAG field is _____**

.

Correct answer is : 20

Solution :

tag = 32 - (7+5) =20 bits

Question 20

**Consider the function func shown below:**

int func(int num)

{

int count = 0;

while (num)

{

count++;

num>>= 1;

}

return (count);

}

The value returned by func(435)is __________.

int func(int num)

{

int count = 0;

while (num)

{

count++;

num>>= 1;

}

return (count);

}

The value returned by func(435)is __________.

.

Correct answer is : 9

Question 21

**Suppose n and p are unsigned int variables in a C program. We wish to set p to nC3 . If n is large, which one of the following statements is most likely to set p correctly?**

A : p = n * (n – 1) * (n-2) / 6;

B : p = n * (n – 1) / 2 * (n-2) / 3;

C : p = n * (n – 1) / 3 * (n-2) / 2;

D : p = n * (n – 1) / 2 * (n-2) / 6.0;

.

Correct answer is : B

Solution :

n*(n-1) is an even number so we divide it by 2 and the rest by 3. The output will be same but overflow can be avoided.

Question 22

**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, 3, 2, 1, 5

B : 10, 8, 7, 2, 3, 1, 5

C : 10, 8, 7, 1, 2, 3, 5

D : 10, 8, 7, 5, 3, 2, 1

.

Correct answer is : A

Question 23

**Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?**

T(n) = | 2T(n/2) + log n

T(n) = | 2T(n/2) + log n

A : θ (n)

B : θ (nlog n)

C : θ (n

^{2})

D : θ (log n)

.

Correct answer is : A

Question 24

**Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing**

A : the shortest path between every pair of vertices.

B : the shortest path from W to every vertex in the graph.

C : the shortest paths from W to only those nodes that are leaves of T.

D : the longest path in the graph.

.

Correct answer is : B

Solution :

One of the application of BFS algorithm is to find the shortest path between nodes u and v. But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from w to every vertex of the graph

Question 25

**If L1= { a**

(I) L1.L2 is a regular language

(II) L1.L2 = { a

Which one of the following is CORRECT ?

^{n}| n>=0 } and L2 = { b^{n}| n>=0 } , Consider(I) L1.L2 is a regular language

(II) L1.L2 = { a

^{n}b^{n}| n>0 }Which one of the following is CORRECT ?

A : Only I

B : Only II

C : Both I and II

D : Neither I and II

.

Correct answer is : A

Solution :

L1.L2 is also regular since regular languages are closed under concatenation.

But L1.L2 is not { a

^{n}b

^{n}| n >=0 } because both the variable is independent in both languages.

Question 26

**Let m A <=**

_{m}B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?A : If m A <=

_{m}B and B is recursive then A is recursive.

B : If m A <=

_{m}B and A is undecidable then B is undecidable.

C : If m A <=

_{m}B and B is recursively enumerable then A is recursively enumerable.

D : If m A <=

_{m}B and B is not recursively enumerable then A is not recursively enumerable.

.

Correct answer is : D

Question 27

**Consider the grammar defined by the following production rules, with two operators * and +**

S -> T *P

T -> U | T*U

P -> Q + P | Q

Q ->Id

U -> Id

Which one of the following is TRUE?

S -> T *P

T -> U | T*U

P -> Q + P | Q

Q ->Id

U -> Id

Which one of the following is TRUE?

A : + is left associative, while * is right associative

B : + is right associative, while * is left associative

C : Both + and * are right associative

D : Both + and * are left associative

.

Correct answer is : B

Solution :

S->T× P

T-> U | T *U

P -> Q + P |Q

Q -> Id

U -> Id

As the production rule T->T×U is defined as left recursive rule, so * is left associate operator.

As the production rule P->Q + P is defined as right recursive rule, so + is right associative operator.

Question 28

**Which one of the following is NOT performed during compilation?**

A : Dynamic memory allocation

B : Type checking

C : Symbol table management

D : Inline expansion

.

Correct answer is : A

Solution :

Dynamic memory allocation is done after compilation when we have an exe file which is to be loaded in the memory dynamically.

Question 29

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

A : The requirements document also describes how the requirements that are listed in the document are implemented efficiently.

B : Consistency and completeness of functional requirements are always achieved in practice.

C : Prototyping is a method of requirements validation.

D : Requirements review is carried out to find the errors in system design.

.

Correct answer is : C

Question 30

**A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 x 10**

^{6}bytes disk on which the file system is stored and data block size is 10^{3}bytes, the maximum size of a file that can be stored on this disk in units of 10^{6}bytes is ____________..

Correct answer is : 99.55 - 99.65

Solution :

Number of entries in the FAT = Disk Capacity/Block size = 10

^{8}/10

^{3}= 10

^{5}

Total space consumed by FAT = 10

^{5}* 4 B = 0.4 * 10

^{6}B

Maximum size of file that can be stored = 100 * 10

^{6}– 0.4 * 10

^{6}= 99.6 * 10

^{6}B

Answer: 99.6

Question 31

**The maximum number of super keys for the relation schema R (E, F, G, H) with E as the key is __________.**

.

Correct answer is : 8

Solution :

The maximum number of super keys for the relation schema R(E,F,G,H) with E as the key is 2

^{3}= 8 as any subset of non key attributes along with key attribute will form the super key of R.

As we have 3 nonkey all (F, G and H) so subsets will be 2

^{3}

Question 32

**Given an instance of the STUDENTS relation as shown below For (StudentName, StudentAge) to be a key for this instance, the value X should NOT be equal to____________**

.

Correct answer is : 19

Solution :

For (Student Name, student age) to be a key for given instance of STUDENTS relation, the pair value should not get repeated in any two tuples p and q (uniqueness in forced by the definition of key)

Output :-

Shankar age should not b 19

Shankar 19

Question 33

**Which one of the following is TRUE about the interior gateway routing protocols – Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)?**

A : RIP uses distance vector routing and OSPF uses link state routing

B : OSPF uses distance vector routing and RIP uses link state routing

C : Both RIP and OSPF use link state routing

D : Both RIP and OSPF use distance vector routing

.

Correct answer is : A

Solution :

RIP Uses Distance Vector Routing and OSPF uses Link State Routing.

Question 34

**Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?**

A : connect

B : bind

C : listen

D : accept

.

Correct answer is : C

Solution :

(a) The connect function is used by a TCP client to establish a connection with a TCP server.

(b) The bind function assigns a local protocol address to a socket. With the Internet protocols, the protocol address is the combination of either a 32-bit IPv4 address or a 128-bit IPv6 address, along with a 16-bit TCP or UDP port number.

(c) The listen function converts an unconnected socket into a passive socket, indicating that the kernel should accept incoming connection requests directed to it. d) Accepts the connection request after listening.

Question 35

**In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender S and traverses to R, as shown. The links within each ISP and across the two ISPs, are all point-to-point’ optical links. The initial value of the TTL field is 32. The maximum possible value of the TTL field when R receives the datagram is ____________.**

.

Correct answer is : 26

Solution :

The TTL field is set by the sender of the datagram, and reduced by every router on the route to its destination. So, there are 5visits at 5 routers and one visit at receiver R in above figure which leads 32 – 6 = 26.

Question 36

**Consider the store and forward packet switched network given below. Assume that the bandwidth of each link is 10**

^{6}bytes / sec. A user on host A sends a file of size 10^{3}bytes to host B through routers R1 and R2 in three different ways. In the first case a single packet containing the complete file is transmitted from A to B. In the second case, the file is split into 10 equal parts, and these packets are transmitted from A to B. In the third case, the file is split into 20 equal parts and theseA : T1 < T2 < T3

B : T1 > T2 > T3

C : T2 = T3, T3 < T1

D : T1 = T3, T3 > T2

.

Correct answer is : D

Question 37

**An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3.**

Q—R1—R2—R3—H

H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer encryption is used, with DES as the shared key encryption protocol. Consider the following four pieces of information:

[I1] The URL of the file downloaded by Q

[I2] The TCP port numbers at Q and H

[I3] The IP addresses of Q and H

[I4] The link layer addresses of Q and H

Which of I1, I2, I3, and I4 can an intruder learn through sniffing at R2 alone?

Q—R1—R2—R3—H

H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer encryption is used, with DES as the shared key encryption protocol. Consider the following four pieces of information:

[I1] The URL of the file downloaded by Q

[I2] The TCP port numbers at Q and H

[I3] The IP addresses of Q and H

[I4] The link layer addresses of Q and H

Which of I1, I2, I3, and I4 can an intruder learn through sniffing at R2 alone?

A : Only I1 and I2

B : Only I1

C : Only I2 and I3

D : Only I3

.

Correct answer is : C

Solution :

An Intruder can’t learn [I1] through sniffing at R2 because URLs and Download are functioned at Application layer of OSI Model.

An Intruder can learn [I2] through sniffing at R2 because Port Numbers are encapsulated in the payload field of IP Datagram. An Intruder can learn

[I3] through sniffing at R2 because IP Addresses and Routers are functioned at network layer of OSI Model.

An Intruder can’t learn [I4] through sniffing at R2 because it is related to Data Link Layer of OSI Model.

Question 38

**A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assuming no caching, which one of the following is correct about the HTML webpage loading (including the embedded image)?**

A : Q needs to send at least 2 HTTP requests to S, each necessarily in a separate TCP connection to server S

B : Q needs to send at least 2 HTTP requests to S, but a single TCP connection to server S is sufficient

C : A single HTTP request from Q to S is sufficient, and a single TCP connection between Q and S is necessary for this

D : A single HTTP request from Q to S is sufficient, and this is possible without any TCP connection between Q and S

.

Correct answer is : B

Solution :

Whenever a browser opens a webpage, it makes a separate request for each object of page like image, css, javascript, etc. However if multiple resources are served from same server, then one TCP connect is sufficient. There can be more than one TCP connections also but the it can be done in one connection so by condition of sufficiency it is true.

Question 39

**Consider the following schedule S of transactions T1, T2, T3, T4**

Which one of the following statements is CORRECT?

Which one of the following statements is CORRECT?

A : S is conflict-serializable but not recoverable

B : S is conflict-serializable but is recoverable

C : S is both conflict-serializable and recoverable

D : S is neither conflict-serializable nor is it recoverable

.

Correct answer is : C

Solution :

According to the precedence graph In the schedule S of transactions T1 ,T2 ,T3 and T4 for each pair of transaction Ti and Tj , such that Tj reads a data item previously written by Ti the commit operation of Tj appears after the commit operation of Ti hence the schedule is recoverable schedule.

Question 40

**Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R)) < size(s(S)), the join will have fewer number of disk block accesses if**

A : relation r(R) is in the outer loop.

B : relation s(S) is in the outer loop.

C : join selection factor between r(R) and s(S) is more than 0.5.

D : join selection factor between r(R) and s(S) is less than 0.5.

.

Correct answer is : A

Solution :

A join between r(R) and s (S) using nested loop method will be as follows.

For each tuple r in R do

For each tuple s in S do

If r and s satisfy the join condition then output the tuple

Cost estimations for the above loop: – b(R) and b(S) number of blocks in R and in S – Each block of outer relation is read once – Inner relation is read once for each block of outer relation Summing up : IO= b(R)+b(R)*b(S) total IO operations this will be lowest when R is in outer loop.

Question 41

**Consider the procedure below for the Producer-Consumer problem which uses semaphores. Which one of the following is TRUE?**

A : The producer will be able to add an item to the buffer, but the consumer can never consume it.

B : The consumer will remove no more than one item from the buffer.

C : Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.

D : The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

.

Correct answer is : C

Solution :

when buffer is empty n=0 and s=1 and if a Consumer comes he makes s=0 and got stuck at n=0 wait. Now if a producer comes it gets stuck at Semwait(s) as s=0.

Question 42

**Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires tc CPU milliseconds and then initiates a single I/O operation that lasts for tio milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:**

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.

.

Correct answer is : 1000

Solution :

There are three processes A, B and C that run in round robin manner with time slice of 50 ms. Processes atart at 0, 5 and 10 miliseconds. The processes are executed in below order A, B, C, A 50 + 50 + 50 + 50 (200 ms passed) Now A has completed 100 ms of computations and goes for I/O now B, C, B, C, B, C 50 + 50 + 50 + 50 + 50 + 50 (300 ms passed) C goes for i/o at 500ms and it needs 500ms to finish the IO. So C would complete its first IO at 1000 ms

Question 43

**A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?**

A : Least-recently-used

B : First-in-first-out

C : Last-in-first-out

D : Most-recently-used

.

Correct answer is : D

Solution :

Page reference string for the program will be:-

1, 2, 3, 4, ------------100, 1, 2, 3, 4, ------------100, 1, 2, 3, 4, ------------100,

The current status of 20 frames shows page numbers from 101 to 120.

So there would be 300 page faults in total (each access 100 page faults).

The first 20 accesses to pages from 1 to 20 would definitely cause page fault. When 21st is accessed, there is another page fault. The page swapped out would be 20 because 20 is going to be accessed farthest in future. When 22nd is accessed, 21st is going to go out as it is going to be the farthest in future. The above optimal page replacement algorithm actually works as most recently used in this case.

Question 44

**For a C program accessing X[i] [j] [k], the following intermediate code is generated by a compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.**

t0 = i * 1024

t1 = j * 32

t2 = k * 4

t3 = t1 + t0

t4 = t3 + t2

t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

t0 = i * 1024

t1 = j * 32

t2 = k * 4

t3 = t1 + t0

t4 = t3 + t2

t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

A : X is declared as “int X[32] [32] [8]”.

B : X is declared as “int X[4] [1024] [32]”.

C : X is declared as “char X[4] [32] [8]”.

D : X is declared as “char X[32] [16] [2]”.

.

Correct answer is : A

Solution :

It is given that Size of int is 4B and of char is 1B. The memory is byte addressable. Let the array be declared as Type X[A][B][C] (where Type = int/char and A,B,C are natural numbers).

From t0 = i*1024, we conclude that B*C*(size of Type) = 1024.

From t1 = j*32, we conclude that C*(size of Type) = 32.

From t2 = k*4, we conclude that size of Type = 4.

Type = int, and

C = 8, and

B = 32.

Question 45

**Let < M > be the encoding of a Turing machine as a string over S = {0,1} . Let L = {< M > |M is a Turning machine that accepts a string of length 2014}. Then, L is**

A : decidable and recursively enumerable

B : undecidable but recursively enumerable

C : undecidable and not recursively enumerable

D : decidable but not recursively enumerable

.

Correct answer is : B

Solution :

The language accepted by the Turing machine is recursively enumerable. If is undecidable as the Turing machine may halt or it may loop for the strings whose length is not equal to 2014.

Question 46

**Let L1 = w ∈ {0,1} * |w has at least as many occurrences of (110)’s as (011)’s}. Let L2 = {w Î 0,1 * | w has at least as many occurrence of (000)’s as (111)’s}. Which one of the following is TRUE?**

A : L1 is regular but not L2

B : L2 is regular but not L1

C : Both L1 and L2 are regular

D : Neiher L1 and L2 are regular

.

Correct answer is : A

Solution :

The automaton for L1 is as follows and No finite state automata can be constructed for L2.

Question 47

**Consider two strings A "= q pqrr " and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.**

.

Correct answer is : 34

Solution :

Given is

A = “qpqrr”

B = “pqprqrp”

The longest common subsequence (not necessarily contiguous) between A and B is having 4 as the length, so x=4 and such common subsequences are as follows:

(1) qpqr

(2) pqrr

(3) qprr

So y = 3 (the number of longest common subsequences) hence x+10y = 4+10*3 = 34.

Question 48

**Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.**

.

Correct answer is : 358

Solution :

The implementation of optimal algorithm for merging sequences is as follows. In it total number of comparisons is (44-1)+(94-1)+(65-1)+(159-1) = 358

Question 49

**Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.**

.

Correct answer is : 6

Question 50

**Consider the following function**

double f (double x) {

if ( abs (x*x – 3) < 0. 01) return x;

else return f (x / 2 + 1.5/x);

}

Give a value q (to 2 decimals) such that f (q) will return q:______

double f (double x) {

if ( abs (x*x – 3) < 0. 01) return x;

else return f (x / 2 + 1.5/x);

}

Give a value q (to 2 decimals) such that f (q) will return q:______

.

Correct answer is : 1.72 - 1.74

Solution :

If condition given in function definition should be ‘TRUE’, for f (q) to return value q. The condition is as follows:

if (abs(x ×x - 3)<0.01) return x;

The above condition will be true when x=1.73.

Question 51

**Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?**

A : A queue cannot be implemented using this stack.

B : A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of

C : A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a

D : A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

.

Correct answer is : C

Solution :

Option (a) is false because queue can be implemented by using the modified stack as by reversing the stack. LIFO will become FIFO. Implementation of ENQUEUE & DEQUEUE takes four sequence of instructions as follows:

1 .ENQUEUE : Reverse , Push , Reverse and DEQUEUE : Pop.

2.Enqueue: Push and Dequeue: Reverse, POP, Reverse

Question 52

**Consider the C function given below**

int f(int j)

{

static int i = 50;

int k;

if (i == j)

{

printf(“something”);

k = f(i);

return 0;

}

else return 0;

}

Which one of the following is TRUE?

int f(int j)

{

static int i = 50;

int k;

if (i == j)

{

printf(“something”);

k = f(i);

return 0;

}

else return 0;

}

Which one of the following is TRUE?

A : The function returns 0 for all values of j.

B : The function prints the string something for all values of j.

C : The function returns 0 when j = 50.

D : The function will exhaust the runtime stack or run into an infinite loop when j = 50.

.

Correct answer is : D

Solution :

For any value of ‘j’ other than 50 the function will return 0, for j=50, then condition (i==j) will be true, it will print “something” and function will be called recursively with same value till the run time stack overflows.

Question 53

**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 : A smaller block size implies better spatial locality

B : A smaller block size implies a smaller cache tag and hence lower cache tag overhead

C : A smaller block size implies a larger cache tag and hence lower cache hit time

D : A smaller block size incurs a lower cache miss penalty

.

Correct answer is : D

Solution :

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 54

**If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?**

A : Width of tag comparator

B : Width of set index decoder

C : Width of way selection multiplexor

D : Width of processor to main memory data bus

.

Correct answer is : D

Solution :

When associativity is doubled, then the set offset will be effected, accordingly, the number of bits used for TAG comparator be effected.

Width of set index decoder also will be effected when set offset is changed.

Width of wag selection multiplexer wil be effected when the block offset is changed.

With of processor to main memory data bus is guaranteed to be NOT effected.

Question 55

**The value of a float type variable is represented using the single-precision 32-bit floating point format of IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mantissa. A float type variable X is assigned the decimal value of -14.25. The representation of X in hexadecimal notation is**

A : C1640000H

B : 416C0000H

C : 41640000H

D : C16C0000H

.

Correct answer is : A

Question 56

**In the Newton-Raphson method, an initial guess of x0 = 2 is made and the sequencex0,x1,x2 ... is obtained for the function**

0.75x

Consider the statements

(I) x3 = 0 .

(II) The method converges to a solution in a finite number of iterations.

Which of the following is TRUE?

0.75x

^{3}- 2x^{2}- 2x +4 = 0Consider the statements

(I) x3 = 0 .

(II) The method converges to a solution in a finite number of iterations.

Which of the following is TRUE?

A : Only I

B : Only II

C : Both I and II

D : Neither I and II

.

Correct answer is : A

Question 57

**The product of the non-zero eigenvalues of the matrix is**

.

Correct answer is : 6

Question 58

**The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is ______ .**

.

Correct answer is : 0.259 - 0.261

Solution :

Let A = divisible by 2, B = divisible by 3 and C = divisible by 5, then

n(A) = 50, n(B) = 33, n(C) = 20

n(A ∩ B) = 16 (100/6)

n(A ∩ C) = 10 (100/10)

n(B ∩ C) = 6 (100/15)

n(A ∩ B ∩ C) = 3 (100/(2*3*5))

Now find n(A U B U C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ B) -n(B ∩ C) + n(A ∩ B ∩ C)

(100 - n(A U B U C))/100

Substituting the values we get answer as 0.26

Question 59

**The number of distinct positive integral factors of 2014 is _________________________**

.

Correct answer is : 8

Solution :

2014 = 2×19×53 i.e., product of prime factors

Number of distinct positive integral factors of 2014 is (2)×(2)×(2) = 8.

Question 60

**Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U.**

Consider the following two statements:

S1: There is a subset of S that is larger than every other subset.

S2: There is a subset of S that is smaller than every other subset.

Which one of the following is CORRECT?

Consider the following two statements:

S1: There is a subset of S that is larger than every other subset.

S2: There is a subset of S that is smaller than every other subset.

Which one of the following is CORRECT?

A : Both S1 and S2 are true

B : S1 is true and S2 is false

C : S2 is true and S1 is false

D : Neither S1 nor S2 is true

.

Correct answer is : A

Solution :

From given data S1 is true ,since null set is larger than every other set ,and S2 is true since the universal set {1,2,...,2014} is smaller than every other set.

Both s1 and s2 are true.

Question 61

**A cycle on n vertices is isomorphic to its complement. The value of n is _____.**

.

Correct answer is : 5

Solution :

Consider a cycle on five vertices C5

C5 and C5` are isomorphic

Question 62

**The number of distinct minimum spanning trees for the weighted graph below is**

.

Correct answer is : 6

Question 63

**Which one of the following Boolean expressions is NOT a tautology?**

A : ((a -> b) ∧ (b -> c)) -> (a -> c)

B : (a <-> c) -> (~ b -> (a ∧ c))

C : (a ∧ b ∧ c) -> (c ∧ a )

D : a -> (b -> a)

.

Correct answer is : B

Question 64

**SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below:**

Select * from R where a in (select S. a from S)

Select * from R where a in (select S. a from S)

A : Select R. * from R, S where R. a=S. a

B : Select distinct R. * from R,S where R. a=S. a

C : Select R. * from R, (select distinct a from S) as S1 where R. a=S1.a

D : Select R. * from R, S where R.a = S. a and is unique R

.

Correct answer is : C

Question 65

**Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in 1 millisecond is ____________**

.

Correct answer is : 10000

Solution :

Each write request, the bus is occupied for 100 n.s

Storing of data requires 100 n.s.

In 100 n.s - 1 store

100/10

^{6}n.s. = 1 store

1m.s. = 10

^{6}/ 100 stores = 10000 stores

## 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.