Binary Heap MCQ Quiz - Objective Question with Answer for Binary Heap - Download Free PDF

The correct answer is Option 1) Linear search.

Key Points

• Linear search (also called sequential search) does not require the array to be sorted.
• It works by checking each element one by one from the start until the desired element is found or the end of the array is reached.
• It is simple but less efficient than other searching algorithms for large datasets.

Additional Information 

• Binary search requires a sorted array and works by repeatedly dividing the search interval in half.
• Interpolation search also requires a sorted (uniformly distributed) array and estimates the position of the target value.
• Jump search works on sorted arrays and involves jumping ahead by fixed steps to find a block where the element might exist.
• Only linear search can be reliably used on unsorted data.

The correct answer is: option 2: Leaf

Concept:

A max heap is a complete binary tree in which the value of each node is greater than or equal to its children. This ensures that the maximum key is at the root.

Key Properties of Max Heap:

• The largest element is always at the root.
• Values decrease as you move from the root to the leaves.
• Thus, the smallest element must be in one of the leaf nodes, as these are the furthest from the root and have no children.

Explanation of options:

• Option 1 – Root: ❌ Contains the largest key in a max heap.
• Option 2 – Leaf: ✅ Correct. The smallest key will be among the leaf nodes.
• Option 3 – Node: ❌ Too vague — all positions in the tree are nodes.
• Option 4 – Either root or node: ❌ Incorrect — only leaf node can guarantee smallest key in a max heap.

Hence, the correct answer is: option 2: Leaf

Let T(n) be the number of different binary search trees on n distinct elements. Then:

T(n) = ∑_k=1ⁿ T(k-1) T(x) where x is:

• 1) n - k + 1
• 2) n - k
• 3) n - k - 1
• 4) n - k - 2

The correct answer is option 1: n - k + 1

Key Points

• The formula for the number of different binary search trees (BSTs) on n distinct elements can be understood as follows:
  • For each element k (from 1 to n) chosen as the root, there are T(k-1) ways to arrange the elements to the left of k (i.e., the left subtree) and T(x) ways to arrange the elements to the right of k (i.e., the right subtree).
  • In this context, x represents the number of elements remaining after choosing k and the elements to its left, which is n - k + 1.
  • Thus, the formula is: T(n) = ∑_k=1ⁿ T(k-1) T(n - k + 1).

Additional Information

• The number of different BSTs on n distinct elements is also known as the nth Catalan number, which has a closed-form expression: C(n) = (1 / (n + 1)) (2n choose n).
• This counting problem is fundamental in combinatorial mathematics and has applications in various fields, including computer science and algorithm design.
• Understanding the properties and formulas of BSTs helps in optimizing search and sort operations in data structures.

Key Points

•  A binary search tree (BST) is a binary tree where each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
• In a balanced BST, the time complexity for searching is O(log n) due to the tree's height being log(n).
• However, in a completely skewed (left or right) BST, the tree essentially behaves like a linked list.
• This means each node only has one child, and the tree's height becomes n (number of nodes).
• Therefore, the worst-case time complexity of searching an element in a completely skewed BST is O(n) because you may need to traverse all the nodes.

Important Points

•  In a balanced BST, operations like insertion, deletion, and search have average time complexities of O(log n).
• In a completely skewed BST, these operations degrade to O(n) in the worst case.

Additional Information

•  Self-balancing BSTs like AVL trees and Red-Black trees maintain their height close to log(n), ensuring efficient operations.
• Understanding the structure and properties of different types of BSTs is crucial for optimizing search operations in various applications.

The correct answer is 14.

Key Points

• The number of distinct binary search trees (BSTs) that can be formed with 'n' distinct keys is given by the nth Catalan number.
• The nth Catalan number is calculated using the formula: C(n) = (2n)! / ((n+1)!n!)
• For n = 4, the Catalan number is C(4) = (2*4)! / ((4+1)!4!) = 8! / (5!4!) = (8*7*6*5*4*3*2*1) / ((5*4*3*2*1)*(4*3*2*1)) = 40320 / (120*24) = 40320 / 2880 = 14
• Hence, the number of distinct binary search trees that can be created out of 4 distinct keys is 14.

Additional Information

• The Catalan numbers appear in various counting problems in combinatorial mathematics, often involving recursively-defined objects.
• Other applications of Catalan numbers include counting the number of expressions containing n pairs of correctly matched parentheses, the number of ways to triangulate a polygon, and more.
• The first few Catalan numbers for n = 0, 1, 2, 3, 4 are 1, 1, 2, 5, and 14 respectively.
• The formula for the nth Catalan number can be derived from the binomial coefficients.

The correct answer is "option 4".

CONCEPT:

A Binary Search Tree (BST) is also known as an ordered tree or sorted binary tree.

It is a binary tree with the following properties:

1. The left sub-tree of a node contains only nodes with key-value lesser than the node’s key value.

2.  The right subtree of a node contains only nodes with a key-value greater than the node’s key value.

There are three types of traversal:

1. In-order traversal: In this traversal, the first left node will traverse, the root node then the right node will get traversed.

2. Pre-order traversal: In this traversal, the first root node will traverse, the left node then the right node will get traversed.

3. Post-order traversal: In this traversal, the First left node will traverse, the right node then the root node will get traversed.

The in-order traversal of the Binary search tree always returns key values in ascending order.

EXPLANATION:

The pre-order traversal of given BST is:

30, 20, 10, 15, 25, 23, 39, 35, 42.

So, the In-order traversal of the BST is:

10, 15, 20, 23, 25, 30, 35, 39, 42.

The Binary Search Tree is:

So the post-order traversal of the tree is:

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

Hence, the correct answer is "option 4".

Statement I:  3, 5, 7, 8, 15, 19, 25

It doesn't violate Binary search tree property and hence it is the correct order of traversal.

Statement II: 5, 8, 9, 12, 10, 15, 25

15 is left of 12 which violates binary search tree property.

Statement III: 2, 7, 10, 8, 14, 16, 20

14 is left of 10 which violates binary search tree property.

Statement IV: 4, 6, 7, 9 18, 20, 25 

It doesn't violate Binary search tree property and hence it is the correct order of traversal.

The correct answer is "option 3".

CONCEPT:

The binary heap is a complete binary tree with heap properties.

Binary heap is either max. heap (root value > all key values) or min. heap. (root value < all key values).

EXPLANATION:

Binary heap elements can be represented using an array with index value i (i < = n),

Parent node of element will be at index: floor (i / 2)

Left Child node will be at index: 2 * i

Right child node will be at index: 2 * i + 1

Hence, the index of the parent is floor (i / 2).

The correct answer is option 4.

Concept:

The given data,

preorder = ABCDEF

In order = BADCFE

The binary tree for the traversal is,

Post order for the above tree is,

BDFECA

Hence the correct answer is BDFECA.

Concept:

Max heap: Root node value should be greater than child nodes.

Whenever we insert new element in heap, we will insert at the last level of heap.

After inserting element if max heap doesn’t follow the property then we will apply heapify algorithm until we get max heap.

Explanation:

Initial Heap

After inserting 1:

After inserting 7:

It doesn’t follow max heap property because 7 is greater than 5 so we will apply heapify algorithm on node 7.

After applied heapify algorithm:

Level order: 10, 8, 7, 3, 2, 1, 5

Hence option 1 is the correct answer.

Concept:

AVL tree is a height balanced binary search tree.

Insertion in AVL takes Θ (log n) time and height of an AVL tree with n nodes is log n.

Calculation:

The given AVL tree already has n nodes. Now each successive insertion would involve two operations: Θ(log n) to find the appropriate place to insert and another Θ(log n) to do any rotation if required. So in worst case, each successive insertion requires 2 log n operation i.e. Θ (log n).

Therefore, n² insertions would require Θ (n² log n). 

The correct answer is option 1

Concept:

A binary search tree (BST) is a node-based binary tree data structure and it follows the following points

1. Left sub-tree nodes key value will exist only if lesser than the parent node key value.
2. Right sub-tree nodes key value will exist only if greater than the parent node key value.
3. Left sub-tree and Right sub-tree must be a Binary search tree.
    

Explanation:

Step 1: First 10 comes and now that is the Root node.

Step 2: Now 1 came and 1 < 10 then insert Node 1 to the Left of Node 10.

Step 3: Now 3 came and 3 < 10 go to the Left of                  

Node 10 and check 3 > 1 then insert Node 3  to the Right of Node  1.

Step 4: Now 5 came  and 5 < 10 go to the  Left  of  

Node 10 and check 5 > 1 go to the Right of Node 1 then check  5 > 3 then insert Node 5 to the Right of Node 3.

Step 5: Now 15 came and 15 > 10 then insert Node 15 to the Right of Node 10.

Step 6: Now 12 came and 12 > 10  go to the  Right of  Node 10 and check 15 > 12 then insert Node 12  to the Left of Node 15.

Step 7:  Now 16 came and 16 > 10 go to the Right of                  

10 and check 16 > 15 then insert 16  to the Right of Node 15.

After step 7,  we can count the height of the tree as 3.

Important Points

Follow the longest path in the tree and count the edges that are height.

Tips To Learn:

Left sub-tree(key)<Node(key)<Right sub-tree(key)

Node(key): Parent node of  Left sub-tree and Right sub-tree

The correct answer is option 2.

Concept:

Binary tree:

A binary tree is a tree in which no node can have more than two children. Every binary tree has parents, children, siblings, leaves, and internal nodes.

Height of a binary tree:

The height of a binary tree is equal to the largest number of edges from the root to the most distant leaf node.

Explanation:

Hence the correct answer is 2.

The correct answer is option 1.

Key Points

• In a general scenario,  binary search mid-value computed with, mid=(low+high)/2.
• However, with a vast list of elements, "high" would be a very large value. As a result, it's possible that it's beyond the Integer limit. It's known as an integer overflow.
• To stop this Integer overflow, the ‘mid' value can also be determined using, mid  = (High - Low)/2 + Low
• Integer overflow is never an issue with this form.

Explanation

mid : = (High - Low)/2 + Low 

mid : =  High/2 - Low/2 + low 

mid : =   (High + Low)/2

Alternate Method

• Option D is removed because it is the same as the incorrect option.
• Taking into account The low index is 10, while the high index is 15.
• Option B returns a mid-index of 3 that is not even in the sub-array index.
• Choice C returns a mid-index of 2 that isn't even in the sub-array index.
• Option A is the best solution.

Hence the correct answer is mid : = (High - Low)/2 + Low .

Concepts:

Minimum height of the tree is when all the levels of the binary search tree (BST) are completely filled.

Maximum height of the BST is the worst case when nodes are in skewed manner.

Formula:

Minimum height of the BST with n nodes is ⌈log2 (n + 1)⌉ - 1

The maximum height of the BST with n nodes is n - 1.

BST with a maximum height:

Insertion:

Traverser the BST to the maximum height

Worst-case time complexity of Insertion = θ (n - 1) ≡ θ (n)

Deletion:

Traverser the BST to the maximum height

Worst-case time complexity of  = θ (n - 1) ≡ θ (n)