Final Quiz

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

• (a) log2n

• (b) n-1

• (c) n

• (d) 2n

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”?

• 1

• 3

• 7

• 8

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)

Which of the following statements is false?

• A tree with n nodes has (n – 1) edges

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

• A complete binary tree with n internal nodes has (n + 1) leaves.

• The maximum number of nodes in a binary tree of height h is (2h+1-1)

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)

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))

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

• (c) X—3 Y—2 Z-1

• (d) X—2 Y—3 Z-1

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) Both are True

• (d) None of the above

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

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) 2h -1

• (b) 2h-1 – 1

• (c) 2h+1 -1

• (d) 2h+1