LinkedLists
Nodes are connected to each other using this reference
What is next / next node
A stack can be built using these two data structures
what are arrays and linked lists
These are the two steps of a recursive method
The base case and the recursive case
These are the best and worst time efficiencies
What are O(1) and O(n!)
All deque operations have this efficiency
What is O(1)
Doubly linked lists are different than singly linked lists in that they have this reference
What is previous / previous node
These are the 4 main methods of a stack and a queue (use the appropriate names for each)
Stack: what are push(), pop(), peek(), isEmpty()
Queue: what are offer(), poll(), peek(), element()
A binary search tree is different than a general tree in that it is limited to this many of these for each entry
These data structures have O(n) search, O(1) insertion, and O(1) deletion
what is an expression tree
A node stores data using this data type
What is generic
The only stack method that doesn't return an item
what is peek()
This kind of tree must be a perfect tree, but this kind may not be one.
What are full and complete trees
This is the best and worst case efficiency of a binary search
What are O(log n) and O(n)
Binary tree is implemented differently than all other data structures because its methods are this
what is recursive
what is reallocate()
A stack is this while a queue is this
what are LIFO (last-in, first-out) and FIFO (first-in, first-out)
An expression tree must use this type of traversal
What is inorder traversal
Rank the following Big-O efficiencies: O(n^2), O(n log n), O(1), O(n!), O(log n), O(n!), O(2^n) from least to most efficient.
What is O(n!), O(2^n), O(n^2), O(n log n), O(n), O(log n), O(1)
What data structures are best suited for a revolving sushi bar, a barrel of monkeys game, an ancestry diagram, and a bar bell?
revolving sushi bar: circular array/queue
barrel of monkeys game: singly linked list
ancestry diagram: doubly linked list
barbell: stack
Insertion at the beginning, removal from the middle, and adding to the very end of a doubly linked list have these efficiencies (list 3 big-O's)
What are O(1), O(n), O(1)
BUT traditionally we only add or remove at the beginning / end
what is double ended
List the order of root, left, and right for each tree traversal
preorder: root, left, right
inorder: left, root, right
postorder: left, right, root
hint: look at where root is
What are the efficiencies of recursive fibonacci and recursive factorial?
What are O(2^n) and O(n)
Hint: how many operations do we recurse through each time
Given the front of a circular queue "f" and its capacity "c", what is the missing line in its reallocate() method's for loop:
for (int i = 0; i < size; i++) {
newData[i] = oldData[i];
// what goes here?
}
what is f = (f + 1) % c;