Topics for Final Examination
Data Structures
May 3, 2001

The second part of the examination will be in class during the regularly scheduled class at 9:30 on May 3rd.  It will last until 10:50.  The topics that students are responsible for are:

1. Read a line from the keyboard.
2. Write a function that would fill an array with N random values.
3. Declare an array.
4. Declare a file variable.
5. Open a file for output.
6. Close a file.
7. Write N values from an array to a file.
8. Write a generic function that would sort the first N elements of an array using the bubble sort.
9. Be able to give the results of each pass of a bubble sort.
10. Write a generic function that would sort the first N elements of an array using the insert sort.
11. Be able to give the results of each pass of a insert sort.
12. Write a generic function that would sort the first N elements of an array using the quick sort.
13. Be able to hand sort an array using the quick sort.
14. Write a procedure that would obtain from the user the name of an input file, the name of an output file, and the number of elements to be processed.
15. Write a procedure that would read N numbers from an input file into an array.  The parameters of the procedure are the filename, the array, and the number.
16. Write a procedure that would write N numbers from an array to an output file, with 10 numbers per line.  The parameters of the procedure are the filename, the array, and the number.
17. Write a C++ header file as specified by the instructor.
18. Write the implementation of a C++ header file.
19. Write a stack class declaration.
20. Define a stack.
21. Draw a stack after a series of stack operations.
22. Write a stack class declaration.
23. Define a stack.
24. Draw a stack after a series of stack operations
25. Implement each of the stack operations
• constructor & destructor
• pop
• push
• top
• empty
26. Draw diagrams of each stack operation
• pop
• push
27. Draw a picture of the heap after
• a pop operation
• a push operation
• a series of operations
28. Understand post-fix notation
29. Write a program evaluating a file of post-fix expressions
30. Write a program reading numbers from a file and inserting them into a tree
31. Write a program that would time various sort routines.
32. Draw a tree after an insert operation
33. Write a tree class declaration
34. Implement some of the elements of a tree class.
• Recursive insert operation
• Recursive write operations
• Recursive delete operation
• Public operations.