**DS | GATE-2013 | Data Structures**

- G is a graph on n vertices and 2n – 2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
**[GATE – 2013]**

a. For every subset of k vertices, the induced subgraph has at most 2k–2 edges

b. The minimum cut in G has at least two edges

c. There are two edge-disjoint paths between every pair to vertices

d. There are two vertex-disjoint paths between every pair of vertices

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

- You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, …, n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?
**| GATE-2013 |**

a. θ(log n)

b. θ(n)

c. θ(nlog n)

d. None of the above, as the tree cannot be uniquely determined

*Answer : b)*

- We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is :
**| GATE-2013 |**

a. θ(n)

b. θ(log n)

c. θ(nlog n)

d. θ(n^{2})

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

**4.** The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,7 in the given order. What will be the contents of the list after the function completes execution? struct node { int value; struct node * next; }; Void rearrange (struct node * list){ struct node * p, * q; int temp; if (!list !list – > next)return; p = list; q = list – > next; while (q){ temp = p- > value;p- > value = q- > value; q- > value = temp;p = q- > next; q = p ? p- > next : 0; } } **| GATE-2013 |**

a. 1,2,3,4,5,6,7

b. 2,1,4,3,6,5,7

c. 1,3,2,5,4,7,6

d. 2,3,4,5,6,7,1

*Answer : b)*

**5. **Which of the following is TRUE? ** | GATE-2013 |**

a. The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)

b. The cost of searching an AVL tree is θ (log n) but that of a complete binary tree is θ (n log n)

c. The cost of searching a binary search tree is O (log n ) but that of an AVL tree is θ(n)

d. The cost of searching an AVL tree is θ (n log n) but that of a binary search tree is O(n)

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

**6.** The following three are known to be the preorder, inorder and postorder sequences of a binary tree. But it is not known which is which. MBCAFHPYK KAMCBYPFH MABCKYFPH Pick the true statement from the following. **[ GATE – 2013 ]**

a. I and II are preorder and inorder sequences, respectively

b. I and III are preorder and postorder sequences, respectively

c. II is the inorder sequence, but nothing more can be said about the other two sequences

d. II and III are the preorder and inorder sequences, respectively

*Answer : d)*

**7.** Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first visited. Which all of the above is (are) possible output(s)?**[ GATE – 2013 ]**

a. I and III only

b. II and III only

c. II, III and IV only

d. I, II and III only

*Answer : b)*

**8. **Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = k mod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?**[ GATE – 2013 ]**

a. 2

b. 4

c. 6

d. 7

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

**9.** A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. **[ GATE – 2013 ]**

I. 81, 537, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

a. II and III only

b. I and III only

c. III only

d. III and IV only

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

**10. **A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81, 537, 102, 439, 285, 376, 305 II. 52, 97, 121, 195, 242, 381, 472 III. 142, 248, 520, 386, 345, 270, 307 IV. 550, 149, 507, 395, 463, 402, 270 Which of the following statements is TRUE?** [ GATE – 2013 ]**

a. I, II and IV are inorder sequences of three different BSTs

b. I is a preorder sequence of some BST with 439 as the root

c. II is an inorder sequence of some BST where 121 is the root and 52 is a leaf

d. IV is a postorder sequence of some BST with 149 as the root

*Answer : c)*

- The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity :
**[ GATE – 2013 ]**

a. θ(m+n)

b. θ(n)

c. θ(m)

d. θ(mn)

*Answer : a)*

- The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is :
**[ GATE – 2013 ]**

a. MNOPQR

b. NQMPOR

c. QMNPRO

d. QMNPOR

*Answer : c)*

**13.** A Binary search tree (BST) stores values in the range 37 to 573 . Consider the following sequence of keys. **[ GATE – 2013 ]**

I. 81, 573, 102, 439, 285, 376, 305

II. 52, 97, 121, 195, 242, 381, 472

III. 142, 248, 520, 386, 345, 270, 307

IV. 550, 149, 507, 395, 463, 402, 270

How many distinct BSTs can be constructed with 3 distinct Keys?

a. 4

b. 5

c. 6

d. 9

*Answer : b)*

**14. **A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. n_{3} can be expressed as : **[ GATE – 2013 ]**

a. n1 + n2 -1

b. n1 – 2

c. [(n1 + n2) / 2]

d. n2 – 1

*Answer : b)*

**15.** A binary tree with n > 1 nodes has n_{1}, n_{2} and n_{3} nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbors. Starting with the above tree, while there remains a node v of degree two in the tree, add an edge between the two neighbors of v and then remove v from the tree. How many edges will remain at the end of the process? ** [ GATE – 2013 ]**

a. 2 * n_{1} – 3

b. n_{2} + 2 * n_{1} – 2

c. n_{3} – n_{2}

d. n_{2} + n_{1} – 2

*Answer : a)*