## Data Structures - C++

### Topics for the Final Exam

For all of these topics you may get a theoretical question or an impletation exercise
• Recursion
• Sorting Algorithms
*Heap Sort
*Quick Sort
Merge Sort
• *Basic Linked List
• *Fifo Linked List
• *Lifo Linked List
• *Heap Linked List
• *Binary Tree Linked List
• *Basic Sorted Linked List
• *Array Implementation Fifo
• *Array Implementation Lifo
• *Array Implementation Heap
• Array Implementation Binary Tree
• Multi-Node Trees
• *Red Black Trees (Theory)
• *Virtual Functions
• *Virtual Classes (Abstract Classes)
• *Inheritance

## Lab in Advanced - C++

### Topics for the Final Exam

For all of these topics you may get a theoretical question or an impletation exercise
• *Template Classes
• *Template Functions
• *Binary Tree using Templates
• *Inheritance
• *Virtual Functions
• Bitwise Operations
• *Exception Handling
• The String Class

### Possible Programming questions:

#### Data structures

• Write the up-heap function for a LL heap with parent pointers.
• Write the down-heap function for a LL heap with parent pointers.
• Write the up-heap function for an array heap.
• Write the down-heap function for an array heap.
• Write a function which given the desired horizontal row in a LL Binary tree, will print that row from left to write.
• Write a recursive function to in order print a LL BST.
• Write a full implementation of a FIFO in an array of size 10. If more than 10 elements are in the FIFO at any one time the push function should fail.
• Write a full implementation of a LIFO in an array of size 10. If more than 10 elements are in the FIFO at any one time the push function should fail.
• write a funtion to insert elements to a sorted linked list with a next and previous pointer
• write the quick sort algorithm to sort a linked list of nodes.
• Use a heap to sort an array of floats
• Create a linked list containing objects of type cat and dog which inherit from a class animal
• Write a linked list class called fifolifo with 3 functions, push, lifopop, fifopop;
• Show in code how you can create a fifo using a preexistent lifo class.

#### C++ Workshop

• Given a class to store a Mixed Fraction, over the +,=,-,==,<<, >>, /, * , ++ , --, > , < , >= operators for two mixed fractions, for a mixed fraction and an int, and for an int and a mixed fraction, where applicable.
• write a template for a quicksort function so that I can sort any type of array
• Write a multiply function that checks the size of the multiplicand and the multiplier (the integer parameters) and throws an exception if the predicted result will be too large to hold in an int
• create a class that can only be instantiated once. Any attempt to create more than once instance will throw and exception.
• Create a base class and a derived class such that a base class pointer to a derived class object will call the "print" function in the derived class.
• create a class that cannot be instatiated but which has a function that prints "hello world". Call this function in the main function.
• create a memory leak of 400 bytes.
• write a copy constuctor for the class student . Student has the following attributes: 1. char * name; 2. int IDNumber; 3. float GPA;

### Theory questions - Advanced C++

1. What is the syntax for calling a static function?
2. Give an example of when a copy constructor is required.
3. If a function only returns a single integer (indicating success or failure of that
function) How can you in old style C still effectively return other information?
4. How does C++ address this same issue?
5. Why must you use the reference parameter when defining a copy constructor?
6. What is the difference between the implementation of the assignment operator and the copy constructor, assuming you write both for you class?
7. List the ways the copy constructor can be called (both explicitly and implicitly).
8. When do you need to run the delete command explicitly?
9. When do you need the write a destructor function?
10. What does the default copy constructor do? What does it not do?
11. What are the various methodologies for editing a file (to store and update data)? Give Three.
12. What are their pros and cons of each method?
13. What is the difference between protected and private?
14. What is the difference between a virtual function and a regular function?
15. What are some advantages of using a purely virtual function as opposed to a virtual one? Disadvantages?
16. How in code do you create a Pure Virtual function?
17. What are the advantages and disadvantages of using a template class to create a linked list versus using an inheriting parent class?
18. When do we need to overload the assignment operator?
19. Can a template class inherit from a template class? Why might you want to do this as opposed to just inheriting from a class?
20. On what can you use the -> operator?
21. Can a function be static and virtual?
22. What is a static member of a class?
23. What is a const variable?
24. What is the difference between an array name and a pointer?
25. What does making a function a "friend" do?
26. In operator overloading, when do you need to use "friendship"?
27. Why should parameters passed by reference be defined as const as opposed to one passed by value?
28. How do you explicitly run the base class constructor from the derived class constructor?
29. What is the syntax for initializing a static member?
30. Can child classes initialize a const static variable in the parent?
31. If a child changes the value of a static member in the parent class, will instances of the parent class see the change?
32. If a function is virtual in the parent but not in the child will a parent pointer pointing to a grandchild run the parent function, the child function , or the grandchild function? Explain.
33. What is the difference between a deep and a shallow copy? Why is this significant?
34. Why is exception handling better than returning a special value to indicate failure? (two reasons)
35. What result would be achieved by making the constructor function of a parent class protected?
36. What does the word const in the code "int function( int a ) const" do?
37. What is an initialization list? Where is it used?
38. Can you over load a static function with non-static version?

### Theory questions - Data Structures

1. What is a divide and conquer algorithm? Why is it efficient?
2. What is a sentinel value? How does it assist in creating a bounded array?
3. What are the advantages and disadvantages of using an array to implement a heap?
4. Why is a heap better suited to be implemented using an array than a binary search tree is?
5. What is the rule of least access (least privilege)?
6. When creating a heterogeneous linked list, what different designs might you use?
What class structures could you use?
7. Give an example of a type of application for which a Fifo is needed.
8. Give an example of a type of application for which a Lifo is needed.
9. Give an example of a type of application for which a Binary Search Tree is needed.
10. How do you determine the efficiency of an algorithm (Big O notation)? What do you consider and what do you ignore? Why?
11. For an algorithm that is O(n log n) does it become more or less efficient as the number of variables being worked on increases?
12. What is the worst case scenario for a binary search tree? Explain.
13. What is a balanced tree?
14. When do 2-3-4 trees increase their number of rows?
15. In terms of rows, which is more balanced, a heap or a binary red/black tree?
16. Is a binary red/black tree more or less balanced than true 2-3-4 tree? Explain.
17. What is the inherent difficulty in implementing a Fifo Array versus a Lifo Array?

### Theory questions - Object Oriented Programming

2. When overloading an operator, what considerations go into deciding what the function should do?
3. How do classes enable you to solve the problem of functions only returning one
variable? (give two ways)
4. Why are functions in classes also called methods?
5. What is data abstraction?
6. How is data encapsulation achieved?
7. What is polymorphism and why is it desirable?
8. Why are classes default private and structs default public?
9. What is private inheritance? When might you use it?
10. When might using a private constructor function be advisable? What design pattern can it facilitate?
11. What is a "has a" relation? How do you implement it in C++?
12. What is an "is a" relation? How do you implement it in C++?
13. How should you decide which to use?

### Theory questions - Principles of Programming Languages

1. Why were classes invented?
2. Why was inheritance invented? What design/software goals does it facilitate?