What is the primary advantage of a B-Tree over a binary search tree?
A Self-balancing
B Better space utilization
C Support for more data
D Faster search
A B-Tree allows for better space utilization compared to a binary search tree because it stores multiple keys in a node and balances itself automatically. This structure makes it ideal for systems that need efficient storage and retrieval on disk-based systems.
Which operation is performed by a heap to ensure the heap property is maintained after insertion?
A Sifting
B Sorting
C Traversing
D Merging
After inserting an element into a heap, the “sifting” operation (either up or down, depending on the type of heap) is performed to restore the heap property, ensuring that each parent node is either greater or smaller than its children.
Which of the following is true about a max-heap?
A The root node is the smallest
B It is unordered
C The root node is the largest
D All elements are equal
In a max-heap, the root node contains the largest element. Every parent node is larger than or equal to its children. This property allows efficient retrieval of the maximum element in O(1) time.
What is the time complexity of deleting the root node in a max-heap?
A O(n log n)
B O(n)
C O(n²)
D O(log n)
Deleting the root node in a max-heap requires replacing it with the last element, then performing a heapify operation (sifting down). This operation has a time complexity of O(log n) because it involves traversing the height of the heap.
Which of the following best describes the structure of a B-Tree?
A Multi-level tree with ordered nodes
B Linked list with a root node
C Single-level tree with multiple roots
D Binary search tree with balanced nodes
A B-Tree is a multi-level, self-balancing search tree where each node can contain multiple keys. It ensures that all leaf nodes are at the same level, allowing for efficient disk-based storage and retrieval of data.
In a priority queue, which element is removed first?
A Latest element added
B Highest priority element
C Random element
D First element inserted
In a priority queue, elements are dequeued based on their priority. The element with the highest priority is removed first, making it ideal for scheduling tasks where certain jobs must be processed before others.
Which of the following is a feature of a Fibonacci heap?
A Constant time for insertions
B Logarithmic time for all operations
C No need for rebalancing
D Constant time for insertions
A Fibonacci heap allows constant time insertions, which is one of its key advantages over other heap structures. This is achieved by lazy merging and restructuring, though other operations like deletion take O(log n) time.
Which of the following algorithms is commonly used with heaps to find the k-th largest element in a stream of data?
A Quick Sort
B Heap Sort
C Priority Queue
D Merge Sort
A priority queue (implemented as a heap) is commonly used to find the k-th largest element in a stream of data. By maintaining a heap of size k, the k-th largest element can be found efficiently by examining the root of the heap.
Which of the following best describes the operation of a binary heap?
A The heap property ensures a complete binary tree
B The tree is fully balanced
C Each node can have multiple children
D The root is always at the bottom
A binary heap is a complete binary tree where the heap property is maintained: in a max-heap, each parent node is larger than its children; in a min-heap, each parent node is smaller than its children. This choice guarantees efficient retrieval operations.
What is the time complexity for building a heap from an unsorted array?
A O(n log n)
B O(n)
C O(n²)
D O(log n)
Building a heap from an unsorted array can be done in O(n) time. This is achieved by performing a series of “heapify” operations from the bottom of the tree upwards, rather than inserting elements one by one.
Which type of B-Tree is most commonly used in database indexing systems?
A 2-3-4 Tree
B Red-Black Tree
C B+ Tree
D 2-3 Tree
The B+ Tree is widely used in database indexing systems because it allows efficient search, insertion, and deletion operations. It is a variant of the B-Tree that stores data only in leaf nodes, making range queries more efficient.
In a Fibonacci heap, which operation is most efficient?
A Merging heaps
B Insertion
C Decrease key
D Deletion of minimum element
Merging two Fibonacci heaps is the most efficient operation, with a time complexity of O(1). This is one of the reasons Fibonacci heaps are preferred for certain graph algorithms, such as Dijkstra’s algorithm.
Which of the following is true for a binary heap?
A It always requires rebalancing after every operation
B It can be a max-heap or a min-heap
C Its nodes must be balanced
D It is not a complete binary tree
A binary heap can be either a max-heap (where the root contains the largest element) or a min-heap (where the root contains the smallest element). This property is selected based on the application’s needs.
In which of the following situations is a heap most useful?
A Storing a collection of ordered elements
B Sorting a list of numbers
C Storing and retrieving elements by priority
D Performing range queries
Heaps are most useful in priority queues, where elements must be retrieved based on their priority rather than their insertion order. They ensure efficient retrieval and insertion of the highest or lowest priority element.
Which property must be satisfied by a B-Tree?
A It is always a complete tree
B The tree must be balanced after every insertion
C Nodes contain only one key
D All leaf nodes are at the same depth
A key property of a B-Tree is that all leaf nodes must be at the same depth. This ensures that search operations are efficient, as every path from the root to a leaf has the same length.