Exam 2 Review, CS 250

Topics:

  • Pointers
  • Dynamic Arrays
  • Linked Lists
  • Stacks and Queues
  • Algorithm Efficiency

Question Breakdown:

#QuestionWeight
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%

Question types:

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:

Pointers

  • 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.

Growth Rates

  • 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.