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

20. in a k-way set associative cache, the cache is divided into v sets, each of which consists of k lines. The lines of a set are placed in sequence one after another. The lines in set s are sequenced before the line in set(s+1). The main memory blocks are numbered 0 onwards. The main memory block numbered j must be mapped to any one of the cache lines from

a) (j mod v) *k  to (j mod v) *k+(k-1)

b) (j mod v)  to (j mod v)+ (k-1)

c) (j mod k)  to (j mod k)+(v-1)

d) (j mod k) *v  to (j mod k) *v+(v-1)

Answer: b

21. Which one of the following expression does Not represent exclusive NOR of x and y?

a) xy+x’y’

b) x⊕y’

c)x’⊕y

d)x’⊕y’

Answer: d

22. Which one of the following function is continuous at x=3?

Answer: a

Next: Gate 2013 Computer Science Questions 23 to 29
Previous : Gate 2013 Computer science and information technology Answer key 11-16