## GATE 2005-IT

 Question 1

A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn from the bag, its colour recorded and it is put back in the bag. This process is repeated 3 times. The probability that no two of the marbles drawn have the same colour is

 A 1/36 B 1/6 C 1/4 D 1/3
Engineering-Mathematics       Probability
Question 1 Explanation:
No. of colours = 3(b,g,r)
Total possible combinations = 3! = 6
Probability of blue marble = 10/60[10 + 20 + 30 = 60]
Probability of green marble = 20/60
Probability of red marble = 30/60
The probability that no two of the marbles has same colour = [10/60 * 20/60 * 30/60] = 1/6
 Question 2

If the trapezoidal method is used to evaluate the integral obtained 01x2dx ,then the value obtained

 A is always > (1/3) B is always < (1/3) C is always = (1/3) D may be greater or lesser than (1/3)
Engineering-Mathematics       Calculus
Question 2 Explanation:
Note: Out of syllabus.
 Question 3

The determinant of the matrix given below is A -1 B 0 C 1 D 2
Engineering-Mathematics       Linear-Algebra
Question 3 Explanation: determinant = product of diagonal element [upper triangular matrix]
= -1 * 1 * 1 * 1
= -1
 Question 4

Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language if Lc ∪ Mc is TRUE?

 A It is necessarily regular but not necessarily context-free. B It is necessarily context-free. C It is necessarily non-regular. D None of the above.
Theory-of-Computation       Regular Languages and finite automata
Question 4 Explanation:
Context-free languages not closed under complementation. So, Lc ∪ Mc is neither regular nor context-free. It might be context sensitive language.
 Question 5

Which of the following statements is TRUE about the regular expression 01*0?

 A It represents a finite set of finite strings. B It represents an infinite set of finite strings. C It represents a finite set of infinite strings. D It represents an infinite set of infinite strings.
Theory-of-Computation       Regular languages and finite automata
Question 5 Explanation:
The given expression 01*0 is regular. So this is a finite string. So options C and D are false and * is placed. So this is infinite set.
So, given regular expression represents an infinite set of finite strings.
 Question 6

The language {0n 1n 2n | 1 ≤ n ≤ 106} is

 A regular B context-free but not regular C context-free but its complement is not context-free D not context-free
Theory-of-Computation       Regular languages and finite automata
Question 6 Explanation:
In this the value of n is finite then we can be able to construct a finite state automata for this language.
So, given language is regular.
 Question 7

Which of the following expressions is equivalent to (A⊕B)⊕C

 A B C D None of these
Theory-of-Computation       Logical-Functions-and-Minimization
Question 7 Explanation:
(A⊕B)⊕C
⇒ We know that
A⊕B = A'B + AB'
A⊙B = AB + A'B' ⇒ (A⊕B)'C + (A⊕B)C'
⇒ (A⊙B)C + (A'B + AB')C'
⇒ (AB + A'B')C + (A'B + AB')C'
⇒ ABC + A'B'C + A'BC' + AB'C'
⇒ ABC + (A'B'C + A'B'C) + A'BC' + AB'C'
[We know that A + A = A]
⇒ ABC + A'B'C + A'B'C + A'BC' + AB'C'
⇒ ABC + A'(B'C + BC') + B'(A'C + AC')
⇒ ABC + A'(B⊕C) + B'(A⊕C)
 Question 8

Using Booth’s Algorithm for multiplication, the multiplier -57 will be recoded as

 A 0 -1 0 0 1 0 0 -1 B 1 1 0 0 0 1 1 1 C 0 -1 0 0 1 0 0 0 D 0 1 0 0 -1 0 0 1
Computer-Organization       Booth\'s-Algorithm
Question 8 Explanation:
Consider option A: Question 9

A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing?

 A 10 B 6.4 C 1 D 0.64
Computer-Organization       Cache
Question 9 Explanation:
We know that 1ms = 106ns
In 106ns refresh 100 times.
Each refresh takes 100ns.
Memory cycle time = 64ns
Refresh time per 1ms i.e., per 106ns = 100 * 100 = 104ns
Refresh time per 1ns = (104)/(106) ns
Refresh time per cycle = (104*64)/(106) = 64ns
Percentage of the memory cycle time is used for refreshing = (64*100)/64 = 1%
 Question 10

A two-way switch has three terminals a, b and c. In ON position (logic value 1), a is connected to b, and in OFF position, a is connected to c. Two of these two-way switches S1 and S2 are connected to a bulb as shown below. Which of the following expressions, if true, will always result in the lighting of the bulb ?

 A B C D Digital-Logic-Design       Circuits-Output
Question 10 Explanation:
The bulb will be on when both the switch S1 and S2 are in same state, either OFF (or) ON: From this we can clearly know that given is EX-NOR operation i.e.,
(S1⊙S2) = (S1⊕S2)'
 Question 11

How many pulses are needed to change the contents of a 8-bit up counter from 10101100 to 00100111 (rightmost bit is the LSB)?

 A 134 B 133 C 124 D 123
Digital-Logic-Design       Sequential-Circuits
Question 11 Explanation:
The 8 bit counter will be 0-255 to move from 10101100 (172) to 1000111 (39).
→ First counter is move from 172 to 255 = 83 pulses
→ 255 to 0 = 1 pulse
→ 0 to 39 = 39 pulses
Total = 83 + 1 + 39 = 123 pulses
 Question 12

The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

 A p B p + 1 C n - p D n - p + 1
Algorithms       Tree Traversals
Question 12 Explanation:
Total element = n
RST contains elements = p
Root contains = 1 element
1st contains = n - (p + 1) element Root contains the value is n - p.
 Question 13

A function f defined on stacks of integers satisfies the following properties.

` f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. `

If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

 A 6 B 4 C 3 D 2
Data-Structures       Queues-and-Stacks
Question 13 Explanation:
2, -3, 2, -1, 2
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,-3)) = max(2,0) + (-3) = 2 - 3 = -1
f(push(-1,2)) = max(-1,0) + 2 = 0 + 2 = 2
f(push(2,-1)) = max(2,0)+ (-1) = 2 - 1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
 Question 14

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

 A k B k + 1 C n - k - 1 D n - k
Algorithms       Graph-Traversal
Question 14 Explanation:
In a graph G with n vertices and p component then G has n - p edges(k).
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = n-p
p = n - k
 Question 15

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

```1. Bellman-Ford algorithm       A: O ( m log n)
2. Kruskal’s algorithm          B: O (n3)
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        D: O (n + m) ```
 A 1→ C, 2 → A, 3 → B, 4 → D B 1→ B, 2 → D, 3 → C, 4 → A C 1→ C, 2 → D, 3 → A, 4 → B D 1→ B, 2 → A, 3 → C, 4 → D
Algorithms       General
Question 15 Explanation:
Bellman-ford algorithm → O(nm)
Krushkal's algorithm → O(m log n)
Floyd-Warshall algorithm → O(n3)
Topological sorting → O(n+m)
 Question 16

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

 A 2 B 3 C 4 D 6
Algorithms       Sorting-and-Searching
Question 16 Explanation:
43%10 = 3 [occupy 3]
165%10 = 5 [occupy 5]
62%10 = 2 [occupy 2]
123%10 = 3 [3 already occupied, so occupies 4]
142%10 = 2 [2, 3, 4, 5 are occupied, so it occupies 6]
 Question 17

A student wishes to create symbolic links in a computer system running Unix. Three text files named "file 1", "file 2" and "file 3" exist in her current working directory, and the student has read and write permissions for all three files. Assume that file 1 contains information about her hobbies, file 2 contains information about her friends and file 3 contains information about her courses. The student executes the following sequence of commands from her current working directory

```ln -s file 1 file 2
ln -s file 2 file 3 ```

Which of the following types of information would be lost from her file system?

`(I) Hobbies (II) Friends (III) Courses`
 A (I) and (II) only B (II) and (III) only C (II) only D (I) and (III) only
Operating-Systems       Unix
Question 17 Explanation:
Note: Out of syllabus.
 Question 18

The shell command

` find -name passwd -print `

is executed in /etc directory of a computer system running Unix. Which of the following shell commands will give the same information as the above command when executed in the same directory?

 A ls passwd B cat passwd C grep name passwd D grep print passwd
Operating-Systems       Shell-Command
Question 18 Explanation:
Note: Out of syllabus.
 Question 19

A user level process in Unix traps the signal sent on a Ctrl-C input, and has a signal handling routine that saves appropriate files before terminating the process. When a Ctrl-C input is given to this process, what is the mode in which the signal handling routine executes?

 A kernel mode B superuser mode C privileged mode D user mode
Operating-Systems       Unix
Question 19 Explanation:
Note: Out of syllabus.
 Question 20

The Function Point (FP) calculated for a software project are often used to obtain an estimate of Lines of Code (LOC) required for that project. Which of the following statements is FALSE in this context.

 A The relationship between FP and LOC depends on the programming language used to implement the software. B LOC requirement for an assembly language implementation will be more for a given FP value, than LOC for implementation in COBOL C On an average, one LOC of C++ provides approximately 1.6 times the functionality of a single LOC of FORTRAN D FP and LOC are not related to each other
Software-Engineering       LOC
Question 20 Explanation:
Note: Out of syllabus.
 Question 21

Consider the entities 'hotel room', and 'person' with a many to many relationship 'lodging' as shown below: If we wish to store information about the rent payment to be made by person (s) occupying different hotel rooms, then this information should appear as an attribute of

 A Person B Hotel Room C Lodging D None of theseThe information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person. The information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person.
Database-Management-System       ER-Model
Question 21 Explanation:
The information should appear as an attribute of lodging, because this is the only common attribute that relating to the hotel room and person.
 Question 22

A table has fields Fl, F2, F3, F4, F5 with the following functional dependencies

` F1 → F3,  F2→ F4,  (F1.F2) → F5 `

In terms of Normalization, this table is in

 A 1 NF B 2 NF C 3 NF D None
Database-Management-System       Normalization
Question 22 Explanation:
F1 → F3 ......(i)
F2 → F4 ......(ii)
(F1⋅F2) → F5 .....(iii)
F1F2 is the candidate key.
F1 and F2 are the prime key.
In (i) and (ii) we can observe that the relation from P → NP which is partial dependency. So this is in 1NF.
There are 22 questions to complete.

Register Now