Data Structures, unit: Arrays and Strings. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is an array?
Show answer
A fixed-size, contiguous block of memory storing elements of the same type- What is the time complexity of accessing an array element by index?
Show answer
O(1), constant time- What is the time complexity of inserting an element at the end of a dynamic array (amortized)?
Show answer
O(1) amortized- What is the time complexity of inserting an element at the beginning of an array?
Show answer
O(n), since all existing elements must shift- What is a dynamic array?
Show answer
An array that automatically resizes itself when it runs out of capacity- What happens when a dynamic array's underlying storage is full and a new element is added?
Show answer
A new, larger array is allocated and existing elements are copied over- What is amortized time complexity?
Show answer
The average cost per operation over a sequence of operations, smoothing out occasional expensive ones- What is a multidimensional array?
Show answer
An array of arrays, such as a 2D grid used for matrices- What is a string, in terms of its underlying data structure?
Show answer
Typically an array (or sequence) of characters- What is string immutability?
Show answer
A property where a string's contents cannot be changed after creation, common in languages like Python and Java- What is a substring?
Show answer
A contiguous sequence of characters within a larger string- What is string concatenation?
Show answer
Joining two or more strings together into one- What is the time complexity of searching for an element in an unsorted array?
Show answer
O(n), linear time- What is the time complexity of searching for an element in a sorted array using binary search?
Show answer
O(log n)- What is an index out of bounds error?
Show answer
An error from accessing an array position beyond its valid range
FlashKeepers