Advance Data Structure Quiz-B-2

2.

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

Correct Answer

A. (n-1)/2

Explanation

The maximum height of the binary tree constructed with n nodes, where each node has either zero or two children, can be determined by observing that each level of the tree can accommodate twice as many nodes as the previous level. Therefore, the number of nodes in each level can be represented by the powers of 2. The maximum height of the tree will be when the last level is filled completely, i.e., when the number of nodes in the last level is equal to n. By solving for n in the equation 2^h = n, we can determine the maximum height of the tree to be (n-1)/2.

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?

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.

Correct Answer

A. 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 as the original tree or it may be different, depending on the specific case. The structure can change if the key that is added back causes a violation of any of the R-B tree properties. In such cases, the tree will need to be rebalanced to restore the properties, resulting in a different structure. However, if the added key does not violate any properties, the resulting tree will be the same as the original. Therefore, the structure of the resulting R-B tree can vary depending on the specific case.

Rate this question:

4.

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

Pre-order
Post-order
In-order
None of these

Correct Answer

A. 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 current node, and finally the right subtree. This ensures that the values are visited in ascending order, resulting in a sorted output.

Rate this question:

5.

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.

Correct Answer

A. 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 specific case of deletion and addition can affect the balance and arrangement of nodes in the tree. In some cases, the structure may remain unchanged, while in others, it may be altered. Therefore, it is not possible to determine with certainty whether the resulting trees will be the same or different without considering the specific case.

Rate this question:

6.

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.

Correct Answer

A. 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 can have up to 3 child nodes. This is one of the defining characteristics of a 2-3 Tree, where each internal node can have either 2 or 3 child nodes. Having a maximum of 3 children allows for more flexibility in balancing the tree and maintaining its properties.

Rate this question:

7.

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

Correct Answer

A. 4

Explanation

A 2-3 tree is a tree where all internal nodes have either 2 or 3 children. In a 2-3 tree, each internal node represents a range of values, and the number of children of an internal node represents the number of ranges that node covers. In this case, the tree has 9 leaves, which means it represents 9 ranges of values. To have 9 leaves with the minimum number of internal nodes, we can have 4 internal nodes, where each internal node has 2 children except for the last internal node, which has 3 children. Therefore, the number of internal nodes of a 2-3 tree having 9 leaves could be 4.

Rate this question:

8.

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

Insert
Find
Delete
None of these

Correct Answer

A. Delete

Explanation

The correct answer is "Delete". In a red-black tree, deletion is one of the operations that can be performed. Red-black trees are a type of balanced binary search tree that maintain a balance between the number of black nodes on any path from the root to a leaf. The deletion operation in a red-black tree involves removing a node from the tree while maintaining the balance and properties of the tree, such as the red-black color property and the binary search tree property.

Rate this question:

9.

The rotation need to be done is

LL
LR
RL
None of these

Correct Answer

A. LL

Explanation

The given answer "LL" indicates that a left rotation needs to be performed twice. A left rotation involves moving the left child of a node up to replace the node, while the node becomes the right child of the original left child. Therefore, performing two left rotations will effectively move the original node two levels down in the left subtree.

Rate this question:

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

Correct Answer

A. 2exp(h+1)-1

Explanation

The given correct answer, 2^(h+1)-1, represents the maximum number of nodes possible in a binary search tree (BST) with a height of h. This formula is derived from the fact that in a BST, each node can have at most two children. Therefore, at each level of the tree, the number of nodes doubles. By subtracting 1 from 2^(h+1), we account for the root node. Thus, 2^(h+1)-1 gives the maximum number of nodes that can be present in the tree.

Rate this question:

11.

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

Correct Answer

A. O(nlg(n))

Explanation

The correct answer is O(nlg(n)) because in a binary search tree, each node has at most two children. Therefore, in order to traverse all the nodes, we need to visit each node once. The time complexity of visiting each node is O(n). Additionally, when printing the nodes in order, we need to compare and sort the values, which takes O(lg(n)) time for each node. Therefore, the overall time complexity is O(nlg(n)).

Rate this question:

12.

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

Correct Answer

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

13.

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

Correct Answer

A. R-B Tree

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 self-balancing binary search tree that ensures the height of the tree remains balanced. By maintaining certain properties, such as the red-black colorings and rotations, the Red-Black Tree guarantees a maximum height of O(lgn), which allows for efficient search, insertion, and deletion operations.

Rate this question:

14.

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)

Correct Answer

A. (4,7)

Explanation

The number of nodes in the left sub-tree of the root is 4, and the number of nodes in the right sub-tree of the root is 7. This can be determined by traversing the binary search tree and counting the number of nodes in each sub-tree.

Rate this question:

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

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 can have at most two children, a left child and a right child. By inserting the numbers into the binary tree in a specific order, such as in-order traversal, the numbers can be sorted. The time complexity of inserting n numbers into a binary tree is O(nlogn), which satisfies the requirement. Therefore, a binary tree can be used for this purpose.

Rate this question:

Advance Data Structure Quiz-b-2

The tree is an example of

Quiz Preview

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?

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?

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

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?

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

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

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

The rotation need to be done is

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?

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

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?

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

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

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