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

 A 3/23 B 6/23 C 3/10 D 3/5
Aptitude       Numerical
Question 1 Explanation:
Let us consider total no. of families = 100
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?

 A 15 B 20 C 25 D 35
Aptitude       Numerical
Question 2 Explanation:
n = 200
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?

 A (∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)] B (∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧¬ c(x, y)] C ¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)] D ¬(∀x)(∃y)[(a(x, y) ∨ b(x, y)) → c(x, y)]
Engineering-Mathematics       Prepositional-Logic
Question 3 Explanation: Question 4

Let R1 be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 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 R1) if x + y is divisible by 3.
2. An element x in B is related to an element y in C (under R2) if x + y is even but not divisible by 3.
Which is the composite relation R1R2 from A to C?

 A R1R2 = {(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)} B R1R2 = {(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)} C R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)} D R1R2 = {(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}
Engineering-Mathematics       Relations
Question 4 Explanation:
From the given information,
R1 ={(1,2), (1,8), (3,6), (5,4), (7,2), (7,8)}
where x+y is divisible by 3
R2 = {(2,2), (4,4), (6,2), (6,4), (8,2)}
where x+y is not divisible by 3
Then the composition of R1 with R2 denotes R1R2, is the relation from A to C defined by property such as:
(x,z) ∈ R1R2, iff if there is a y ∈ B such that (x,y) ∈ R1 and (y,z) ∈ R2.
Thus, R1R2 = {(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?

 A n - 1 B n C n + 1 D 2n - 1
Engineering-Mathematics       Graph-Theory
Question 5 Explanation:
Maximum number of edges in an acyclic undirected graph = No. of vertices - 1
= n - 1
 Question 6

What values of x, y and z satisfy the following system of linear equations? A x = 6, y = 3, z = 2 B x = 12, y = 3, z = -4 C x = 6, y = 6, z = -4 D x = 12, y = -3, z = 0
Engineering-Mathematics       Linear-Algebra
Question 6 Explanation: Question 7

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

 A (a* + b* + c*)* B (a*b*c*)* C ((ab)* + c*)* D (a*b* + c*)*
Theory-of-Computation       Regular-Expressions
Question 7 Explanation:
With the given r.e. (a+b+c)* we can generate "a".
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?

 A 3 B 4 C 5 D 6
Digital-Logic-Design       Logic-Gates
Question 8 Explanation: To create 2-input Exclusive-OR function we require 4 NAND gates.
 Question 9

Which one of the following statements is FALSE?

 A There exist context-free languages such that all the context-free grammars generating them are ambiguous B An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it C Both deterministic and non-deterministic pushdown automata always accept the same set of languages D A finite set of string from one alphabet is always a regular language
Theory-of-Computation       General
Question 9 Explanation:
Deterministic automata can be able to recognize all the deterministic context-free languages.
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?

 A 32 K × 16 bits B 64 K × 16 bits C 16 K × 32 bits D 64 K × 32 bits
Digital-Logic-Design       Multiplexer
Question 10 Explanation:
Input: 2 lines, 8 bits each
Possible combination in ROM = (28 × (28) [size of truth table]
= 216
= 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)?

 A 8 Mbps B 6.4 Mbps C 0.8 Mbps D 0.64 Mbps
Operating-Systems       I/O-Handling
Question 11 Explanation:
Horizontal sweep time = 100µs
Total number of bits transmitted = 80 * 8 = 640 bits
Bit rate = (640 * 106)/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?

 A 13.0 ns B 12.8 ns C 12.6 ns D 12.4 ns
Computer-Organization       Cache
Question 12 Explanation:
Average access time = [H1 * T1] + [(1 - H1) * Hm * Tm]
H1 = 0.8, (1 - H1) = 0.2
H2 = 0.9, (1 - H2) = 0.1
T1 = Access time for level 1 cache = 1ns
T2 = Access time for level 2 cache = 10ns
Hm = Hit rate of main memory = 1
Tm = 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?

 A O(n) B O(log2 n) C O(logn) D O(1)
Question 13 Explanation:
Worst case complexity for deleting a node from singly linked list is O(1).
 Question 14

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

 A Stack B Address Space C File Descriptor Table D Message Queue
Operating-Systems       Memory-Management
Question 14 Explanation:
Threads cannot share the stack to maintaining the function calls and they can have individual function call sequences.
 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?

 A x = 1 + x; B x = 1 - x; C x = x - 1; D x = 1 % x;
Programming       Programming
Question 15 Explanation:
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) ```
 A II and III B II and IV C I and III D II only
Operating-Systems       Unix
Question 16 Explanation:
Note: Out of syllabus.
 Question 17

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

 A effort and duration based on the size of the software B size and duration based on the effort of the software C effort and cost based on the duration of the software D size, effort and duration based on the cost of the software
Software-Engineering       SE
Question 17 Explanation:
Note: Out of syllabus.
 Question 18

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

 A Entity Relationship Diagram B Deployment Diagram C Data Flow Diagram D Use Case Diagram
Software-Engineering       HTML
Question 18 Explanation:
Note: Out of syllabus.
 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?

 A Defect Detection B Defect Prevention C Defect Isolation D Defect Propagation
Software-Engineering       SE
Question 19 Explanation:
Note: Out of syllabus.
 Question 20

A software configuration management tool helps is

 A keeping track of the schedule based on the milestones reached B maintaining different versions of the configurable items C managing manpower distribution by changing the project structure D all of the above
Software-Engineering       SE
Question 20 Explanation:
Note: Out of syllabus.
 Question 21

Which level of locking provides the highest degree of concurrency in a relational database?

 A Page B Table C Row D Page, table and row level locking allow the same degree of concurrency
Database-Management-System       Transactions and concurrency control
Question 21 Explanation:
In page level locking, it will lock whole page i.e., all rows are highly restrictive.
Table locking can be used for concurrency control with DDL operations.
In row share table is less restrictive but it consists of highest degree of concurrency compared to page and table.
 Question 22

Which one of the following statements is FALSE?

 A Packet switching leads to better utilization of bandwidth resources than circuit switching. B Packet switching results in less variation in delay than circuit switching. C Packet switching requires more per packet processing than circuit switching. D Packet switching can lead to reordering unlike in circuit switching.