CS 106B: Programming Abstractions, Winter 2018

Rules and Information:

Same as on the midterm exam (see rules below).

Syntax Reference Sheet:

• syntax reference sheet (will be given out attached to your exam as a reference; bring your textbook to reference any other C++ syntax/libraries)

Practice Exams and Review:

• practice final #1 | key (based on Autumn 2013 practice final 1)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. binarySearch1, selectionSort1, insertionSort1, mergeSort1 (searching/sorting read)
  2. linkedListMystery (linked lists read)
  3. chopBothSides (linked lists write)
  4. bstAdd1 (binary trees read)
  5. swapChildrenAtLevel (binary trees write)
  6. heapAddRemove (heaps read)
  7. graphPropertiesExam (graphs read)
  8. containsBidiPath (graphs write)
  9. polymorphismMystery (inheritance read)
  10. RiggedDice (inheritance write)
• practice final #2 | key (based on Autumn 2013 practice final 2)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. linked list nodes (linked lists read)
  2. digitsSorted (recursion)
  3. isSortedBy (linked lists write)
  4. binary trees read: missing; use answer key instead
  5. removeMatchingLeaves (binary trees write)
  6. heapAddRemove (heaps read)
  7. graphPropertiesExam (graphs read)
  8. popular (graphs write)
  9. polymorphismMystery (inheritance read)
  10. GradStudent (inheritance write) - missing; use answer key instead
• practice final #3 | key (based on Autumn 2013 final)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. binarySearch3, mergeSort3 (searching and sorting read)
  2. linkedListMystery (linked lists read)
  3. binary trees read: missing; use answer key instead
  4. range (binary trees write)
  5. hashMapOperations (hashing read)
  6. graphs read: missing; use answer key instead
  7. findHamiltonPath (graphs write)
  8. polymorphismMystery (inheritance read)
  9. StudentTicket (inheritance write) - missing; use answer key instead
• practice final #4 | key (based on Winter 2014 final)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. linked lists read: missing; use answer key instead
  2. expand (linked lists write)
  3. binary trees read: missing; use answer key instead
  4. makeFull (binary trees write)
  5. heapAddRemove (heaps read)
  6. graphs read: missing; use answer key instead
  7. bipartiteSets (graphs write)
  8. hashMapOperations (hashing read)
  9. polymorphismMystery (inheritance read)
  10. MemoryCalculator (inheritance write)
• More practice problems can be found in the textbook and in your section handouts.
• Sample final exam(s) posted here are intended to be similar to the actual final. The number of problems and type of problems on the actual exam will be relatively similar to what is seen on these practice exams, though we do not promise that it will be exactly the same in length or in difficulty.

Additional Sample Problems:

If you want more practice problems, here are links to some past exams given in 106B by other instructors. They don't exactly match the current exam format, so they may be of limited use. Some of the problems on these tests don't match the topics, difficulty level, and/or type of questions we currently plan to ask. These links are provided merely as a convenience to help you study.

• Spring 2014 (Cynthia Lee): final exam
• Spring 2013 (Keith Schwarz): practice midterm 2 (final) | key | midterm 2 (final) | key
• Winter 2013 (Eric Roberts): practice midterm 2 | key | midterm key | practice final 1 | key | practice final 2 | key
• Autumn 2012 (Jerry Cain): practice final | key | final | key

Topics to Study:

The actual exam will have roughly 10 total problems. Those problems will be selected from the following categories. For each category, you may be asked to read code (look at a piece of existing code and answer questions about it, such as writing its output), and/or write code (write a piece of code such as a function or short program that solves a problem about that topic).

• linked lists: read/write code to manipulate a chain of ListNode objects from lecture, or a similar linked list class
• recursion and/or recursive backtracking: write a function that uses recursion to solve a problem, possibly one involving backtracking
• binary trees: simulate operations on a binary search tree (BST) such as adding or removing elements; perform traversals on a binary tree; add behavior to the BinaryTree class from lecture or a similar binary tree class
• implementing data structures: simulate operations on a data structure we implemented or discussed the implementation of in lecture, such as a tree set/map, hash set/map; stack, queue, vector; and/or, add behavior to an existing implementation class such as TreeSet or ArrayList
• graphs: look at a given graph and answer questions about it, such as connectedness, cyclicness, degrees; simulate the execution of path-searching algorithms such as DFS, BFS, Dijkstra's algorithm, A*; simulating execution of Kruskal's algorithm
• binary heaps: simulate the adding/removal of nodes from a binary min-heap or max-heap
• hashing: simulate operations on a hash set or hash map data structure
• searching and sorting: demonstrate knowledge of the behavior of selection, insertion, merge, or quick sort algorithms
• inheritance, polymorphism, object-oriented programming: look at a piece of code involving inheritance and interpret its output; and/or, write a class that uses inheritance to extend some existing base class

• The following topics are guaranteed NOT to be required to solve any problem on the final exam:
  • drawing fractals; graphics with the GWindow class
  • multiple inheritance; pure virtual functions; private inheritance
  • overloading the = operator, copy constructors, and deep copying
  • the Standard Template Library (STL)
  • writing your own C++ template classes such as ArrayList<T>
  • details of how to perform rotations on an AVL tree to restore its balance
  • other kinds of advanced trees such as AVL, Red/Black, Splay, or prefix trees (tries)
  • anything else not explicitly covered in lecture or homework
  • any material that is only covered in the "Overflow" slides at the end of various lecture slide decks

Reference Sheet:

• syntax reference sheet (will be given out attached to your exam as a reference; bring your textbook to reference any other C++ syntax/libraries)

Practice Exams:

Sample midterm exam(s) posted here are intended to be very similar to the actual midterm. The number of problems and type of problems on the actual exam will be much like what is seen on these practice exams. You can test your answer by typing it into Qt Creator or CodeStepByStep.

• practice midterm #1 | key (based on an Autumn 2013 practice midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery1
  2. wordStats
  3. collectionMystery1
  4. byAge
  5. bigOh1
  6. recursionMystery1
  7. moveToEnd
  8. crack
  9. list nodes
• practice midterm #2 | key (based on an Autumn 2013 practice midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery2
  2. flipLines
  3. collectionMystery2
  4. isSorted
  5. bigOh2
  6. recursionMystery2
  7. largestDigit
  8. printSquares
  9. list nodes
• practice midterm #3 | key (based on an Autumn 2013 practice midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery3
  2. coinFlip
  3. collectionMystery3
  4. removeBadPairs
  5. bigOh3
  6. recursionMystery3
  7. matchCount
  8. isMeasurable
  9. list nodes
• practice midterm #4 | key (based on Autumn 2013 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery4
  2. inputStats
  3. collectionMystery4
  4. starters
  5. bigOh4
  6. recursionMystery4
  7. indexOf
  8. chainExists
  9. list nodes
• practice midterm #5 | key (based on Winter 2014 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery5
  2. printBox
  3. collectionMystery5
  4. rarest
  5. bigOh5
  6. recursionMystery5
  7. sequence
  8. isElementSpellable
  9. list nodes
• practice midterm #6 | key (based on Summer 2014 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery6
  2. printMostCommonName
  3. collectionMystery6
  4. pairFrequencies
  5. bigOh6
  6. recursionMystery6
  7. printRange
  8. squishWord
• practice midterm #7 | key (based on Autumn 2014 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. collectionMystery7
  2. coolest
  3. bigOh7
  4. recursionMystery7
  5. mergeDigitPairs
  6. canPack
  7. list nodes
• practice midterm #8 | key (based on Spring 2015 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. collectionMystery8
  2. wordChain
  3. bigOh8
  4. recursionMystery8
  5. collapseSequences
  6. largestSum
  7. list nodes
• practice midterm #9 | key (based on Autumn 2015 midterm)

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameterMystery9
  2. collectionMystery9
  3. areaCodes
  4. bigOh9
  5. recursionMystery9
  6. replaceAll
  7. phoneWords
  8. list nodes
• More practice problems can be found in the textbook and in your section handouts.

Rules and Information:

• The exam is to be completed individually and without any assistance from a partner or other students.
• The exam is open-book for the Programming Abstractions in C++ textbook, or any other relevant textbooks you want to bring. You can bring the current edition of the book, or the previous ring-bound "course reader" edition, but not a digital copy and not a printout of the book on loose paper.
• The exam is closed-notes and closed for all other resources. You may not bring or use any other printed materials such as handouts, slides, or practice exams. (A "syntax reference sheet" of necessary syntax will be given to you at the exam.) You may not use any computing devices of any kind including calculators, cell phones, music players, iPad/Kindles, or other electronic devices. Please do not have any of these devices out nor use any of them during the exam.
• Unless a question specifically mentions otherwise, your code you write will be graded purely on external correctness (proper behavior and output) and not on internal correctness (style). So, for example, redundancy or lack of comments will not reduce your score.
• You don't need to write any #include statements in your exam code.
• Please do not abbreviate any code on the exam. Abbreviated code will be ignored during grading.
• Unless otherwise specified, it is fine to write helper functions to implement the required behavior.
• Please be quiet during the exam. If you have a question or need, please quietly exit the room and a nearby SL or TA will assist you.
• Any corrections or clarifications to the exam will be written at the front of the room.
• Please follow the Stanford Honor Code during the exam. Work on the exam alone and submit only your own work. Please also take action to prevent any inappropriate activity conducted by others, such as speaking to the person and asking them to stop, or reporting the activity to the instructor.
• When you have finished the exam, please leave the room quietly and bring your exam to the instructor and SLs.

Topics to Study:

The actual midterm exam will have roughly 8-10 total problems. Those problems will be selected from the following categories. For each category, you may be asked to read code (look at a piece of existing code and answer questions about it, such as writing its output), and/or write code (write a piece of code such as a function or short program that solves a problem about that topic).

• C++ basics: console input/output; strings, streams (file I/O), functions; passing parameters by value and by reference; return
• using ADTs: the collections from the Stanford C++ library, such as Vector, Grid, Stack, Queue, Set, Map, HashSet, HashMap, or Lexicon; understanding tradeoffs between various data structures
• algorithm analysis / Big-Oh: look at a given piece of code and answer questions about its runtime complexity, and/or write a piece of code that solves a problem within a given Big-Oh limit
• recursion: look at a piece of recursive code and write its output, and/or write a function that uses recursion to solve a problem
• backtracking: write a function that uses recursive backtracking to solve a problem
• pointers: write lines of code that use pointers, and/or look at a piece of pointer code and answer questions about it (including short chains of linked nodes)

• The following topics are guaranteed NOT to be required to solve any problem on the midterm:
  • complex output formatting with the iomanip library (e.g. setw, setprecision)
  • searching and sorting algorithms
  • drawing fractals
  • the GWindow class or any other code related to graphical user interfaces (GUIs)
  • arrays
  • priority queues and heaps
  • creating your own classes of objects
  • writing C++ template classes
  • operator overloading
  • anything else not explicitly covered in lecture or homework
  • any material that is only covered in the "Overflow" slides at the end of various lecture slide decks
  • any material covered past the end of week 5 of the course (material from weeks 1-5 inclusive will be tested on the exam)

Here is a handout created by a past CS 106B instructor with her advice about how to study for, and take, a CS 106B exam. Note that not all of the information and policies in this handout are correct for the current quarter; for example, in Julie's quarter the exam was open-notes, but the exam this quarter is not.

• Exam Strategies (by Julie Zelenski)