## GATE 2004-IT

Question 1 |

In a population of N families, 50% of the families have three children, 30% of the families have two children and the remaining families have one child. What is the probability that a randomly picked child belongs to a family with two children?

3/23 | |

6/23 | |

3/10 | |

3/5 |

In that 50% of families having 3 children

i.e., 50×3 = 150 (No. of children)

→ Likes that 30% have 2 children = 30×2 = 60

→ 20% have 1 children = 20×1 = 20

Probability of choosing a children the family have two children

= 60/(150+60+20) = 60/230 = 6/23

Question 2 |

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course; 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization; 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses.How many students have not taken any of the three courses?

15 | |

20 | |

25 | |

35 |

PL = 125

DS = 85

CO = 65

PL & DS = 50

DS & CO = 35

CO & PL = 30

PL & DS & CO = 15

⇒ Not taken any course = 200 - (60 +15+15+35+15+15+20)

= 200 - 175

= 25

Question 3 |

Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y chosen from some universe. Consider the following statement:

(∃x)(∀y)[(a(x, y) ∧ b(x, y)) ∧ ¬c(x, y)]Which one of the following is its equivalent?

(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)] | |

(∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧¬ c(x, y)] | |

¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)] | |

¬(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)] |

Question 4 |

Let R_{1} be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R_{2} be another relation from B to C = {1, 2, 3, 4} as defined below:

1. An element x in A is related to an element y in B (under R_{1}) if x + y is divisible by 3.

2. An element x in B is related to an element y in C (under R_{2}) if x + y is even but not divisible by 3.

Which is the composite relation R_{1}R_{2} from A to C?

R _{1}R_{2} = {(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)} | |

R _{1}R_{2} = {(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)} | |

R _{1}R_{2} = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)} | |

R _{1}R_{2} = {(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)} |

R

_{1}={(1,2), (1,8), (3,6), (5,4), (7,2), (7,8)}

where x+y is divisible by 3

R

_{2}= {(2,2), (4,4), (6,2), (6,4), (8,2)}

where x+y is not divisible by 3

Then the composition of R

_{1}with R

_{2}denotes R

_{1}R

_{2}, is the relation from A to C defined by property such as:

(x,z) ∈ R

_{1}R

_{2}, iff if there is a y ∈ B such that (x,y) ∈ R

_{1}and (y,z) ∈ R

_{2}.

Thus, R

_{1}R

_{2}= {(1,2), (3,2), (3,4), (5,4), (7,2)}

Question 5 |

What is the maximum number of edges in an acyclic undirected graph with n vertices?

n - 1 | |

n | |

n + 1 | |

2n - 1 |

= n - 1

Question 6 |

What values of x, y and z satisfy the following system of linear equations?

x = 6, y = 3, z = 2 | |

x = 12, y = 3, z = -4 | |

x = 6, y = 6, z = -4 | |

x = 12, y = -3, z = 0 |

Question 7 |

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c)*?

(a* + b* + c*)* | |

(a*b*c*)* | |

((ab)* + c*)* | |

(a*b* + c*)* |

From option 'c' we cannot be able to create a without b. So option is not equivalent.

Question 8 |

What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-OR function without using any other logic gate?

3 | |

4 | |

5 | |

6 |

To create 2-input Exclusive-OR function we require 4 NAND gates.

Question 9 |

Which one of the following statements is FALSE?

There exist context-free languages such that all the context-free grammars generating them are ambiguous | |

An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it | |

Both deterministic and non-deterministic pushdown automata always accept the same set of languages | |

A finite set of string from one alphabet is always a regular language |

But non-deterministic ones can recognize all context-free languages.

So, option C is false.

Question 10 |

What is the minimum size of ROM required to store the complete truth table of an 8-bit × 8-bit multiplier?

32 K × 16 bits | |

64 K × 16 bits | |

16 K × 32 bits | |

64 K × 32 bits |

Possible combination in ROM = (2

^{8}× (2

^{8}) [size of truth table]

= 2

^{16}

= 64 KB

= 64 K ×16 bits

Question 11 |

What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and horizontal sweep time of lOOµs (including 20 µs of retrace time)?

8 Mbps | |

6.4 Mbps | |

0.8 Mbps | |

0.64 Mbps |

Total number of bits transmitted = 80 * 8 = 640 bits

Bit rate = (640 * 10

^{6})/100 = 6.4 Mbps

Question 12 |

Consider a system with 2 level caches. Access times of Level 1 cache, Level 2 cache and main memory are 1 ns, 10ns, and 500 ns, respectively. The hit rates of Level 1 and Level 2 caches are 0.8 and 0.9, respectively. What is the average access time of the system ignoring the search time within the cache?

13.0 ns | |

12.8 ns | |

12.6 ns | |

12.4 ns |

_{1}* T

_{1}] + [(1 - H

_{1}) * H

_{m}* T

_{m}]

H

_{1}= 0.8, (1 - H

_{1}) = 0.2

H

_{2}= 0.9, (1 - H

_{2}) = 0.1

T

_{1}= Access time for level 1 cache = 1ns

T

_{2}= Access time for level 2 cache = 10ns

H

_{m}= Hit rate of main memory = 1

T

_{m}= Access time for main memory = 500ns

Average access time = [(0.8 * 1) + (0.2 * 0.9 * 10) + (0.2)(0.1) * 1 * 500]

= 0.8 + 1.8 + 10

= 12.6ns

Question 13 |

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best known algorithm to delete the node x from the list?

O(n) | |

O(log ^{2} n) | |

O(logn) | |

O(1) |

Question 14 |

Which one of the following is NOT shared by the threads of the same process?

Stack | |

Address Space | |

File Descriptor Table | |

Message Queue |

Question 15 |

Let x be an integer which can take a value of 0 or 1. The statement if(x = =0) x = 1; else x = 0; is equivalent to which one of the following?

x = 1 + x; | |

x = 1 - x; | |

x = x - 1; | |

x = 1 % x; |

For x = 0, it gives 1.

For x = 1, it gives 0.

Question 16 |

Which of the following commands or sequences of commands will rename a file x to file y in a unix system?

I. mv y,x II. mv x,y III. cp y, x(rm x) IV. cp x, y (rm x)

II and III | |

II and IV | |

I and III | |

II only |

Question 17 |

In a software project, COCOMO (Constructive Cost Model) is used to estimate

effort and duration based on the size of the software | |

size and duration based on the effort of the software | |

effort and cost based on the duration of the software | |

size, effort and duration based on the cost of the software |

Question 18 |

The diagram that helps in understanding and representing user requirements for a software project using UML (Unified Modeling Language) is:

Entity Relationship Diagram | |

Deployment Diagram | |

Data Flow Diagram | |

Use Case Diagram |

Question 19 |

A software organization has been assessed at SEI CMM Level 4. Which of the following does the organization need to practice beside Process Change Management and Technology Change Management in order to achieve Level 5?

Defect Detection | |

Defect Prevention | |

Defect Isolation | |

Defect Propagation |

Question 20 |

A software configuration management tool helps is

keeping track of the schedule based on the milestones reached | |

maintaining different versions of the configurable items | |