Advance Data Structure Quiz-b-1
Advance Data Structure Quiz-1
Questions and Answers
- 1.
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 TreeExplanation
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 remains balanced. The tree maintains a balance between the black nodes on each path from the root to the leaves, preventing the tree from becoming too imbalanced. This balancing property guarantees that the height of the tree is logarithmic in the number of nodes, making it an efficient data structure for searching, insertion, and deletion operations.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 3Explanation
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 the 2-3 Tree allows for efficient insertion and deletion operations while maintaining a balanced tree structure.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 can either be the same as the original tree or different, depending on the case. This is because the structure of the resulting tree will depend on the specific key that was deleted and added back, as well as the positions of other keys in the tree. Therefore, it is not possible to determine whether the resulting tree will be the same or different without considering the specific case.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
The structure of the resulting 2-3 tree may be the same or different depending on the specific case. When a key is deleted from a 2-3 tree, the structure may change due to the redistribution or merging of nodes to maintain the balance. However, when the same key is added back, the structure may or may not revert to the original state. It depends on the specific circumstances, such as the position of the key within the tree and the redistribution and merging operations that occur during the deletion and reinsertion processes. Therefore, both trees may be the same or different depending on the 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)-1Explanation
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, for each level of the tree, the number of nodes doubles. By subtracting 1 from the total, we account for the root node. Hence, the formula 2^(h+1)-1 gives the maximum number of nodes in a BST with height h.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 TreeExplanation
A binary search tree is a type of binary tree in which each node has a key value and the left child node has a smaller key value than its parent node, while the right child node has a larger key value. This allows for efficient searching, insertion, and deletion of elements in the tree. The given tree is an example of a binary search tree because it follows the property of having smaller values on the left and larger values on the right.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. DeleteExplanation
The correct answer is "Delete" because the given options represent the possible cases in a red-black tree. "Insert" refers to the case when a new node is added to the tree, "find" refers to searching for a specific node, and "delete" refers to removing a node from the tree. Therefore, "Delete" is the appropriate case for the given options.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)/2Explanation
The maximum height of the tree will be (n-1)/2. This is because in a binary tree where each node has either zero or two children, the number of edges in the longest path from the root to a leaf node will be equal to the height of the tree. Since each node has either zero or two children, the number of leaf nodes will be (n+1)/2. Therefore, the maximum height of the tree will be (n+1)/2 - 1, which simplifies to (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)). This is because in order to traverse all the nodes of a binary search tree, we need to visit each node once. Since there are n nodes in the tree, the time complexity for visiting all the nodes 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 for traversing and printing all the nodes in a binary search tree 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 TreeExplanation
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 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 is the same as the time complexity of sorting n numbers in ascending order. Therefore, a binary tree can be used for this purpose.Rate this question:
-
- 11.
The rotation need to be done is
- A.
LL
- B.
LR
- C.
RL
- D.
None of these
Correct Answer
A. LLExplanation
The given answer "LL" suggests that the rotation needed to be done is a left rotation followed by another left rotation. In a left rotation, the left child of a node becomes the new root, and the original root becomes the right child of the new root. Therefore, performing two consecutive left rotations would result in the left child of the original root becoming the new root, while the original root becomes the right child of the new root.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. 4Explanation
In a 2-3 tree, each internal node can have either 2 or 3 children. Since there are 9 leaves, there must be 8 internal nodes to connect them. To minimize the number of internal nodes, we can create a balanced tree where each internal node has 3 children. In this case, we would need 4 internal nodes to have 9 leaves. Therefore, the correct answer is 4.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-orderExplanation
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, making it an effective way to retrieve the elements of the tree in sorted order.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.
925, 202, 911, 240, 912, 245, 258, 363
- B.
924, 220, 911, 244, 898, 258, 362, 363
- C.
925, 202, 911, 240, 912, 245, 258, 363
- D.
2, 399, 387, 219, 266, 382, 381, 278, 363
Correct Answer
C. 925, 202, 911, 240, 912, 245, 258, 363 -
- 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
- 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 we insert the given integers in order into a binary search tree, the left sub-tree of the root will have 4 nodes (5, 3, 15, 8) and the right sub-tree will have 7 nodes (62, 20, 58, 91, 37, 60, 24).Rate this question:
-
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 19, 2023Quiz Edited by
ProProfs Editorial Team -
Aug 31, 2018Quiz Created by
ADS11
- Binary Code Quizzes
- Computer Concept Quizzes
- Computer Essential Quizzes
- Computer Forensics Quizzes
- Computer Hardware Quizzes
- Computer Networking Quizzes
- Computer Parts Quizzes
- Computer Programming Quizzes
- Computer Science Quizzes
- Computer Security Quizzes
- Computer Shortcut Key Quizzes
- Computer Skills Quizzes
- Computer Virus Quizzes
- Cyber Security Quizzes
- Data Quizzes
- Data Security Quizzes
- Hacking Quizzes
- HCI Quizzes
- Internet Quizzes
- IT SecurITy Quizzes
- Malware Quizzes
- Microprocessor Quizzes
- Network Quizzes
- Operating System Quizzes
- Phishing Quizzes
- Programming Language Quizzes
- Server Quizzes
- Software Quizzes
Back to top