Logical Mind: Data STRucture gate 1

GATE-1995
1. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is

(a) log₂n (b) n-1 (c) n (d) 2ⁿ

Ans: option(b)

Explanation:
A binary tree is a tree data structure in which each node has at most two child nodes.
The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1, or 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.

GATE-1996
2. In the balanced binary tree in the figure given below, how many nodes will become unbalanced when a node is inserted as a child of the node “g”?

(a) 1 (b) 3 (c) 7 (d) 8

Ans: option(b)
Explanation:

A binary tree T is balanced if:
1) Left subtree of T is balanced
2) Right subtree of T is balanced
3) The difference between heights of left subtree and right subtree is not more than 1.

After inserting a node as a child of g, find the balance factors of each node.

Balance Factor of node a = height of left subtree - height of right subtree = 2

Similarly the balance factors of the nodes are b = 2, c = 2, d = 0, g = 1, e = 1 and f = 0.

Nodes having balance factor 1, 0 and -1 are balanced nodes. All other nodes are unbalanced nodes.

Note: Whenever a node gets unbalanced, all the nodes on the path from first unbalanced node to till the root also gets unbalanced. In this problem first unbalanced node was c. So all the nodes from c to root a got unbalanced (i.e. c,b and a.)

GATE - 1996
3. Which of the following sequences denotes the post order traversal sequence of
the tree of the above question 2?
(a) f e g c d b a (b) g c b d a f e (c) g c d b f e a (d) f e d g c b a

Ans: option(c)
Explanation:

As shown in the figure above start from the node a. Each node has been numbered as 1,2,3. When u are finding postorder start from the root and consider the node only when u reach point 3. As shown above the red line indicates the path through which the tree is traversed. The first node that reaches point 3 on traversing is node g, then c, then d, then b, then f, then e and then a. Hence we are considering point 3 for postorder. If you consider point 2 then u will get inorder, and if you consider point 1 u will get preorder.

GATE-1996
4. A binary search tree is generated by inserting in order the following integers:
50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
The number of nodes in the left subtree and right subtree of the root respectively is
(a) (4, 7) (b) (7, 4) (c) (8, 3) (d) (3, 8)

Ans: option (b)
Explanation:
Difference between Binary Tree and Binary Search Tree.

Binary Tree - Tree in which each node has at most two child nodes.

Binary search tree - A binary tree in which the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than or equal to the parent. Binary search tree is used for efficient searching. The binary search tree for the above problem is given below.

GATE-1997
5. A binary search tree contains the value 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in pre-order and the values are printed out. Which of the following sequences is a valid output?
(a) 5 3 1 2 4 7 8 6 (b) 5 3 1 2 6 4 8 7
(c) 5 3 2 4 1 6 7 8 (d) 5 3 1 2 4 7 6 8

Ans: option (d)
Explanation:
Considering the pre-order traversal, try to construct the Binary Search Tree (BST) for each option. We can construct the BST for option (d) only. Other options will violate the BST conditions.

GATE-1998
6. Which of the following statements is false?
(a) A tree with n nodes has (n – 1) edges

(b) A labeled rooted binary tree can be uniquely constructed given its postorder and preorder traversal results.

(c) A complete binary tree with n internal nodes has (n + 1) leaves.
(d) The maximum number of nodes in a binary tree of height h is (2^h+1-1)

Ans: option (c)
Explanation:
option (c) is false. Consider the complete binary tree below. The below complete binary tree has 2 internal nodes, but has only 2 leaves. Hence statement (c) is false.
1
/ \
2 3
/
4

A full binary tree (proper binary tree or 2-tree or strictly binary tree) is a tree in which every node in a binary tree has exactly 0 or 2 children.

A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

For more details Refer: http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

GATE-1998

7. A complete n-ary tree is one in which every node has 0 or n sons. If x is the number of internal nodes of a complete n-ary tree, the number of leaves in it is given by

(a) x(n – 1) +1 (b) xn - 1 (c) xn + 1 (d) x(n+1)

Ans: option (a)

Explanation:

In the above figure, circle represents an internal node and square represents leaf nodes. from the above complete n-ary tree we can see that: -

With 1 internal node => n leaf nodes

With 2 internal node => (n + n-1) leaf nodes = (2n - 1) leaf nodes

With 3 internal node => (n + n + n-2) leaf nodes = (3n - 2) leaf nodes

With x internal node => = (xn - (x-1)) leaf nodes

= xn - x + 1 = x(n -1) +1 leaf nodes.

GATE-2000
8. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?
(a) (1 2 (4 5 6 7))
(b) (1 ((2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 (2 3 NULL) (4 5))

Ans: option (c)
Explanation:
option (a) is not possible because the right subtree (4 5 6 7) is not in the correct format of (X Y Z).
option (b) is not possible because (2 3 4) cannot be the root of the left subtree of 1.
option (b) is not possible because (4 5) is not in the correct format. 4's right child is not specified. If it was (1 (2 3 NULL) (4 5 NULL)), then valid.

GATE-2000

9. The most appropriate matching for the following pairs

X: depth first search 1: heap

Y: breadth-first search 2: queue

Z: sorting 3: stack

is:

(a) X—1 Y—2 Z-3 (b) X—3 Y—1 Z-2

Ans: option (c)

Explanation:

Stack is used for DFS. Queue is used for BFS. Heaps are used in algorithms such as Dijkstra's algorithm, and in the sorting algorithm Heapsort.

GATE-2000
10. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the above

Ans: (d)
Explanation:
Note that we have to consider a complete binary tree.
a
/ \
b c
/ \ /
d e f
Preorder : a b d e c f
Inorder : d b e a f c
Postorder: d e b f c a
So, LASTPOST = a, LASTPRE = f, LASTIN = c

GATE-2003

11. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

a) 7 5 1 0 3 2 4 6 8 9

b) 0 2 4 3 1 6 5 9 8 7

c) 0 1 2 3 4 5 6 7 8 9

d) 9 8 6 4 2 3 0 1 5 7

Ans: option (c)

Explanation:
Binary search tree - A binary tree in which the left child contains only nodes with values less than the parent node, and the right child contains only nodes with values greater than or equal to the parent.

Note: In-order traversal of a BST gives elements in increasing order.

GATE-2004

12. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
(a) 2 (b) 3 (c) 4 (d) 6

Ans: option (b)
Explanation:
The depth (or height) of a tree is the length of the path from the root to the deepest node in the tree. A rooted tree with only one node (the root) has a depth of zero.

GATE-2006

13. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be.

(a) log2n (b) n (c) 2n + 1 (d) 2ⁿ — 1

Ans: option (d)

Explanation:

The question is "To be able to store any binary tree on n vertices the minimum size of X should be". Give importance to any. Suppose u have a binary tree with 2 nodes. It can be as shown below.

A A

/ or \

B B

So, in a worst case, the binary tree can be as shown in the second form. Therefore B will be stored in X[3]. Now consider binary tree with 3 nodes A, B and C. In worst case, root A has a right child B and B has right child C. So C has to be stored in X[7]. hence even if we have only 3 nodes we require an array of minimum size 7.

GATE-2007

14. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

(a) 2^h -1 (b) 2^h-1 – 1

Ans: option (c)

Note:

The number of nodes in a binary tree of height h is at least h + 1, and at most 2^h+1 -1 here h is the depth of the tree. For more properties refer: http://en.wikipedia.org/wiki/Binary_tree#Properties_of_binary_trees

GATE-2007

15. The maximum number of binary trees that can be formed with three unlabeled nodes is:

(a) 1 (b) 5 (c) 4 (d) 3

Ans: option (b)

Explanation:

The maximum number of binary trees that can be formed with 'n' unlabeled nodes is C(2n,n) / n+1.

The binary trees that can be formed with three unlabeled nodes are given below:

1) 2) 3)

O O O

/ \ / \

O O O O

/ \

O O

4) 5)

O O

/ \

O O

\ /

O O

GATE-2007

16. The inorder and preorder traversal of a binary tree are d b e a f c g anda b d e c f g, respectively. The postorder traversal of the binary tree is:

(A) d e b f g c a

(B) e d b g f c a

(D) d e f g b c a

Ans: option (a)

Explanation:

/ \

b c

/ \ / \

d e f g

Considering the inorder, look at the preorder to find the next root node and construct the tree. Then find the postorder, as we have done in the previous questions.

GATE-2002

17. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

(a) n/2 (b) (n-1)/3 (c) (n-1)/2 (d) (2n+1)/3

Ans: option (d)

Explanation:

The number of leaf nodes for an n-ary tree where each node has n children or no children is L = (n-1)I + 1, where L is the number of leaf nodes and I is the number of internal nodes. See question number 7, for details.

Therefore for the above problem, L = (3 -1)I + 1

The total number of nodes is sum of leaf nodes and internal nodes (i.e. L + I )

Therefore, number of internal nodes, I = n - L

L = 2 ( n- L ) + 1

L = 2n - 2L + 1

3L = 2n + 1

Therefore L = (2n +1)/3

GATE-2005

18. How many distinct binary search trees can be created out of 4 distinct keys?

(a) 5 (b) 14 (c) 24 (d) 42

Ans: option (b)

Explanation:

The maximum number of distinct binary search trees that can be formed with 'n' distinct keys is C(2n,n) / n+1.

GATE-2002

19. A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

(a) log₂n (b) log_4/3n (c) log₃n (d) log_3/2n

Ans: option (d)

Explanation:

Consider the weighted balance tree given below.

/ \

b c

Here the height is 2, and only option (d) satisfies it.

GATE-2005

20. Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

(a) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95

(b) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29

(d) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Ans: option (a)

Explanation:

As we have already seen in question number 11, In-order traversal of a BST gives elements in increasing order. Hence option (a)

GATE-2004

21. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

i) Preorder and Postorder

ii) Pnorder and Postorder

iii) Preorder and Inorder

iv) Level order and Postorder

(a) (i) only (b) (ii), (iii) only (c) (iii) only (d) (iv) only

Ans: option (b)

Explanation:

Consider a binary tree having two labels, a and b. We can have two binary trees as below.

a a

/ or \

b b

Traversals for the first tree is given below:-

Preorder : a b

Postorder : b a

Levelorder: a b

Inorder : b a

Traversals for the second tree is given below:-

Preorder : a b

Postorder : b a

Levelorder: a b

Inorder : a a

As you can see, Preorder, Postorder and Level-ordertraversals are the same for the trees. hence, if one of the traversal is 'Inorder' then the tree can be constructed, otherwise not.

GATE-2005

22. Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?

(a) Database relations have a large number of records

(b) Database relations are sorted on the primary key

(d) Data transfer form disks is in blocks.

Ans: option (d)

Explanation:

The B-tree is a generalization of a binary search tree. In B-Tree a node can have more than two children. The B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems. Databases are usually stored in disks. Whenever we require a record from the database, usually a block is transferred to the main memory. Hence a disk block contains fairly large number of keys. Each node in BST contains only one key, but B-Tree is designed to contain large number of keys so that tree height is small. B-tree keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time.

For more details on B-Tree: http://en.wikipedia.org/wiki/B-tree

GATE-2006

23. A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

(a) 1, 3, 5, 6, 8, 9 (b) 9, 6, 3, 1, 8, 5

Ans: option (d)

Explanation:

A heap is a specialized tree-based data structure that satisfies the heap property:

Each node is greater than or equal to each of its children (this kind of heap is called max heap) or Each node is less than or equal to each of its children (this kind of heap is called min heap).

Here it is a 3-ary max heap, therefore each node must be greater than or equal to each of its children. Hence option (d) has only valid sequence of elements).

Option (a) - not valid because, only the highest element can be in the root. Here it is 1.

Option (b) - not valid because, 8 comes as the child of node 6.

Option (c) - not valid because, 5 comes as the child of node 3.

Option (d) - valid.

/ | \

5 6 8

/ |

3 1

GATE-2006

24. Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question, Which one of the following is the sequence of items in the array representing the resultant heap?

(a) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4 (b) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Ans: option (a)

Explanation:

To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle up, heapify-up, or cascade-up), by following this algorithm:

1. Add the element to the bottom level of the heap.

2. Compare the added element with its parent; if they are in the correct order, stop.

3. If not, swap the element with its parent and return to the previous step.

Refer: http://en.wikipedia.org/wiki/Binary_heap

Step1: Add the 7 to the bottom level of the heap:

/ | \

5 6 8

/ | \

3 1 7

Step 2: Compare the added element (7) with its parent (5); Not in order, so step 3.

Step3: Swap the element with its parent.

/ | \

7 6 8

/ | \

3 1 5

Proceed to step 2 again. If they are in the correct order, stop.

Continuing the above procedure with all the elements given, we will get the below shown heap.

/ | \

7 9 8

/ | \ / | \

3 1 5 2 6 4

GATE-2005

25. A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:

10, 8, 5, 3, 2

Two new elements '1' and '7' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

(a) 10, 8, 7, 5, 3, 2, 1 (b) 10, 8, 7, 2, 3, 1, 5

Ans: option(d)

Explanation:

The maximum number of children each node can have depends on the type of heap. Since here nothing is mention we consider that the heap is a binary heap (i.e. each node has at most 2 children).

Initially the heap will be as shown below.

/ \

8 5

/ \

3 2

To add an element, perform the procedure detailed in the question 24. After insertion the heap will be as shown below.

/ \

8 7

/ \ / \

3 2 1 5

GATE -2009

26. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

(a) 25,12,16,13,10,8,14 (b) 25,14,13,16,10,8,12

Ans: option (c)

GATE-2009

27. What is the content of the array after two delete operations on the correct answer to the previous question?

(a) 14,13,12,10,8 (b) 14,12,13,8,10

Ans: option(d)

Explanation:

The procedure for deleting the root from the heap :

1. Replace the root of the heap with the last element on the last level.

2. Compare the new root with its children; if they are in the correct order, stop.

3. If not, swap the element with one of its children and return to the previous step. (Swap with its smaller child in a min-heap and its larger child in a max-heap.)

Initially we have (from the above question)

/ \

14 16

/ \ / \

13 10 8 12

Delete 25:

Step1: Replace the root of the heap (25) with the last element on the last level (12)

/ \

14 16

/ \ /

13 10 8

Step2: Compare the new root with its children. Not on the correct order, hence step 3.

Step3: Swap the element with one of its children. (Since max-heap swap with larger child)

/ \

14 12

/ \ /

13 10 8

Delete 16 using the above procedure. Finally we will get the following heap.

/ \

13 12

/ \

8 10

GATE-2009

28. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.

(a) 2 (b) 3 (c) 4 (d) 5

Ans: option (b)

Explanation:

An AVL tree is a binary tree with the following property:

In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.

Maintaining the above property try to construct a binary tree with 7 nodes.

We will get the following two structures. In both these trees, the height is 3.

1 & 1

/ \ / \

2 3 2 3

/ \ / \ / \

4 5 6 4 5 6

/ \

7 7

GATE-2012

29. The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

The appropriate expression for the two boxes B1 and B2 are

(a) B1 : (1 + height(n->right)), B2 : (1 + max(h1,h2))

(b) B1 : (height(n->right)), B2 : (1 + max(h1,h2))

(d) B1 : (1 + height(n->right)), B2 : max(h1,h2)

Ans: option (a)

GATE-2011

30. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

(a) 0 (b) 1 (c) n! (d) (1/(n+1)).2nCn

Ans: option (b)
Explanation:

The given unlabelled binary search tree can be populated with the elements in 1 way only, because the inorder traversal of that tree should generate the elements in increasing order. (Note: In-order traversal of a BST gives elements in increasing order).

Top Ten Colleges in Delhi for IT students.

UGC Preparation for Freshers

Deepak Singh

(Assistant Professor)

Logical Mind

Data STRucture gate 1

No comments:

Post a Comment

About Me