**DS | GATE-2016 | Data Structures**

**1.** A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efﬁciently. Which one of the following statements is **CORRECT** (*n* refers to the number of items in the queue)? **[GATE – 2016]**

a. Both operations can be performed in *O(1)* time

b. At most one operation can be performed in *O(1)* time but the worst case time for the other operation will be *Ω(n)**c. *Worst case time complexity for both operations will be *Ω(logn)**d. *The worst case time complexity for both operations will be *Ω(n)*

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

* 2. *Consider the following directed graph:

**[GATE – 2016]**

The number of different topological orderings of the vertices of the graph is _____________.

a. 8

b. 7

c. 9

d. 6

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

**3.** Let *G* be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are **TRUE**? **[GATE – 2016]**

P: Minimum spanning tree of *G* does not change

Q: Shortest path between any pair of vertices does not change

a. P only

b. Q Only

c. Both P and Q

d. Neither P and Q

*Answer : a)*

- An operator
*delete(i)*for a binary heap data structure is to be designed to delete the item in the*i*-th node. Assume that the heap is implemented in an array and*i*refers to the*i*-th index of the array. If the heap tree has depth*d*(number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-ﬁx the heap efﬁciently after the removal of the element?**[GATE – 2016]**

a. O(1)

b. O(d) but not O(1)

c. O(2^{d}) but not O(d)

d. O(d 2^{d}) but not O(2^{d})

*Answer : b)*

- Consider the weighted undirected graph with 4 vertices, where the weight of edge {
*i,j*} is given by the entry*W*in the matrix_{ij}*W*.**[GATE – 2016]**

a.12

b.13

c.14

d.15

*Answer : a)*

- Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q
**without**removing it from Q. Similarly Top(S) returns the element at the top of S**without**removing it from S. Consider the algorithm given below.**[GATE – 2016]**

The maximum possible number of iterations of the **while** loop in the algorithm is _________.

a. 256

b. 257

c. 258

d. 259

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

- Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex
*t*at a distance four from the root. If*t*is the*n*-th vertex in this BFS traversal, then the maximum possible value of*n*is _________.**[GATE – 2016]**

a. 33

b. 32

c. 31

d. 34

*Answer : c)*

**8. ***N* items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a *decrease-key* operation, a pointer is provided to the record on which the operation is to be performed. **[GATE – 2016]**

An algorithm performs the following operations on the list in this order: Θ(*N*) *delete*,O(log*N*) *insert*, O(log*N*) *ﬁnd*, and Θ(*N*) *decrease-key*. What is the time complexity of all these operations put together?

a. O(log^{2} N)

b. O(N^{2})

c. O(N)

d. Θ (N^{2} logN)

*Answer : b)*

**9.** A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _________. **[GATE – 2016]**

a. 5

b. 6

c. 7

d. 8

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

**10. **Consider the following New-order strategy for traversing a binary tree:** [GATE – 2016]**

- Visit the root;
- And Visit the right subtree using New-order;
- Visit the left subtree using New-order;

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 – 2 ˆ 6 7 * 1 + – is given by:

a. + – 1 6 7 * 2 ˆ 5 – 3 4 *

b. – + 1 * 6 7 ˆ 2 – 5 * 3 4

c. – + 1 * 7 6 ˆ 2 – 5 * 4 3

d. 1 7 6 * + 2 5 4 3 * – ˆ –

*Answer : c)***DS | GATE-2016 |**

**11.** The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _________. **[GATE – 2016]**

*Note: The height of a tree with a single node is 0.*

a. *64**b. 65**c. 66**d. 67*

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

* 12. *In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efﬁcient algorithm to set the twin pointer in each entry in each adjacency list?

**[GATE – 2016]**

a. Θ(n^{2})

b. Θ(n+m)

c. Θ(m^{2})

d. Θ(n^{4})

*Answer : b)*