Exam 2 Review, CS 250
- Dynamic Arrays
- Linked Lists
- Stacks and Queues
- Algorithm Efficiency
| 1 || Stack and Queues - calling Linked List functions || 12% |
| 2 || Growth Rates - Dynamic Array and Linked List || 12% |
| 3 || Diagramming 1 - Stack || 16% |
| 4 || Diagramming 2 - Queue || 16% |
| 5 || Top and Front Commands || 12% |
| 6 || Growth Rates - Identification || 12% |
| 7 || Dynamic Variable || 10% |
| 8 || Dynamic Array || 10% |
| 9 || Extra Credit - Linked List || +2% |
The extra credit question and the dynamic variable/array questions are short programming problems.
The rest is diagraming, fill in the blank, or multiple choice questions.
Things to know:
- How to allocate and deallocate memory for a dynamic variable using a pointer.
- How to allocate and deallocate memory for a dynamic array using a pointer.
Dynamic Arrays and Linked Lists
- Knowing the growth rates of access, search, and insert functions for Dynamic Arrays and Linked Lists
- Array Access: A dynamic array can access an arbitrary element instantaneously because each element is contiguous in memory.
- List Access: A Linked List only stores the location of the first and last nodes via pointers. To access an arbitrary element, you have to start at the beginning and traverse forward, one-by-one, until you get there.
- Array Search: Have to start at beginning and look at each element until found, or reach the end of the array.
- List Search: Have to start at beginning and look at each element until found, or reach the end of the list.
- Array insert: Insert item at arbitrary position (access is instant). However if Resize() is required, then you need to iterate over all elements of the array, copying them over to a bigger array.
- List insert: Allocate new memory for one new Node item at a time, then update pointers to point to new node.
Stacks and Queues
- Given a diagram of a Stack, draw the updated stack state after Push and Pop commands.
- Given a diagram of a Queue, draw the updated queue state after Push and Pop commands.
- Be able to identify which item is in Front of a Queue after a Push and Pop commands.
- Be able to identify which item is at the Top of a Stack after a Push and Pop commands.
- Know which Linked List functions a Stack calls for Push, Pop, and Top.
- Know which Linked List functions a Queue calls for Push, Pop, and Front.
- Know the growth rates for insert, access, and delete for dynamic array vs. linked list (see above).
- Be able to identify basic growth rates O(1), O(n), O(n2) given some basic code.