DATA STRUCTURES FINAL EXAM
QUESTIONS AND ANSWERS
Big Oh Notation - Correct Answers -- Least upper bound measure of the time
complexity of an algorithm
Algorithm Analysis - Correct Answers -- Analyze code to see if its speed and/or memory
consumption is optimal for a given problem
O(1) - Correct Answers -- Big oh of one
- Constant time
O(logn) - Correct Answers -- Logarithmic Time
- As the problem doubles, it only takes one more unit of time
O(n) - Correct Answers -- Linear time
- As the problem doubles so does the amount of work
O(nlogn) - Correct Answers -- Linear log
O(n^2) - Correct Answers -- Quadratic
Linear Search - Correct Answers -- O(n)
- Typically in terms of worst case
- For unsorted array
Binary Search - Correct Answers -- O(logn)
- Divide and conquer algorithm instead of reading the problem by 1 on each iteration,
we'll reduce it by a fractional amount
- For sorted array
Functional notation - Correct Answers -- A more precise measure of the number of
steps/operations that a given algorithm requires to do complete
Big O from functional notation - Correct Answers -- Keep only the fastest growing term
- Drop coefficient
Recursion - Correct Answers -- A method that calls itself
- Base case: recursion to stop
, - Self-call (maybe indirect)
- Production rule: causes us to approach base case
Tail Recursion - Correct Answers -- The only self-calls are on the last statement of the
function
Non-tail Recursion - Correct Answers -- Call(s) are embedded in the function body
Indirect Recursion - Correct Answers -A() -> B() -> A()
Excessive Recursion - Correct Answers -- Redundant recursion calls
Arrays - Correct Answers -- Continuous chunk of memory
- Random access
---Element 5 is just as accessible as element 20
Linked Base - Correct Answers -- Pointer/Reference
- One or more that link to another data point/node
Named Nodes - Correct Answers -- Nodes that have a pointer(s) assigned to it that are
held in the list object
Linear Data Structures - Correct Answers -- Straight, effectively single dimension
structure
- Commonly implemented with an array
Stack - Correct Answers -- Linear
- Two basic operations
- Push: add data onto the top of the stack
- Pop: remove data from the top of the stack
--- O(1)
Pop() Operation - Correct Answers -1) Return value from the top of the stack
2) Shift the top over
3) Clean memory
Queues - Correct Answers -- Linear data structure
- FIFO (First In First Out) or LILO (Last In Last Out)
- Enqueue: add data onto the last data
- Dequeue: remove data in the front
Linked Based Queue structure - Correct Answers -- Singly Linked
- Two named nodes
Array Based Queue structure - Correct Answers -- Pushing F(Front) and E(End)
towards next array
QUESTIONS AND ANSWERS
Big Oh Notation - Correct Answers -- Least upper bound measure of the time
complexity of an algorithm
Algorithm Analysis - Correct Answers -- Analyze code to see if its speed and/or memory
consumption is optimal for a given problem
O(1) - Correct Answers -- Big oh of one
- Constant time
O(logn) - Correct Answers -- Logarithmic Time
- As the problem doubles, it only takes one more unit of time
O(n) - Correct Answers -- Linear time
- As the problem doubles so does the amount of work
O(nlogn) - Correct Answers -- Linear log
O(n^2) - Correct Answers -- Quadratic
Linear Search - Correct Answers -- O(n)
- Typically in terms of worst case
- For unsorted array
Binary Search - Correct Answers -- O(logn)
- Divide and conquer algorithm instead of reading the problem by 1 on each iteration,
we'll reduce it by a fractional amount
- For sorted array
Functional notation - Correct Answers -- A more precise measure of the number of
steps/operations that a given algorithm requires to do complete
Big O from functional notation - Correct Answers -- Keep only the fastest growing term
- Drop coefficient
Recursion - Correct Answers -- A method that calls itself
- Base case: recursion to stop
, - Self-call (maybe indirect)
- Production rule: causes us to approach base case
Tail Recursion - Correct Answers -- The only self-calls are on the last statement of the
function
Non-tail Recursion - Correct Answers -- Call(s) are embedded in the function body
Indirect Recursion - Correct Answers -A() -> B() -> A()
Excessive Recursion - Correct Answers -- Redundant recursion calls
Arrays - Correct Answers -- Continuous chunk of memory
- Random access
---Element 5 is just as accessible as element 20
Linked Base - Correct Answers -- Pointer/Reference
- One or more that link to another data point/node
Named Nodes - Correct Answers -- Nodes that have a pointer(s) assigned to it that are
held in the list object
Linear Data Structures - Correct Answers -- Straight, effectively single dimension
structure
- Commonly implemented with an array
Stack - Correct Answers -- Linear
- Two basic operations
- Push: add data onto the top of the stack
- Pop: remove data from the top of the stack
--- O(1)
Pop() Operation - Correct Answers -1) Return value from the top of the stack
2) Shift the top over
3) Clean memory
Queues - Correct Answers -- Linear data structure
- FIFO (First In First Out) or LILO (Last In Last Out)
- Enqueue: add data onto the last data
- Dequeue: remove data in the front
Linked Based Queue structure - Correct Answers -- Singly Linked
- Two named nodes
Array Based Queue structure - Correct Answers -- Pushing F(Front) and E(End)
towards next array
