At ProProfs Quizzes, our dedicated in-house team of experts takes pride in their work. With a sharp eye for detail, they meticulously review each quiz. This ensures that every quiz, taken by over 100 million users, meets our standards of accuracy, clarity, and engagement.
Which of the following trees have height as O(lgn) where number of nodes is n.
A.
R-B Tree
B.
Binary Search Tree
C.
Binary Tree
D.
2-3 Tree
Correct Answer A. R-B Tree
Explanation The Red-Black (R-B) Tree has a height of O(lgn) where n is the number of nodes. R-B Trees are a type of balanced binary search tree that ensures the tree remains balanced by applying certain rules during insertion and deletion operations. These rules help maintain a height that is logarithmic with respect to the number of nodes, resulting in efficient search, insert, and delete operations. Therefore, R-B Trees have a height of O(lgn).
Rate this question:
2.
For a 2 -3 Tree which of the following is true
A.
A 2-3 Tree may have root node with only one child
B.
Maximum number of children of any node is 3
C.
A leave can hight either 2 or 3 in a 2-3 tree
D.
Minimum number of children of any node is 2.
Correct Answer B. Maximum number of children of any node is 3
Explanation In a 2-3 Tree, the maximum number of children that any node can have is 3. This means that a node in a 2-3 Tree can have either 2 or 3 child nodes. The tree follows the property that each internal node can have either 2 or 3 child nodes, and each leaf node can have 2 or 3 elements. Therefore, the statement "Maximum number of children of any node is 3" is true for a 2-3 Tree.
Rate this question:
3.
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?
A.
Both trees will be same in all cases
B.
Both will be different in all the cases
C.
Both trees may be same or different depending on the case.
Correct Answer C. Both trees may be same or different depending on the case.
Explanation When a key is deleted from an R-B tree and then added back, the resulting structure of the R-B tree may be the same or different from the original tree depending on the case. This is because the structure of an R-B tree is determined by the specific sequence of operations performed on it. The deletion and subsequent re-addition of a key can potentially lead to different rotations and color adjustments, which can result in a different tree structure. Therefore, it is not guaranteed that both trees will always be the same or always be different.
Rate this question:
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?
A.
Both trees will be same in all cases
B.
Both will be different in all the cases
C.
Both trees may be same or different depending on the case.
Correct Answer C. Both trees may be same or different depending on the case.
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 the tree is determined by the specific keys that are present and their arrangement. If the key being added back fits into the same position it was in before deletion, then the trees will be the same. However, if the key being added back needs to be inserted into a different position, the trees will be different. Therefore, the resulting trees can vary depending on the specific case.
Rate this question:
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?
A.
2exp(h-1)-1
B.
2exp(h+1)-1
C.
2exp(h)-1
D.
2exp(h+1)-1
Correct Answer B. 2exp(h+1)-1
Explanation The correct answer is 2^(h+1) - 1. This formula calculates the maximum number of nodes possible in a binary search tree (BST) based on its height. The height of a BST is defined as the number of edges in the longest path from the root to a leaf node. By using the formula 2^(h+1) - 1, we can calculate the maximum number of nodes that can be present in the tree. This formula works because at each level of the tree, the number of nodes doubles (2^h), and by subtracting 1, we account for the root node. Therefore, the correct answer is 2^(h+1) - 1.
Rate this question:
6.
The tree is an example of
A.
2-3 tree
B.
Binary search Tree
C.
Binomial Heap
D.
Fibonacci Heap
Correct Answer B. Binary search Tree
Explanation A binary search tree is a data structure in which each node has at most two children, a left child and a right child. The tree is organized in such a way that the value of each node in the left subtree is less than the value of the node itself, and the value of each node in the right subtree is greater than the value of the node itself. This allows for efficient searching, insertion, and deletion operations. The given tree can be classified as a binary search tree because it follows this property, making it the correct answer.
Rate this question:
7.
The following are the case of ...................in red black Tree
A.
Insert
B.
Find
C.
Delete
D.
None of these
Correct Answer C. Delete
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 adjusting the tree structure and recoloring nodes to ensure that the red-black properties are preserved. The insert and find operations also play a role in maintaining the red-black properties, but the delete operation specifically deals with removing nodes from the tree.
Rate this question:
8.
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?
A.
(n+1)/2
B.
(n-1)/2
C.
(n/2)-1
D.
(n+1)/2
Correct Answer B. (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 determined by considering the number of edges in the longest path from the root to a leaf node. In this case, the number of edges in the longest path will be equal to the height of the tree.
Since each node has either zero or two children, the number of leaf nodes in the tree will be equal to the number of nodes with zero children. Let's assume this number is x.
In a binary tree, the number of nodes with zero children is always one more than the number of nodes with two children. Therefore, the number of nodes with two children will be x-1.
The total number of nodes in the tree can be calculated as follows:
Total nodes = x + (x-1) = 2x - 1
Since the height of the tree is equal to the number of edges in the longest path, the maximum height of the tree will be (2x-1 - 1)/2 = (2x-2)/2 = x-1 = (n-1)/2.
Hence, the correct answer is (n-1)/2.
Rate this question:
9.
The run time for traversing all the nodes of a binary search tree with n nodes and printing them in an order is
A.
O(nlg(n))
B.
O(√n)
C.
O(n)
D.
O(lg(n))
Correct Answer A. 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 exactly once. This requires a time complexity of O(n). Additionally, when printing the nodes in order, we need to perform a logarithmic operation (lg(n)) for each node in order to determine its correct position in the output. Therefore, the overall time complexity is O(nlg(n)).
Rate this question:
10.
If n numbers are to be sorted in ascending order in O(nlogn) time, which of the following tree can be used
A.
Binary Tree
B.
Binary Search Tree
C.
Max- heap
D.
Min-Heap
Correct Answer A. Binary Tree
Explanation A binary tree can be used to sort n numbers in ascending order in O(nlogn) time. In a binary tree, each node has at most two children, a left child and a right child. By traversing the binary tree in a specific order (such as in-order traversal), the numbers can be retrieved in sorted order. However, it is important to note that a binary tree does not guarantee efficient searching or insertion operations, unlike a binary search tree or a heap.
Rate this question:
11.
The rotation need to be done is
A.
LL
B.
LR
C.
RL
D.
None of these
Correct Answer A. LL
Explanation The correct answer is LL. This indicates that the rotation needed to be done is a left rotation followed by another left rotation.
Rate this question:
12.
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
A.
4
B.
5
C.
6
D.
7
Correct Answer A. 4
Explanation A 2-3 tree is a tree where all internal nodes have either 2 or 3 children. In this case, we are given that the tree has 9 leaves. In a 2-3 tree, the number of internal nodes can be calculated by subtracting 1 from the number of leaves. Therefore, the number of internal nodes in this 2-3 tree with 9 leaves would be 9 - 1 = 8. However, the options provided are 4, 5, 6, and 7. None of these options match the correct answer, so the correct answer is not available.
Rate this question:
13.
Which type of traversal of binary search tree outputs the value in sorted order?
A.
Pre-order
B.
Post-order
C.
In-order
D.
None of these
Correct Answer C. In-order
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, resulting in a sorted output.
Rate this question:
14.
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?
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
A.
(4,7)
B.
(7,4)
C.
(8,3)
D.
(3,8)
Correct Answer A. (4,7)
Explanation The correct answer is (4,7) because when the integers are inserted in order into a binary search tree, the root node is 50. There are four integers (15, 5, 20, 37) that are less than 50 and are inserted into the left sub-tree, and there are seven integers (62, 58, 91, 60, 24) that are greater than 50 and are inserted into the right sub-tree.