112 2nd Midterm Review Topics
Topic areas:
Lectures (chapters 6, 7, 2, 5, templates, standard template library)
Assignments
Labs
Solving problems
Exam Topics from Lecture:
Stacks (chapter 6)
definition of a stack (first in last out: FILO)
what problems can be solved naturally using a stack
reversing data
calculator
run-time stack
recursion w/backtracking (8-queens, solving a maze)
implement functions from a stack class
push
pop (can remove & return or just remove)
top (return first, needed if pop does not return value)
constructor/destructor
solving problems using a stack
Queues (chapter 7)
definition of a queue (first in first out: FIFO)
what problems can be solved naturally using a queue
resource allocation (e.g. printer queue)
simulations
implement functions from a queue class
enqueue
dequeue
size
first
constructor/destructor
priority queue
enqueue
dequeue
solve problems using a queue
C++ Templates
basic idea (don't need to know the exact syntax)
write the pseudo-code to implement a template to do _____
Standard template library
basic idea
how to use a vector
creating
inserting
iterating through the vector (you need to know this code)
Recursion (chapters 2,5)
general idea
the four questions you must answer to construct a recursive solution (the concepts, not the exact words)
1) How can you define the problem in terms of a smaller problem of the same type?
2) How does each step (recursive call) diminish the size of the problem?
3) What instance of the problem can serve as the base case?
4) As the problem size diminishes, will you reach this base case?
need to be able to write and read recursive programs
write a recursive function to do _____
what does the given recursive function do when passed 42
Exam Topics from Labs:
command line arguments
int main(int argc, char *argv[])
file i/o
ofstream ofile(name, ios::out);
ofile << "hello" << endl;
array of pointers to an object
Cust *checkers[10];
the gdb debugger
basics on how to use
finding the cause of a segmentation fault
Exam Topics from Assignments:
p3: telephone bill -- list
list programming
p4: calculator -- stack
how you read input
how the algorithm works
stack programming
p5: simulation -- queue
queue programming questions