CS 240 FINAL: PART 3/4 Flashcards
(14 cards)
Q: Time complexity for search/insert/delete in a hash table?
A: O(1) average, O(n) worst (many collisions)
Q: What is a collision and how is it handled?
A: When two keys hash to the same index.
Handled by: Chaining (linked list at index) AND Open Addressing (find next empty slot)
Q: How does insertion work in a hash table?
A: Hash the key and insert at the index. Handle collisions if necessary.
Q: What is Hashing?
A: A way to map keys to array indices using a hash function.
Q: Time complexity for insert/delete in a Heap?
A: O(log n)
Q: How is a Heap stored?
A: As a complete binary tree using an array.
Q: How does deletion (root) work in a Heap?
A: Replace root with last element, delete last, then heapify down (swap down).
Q: What is a Heap?
A: A binary tree where:
In a Min-Heap, parent ≤ children
In a Max-Heap, parent ≥ children
Q: How does insertion work in a Heap?
A: Add at the end, then heapify up (swap up until heap property is restored).
Q: Time complexity (search/insert/delete) in balanced BST?
A: O(log n) average, O(n) worst case (unbalanced tree).
Q: How does deletion work in a BST?
A:
No child → delete node.
One child → replace with child.
Two children → replace with in-order successor or predecessor.
Q: What is a Binary Search Tree (BST)?
A: A tree where each left child is smaller and each right child is larger than the parent node.
Q: How does searching work in a BST?
A: Start at the root, go left if the target is smaller, right if larger, until found or null.
Q: How does insertion work in a BST?
A: Compare and go left or right recursively until a null spot is found; insert there.
