**DS | GATE-2014 | Data Structures**

- Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
**[GATE – 2014]**

a. θ(n)

b. θ(n+m)

c. θ(n^{2} )

d. θ(m^{2} )

*Answer : c)*

- Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n
^{a}log^{b}n). Then the value of a+10b is ________.**[GATE – 2014]**

a. 1

b. 2

c. 4

d. 3

*Answer : a)***DS | GATE-2014 |**

- Consider the directed graph given below.
**[GATE – 2014]**

Which one of the following is TRUE?

a. The graph does not have any topological ordering.

b. Both PQRS and SRQP are topological.

c. Both PSRQ and SPRQ are topological orderings.

d. PSRQ is the only topological ordering.

*Answer : c)*

- Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t
_{1}and t_{2}be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?**[GATE – 2014]**

a. t_{1}=5

b. t_{1}2

c. t_{1}>t_{2}

d. t_{1}=t_{2}

*Answer : c)*

- Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are :
**[GATE – 2014]**

a. 3, 0, and 1

b. 3, 3, and 3

c. 4, 0, and 1

d. 3, 0, and 2

*Answer : a)*

- Consider the following C function in which size is the number of elements in the array E: The value returned by the function MyX is the :
**[GATE – 2014]**

`int`

`MyX(int`

`*E, unsigned int`

`size)`

`{`

` int`

`Y = 0;`

` int`

`Z;`

` int`

`i, j, k;`

` for(i = 0; i < size; i++)`

` Y = Y + E[i];`

` for(i = 0; i < size; i++)`

` for(j = i; j < size; j++)`

` {`

` Z = 0;`

` for(k = i; k <= j; k++)`

` Z = Z + E[k];`

` if`

`(Z > Y)`

` Y = Z;`

` }`

` return`

`Y;`

`}`

a. maximum possible sum of elements in any sub-array of array E.

b. maximum element in any sub-array of array E.

c. sum of the maximum elements in all possible sub-arrays of array E.

d. the sum of all the elements in the array E.

*Answer : a)***DS | GATE-2014 |**

- Consider the following pseudo code. What is the total number of multiplications to be performed?
**[GATE – 2014]**

D = 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3

a. Half of the product of the 3 consecutive integers.

b. One-sixth of the product of the 3 consecutive integers.

c. One-third of the product of the 3 consecutive integers.

d. None of the above.

*Answer : b)*

- Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.
**[GATE – 2014]**

a. 7

b. 2

c. 5

d. 4

*Answer : d)**Data Structure Set-*5

- An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?
**[GATE – 2014]**

a. n⁄N

b. 1⁄N

c. 1⁄A

d. k⁄n

*Answer : a)***DS | GATE-2014 |**

- A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:
**[GATE – 2014]**

a. 10, 8, 7, 3, 2, 1, 5

b. 10, 8, 7, 2, 3, 1, 5

c. 10, 8, 7, 1, 2, 3, 5

d. 10, 8, 7, 5, 3, 2, 1

*Answer : a)*

- Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing :
**[GATE – 2014]**

a. the shortest path between every pair of vertices.

b. the longest path in the graph.

c. the shortest paths from W to only those nodes that are leaves of T.

d. the shortest path from W to every vertex in the graph.

*Answer : d)***DS | GATE-2014 |**