Algorithms and Data Structures Quiz & Flashcards

Quicksort is generally faster on large datasets due to its average time complexity of O(n log n), unlike quadratic time algorithms.

Recursion uses a stack data structure to keep track of function calls and their states.

A binary tree node can have at most two children: left and right.

Dijkstra's Algorithm is specifically designed to find the shortest path in weighted graphs.

Linked lists can grow and shrink dynamically, unlike arrays that have a fixed size.

Heaps are used to implement priority queues efficiently due to their properties that facilitate fast access to the highest (or lowest) priority element.

Stacks are commonly used for expression evaluation and syntax parsing.

A Deque (double-ended queue) allows insertion and deletion from both ends.

Searching in a balanced binary search tree has a time complexity of O(log n) due to its height balance.

Depth-First Search can be used to detect cycles in a graph by marking visited nodes.

Hash tables can suffer from hash collisions where different keys produce the same hash value.

Binary Heap is not a binary search tree; it is a complete binary tree with heap properties.

Hash functions are used for fast data retrieval by mapping keys to values efficiently.

Adjacency lists are more space-efficient for sparse graphs as they only store edges that exist.

Dynamic programming combines solutions of overlapping subproblems to solve the main problem.

Depth-First Search can be used to perform topological sorting of a directed acyclic graph.

In a circular queue, the last position is connected back to the first, forming a circle.

Merge sort is stable, meaning it preserves the relative order of equal elements.

Tries are used to efficiently store and retrieve strings, especially for prefix-based searches.

Hash maps are most efficient for frequent lookups due to their average O(1) time complexity.

Doubly linked lists allow traversal in both directions, unlike singly linked lists.

Quick sort uses a pivot element to partition the array into subarrays.

Priority queues allow for access to elements based on their priority rather than their order of insertion.

A stack operates on a Last In, First Out (LIFO) basis, inserting and removing elements from the same end.

A combination of a hash map and a doubly linked list efficiently implements a Least Recently Used (LRU) cache.

Kruskal's algorithm is designed to find the minimum spanning tree of a graph efficiently.

Circular linked lists make iteration through the list easier as the last node points back to the first node.

A queue is used in breadth-first search to explore nodes level by level.

Binary trees are often used to store hierarchical data due to their branching structure.

Graph traversal algorithms do not perform node insertion; they visit, check, and possibly update nodes.

Minimum spanning trees are used in network design to minimize the cost of connecting all nodes.

Adjacency lists are more space-efficient, especially for sparse graphs, compared to adjacency matrices.

A stack is essential for implementing a call stack to manage function calls and returns.

Tarjan's Algorithm is used to find strongly connected components in a directed graph.

The best-case time complexity of insertion sort is O(n) when the input array is already sorted.

Tries allow for efficient searching of string prefixes due to their hierarchical structure.

Adjacency matrices are space inefficient for sparse graphs as they use space proportional to the square of the number of vertices.

Bubble sort has a quadratic time complexity, making it inefficient for large datasets.

Dynamic programming stores solutions to subproblems to avoid redundant calculations seen in recursion.

Linked lists are more efficient for frequent insertions and deletions as they do not require shifting elements.

Splay trees are self-adjusting binary search trees designed to optimize frequent access to certain elements.

Circular buffers are ideal for audio streaming due to their efficient management of continuous data.

Merge sort is a divide and conquer algorithm, dividing the array into halves and merging them back in sorted order.

Chaining is a technique where each bucket in a hash map maintains a list of all elements with the same hash value.

Kruskal's Algorithm is a greedy algorithm used to find a minimum spanning tree by choosing the shortest edges first.

A sparse graph has significantly fewer edges than the maximum possible, compared to the number of vertices.

Amortized analysis aims to average out the cost of an operation over a sequence of operations, providing a more realistic performance measure.

A queue is used in breadth-first search to maintain the order of nodes to be explored level by level.