Advance Data Structure Quiz-1

1. 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 R-B tree can be the same as the original tree or different, depending on the case. This is because the structure of an R-B tree is determined by a set of rules that ensure balance and maintain the properties of a red-black tree. Deleting and adding a key can affect the balance of the tree, causing it to be the same or different from the original tree. The outcome will depend on the specific key being deleted and added, as well as the state of the tree before the operations are performed.

Explanation

When a key is deleted from an R-B tree and then added back, the resulting structure of the R-B tree can be the same as the original tree or different, depending on the case. This is because the structure of an R-B tree is determined by a set of rules that ensure balance and maintain the properties of a red-black tree. Deleting and adding a key can affect the balance of the tree, causing it to be the same or different from the original tree. The outcome will depend on the specific key being deleted and added, as well as the state of the tree before the operations are performed.

2. 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 the left child of a node contains a value smaller than the node's value, and the right child contains a value greater than the node's value. This property allows for efficient searching, insertion, and deletion operations. In the given question, the tree is described as an "example," indicating that it serves as a representation or illustration of a binary search tree. Therefore, the correct answer is binary search tree.

Explanation

A binary search tree is a type of binary tree where the left child of a node contains a value smaller than the node's value, and the right child contains a value greater than the node's value. This property allows for efficient searching, insertion, and deletion operations. In the given question, the tree is described as an "example," indicating that it serves as a representation or illustration of a binary search tree. Therefore, the correct answer is binary search tree.

3. 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 visits the left subtree first, then the root, and finally the right subtree. This ensures that the values are visited in ascending order, making it an effective way to retrieve the values in sorted order from a binary search tree.

Explanation

In-order traversal of a binary search tree outputs the values in sorted order because it visits the left subtree first, then the root, and finally the right subtree. This ensures that the values are visited in ascending order, making it an effective way to retrieve the values in sorted order from a binary search tree.

4. 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.

When a key is deleted from a 2-3 tree and then added back, the resulting structure of the 2-3 tree may be the same or different from the original tree, depending on the case. This is because the structure of a 2-3 tree is determined by the specific keys that are inserted and deleted. The order in which the keys are inserted or deleted can affect the splitting and merging of nodes, which can result in different tree structures. Therefore, it is possible for the trees to be the same or different depending on the specific keys and operations performed.

Explanation

When a key is deleted from a 2-3 tree and then added back, the resulting structure of the 2-3 tree may be the same or different from the original tree, depending on the case. This is because the structure of a 2-3 tree is determined by the specific keys that are inserted and deleted. The order in which the keys are inserted or deleted can affect the splitting and merging of nodes, which can result in different tree structures. Therefore, it is possible for the trees to be the same or different depending on the specific keys and operations performed.

5. 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

In a 2-3 tree, each internal node can have either 2 or 3 children. Since the tree has 9 leaves, there are a total of 9-1=8 internal nodes. However, not all internal nodes need to have 3 children. It is possible to have some internal nodes with 2 children and some with 3 children. Therefore, the number of internal nodes can be less than 8. The minimum number of internal nodes required to have 9 leaves is 4, where there are 3 internal nodes with 2 children each and 1 internal node with 3 children. Therefore, the correct answer is 4.

Explanation

In a 2-3 tree, each internal node can have either 2 or 3 children. Since the tree has 9 leaves, there are a total of 9-1=8 internal nodes. However, not all internal nodes need to have 3 children. It is possible to have some internal nodes with 2 children and some with 3 children. Therefore, the number of internal nodes can be less than 8. The minimum number of internal nodes required to have 9 leaves is 4, where there are 3 internal nodes with 2 children each and 1 internal node with 3 children. Therefore, the correct answer is 4.

6. The rotation need to be done is

LL

LR

RL

None of these

The correct answer is "LL" because the given options represent different types of rotations in a binary tree. "LL" refers to a left rotation followed by another left rotation. This means that the left child of the root becomes the new root, and the old root becomes the right child of the new root. This rotation helps to balance the tree and maintain its structure.

Explanation

The correct answer is "LL" because the given options represent different types of rotations in a binary tree. "LL" refers to a left rotation followed by another left rotation. This means that the left child of the root becomes the new root, and the old root becomes the right child of the new root. This rotation helps to balance the tree and maintain its structure.

7. 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, the delete operation involves removing a node from the tree while maintaining the red-black properties. This operation requires careful restructuring and recoloring of nodes to ensure that the tree remains balanced and satisfies all the red-black tree properties. The insert and find operations also play a role in maintaining the red-black tree properties, but the delete operation specifically deals with removing nodes.

Explanation

The correct answer is "Delete". In a red-black tree, the delete operation involves removing a node from the tree while maintaining the red-black properties. This operation requires careful restructuring and recoloring of nodes to ensure that the tree remains balanced and satisfies all the red-black tree properties. The insert and find operations also play a role in maintaining the red-black tree properties, but the delete operation specifically deals with removing nodes.

8. 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 is what differentiates a 2-3 Tree from other types of trees, where the maximum number of children per node may vary. In a 2-3 Tree, each node can have either 2 or 3 children, and the tree is balanced such that all leaf nodes are at the same height.

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 is what differentiates a 2-3 Tree from other types of trees, where the maximum number of children per node may vary. In a 2-3 Tree, each node can have either 2 or 3 children, and the tree is balanced such that all leaf nodes are at the same height.

9. 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 the worst case, each level of the tree will be completely filled except for the last level, which may be partially filled. The number of nodes in a completely filled binary tree of height h can be calculated using the formula 2^h - 1. In this case, we want to find the maximum height, so we need to find the largest value of h such that 2^h - 1 is less than or equal to n. By solving this equation, we get h = log2(n+1) - 1. Since the height of the tree is one less than h, the maximum height can be expressed as (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 the worst case, each level of the tree will be completely filled except for the last level, which may be partially filled. The number of nodes in a completely filled binary tree of height h can be calculated using the formula 2^h - 1. In this case, we want to find the maximum height, so we need to find the largest value of h such that 2^h - 1 is less than or equal to n. By solving this equation, we get h = log2(n+1) - 1. Since the height of the tree is one less than h, the maximum height can be expressed as (n-1)/2.

10. 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 maximum number of nodes possible in a binary search tree (BST) with height h can be calculated using the formula 2^(h+1) - 1. This formula is derived from the fact that at each level of the BST, the number of nodes doubles. Therefore, at the root level, there is 1 node, at the next level there are 2 nodes, at the next level there are 4 nodes, and so on. So, the total number of nodes in the BST can be calculated by summing up the number of nodes at each level, which is equivalent to 2^(h+1) - 1.

Explanation

The maximum number of nodes possible in a binary search tree (BST) with height h can be calculated using the formula 2^(h+1) - 1. This formula is derived from the fact that at each level of the BST, the number of nodes doubles. Therefore, at the root level, there is 1 node, at the next level there are 2 nodes, at the next level there are 4 nodes, and so on. So, the total number of nodes in the BST can be calculated by summing up the number of nodes at each level, which is equivalent to 2^(h+1) - 1.

11. 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 the numbers in a specific order, such as in the order they are given or in a sorted order. Then, by performing an in-order traversal of the binary tree, the numbers can be retrieved in ascending order. This traversal takes O(n) time, and since the height of a binary tree is O(logn), the overall time complexity is O(nlogn).

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 the numbers in a specific order, such as in the order they are given or in a sorted order. Then, by performing an in-order traversal of the binary tree, the numbers can be retrieved in ascending order. This traversal takes O(n) time, and since the height of a binary tree is O(logn), the overall time complexity is O(nlogn).

12. 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 correct answer is O(nlg(n)) because in order to traverse all the nodes of a binary search tree, we need to visit each node once. The time complexity of visiting a node is O(1). Since there are n nodes in the tree, the total time complexity is O(n). Additionally, printing the nodes in order requires sorting them, which has a time complexity of O(nlg(n)) in the average case. Therefore, the overall time complexity is O(nlg(n)).

Explanation

The correct answer is O(nlg(n)) because in order to traverse all the nodes of a binary search tree, we need to visit each node once. The time complexity of visiting a node is O(1). Since there are n nodes in the tree, the total time complexity is O(n). Additionally, printing the nodes in order requires sorting them, which has a time complexity of O(nlg(n)) in the average case. Therefore, the overall time complexity is O(nlg(n)).

13. 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

14. 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

The Red-Black Tree has a height of O(lgn) where n is the number of nodes. This is because the Red-Black Tree is a balanced binary search tree that maintains a balance between the left and right subtrees. It achieves this balance by enforcing certain properties, such as every node being either red or black, and the number of black nodes on any path from the root to a leaf being the same. These properties ensure that the tree remains balanced and the height is logarithmic in relation to the number of nodes.

Explanation

The Red-Black Tree has a height of O(lgn) where n is the number of nodes. This is because the Red-Black Tree is a balanced binary search tree that maintains a balance between the left and right subtrees. It achieves this balance by enforcing certain properties, such as every node being either red or black, and the number of black nodes on any path from the root to a leaf being the same. These properties ensure that the tree remains balanced and the height is logarithmic in relation to the number of nodes.

15. 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 inserting the integers in order, the first integer 50 becomes the root of the binary search tree. The integers less than 50 (15, 5, 20, 37, 24) are inserted on the left sub-tree, which results in 4 nodes. The integers greater than 50 (62, 58, 91, 60) are inserted on the right sub-tree, which results in 7 nodes. Therefore, the number of nodes in the left sub-tree and right sub-tree of the root are 4 and 7 respectively.

Explanation

The correct answer is (4,7) because when inserting the integers in order, the first integer 50 becomes the root of the binary search tree. The integers less than 50 (15, 5, 20, 37, 24) are inserted on the left sub-tree, which results in 4 nodes. The integers greater than 50 (62, 58, 91, 60) are inserted on the right sub-tree, which results in 7 nodes. Therefore, the number of nodes in the left sub-tree and right sub-tree of the root are 4 and 7 respectively.