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
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)
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
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.
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.
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
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
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
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
.64
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
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
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
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
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
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
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
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
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
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
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