CPSC 225

Intermediate Programming

Fall 2005

Exam Review Information

Midterm 1

Midterm 1 will be written (not on the computer) and in a regular class period. It will be closed book/notes.

The main topics that will be covered are listed below.

Basic C++ Programming

program structure (where #includes go, what main looks like, concepts like expressions and statements, etc)
basic statements: variable declarations, assignment statements
input/output
conditionals: if statements, switches
loops: while loops, for loops, do-while loops
C++ programming standards (indentation, naming conventions, commenting, etc)

Functions

declaring functions: function prototypes, function implementation
function calls
parameter passing: call-by-value, call-by-reference, call-by-const-reference (syntax for declaring a parameter using a certain technique, semantics of how the parameter values are set up in the function call, what may be passed as an argument/actual parameter in a function call, why you'd use each technique)
overloading functions (what it means, how to do it, determining which implementation is called, when it is appropriate to use)

Arrays

declaring arrays
accessing individual slots of an array
passing arrays as parameters to functions
arrays and =, ==, !=, <, >, etc.
multidimensional arrays (declaring, accessing, passing to functions)

Classes & Objects

why classes are useful/important
the philosophy of object-oriented programming
class syntax: class declaration, class implementation, public/private, initializer lists
special class methods: constructors, accessors, mutators (what they are, how to declare/implement them, why one might want them)
object syntax: declaring variables, creating objects, using objects
semantics: what happens when a variable with a class type is declared, what happens when a constructor is called, what constructor is called when, what happens when a method is invoked on an object
arrays where the base type is a class type (instead of a primitive type)
arrays as instance variables in classes

Characters & Strings

C-strings: how they are represented, when it is necessary to use them
C++ string class: creating C++ strings, initializing/assigning/comparing C++ strings, basic operations (concatenation, accessing characters, length, extracting substrings)
I/O with C-strings, C++ strings, and characters: cin and cout, other ways of getting/manipulating input (get, getline, putback)
converting between C-strings and C++ strings (both directions)

There are a lot of routines for manipulating characters and strings (both C-strings and C++ strings) - you should know the major ones (generally those mentioned above and/or those used in homeworks) and should be familiar with the others, but you won't be expected to memorize every possible routine. For the less common things, you might be given a list of function prototypes (but no descriptions) and be asked to use the appropriate one(s) to accomplish a particular task.

Files

basic reading and writing from files (#includes, opening files, variable types, actual reading/writing, closing files, etc)
error-checking (e.g. failure to open a file)
detecting and working with eof
streams as function parameters

Things like formatting of output (two decimal places, in columns, etc) might appear on a bonus but wouldn't be required.

Miscellaneous

terminology (be familiar with/be able to define terms used in the course)
standard functions: using common functions such as sqrt, pow, etc. and what #includes are needed (if any)
random numbers: rand() and srand(), obtaining a random number in particular range, etc
type casting: static_cast and when to use it
assertions (syntax, semantics, #includes, why you'd use them)
operator overloading: when to overload an operator, syntax, when to overload an operator as a class method and when as a free function
friend functions: when to use friend functions, syntax

Again, you don't have to know every standard library function in existence, but you should know how to use the ones used in class examples and homeworks (like sqrt, pow, rand, srand).

Stacks & Queues

the ADT (what stacks and queues are, what the typical operations are and what they do)
applications of stacks and queues (e.g. reversing strings, paren balancing)
array-based implementation of stacks and queues

You are responsible for everything in the assigned reading (chapters 1-5, 6.1-6.2, 7.1-7.2, 8-9, 10.1-10.2, 11.1, and 12) even if it wasn't specifically mentioned in class and/or it isn't specifically listed above. However, the exam is only 55 minutes long - which limits the number and depth of the questions asked. Given this constraint (and the fact that the exam is closed book), the focus will be on the essentials that every C++ programmer really ought to know without looking it up. This means the basic syntax and semantics of the topics listed above, along with knowing when it is appropriate to use what. It is fair to say that there will be more emphasis on new topics in C++ and differences between C++ and Java than there will be on just writing a basic program which is virtually identical to its Java counterpart, though certainly one couldn't get very far by completly ignoring the similarities. Somewhat sneaky but important/common C++ quirks or differences may appear; very sneaky and uncommon quirks are more likely to be relegated to bonuses if they appear at all.

Sample Problems

In terms of specific topics, it is likely (though not guaranteed) that there will be at least a question involving the semantics of parameter passing, something involving manipulation of arrays, a class implementation question, and a question involving file I/O.

If you are looking for pre-exam practice, try the book's self-test exercises and end-of-chapter programming projects. You can practice reading code by looking at the examples on the syllabus page.

Midterm 2

Midterm 2 will be a take-home exam. It will be open book/notes. Specifically, this means that you can use your own copy of the course textbook, your own notes made prior to the time the exam was handed out, your own lab solutions, and any materials or examples posted on the course webpage or linked directly to it. You may use a computer.

The main topics that will be covered are listed below. The emphasis will be on topics which are new since the last exam, but it is not possible to completely avoid earlier topics.

Pointers & Dynamic Memory Allocation

working with pointer types: the meaning of a pointer, declaring a pointer, the * and & operators, passing pointers to functions, the special value NULL
things to avoid: dereferencing a NULL pointer, dangling pointers, memory leaks (what is each thing)
dynamically-allocated memory: allocating memory, deleting memory
dynamically-allocated arrays: declaring, allocating, initializing, working with (including passing to functions), deallocating 1D and 2D arrays
dynamically-allocated memory and classes: when to include copy constructors, assignment operators, destructors and what proper implementations of these look like
this: what it is, when to use it

Linked Lists

the concept of what a linked list is, how one is represented (via a head pointer), what a list node is, what a list node class looks like
manipulating a linked list: the "pattern" of having a "finger" pointer moving through the list, working out code for tasks like printing a list, finding its length, inserting, removing, copying, deallocating as well as more complex manipulations, passing a linked list to a function
the advantages and disadvantages of linked lists vs. arrays as a way of storing a collection of things

Inheritance

inheritance: how to indicate that one class is a subclass of another, how to extend a class (adding new things), how to override methods, why you'd want to use inheritance or override methods
polymorphism: what it is, why it is useful
binding: the difference between early and late binding, how each kind is indicated, the semantics (how to identify which version of a method is used in a particular program)
pure virtual functions and abstract classes: what "pure virtual" and "abstract" mean, how to declare a method to be pure virtual, how to override it in a subclass, why you'd want to make something pure virtual
the meaning of private, protected, public as they relate to subclasses

Applications

implementing classes which use dynamically-allocated arrays and/or linked lists to store things: what the instance variables look like, constructors/copy constructors/operator=/destructors (e.g. stack, queue, priority queue)

You are responsible for everything in the assigned reading (Savitch 8.2, 10.1-10.3, 14-15, 17.1-17.2) even if it wasn't specifically mentioned in class and/or it isn't specifically listed above.

Sample Problems

You should expect questions involving reading/tracing code, writing code, and short answers about code or concepts. Reading/tracing code (e.g. indicating what the output would be, numbering statements in the order they are executed, or describing what occurs) demonstrates knowledge of the semantics of an operation. Because you are allowed to use a computer on the exam, any tracing questions will require you to show your work and/or explain how you achieved the result - just produce the output of the trace will not earn any credit. Writing code demonstrates knowledge of syntax, semantics, and when it is appropriate to use a given construct.

In terms of specific topics, it is likely (though not guaranteed) that there will be at least a question involving linked lists, one involving binding, and one involving writing subclasses.

If you are looking for pre-exam practice, try the book's self-test exercises and end-of-chapter programming projects. You can practice reading code by looking at the examples on the syllabus page.

Final Exam

The final exam will be in the scheduled time slot. Most of it will be written (not on the computer), but there might be a component on the computer. It will be closed book/notes.

Approximately 1/3 to 2/3 of the exam will specifically address topics which are new since the last exam (though it is not possible to completely avoid earlier topics due to the cumulative nature of the material). Those main topics are listed below. The remainder of the exam will specifically address earlier material.

Templates

syntax: how to write a template class
semantics: what a template class means, what happens when the program is compiled (and the implications of this for what the compiler commandline looks like)
why you'd use a template class: what is the purpose, in what circumstance is a template class appropriate, what are other techniques for achieving similar results, what are the pros and cons of each technique

Recursion

terminology: what a recursive definition is, what "base cases" and "recursive cases" are
syntax: how to write a recursive function, how scoping rules apply with recursion
semantics: what is necessary to make a recursive function work, how to trace a recursive function
using recursion to solve problems: writing a recursive function given a recursive definition, designing recursive functions (without an explicit recursive definition), backtracking (what it is, when it is useful, how recursion fits in)

Trees & Binary Trees

terminology: tree, binary tree, proper binary tree, complete binary tree, full binary tree, node, root, leaf, internal node, parent, child, subtree, subtree rooted at a particular node, height, depth, size, etc.
properties: the shape and height of minimum- and maximum-height binary trees with n nodes, the number of nodes in a proper binary tree
traversals: preorder, inorder, postorder (the definition of the traversal, being able to identify the nodes in the order visited)
BinaryTree ADT: typical operations (what they are, how to use them)
linked-structure implementation: what the tree node class looks like (instance variables, method implementations), what the binary tree class looks like (instance variables, method implementations)
working with trees: writing pseudocode/code to work with the BinaryTree ADT e.g. computing size, height, depth of a node, evaluating an expression tree, etc.
binary search trees: what they are (be able to define, recognize, and/or create an example of one), how to use BinaryTree to implement, implementation of search, insert, remove operations

Testing & Debugging

how to develop test cases
debugging: the steps in the methodical approach, and how to carry them out

You are responsible for everything in the assigned reading (chapters 13, 16, 17.4) even if it wasn't specifically mentioned in class and/or it isn't specifically listed above. You are also responsible for material covered in class that is not in the book. However, since the exam is a closed book exam, you will not be expected to have memorized every little bit of syntax or C++ library function - focus on the syntax and library functions used in class and on the homeworks/projects.

Sample Problems

As with the midterms, you should expect questions involving reading/tracing code, writing code, and short answers about code or concepts. Reading/tracing code (e.g. indicating what the output would be, numbering statements in the order they are executed, or describing what occurs) demonstrates knowledge of the semantics of an operation. Writing code demonstrates knowledge of syntax, semantics, and when it is appropriate to use a given construct. There may also be synthesis questions which require applying your knowledge of C++ and program design to make a choice or discuss several alternatives to solving a problem. Examples include comparing the pros/cons of two syntax alternatives or explaining when it is appropriate to apply a particular technique.

In terms of specific topics, it is likely (though not guaranteed) that there will be at least a question involving recursion (most likely writing and/or tracing a recursive function) and one involving manipulating binary trees (i.e. implementing some operation on a binary tree, either directly with the linked structure or using the BinaryTree ADT). Major topics from the midterms are also likely question topics: parameter passing, arrays, class implementation, reading/writing files, linked lists, writing subclasses, and types of C++ expressions.

The following practice questions are for just that - practice. You may see one of these questions (or a similar one) on the exam - and you may not. If, however, you are comfortable with solving all of them, you should be in very good shape for solving any question that does come up on the exam.

Linked list practice questions, in a rough order from easiest to hardest: (thanks to Nick Parlante)

Write a function to count the number of times a given value occurs in a linked list.
Write a function to get the element stored in the nth node of a linked list.
Write a function to deallocate a linked list.
Write a function to remove the head node of a linked list, returning the node's data.
Write a function to insert a new node at a specified index in a linked list.
Write a function to insert a new node in the correct position in a linked list whose nodes are sorted in increasing order by element.
Write a function which takes two linked lists and appends the second to the end of the first. (e.g. if the first list contains elements 1, 2, 3 and the second list contains elements 4, 5, 6 the new list should contain 1, 2, 3, 4, 5, 6 - in that order)
Given a linked list, split it into two lists - one containing the first n/2 elements and the other containing the second n/2 elements (where n is the number of elements in the original list). If n is odd, put the extra element in the first list.
Write a function to remove duplicate elements from a linked list. The first occurrence of each element should be left.
Given two linked lists, move the node from the front of the second list to the front of the first list.
Given a linked list, split it into two lists by alternating nodes, preserving the order of nodes in the original list. (e.g. if the list contains the elements 1, 2, 3, 4, 5, 6 then the first list should have 1, 3, 5 and the second list 2, 4, 6) If there are an odd number of nodes, the first list should get the extra one.
Write a function which, given two linked lists, merges the lists into a single list by alternating elements from each list. (e.g. if the first list contains 1, 4, 2, 5 and the second list contains 0, 3, 8 then the result should be 1, 0, 4, 3, 2, 8, 5) If either list runs out of nodes, the remaining nodes from the other list should be taken without alternating.
Write a function which, given two linked lists whose elements are sorted in increasing order, merges the lists into a single list in sorted order. (e.g. if the first list contains 1, 2, 4, 5 and the second list contains 0, 3, 8 then the result should be 0, 1, 2, 3, 4, 5, 8) Duplicates are allowed.
Write a function which, given two linked lists whose elements are sorted in increasing order, returns a list containing just the elements which appear in both lists. (e.g. if the first list contains 1, 2, 4, 5 and the second list contains 0, 2, 3, 5, 8 then the result should contain 2, 5)
Write a function which reverses the order of nodes in a linked list.

Other linked list questions might be to implement one or more methods of a stack, queue, or priority queue using a linked list to store the elements.

For binary trees, you might be asked to write code to directly manipulate the linked tree structure such as:

Write a function to deallocate a binary tree, given a pointer to the root node. (i.e. write a destructor for the BinaryTree class)
Write a function to copy a binary tree, given a pointer to the root node. (i.e. write a copy constructor for the BinaryTree class)

Or, you might be asked to manipulate an instance of the BinaryTree class. Perhaps:

Write a function which, given a binary tree, determines the height of the tree.
Write a function which, given a binary tree, prints out the nodes in the order of a preorder (or postorder or inorder) traversal.
Write a function which, given a binary search tree, finds the smallest (or largest) element in the tree.
Write a function which, given a binary tree and two nodes of the tree, determines if the first node is a descendant (or ancestor) of the second. (Node A is a descendant of node B if node A is contained in the subtree rooted at B and isn't B. Node A is an ancestor of node B if node A is B's parent or grandparent or great-grandparent or...)
Write a function which, given a binary tree, determines if a particular element is contained in the tree.
Write a function which, given a binary tree, counts how many times a particular element is contained in the tree.
[more difficult] Write a function which, given a binary search tree and an integer k >= 1, finds the kth smallest element in the tree. (i.e. k = 1 means to find the smallest, k = 2 means to find the second smallest, etc)

Other binary tree questions might be to implement one or more methods of a priority queue or binary search tree using a binary tree.