Advance Data Structure Quiz-c-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
An R-B Tree has a height of O(lgn) where the number of nodes is n. This means that as the number of nodes in the tree increases, the height of the tree will increase logarithmically. This property makes R-B Trees efficient for operations such as insertion, deletion, and searching, as the height of the tree remains relatively small even with a large number of nodes. On the other hand, Binary Search Trees, Binary Trees, and 2-3 Trees do not have a guaranteed height of O(lgn) and can have a height of O(n) in the worst case, resulting in less efficient 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 in a 2-3 Tree can have either 2 or 3 children. This property allows for efficient balancing of the tree and ensures that the tree remains balanced even after insertions and deletions.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
The structure of the resulting R-B tree may be the same or different depending on the case because the deletion and re-insertion of a key can have different effects on the tree. If the key being deleted and added back does not affect the balance of the tree, then the resulting tree will be the same as the original. However, if the key being deleted and added back causes any restructuring or rebalancing of the tree, then the resulting tree will be different from the original. 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 tree can be the same as the original tree or it can be different, depending on the case. This is because the structure of a 2-3 tree depends on the specific keys that are inserted and deleted. If the key that is deleted and added back is in a position that causes a restructuring of the tree, then the resulting tree will be different. However, if the key can be inserted back into the tree without causing any restructuring, then the resulting tree will be the same as the original tree. Therefore, both scenarios are possible.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 answer, 2^(h+1)-1, is the formula for calculating the maximum number of nodes possible in a binary search tree (BST) of height h. This formula is derived from the fact that at each level of the BST, the number of nodes doubles. The height of the tree is the number of levels minus one, so by raising 2 to the power of (h+1) and subtracting 1, we get the maximum number of nodes in the tree. 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 TreeExplanation
A binary search tree is a data structure in which each node has at most two children, and the left child is always smaller than the parent while the right child is always larger. This property allows for efficient searching, insertion, and deletion operations. The given tree is an example of a binary search tree because it follows the defined property, with 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 given correct answer, "Delete," suggests that the cases mentioned (insert, find, delete) are all related to operations performed on a red-black tree. In a red-black tree, the delete operation involves removing a node from the tree while maintaining the properties of a red-black tree, such as the color balance and ordering of the nodes. Therefore, the cases mentioned are specifically referring to the different scenarios that can occur during the deletion process in a red-black 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)/2Explanation
The maximum height of a binary tree with n nodes, where each node has either zero or two children, can be calculated using the formula (n-1)/2. This formula holds true because in a binary tree, each node has at most two children. Therefore, the number of edges in the longest path from the root to a leaf node is equal to the height of the tree. Since each node has either zero or two children, the number of edges will be one less than the number of nodes. Hence, the formula for the maximum height 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, printing the nodes in order also takes O(n) time. Therefore, the overall time complexity is O(n) for traversing and printing. However, since the binary search tree is balanced, the height of the tree is approximately lg(n). As a result, the time complexity becomes O(n * lg(n)), which is the most efficient option among the given choices.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 performing an in-order traversal of the binary tree, the numbers can be visited in ascending order. However, it is important to note that a binary tree does not guarantee efficient searching or insertion operations, so it may not be the most optimal choice for sorting large sets of numbers.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 correct answer is LL, which stands for Left-Left rotation. In a binary search tree, LL rotation is performed when a node's left child has a left child. This rotation helps in maintaining the balance of the tree by making the left child the new root and the original root as its right child. This ensures that the tree remains sorted and allows for efficient search and retrieval operations.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
A 2-3 tree is a tree where all internal nodes have either 2 or 3 children. In this case, we are looking for the number of internal nodes in a 2-3 tree with 9 leaves. Since each internal node has either 2 or 3 children, the number of internal nodes must be less than or equal to the number of leaves divided by 2. In this case, 9 leaves divided by 2 is 4.5, so the number of internal nodes could be 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 root node, 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.
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) -
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 22, 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