GATE CS and IT 2013 Answers

General Aptitude Questions

56-60 carry one mark each

56. Which one of the following options is the closest in meaning to the word given below?

Nadir

a) Highest

b) Lowest

c) Medium

d) Integration

 Answer: b

57. Complete the sentence:

Universalism is to particularism as diffuseness is to ________

a) specificity

b) neutrality

c) generality

d) adaptation

Answer: a

58. What will be the maximum sum of 44, 42, 40, ... ?

a) 502

b) 504

c) 506

d) 500

Answer: c

GATE 2013 CS and IT answer key

Common data questions 50 and 51

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed

void find _ and _ replace (char * A, char * oldc, char *newc) {

for(int i=0; i<5; i++)

for(int j=0; j <3; j++)

if(A[i]= = oldc[j])  A[i]= newc[j] ;

}

The procedure is tested with the following four test cases

(1) oldc = "abc ", newc = "dab"

(2) oldc = " cde", newc = "bcd"

(3) oldc = "bca", newc = "cda"

(4) oldc = "abc ", newc = "bac "

50. The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

a) Only one

b) Only two

c) Only three

d) All four

Answer: b

51. If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?

a) None

b) 2 only

c) 3 and 4 only

d) 4 only

Answer: c

Computer science GATE 2013 Answer key

42. What is the return value of  f(p,p) ,if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.

int f (int &x, int c) {

c=c-1;

if (c==0) return 1;

x=x+1;

return f(x,c) * x;

}

a) 3024

b) 6561

c) 55440

d) 161051

Answer: b

43. The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

a) 10,20,15,23,25,35,42,39,30

b) 15,10,25,23,20,42,35,39,30

c) 15,20,10,23,25,42,35,39,30

d) 15,10,23,25,20,35,42,39,30

Answer: d

GATE Exam 2013 Computer science answer key

37. In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence numbers of the first and the last bytes of the payload, respectively are

a) Last fragment, 2400 and 2789

b) First fragment, 2400 and 2759

c) Last fragment, 2400 and 2759

d) Middle fragment, 300 and 689

Answer: c

38. The following figure represents access graphs of two modules M1 and M2. The filled circles represent methods and the unfilled circles represent attributes. If method m is moved to module M2 keeping the attributes where they are, what can we say about the average cohesion and coupling between modules in the system of two modules?

a) There is no change.

b) Average cohesion goes up but coupling is reduced.

c) Average cohesion goes down and coupling also reduces.

d) Average cohesion and coupling increase.

GATE 2013 questions cs and IT

30. The number of elements that can be sorted in Q(logn) time using heap sort is

a) Θ(1)

b) Θ(√ logn)

c) Θ((logn)/(log log n)

d) Θ(log n)

Answer: a

31. Consider the following function

int unknown int n {

int i, j, k 0;

for( i= n / 2; i<= n; i++)

            for ( j=2; j<=n; j= j * 2)

                        k=k +n / 2;

return k ;

}

The return value of the function is

a) Θ(n2)

b) Θ(n2 log n)

c) Θ(n3)

d) Θ(n3log n)

Answer: b

32. Consider the following languages

            L1= { 0p1q0r | p,q,r ≥ 0}

           L2= { 0p1q0r | p,q,r ≥ 0,p≠ r}

Which one of the following statements is FALSE?

a)  L2 is context–free

b) L2∩L2 is context–free

c) Complement of L2 is recursive

d) Complement of L1 is context–free but not regular

Answer: d

33. Consider the DFA given below.

Computer Science Gate questions 2013

23. Function f is known at the following points:

x	0	0.3	0.6	0.9	1.2	1.5	1.8	2.1	2.4	2.7	3.0
f(x)	0	0.09	0.36	0.81	1.44	2.25	3.24	4.41	5.76	7.29	9.00

The value of ∫03f(x)dx  computed using the trapezoidal rule is          (integral f(x)dx from o to 3)

a)      8.983

b)     9.003

c)      9.017

d)     9.045

Answer: d

24. Consider an undirected graph of eight vertices. The probability that there is an edge between a pair of vertices is ½. What is the expected number of unordered cycles of length three?

a)1/8 

b) 1

c) 7

d) 8

Answer: c

25. Which of the following statements is/are TRUE for undirected graphs?

 P: Number of odd degree vertices is even

Q: Sum of degrees of all vertices is even

a)     P only

b)     Q only

c)      Both P and Q

d)     Neither P nor Q
Answer: c

Computer Science Gate 2013 Answer key

17. Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine

2. Turing recognizable languages are closed under union and complementation

3. Turing decidable languages are closed under intersection and complementation

4. Turing recognizable languages are closed under union and intersection

A)     1 and 4 only

B)      1 and 3 only

C)     2 only

D)     D) 3 only

Answer: c

18. Which of the following statements are TRUE?

1. The problem of determining whether there exist a cycle in an undirected graph in P.

2. The problem of determining whether there exist a cycle in an undirected graph is in NP.

3. If a problem A in NP-complete, there exist a non-deterministic polynomial time algorithm to solve A.

a) 1,2 and 3

b) 1 and 2 only

c) 2 and 3 only

d) 1 and 3 only

Answer: a

19. What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

a) Θ(n2)

b) Θ(n2 log n)

c) Θ(n3)

d) Θ(n3log n)
Answer: c

GATE 2013 computer science and information technology answer key

11. Match the following domain in GROUP 1 with the solution technologies in GROUP 2

GROUP 1

p) Service oriented computing

Q) Heterogeneous communicating system

R) Information representation

S) Process Description

GROUP 2

1)     Interoperability

2)     BPMN

3)     Publish-find-bind

4)     XML

a)      p-1, Q-2, R-3, S-4

b)     P-3, Q-4, R-2, S-1

c)      P-3, Q-1, R-4, S-2

d)     P-4, Q-3, R-2, S-1

Answer: c

12. The transport layer protocol used for real time multimedia, file transfer, DNS and email respectively are

a) TCP,UDP,UDP and TCP

B) UDP,TCP,TCP and UDP

C) UDP,TCP,UDP and TCP

D) TCP,UDP,TCP and UDP

Answer: c

GATE 2013 Computer science answer key

1. A binary operation ⊕ on a set of integers is defined as x⊕y=x2+y2.  Which of the following statements is TRUE about ⊕?

a) Commutative but not associative

b) Both commutative and associative

c) Associative but not commutative

d) Neither commutative nor associative

Answer: a

2. Suppose p is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and p has a Poisson distribution with mean 3. What is the probability of observing fewer than three cars during any given minute in this interval?

a) 8/(2e3)  b) 9/(2e3)   c) 17/(2e3)   d) 26/(2e3)

Answer: c

3. Which one of the following is NOT equal