Flashcard library · Computer Science
Computer Science: Data Structures
This flashcard deck covers fundamental concepts in Computer Science Data Structures, including common linear and non-linear structures, algorithmic complexity analysis, and essential terms. It's designed to help students grasp the core principles required for understanding how data is organized and efficiently managed.
Want to actually learn these?
Create a free NoteFren account to study with spaced repetition, or turn your own notes into cards like these.
What is a data structure?
A data structure is a particular way of organizing data in a computer so that it can be accessed and modified efficiently. It defines the relationship between data and the operations that can be performed on it.
What are the main categories of data structures?
Data structures are primarily categorized as linear (e.g., arrays, linked lists, stacks, queues) or non-linear (e.g., trees, graphs, hash tables).
What is an algorithm's time complexity?
Time complexity measures the amount of time an algorithm takes to run as a function of the input size, typically expressed using Big O notation.
What is an algorithm's space complexity?
Space complexity measures the amount of memory an algorithm uses as a function of the input size during its execution.
What is Big O notation used for?
Big O notation is used to describe the upper bound or worst-case performance of an algorithm's time or space complexity, indicating how its resource usage grows with input size.
What is an array?
An array is a collection of elements of the same data type, stored at contiguous memory locations, allowing for direct access to any element using its index.
What is a linked list?
A linked list is a linear data structure where elements are stored in nodes, each containing data and a reference (or pointer) to the next node in the sequence.
What is a stack?
A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle, meaning the last element added is the first one to be removed. Operations are Push (add) and Pop (remove).
What is a queue?
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle, meaning the first element added is the first one to be removed. Operations are Enqueue (add) and Dequeue (remove).
What is a tree data structure?
A tree is a non-linear hierarchical data structure consisting of nodes connected by edges, where each node has a parent (except the root) and zero or more children.
What is a binary tree?
A binary tree is a tree data structure where each node has at most two children, typically referred to as the left child and the right child.
What is a hash table (or hash map)?
A hash table is a data structure that maps keys to values using a hash function, providing efficient average-case time complexity for operations like insertion, deletion, and lookup.
What is a graph data structure?
A graph is a non-linear data structure consisting of a finite set of vertices (nodes) and a set of edges that connect pairs of vertices, representing relationships between them.
What is the primary advantage of a B-tree over a binary search tree for disk-based storage?
B-trees are optimized for disk-based storage by keeping data sorted and allowing multiple child nodes per parent, which minimizes the number of disk I/O operations required to access data.
What is the purpose of a heap data structure?
A heap is a specialized tree-based data structure that satisfies the heap property, typically used to implement priority queues and efficiently find the minimum or maximum element.