Advance Data Structure Quiz-a-2

1. Which of the following trees have height as O(lgn) where number of nodes is n.

R-B Tree

Binary Search Tree

Binary Tree

2-3 Tree

R-B Tree has a height of O(lgn) where the number of nodes is n. This is because R-B Trees are balanced binary search trees that maintain a balance between the left and right subtrees. The height of an R-B Tree is always logarithmic with respect to the number of nodes, ensuring efficient operations like search, insertion, and deletion. Therefore, R-B Trees are suitable for scenarios where a large number of operations need to be performed on a dynamic set of data.

Explanation

R-B Tree has a height of O(lgn) where the number of nodes is n. This is because R-B Trees are balanced binary search trees that maintain a balance between the left and right subtrees. The height of an R-B Tree is always logarithmic with respect to the number of nodes, ensuring efficient operations like search, insertion, and deletion. Therefore, R-B Trees are suitable for scenarios where a large number of operations need to be performed on a dynamic set of data.

2. Which type of traversal of binary search tree outputs the value in sorted order?

Pre-order

Post-order

In-order

None of these

In-order traversal of a binary search tree outputs the values in sorted order because it follows the left-root-right order. This means that it first visits the left subtree, then the root node, and finally the right subtree. By visiting the left subtree first, it ensures that the smaller values are visited before the larger values, resulting in a sorted output.

Explanation

In-order traversal of a binary search tree outputs the values in sorted order because it follows the left-root-right order. This means that it first visits the left subtree, then the root node, and finally the right subtree. By visiting the left subtree first, it ensures that the smaller values are visited before the larger values, resulting in a sorted output.

3. Suppose a binary tree is constructed with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be?

(n+1)/2

(n-1)/2

(n/2)-1

(n+1)/2

The maximum height of a binary tree with n nodes, where each node has either zero or two children, can be found by considering the worst-case scenario. In this case, the tree will be a complete binary tree, where all levels are completely filled except possibly for the last level, which is filled from left to right. The number of nodes in a complete binary tree can be calculated using the formula 2^(height+1) - 1. Solving this equation for height, we get height = log2(n+1) - 1. Since the question asks for the maximum height, we take the ceiling of this value, which gives us (n-1)/2. Therefore, the correct answer is (n-1)/2.

Explanation

The maximum height of a binary tree with n nodes, where each node has either zero or two children, can be found by considering the worst-case scenario. In this case, the tree will be a complete binary tree, where all levels are completely filled except possibly for the last level, which is filled from left to right. The number of nodes in a complete binary tree can be calculated using the formula 2^(height+1) - 1. Solving this equation for height, we get height = log2(n+1) - 1. Since the question asks for the maximum height, we take the ceiling of this value, which gives us (n-1)/2. Therefore, the correct answer is (n-1)/2.

4. If we first delete a key from an R-B tree and add it back then, how does the structure of resulting R-B tree compare with original R-B tree?

Both trees will be same in all cases

Both will be different in all the cases

Both trees may be same or different depending on the case.

When a key is deleted from an R-B tree and then added back, the resulting structure of the tree can be the same or different from the original R-B tree. This is because the structure of the resulting tree depends on the specific case and the key that was deleted and added back. In some cases, the structure may remain unchanged, while in other cases, it may be different due to the re-balancing operations performed during the deletion and re-insertion process. Therefore, it is not possible to determine whether the trees will be the same or different without considering the specific case.

Explanation

When a key is deleted from an R-B tree and then added back, the resulting structure of the tree can be the same or different from the original R-B tree. This is because the structure of the resulting tree depends on the specific case and the key that was deleted and added back. In some cases, the structure may remain unchanged, while in other cases, it may be different due to the re-balancing operations performed during the deletion and re-insertion process. Therefore, it is not possible to determine whether the trees will be the same or different without considering the specific case.

5. The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?

2exp(h-1)-1

2exp(h+1)-1

2exp(h)-1

2exp(h+1)-1

The correct answer is 2^(h+1) - 1. The maximum number of nodes in a binary search tree (BST) can be calculated using the formula 2^(h+1) - 1, where h is the height of the tree. This formula is derived from the fact that each node in a BST has at most two children. The height of the tree determines the number of levels, and at each level, the number of nodes doubles. Therefore, the maximum number of nodes is obtained when the tree is completely balanced and has the maximum possible height.

Explanation

The correct answer is 2^(h+1) - 1. The maximum number of nodes in a binary search tree (BST) can be calculated using the formula 2^(h+1) - 1, where h is the height of the tree. This formula is derived from the fact that each node in a BST has at most two children. The height of the tree determines the number of levels, and at each level, the number of nodes doubles. Therefore, the maximum number of nodes is obtained when the tree is completely balanced and has the maximum possible height.

6. A 2-3 is a tree such that a) All internal nodes have either 2 or 3 children b) All path from root to leaves have the same length The number of internal nodes of a 2-3 tree having 9 leaves could be

4

5

6

7

A 2-3 tree is a type of tree where all internal nodes have either 2 or 3 children. In this case, the tree has 9 leaves. To determine the number of internal nodes, we need to find the number of levels in the tree. Since all paths from the root to leaves have the same length, the number of levels in the tree will be equal to the length of any path from the root to a leaf.

Since there are 9 leaves, the length of any path from the root to a leaf will be log base 2 of 9, which is approximately 3.17. Since we need to have a whole number of levels, we can round up to the nearest whole number, which is 4. Therefore, the number of internal nodes in the 2-3 tree with 9 leaves could be 4.

Explanation

A 2-3 tree is a type of tree where all internal nodes have either 2 or 3 children. In this case, the tree has 9 leaves. To determine the number of internal nodes, we need to find the number of levels in the tree. Since all paths from the root to leaves have the same length, the number of levels in the tree will be equal to the length of any path from the root to a leaf.

Since there are 9 leaves, the length of any path from the root to a leaf will be log base 2 of 9, which is approximately 3.17. Since we need to have a whole number of levels, we can round up to the nearest whole number, which is 4. Therefore, the number of internal nodes in the 2-3 tree with 9 leaves could be 4.

7. The tree is an example of

2-3 tree

Binary search Tree

Binomial Heap

Fibonacci Heap

A binary search tree is a type of binary tree where each node has a key that is greater than all keys in its left subtree and less than all keys in its right subtree. This property allows for efficient searching, insertion, and deletion operations. In the given question, the tree is described as an example, suggesting that it represents a specific instance of a binary search tree.

Explanation

A binary search tree is a type of binary tree where each node has a key that is greater than all keys in its left subtree and less than all keys in its right subtree. This property allows for efficient searching, insertion, and deletion operations. In the given question, the tree is described as an example, suggesting that it represents a specific instance of a binary search tree.

8. If we first delete a key from 2-3 tree and then add it back then, how does the structure of resulting 2-3 tree compare with original 2-3 tree?

Both trees will be same in all cases

Both will be different in all the cases

Both trees may be same or different depending on the case.

The structure of the resulting 2-3 tree may be the same or different from the original 2-3 tree depending on the case. When a key is deleted and then added back, the resulting tree may have the same structure as the original if the key is added back to the same location. However, if the key is added back to a different location, the structure of the resulting tree will be different from the original. Therefore, both trees may be the same or different depending on the specific case.

Explanation

The structure of the resulting 2-3 tree may be the same or different from the original 2-3 tree depending on the case. When a key is deleted and then added back, the resulting tree may have the same structure as the original if the key is added back to the same location. However, if the key is added back to a different location, the structure of the resulting tree will be different from the original. Therefore, both trees may be the same or different depending on the specific case.

9. The following are the case of ...................in red black Tree

Insert

Find

Delete

None of these

The correct answer is "Delete". In a red-black tree, deletion of a node is one of the operations that can be performed. When a node is deleted, the tree needs to be adjusted to maintain the properties of a red-black tree, such as the balance of black nodes and the red-black coloring. Therefore, deletion is a case that needs to be considered in red-black tree operations.

Explanation

The correct answer is "Delete". In a red-black tree, deletion of a node is one of the operations that can be performed. When a node is deleted, the tree needs to be adjusted to maintain the properties of a red-black tree, such as the balance of black nodes and the red-black coloring. Therefore, deletion is a case that needs to be considered in red-black tree operations.

10. The rotation need to be done is

LL

LR

RL

None of these

The correct answer is LL, which stands for Left Left rotation. This means that the rotation needs to be done by rotating the given object twice to the left.

Explanation

The correct answer is LL, which stands for Left Left rotation. This means that the rotation needs to be done by rotating the given object twice to the left.

11. Suppose we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequence could not be the sequence of the node examined?

925, 202, 911, 240, 912, 245, 258, 363

924, 220, 911, 244, 898, 258, 362, 363

925, 202, 911, 240, 912, 245, 258, 363

2, 399, 387, 219, 266, 382, 381, 278, 363

not-available-via-ai

Explanation

not-available-via-ai

12. For a 2 -3 Tree which of the following is true

A 2-3 Tree may have root node with only one child

Maximum number of children of any node is 3

A leave can hight either 2 or 3 in a 2-3 tree

Minimum number of children of any node is 2.

In a 2-3 Tree, the maximum number of children that any node can have is 3. This means that a node can have up to 3 child nodes. This property of 2-3 Trees allows for efficient balancing and searching operations, as the tree can accommodate a larger number of elements in each node. Having more children per node reduces the overall height of the tree, leading to faster search and insertion times.

Explanation

In a 2-3 Tree, the maximum number of children that any node can have is 3. This means that a node can have up to 3 child nodes. This property of 2-3 Trees allows for efficient balancing and searching operations, as the tree can accommodate a larger number of elements in each node. Having more children per node reduces the overall height of the tree, leading to faster search and insertion times.

13. 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 the node in the left sub-tree and right sub-tree of the root, respectively, is

(4,7)

(7,4)

(8,3)

(3,8)

The correct answer is (4,7) because when the integers are inserted in order into the binary search tree, the root node will be 50. The left sub-tree of the root will have 4 nodes (15, 5, 20, 37) and the right sub-tree of the root will have 7 nodes (62, 58, 91, 60, 24, 3, 8).

Explanation

The correct answer is (4,7) because when the integers are inserted in order into the binary search tree, the root node will be 50. The left sub-tree of the root will have 4 nodes (15, 5, 20, 37) and the right sub-tree of the root will have 7 nodes (62, 58, 91, 60, 24, 3, 8).

14. The run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is

O(nlg(n))

O(√n)

O(n)

O(lg(n))

The runtime for traversing all the nodes of a binary search tree and printing them in order is O(nlg(n)). This is because in a binary search tree, each node has at most two children. Therefore, in the worst case scenario, we need to visit each node exactly once. Additionally, printing the nodes in order requires sorting them, which has a time complexity of O(nlg(n)). Therefore, the overall runtime is O(nlg(n)).

Explanation

The runtime for traversing all the nodes of a binary search tree and printing them in order is O(nlg(n)). This is because in a binary search tree, each node has at most two children. Therefore, in the worst case scenario, we need to visit each node exactly once. Additionally, printing the nodes in order requires sorting them, which has a time complexity of O(nlg(n)). Therefore, the overall runtime is O(nlg(n)).

15. If n numbers are to be sorted in ascending order in O(nlogn) time, which of the following tree can be used

Binary Tree

Binary Search Tree

Max- heap

Min-Heap

A binary tree can be used to sort n numbers in ascending order in O(nlogn) time. The binary tree can be constructed by inserting each number into the tree in a specific order. Then, by performing an in-order traversal of the tree, the numbers can be retrieved in ascending order. However, it is important to note that a binary search tree, max-heap, or min-heap cannot guarantee the O(nlogn) time complexity for sorting. Therefore, the correct answer is a binary tree.

Explanation

A binary tree can be used to sort n numbers in ascending order in O(nlogn) time. The binary tree can be constructed by inserting each number into the tree in a specific order. Then, by performing an in-order traversal of the tree, the numbers can be retrieved in ascending order. However, it is important to note that a binary search tree, max-heap, or min-heap cannot guarantee the O(nlogn) time complexity for sorting. Therefore, the correct answer is a binary tree.