CMSC 202 Fall 2001
Final Exam Review
Sections 0101 - 0104

Scope of the exam

Like many other subjects, computer science is cumulative in nature.  We can't discuss each aspect of computer science in isolation.  Therefore, our final exam will also be cumulative.  The vast majority (80% or more) of the exam will be taken from material presented since the second exam.  The remaining 10-20% will be taken from other material we have covered this semester.  The exam is 2 hours long and is scheduled for Thursday, Dec 13th at 1:00 in LH 2

The format of the final exam will be much like that of exam 2 -- some short answer questions on concepts, some code to write and some code to interpret.

 Material since exam 2

Listed below are the major areas discussed since the second exam.  Under each area is a suggested list of topics pertinent to that area of study.  This list is to be used only as a study guide.  This list SHOULD NOT be considered exhaustive in any way, but if you understand all the material listed here should do fine on the exam. Some questions on the exam may come from the list, albeit in a somewhat modified form.  Some questions on the exam will not be found here.  When appropriate, class definitions will be provided with the exam questions.
 

    Templates

    1. What is the purpose of a function template?
    2. What makes a function template appropriate?
    3. Given a  written description, be able to write a syntactically correct function template.
    4. What is the purpose of a class template?
    5. Be able to read, interpret and use a class template.
    6. Given a written description, be able to write a syntactically correct class template.
    7. Be able to explain what happens when compiling/linking code that includes a function/class template.
    8. Be able to explain the concept of  "container class".
    9. What is an iterator? Why are they a useful concept ?
    10. Be able to use a class/function template to implement the solution to a simple application.
    11. Explain why it is sometimes necessary to implement type specific versions of a template function (such as Max( ) for strings as described in class).
    12. Explain why function/class templates are considered a form of polymorphism.
    13. Although function/template classes are designed to be used for any class, why will using a template with some classes will cause a compiler error?

    Lists

For these questions, the C++ class definitions of List and ListNode will be provided
    1. Show the results (via diagram) of sequences of  inserting/removing in a list.  For example after inserting the values {5, 2, 9, 10, 22, 42, 17} into an initially empty list by calling push_front( ).  by calling push_back( ).
    2. Explain why the ListNode class has no public constructor.
    3. From an object oriented point of view, why does it make sense for List to be a friend of ListNode, when we generally try to avoid friends ?
    4. Be able to write syntactically correct functions which might be part of the list class, or which may have a list as parameters. For example, count the number of elements in a list; return the "node number" at which a particular value was found in the list; the list destructor, inserting a value
    5. Use a list to implement the solution of a simple application.
    6. What is the big-Oh running time of push_front( ), push_back( ), pop_front( ), and pop_back( ) ? Justify your answer.

       Stacks and Queues

For these questions, the C++ class definition of a stack and a queue will be provided.
    1. Show the result (via diagram) of  pushing and popping elements in a stack
    2. Show the result (via diagram) of  enqueueing and dequeueing elements in a queue
    3. Use a stack and/or queue to implement the solution of a simple application.
    4. Write a syntactically correct function which might be part of a stack/queue class or have a stack/queue as a parameter.  For example -- write a function called CopyStack( ) (or CopyQueue) that makes and returns an exact copy of a stack/queue without using the copy constructor; determine if a string/number is a palindrome.
    5. Assuming a List implementation of a stack/queue, what is the big-Oh running time of push/pop/enqueue/dequeue? Justify your answer.
    6. Explain the meaning of the term LIFO.
    7. Explain the meaning of the term FIFO.

Trees

For these questions, the C++ class definition of BinarySearchTree (BST) and TreeNode will be provided.
  1. For any tree T, define path in T, length of a path in T, depth of a node in T, height of a node in T, the depth of T, the height of T
  2. Define full binary tree, complete binary tree, perfect binary tree
  3. Define internal node and external node in a rooted tree.
  4. Given a binary tree, show the output from a Breath-First traversal.
  5. Given a binary tree, show the output from an in-order, pre-order or post-order traversal.
  6. Write the syntactically correct C++ code for in-order, pre-order or post-order traversal for a binary tree.
  7. Define Binary Search Tree
  8. Draw the BST that results from inserting the following integers into an initially empty BST
    { 50, 30, 20, 66, 42, 77, 70, 2 }
  9. Given a BST, show the tree that results from a series of insertions and deletions.
  10. Given a general tree's first-child, next sibling representation, draw the tree.
  11. Given a general tree, draw its first-child, next sibling representation.
  12. Write a syntactically correct function which might be part of a BST class, or use a BST as a parameter.  For example - FindMin( ) that finds and returns the minimum value in a BST; printTree( ) that prints the data from each node in the BST in some order; BST destructor.
  13. Use a BST to implement the solution to a simple application.
  14. Explain why an in-order traversal of a BST always results in the data being printed in sorted order.
  15. Use a queue to write the code for a Breadth-First Search of a binary tree.
  16. Use a stack to write the code for a Depth-First Search of a binary tree.


Material from earlier in the semester

    Some material from earlier in the semester is fundamental to computer science.  In some cases the material is pertinent to topics studied since exam 2.  The exam may contain some questions about this material, or this material may appear in questions about topics studied since exam 2.

Recursion

    1. Given the definition of a recursive mathematical function, write the recursive C++ code.
    2. Given the input to a recursive function, determine the functions output.
    3. Use recursion to implement the traversals of a binary tree.

Other topics

  1. Object Oriented programming principles like encapsulation and data hiding
  2. Dynamic memory allocation -- used in linked lists and trees