The exam will be on

Thursday, 14 April 2005, 9:30 - 10:45 am.

Nothing directly from the Weiss book that is not also discussed below. (But the Weiss book might help your understanding.)

Strings:

1. String Examples Creating strings, accessing and printing chars from them
2. String Basics (less emphasis on this material)
3. String Functions Examples of functions that work with strings

4. Print Array of Strings
5. Rec 7: Array of Strings : command line arguments (skip self-reproducing programs)
6. Array of Strings as Parameter (less emphasis)

7. 2d-arrays
8. Rec 8: Pascal's Triangle : 2-dimensional arrays

9. Structs Overview
10. Simple "bare" structs seldom used
11. Rec 9: Structs and RPN Using bare structs, and an array of structs
12. Java vs. C Using pointers (or references) to structs
13. Structs as parameters Examples of both "bare" structs and pointers to structs

14. Linked List Stack Use of self-referential structs
15. Rec 10: Linked list queue

16. File Input/Output
17. Rec 11: Merging Files

1. Questions about the way ordinary 2-dimensional arrays in C are laid out in memory. For example, suppose an array is declared int a[6][5];.
   1. Give the formula for accessing the array element int a[i][j]; in simulated linear storage.
   2. The array reference int a[4][7]; is technically illegal. Why is it illegal? This reference will access a well-defined location in the array because of the way C handles 2-dimensional arrays. How will C try to access the location and which location will it be (using array subscripts that are in range)?

2. Questions about "bare" structs:
   1. A "bare" struct is one not defined as a pointer to the object (no stars in the main declaration). Why do we recommend against the use of bare structs?
   2. Does Java support bare structs?
   3. What happens when you return a "bare" struct from a function or have two "bare" structs on either side of an assignment statement?

3. Questions about structs:
   1. Given a struct "tag" declaration (such as that in the program at the start of item 13), how does one do the following. (I might give specific examples to work with in a case like this.)
      1. Allocate a pointer to such a struct (declaration of a local variable on the stack).
      2. Allocate a single (bare) copy of such a struct (declaration of a local variable on the stack).
      3. Set the pointer in i) pointing to the struct in ii) above.
      4. Allocate an array of (bare) copies of such a struct (declaration of an object on the stack).
      5. Allocate such a struct using malloc, returning a pointer to it.
      6. Allocate an array of pointers to such a struct using malloc, and then use malloc to allocate each individual struct.
      7. Initialize an array of such structs using {} notation.

4. Questions about RPN:
   1. Given an example of an RPN string with numbers for operands, show how to use a stack to evaluate it.
   2. Show how to use the "railroad" diagrams to translate an example arithmetic expression (of the type in class) into RPN.

5. Questions about linked lists:
   1. What sort of struct is needed for a linked list?
      Assume you are give such a struct and a pointer to a linked list made up from the struct.
   2. Give code to chase down a linked list, visiting the nodes as you go.
   3. Give recursive code to chase a linked list in reverse, visiting the nodes as you go.
   4. Give code to splice two linked lists together, the second tacked on at the end of the first.
   5. Suppose a pointer p points to a node in a linked list. Give code to delete the next node in line after the given node (unless this is the last node). Why couldn't you in general delete the node that was pointed to?

6. Questions about queues:
   1. Draw a diagram of a queue, showing the front and rear pointers, and the direction of the queue as a linked list.
   2. A queue has the form that is has so that one can insert a new node at the (front or rear?) and delete the node at the (front or rear?) in constant time (time independent of the length of the queue).
   3. There is one other insert or delete operation that one can do with a queue in constant time. What is it?

7. Question about file input/output:
   1. Given code to copy a file from one location to another, as in the first program under item 16 above, rewrite the code so that the actual copying is inside a function.

8. Questions about merging two files:
   1. If you are merging two files without sentinels, say what you do if you come to EOF on the first file and not on the second.
   2. If you are merging two files without sentinels, give the circumstances under which you could come to EOF on both files at the same time. Say what you would do in this case.