Question 965 – Nielit Scientist-B IT 4-12-2016
December 3, 2023Question 1087 – Nielit Scientist-B CS 22-07-2017
December 3, 2023UGC NET Dec-2020 and June-2021 Paper-2
| Question 15 |
A data structure is required for storing a set of integers such that each of the following operations can be done in O(log n) time, where n is the number of elements in the set. Deletion of the smallest element
Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
Insertion of an element if it is not already present in the set
Which of the following data structures can be used for this purpose?
| A balanced binary search tree can be used but not a heap. | |
| A heap can be used but not a balanced binary search tree. | |
| Both balanced binary search tree and heap can be used. | |
| Neither balanced binary search tree nor heap can be used. |
Question 15 Explanation:
A Balanced Binary Tree is nothing but an AVL Tree. And Time complexity of an AVL tree for finding an element is (Log n) in the worst case. Heaps are good only for min/max elements. Min heap will have minimum element on root and max element will have maximum at root. But to insert an element which may or may not be present in the heap will take O (N) in the worst case because we need to check all the elements of the heap.
Correct Answer: A
Question 15 Explanation:
A Balanced Binary Tree is nothing but an AVL Tree. And Time complexity of an AVL tree for finding an element is (Log n) in the worst case. Heaps are good only for min/max elements. Min heap will have minimum element on root and max element will have maximum at root. But to insert an element which may or may not be present in the heap will take O (N) in the worst case because we need to check all the elements of the heap.
Subscribe
Login
0 Comments