Algorithms & Data Structures Flashcards
6 cards from real B.S.W.E. Bachelor of Software Engineering practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Algorithms & Data Structures flashcards as text
What is Dijkstra's algorithm used for?
Answer: Finding the shortest path from a source to all nodes in a weighted graph
Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights.
What is a heap data structure?
Answer: A complete binary tree satisfying the heap property where each parent is greater or smaller than its children
A heap is a complete binary tree where each parent is greater (max-heap) or smaller (min-heap) than its children, commonly used to implement priority queues.
What is the space complexity of recursive DFS on a graph with n nodes?
Answer: O(n)
Recursive DFS uses O(n) call stack space in the worst case because the recursion depth can equal the total number of nodes in a path graph.
How does random access time differ between an array and a linked list?
Answer: Array supports O(1) random access; linked list requires O(n) traversal
Arrays support O(1) random access because index arithmetic directly computes the memory address, while linked lists require traversal from the head.
What is memoization in algorithm design?
Answer: Caching the results of function calls to avoid redundant computation on repeated inputs
Memoization stores the results of expensive function calls so that when the same inputs occur again, the cached result is returned immediately.
What is the average-case time complexity of hash table insertion with a good hash function?
Answer: O(1)
Hash table insertion averages O(1) time complexity because a good hash function distributes keys uniformly, minimizing collisions.