CIS 250 Final Review

This review doesn't necessarily have all the topics covered on the final exam, but it does cover most of what will be on the exam. If you know this material, then you should be set.

Show all answers Hide all answers

Objects

What is function overloading? Answer Overloading is writing a function with the same name as another function, but a different parameter list.
What is function overriding? Answer Overriding is writing a function with the same name and parameter list as an inherited function, thus replacing the inherited function.
Describe what public, private, and protected access are. Answer
1. private: only members of the same class have access
2. protected: only members of the same class and subclasses have access
3. public: there are no restrictions on what code has access
What is the difference between a struct and a class? Answer A struct has default public access to its members. A class has default private access to its members.
Describe inheritance. Answer Inheritance is when one class extends another. The subclass (derived class) is the class that extends the superclass (base class). The subclass inherits (and therefore has) the data and methods of the superclass. Even though the subclass contains the data and methods, it might not be able to access them since the superclass may have made some of those members private access.
Describe composition. Answer Composition is when an object has other objects as data members. This is very common. You have probably written many objects that contain either an instance or static String variable. That would be a simple example of composition.
What is the this pointer? Answer The this pointer is a reference to an object itself. Every object has a this pointer which is automatically passed to instance functions/methods - but obviously not to static functions/methods since static functions/methods exist independently of an object.

Data structures

Add 1 and 2 to an empty stack and then remove one item. What is left on the stack? Answer 1
Add 1 and 2 to an empty queue and then remove one item. What is left on the queue? Answer 2
Add 1 and 2 to an empty linked list. Draw a diagram of the resulting linked list? Answer head -> 1 -> 2 -> null or
head -> 2 -> 1 -> null
List common operations on a binary tree in increasing order of difficulty. Answer
1. find minimum or maximum value in the tree (about the same as traverse)
2. traversal (about the same as finding minimum or maximum)
3. find/search
4. insert
5. delete
Add 5, 7, 1, 3, 2, 4, 0, 9 to an empty binary search tree. Show what the tree looks like. Answer
```
      5
     / \
    1   7
   / \   \
  0   3   9
     / \
    2   4
```
Add 5, 7, 1, 3, 2, 4, 0, 9 to an empty binary search tree. Show the inorder traversal of that tree. Answer 0, 1, 2, 3, 4, 5, 7, 9
Add 5, 7, 1, 3, 2, 4, 0, 9 to an empty binary search tree. Show the preorder traversal of that tree. Answer 5, 1, 0, 3, 2, 4, 7, 9
Add 5, 7, 1, 3, 2, 4, 0, 9 to an empty binary search tree. Show the postorder traversal of that tree. Answer 0, 2, 4, 3, 1, 9, 7, 5
Where is the minimum value located in a binary search tree? Answer As far to the left from the root as possible.
Where is the maximum value located in a binary search tree? Answer As far to the right from the root as possible.
If you deleted the 1 in the tree used above, which node would take its place? Answer 2 (the successor), or 0 (the predecessor)
If you deleted the 7 in the tree used above, which node would take its place? Answer 9 (the only child)
If you deleted the 2 in the tree used above, which node would take its place? Answer none
Add 5, 7, 1, 3, 2, 4 to an empty min heap. Show what the resulting heap looks like. Answer
```
         1
        / \
      /     \
     2       4
    / \     /
   7   3   5
```
Add 5, 7, 1, 3, 2, 4 to an empty max heap. Show what the resulting heap looks like. Answer
```
         7
        / \
      /     \
     5       4
    / \     /
   3   2   1
```
Draw a weighted directed graph with the following edges:
A to B (one way, weight 5)
A to C (both ways, weight 4)
C to D (both ways, weight 3)
D to B (one way, weight 2) Answer
```
      5
   A --> B
   |     ^
 4 |     | 2
   |     |
   C --- D
      3
```
Given the weighted directed graph above, what are the neighbors of D? Answer B, C
Given the weighted directed graph above, what are the neighbors of B? Answer There are none.
Given the weighted directed graph above, what are the neighbors of A? Answer B, C
Describe the mimimum spanning tree of a weighted undirected graph with the following edges:
A to B (weight 1)
A to C (weight 3)
B to C (weight 1)
B to D (weight 3)
C to D (weight 1) Answer It would consist of the edges A-B, B-C, C-D. A real test question would include more edges and vertices.
Describe the shortest path from A to D of a weighted undirected graph with the following edges:
A to B (weight 1)
A to C (weight 3)
B to C (weight 1)
B to D (weight 3)
C to D (weight 1) Answer It would be the path from A to B to C to D. A real test question would include more edges and vertices.
Write down the result of a breadth-first search of an undirected graph with these edges:
A-B, B-D, B-E, A-C, C-F, C-G
Answer One possibility: A B C D E F G
Write down the result of a depth-first search of an undirected graph with these edges:
A-B, B-D, B-E, A-C, C-F, C-G
Answer One possibility: A C G F B D E
What are some advantages of using a linked list versus using an array? Answer
1. A linked list can grow as needed, so you don't need to know ahead of time how many items will be in the list.
2. It is easy and efficient to insert items into the middle of a linked list.
3. It is easy and efficient to delete items from the middle of a linked list.
What are some disadvantages of using a linked list versus using an array? Answer
1. Accessing a specific position in an array is much more efficient than finding an item in a linked list.
2. Linked lists have more overhead than arrays.

Programming

If you are given a programming task similar in some respects to the BankAccount assignment, how should you program it? Answer Correctly.