DATA STRUCTURES EXAM 1 REVIEW
QUESTIONS AND ANSWERS
What is a Data Structure? - Correct Answers -A particular way of organizing data in a
computer so that it can be used efficiently
Examples of Data Structures - Correct Answers -Primitive types: bool, char, short, int,
etc.
Composite types: array, struct/class, union
Abstract Data types: stack, queue, list, set, map
Data Structures Details - Correct Answers -(efficient) storage and manipulation of
(large) data sets
Arrays (both static and dynamic), linked lists, linked trees
Used to implement abstract data types e.g. set, list efficient) storage and manipulation
of (large) data sets
What is an Algorithm? - Correct Answers -A self-contained step-by-step set of
operations to be performed
Examples of Algorithms - Correct Answers -Sequential search, binary search
Bubble sort, selection sort, merge sort
Inserting an element into a Binary Search Tree
Algorithm Details - Correct Answers -Operations on data
Insertion and removal of elements
Rearranging data (reverse, sort, merge)
Searching data
programs are ______ _______ + _________ - Correct Answers -Data Structures +
Algorithms
Types of Complexity - Correct Answers -1) Speed -relate operations to input size
, 2) Space - relates number of bytes to input size
example: space for linked list of ints vs array of ints
complexity breakdown - Correct Answers -Best case, average, and worse case.
Big-O notation - Correct Answers -Machine-independent means for specifying efficiency
(complexity)
Concerned with *asymptotic behavior
count key operation using growth or runtime function
example: if T(N)= 9N^2 + 43N + 7
then the algorithm is O(N2)
What is Time Complexity? - Correct Answers -relate operations to input size
aka how long it takes to run a function
What is Space Complexity? - Correct Answers -relates number of bytes to input size
Given a code segment, determine T(N) when counting comparisons. Then give O(N)
for (int i = 0; i < 4; ++i)
for (int j = 4; j >= 0; --j)
if (A[i] != A[j])
... - Correct Answers -T(N)=
O(N)= O(N^2)?
Container class examples - Correct Answers -array, vector, deque, list, forward_list
set, multiset, map, multimap
unordered_set, unordered_multiset, unordered_map, unordered_multimap
stack, queue, priority_queue
string, valarray, bitset (container-like)
Algorithm examples - Correct Answers -accumulate
copy
sort
lower_bound, upper_bound
nth_element
partition
What is an abstract data type? - Correct Answers -collection of values (e.g. ints,
Persons, Lists)
QUESTIONS AND ANSWERS
What is a Data Structure? - Correct Answers -A particular way of organizing data in a
computer so that it can be used efficiently
Examples of Data Structures - Correct Answers -Primitive types: bool, char, short, int,
etc.
Composite types: array, struct/class, union
Abstract Data types: stack, queue, list, set, map
Data Structures Details - Correct Answers -(efficient) storage and manipulation of
(large) data sets
Arrays (both static and dynamic), linked lists, linked trees
Used to implement abstract data types e.g. set, list efficient) storage and manipulation
of (large) data sets
What is an Algorithm? - Correct Answers -A self-contained step-by-step set of
operations to be performed
Examples of Algorithms - Correct Answers -Sequential search, binary search
Bubble sort, selection sort, merge sort
Inserting an element into a Binary Search Tree
Algorithm Details - Correct Answers -Operations on data
Insertion and removal of elements
Rearranging data (reverse, sort, merge)
Searching data
programs are ______ _______ + _________ - Correct Answers -Data Structures +
Algorithms
Types of Complexity - Correct Answers -1) Speed -relate operations to input size
, 2) Space - relates number of bytes to input size
example: space for linked list of ints vs array of ints
complexity breakdown - Correct Answers -Best case, average, and worse case.
Big-O notation - Correct Answers -Machine-independent means for specifying efficiency
(complexity)
Concerned with *asymptotic behavior
count key operation using growth or runtime function
example: if T(N)= 9N^2 + 43N + 7
then the algorithm is O(N2)
What is Time Complexity? - Correct Answers -relate operations to input size
aka how long it takes to run a function
What is Space Complexity? - Correct Answers -relates number of bytes to input size
Given a code segment, determine T(N) when counting comparisons. Then give O(N)
for (int i = 0; i < 4; ++i)
for (int j = 4; j >= 0; --j)
if (A[i] != A[j])
... - Correct Answers -T(N)=
O(N)= O(N^2)?
Container class examples - Correct Answers -array, vector, deque, list, forward_list
set, multiset, map, multimap
unordered_set, unordered_multiset, unordered_map, unordered_multimap
stack, queue, priority_queue
string, valarray, bitset (container-like)
Algorithm examples - Correct Answers -accumulate
copy
sort
lower_bound, upper_bound
nth_element
partition
What is an abstract data type? - Correct Answers -collection of values (e.g. ints,
Persons, Lists)
