### SET 3

Question 1

**A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :B

Solution :

Heap is a complete binary tree.

Question 2

**Consider two binary operators ' ⇑ ' and ' ⇓ ' with the precedence of operator ⇓ being lower than that of the operator ⇑. Operator ⇑ is right associative while operator ⇓ , is left associative. Which one of the following represents the parse tree for expression (7 ⇓ 3 ⇑ 4 ⇑ 3 ⇓ 2)?**

A : B :

C : D :

Answer Discuss it!

.

Correct answer is :B

Question 3

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

Answer Discuss it!

.

Correct answer is :B

Solution :

Sorting the n elements in the increasing order,and placing them in the inorder traversal nodes of the binary tree makes it only BST possible.

Question 4

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

C : B1 : height(n->right), B2 : max(h1,h2)

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

Answer Discuss it!

.

Correct answer is :A

Solution :

The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one. The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.

Question 5

**Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are**

A : Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

B : Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

C : Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

D : Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

Answer Discuss it!

.

Correct answer is :A

Question 6

**Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?**

A : O(1)

B : O(log n)

C : O(n)

D : O(n log n)

Answer Discuss it!

.

Correct answer is :C

Solution :

For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)

Question 7

**The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree? **

A : 10,20,15,23,25,35,42,39,30

B : 15,10,25,23,20,42,35,39,30

C : 15,20,10,23,25,42,35,39,30

D : 15,10,23,25,20,35,42,39,30

Answer Discuss it!

.

Correct answer is :D

Solution :

Pr eorder :30,20,10,15,25,23,39,35,42

Inorder :10,15,20,23,25,30,35,39,42

Question 1

.

Correct answer is :B

Solution :

Heap is a complete binary tree.

Question 2

.

Correct answer is :B

Question 3

.

Correct answer is :B

Solution :

Sorting the n elements in the increasing order,and placing them in the inorder traversal nodes of the binary tree makes it only BST possible.

Question 4

.

Correct answer is :A

Solution :

The box B1 gets exected when left subtree of n is NULL and right sbtree is not NULL. In this case, height of n will be height of right subtree plus one. The box B2 gets executed when both left and right sbtrees of n are not NULL. In this case, height of n will be max of heights of left and right sbtrees of n plus 1.

Question 5

.

Correct answer is :A

Question 6

.

Correct answer is :C

Solution :

For skewed binary search tree on n nodes, the tightest upper bound to insert a node is O(n)

Question 7

.

Correct answer is :D

Solution :

Pr eorder :30,20,10,15,25,23,39,35,42

Inorder :10,15,20,23,25,30,35,39,42