Exam 1 is Wed Oct 14. It will cover all material from Day 1 up to and including Day 15. The exam will be during normal class time in our same room. The exam will be written, no notes, no calculator, just pencil/pen/eraser and paper. There should be around 5 to 6 problems on the exam.

Answers

Sample Questions

• Write a fragment of C++ code that creates an array of 42 integers and puts the numbers 0, 10, 20, ... in the components of the array.

• Draw a picture of memory after these statements:

    int *m = new int[2];
    m[0] = 0;
    m[1] = 1;
    int *p = m;
    p[0] = 4;
    p[0] = 5;

• Consider the ArrayStack implementation which stores properties n, array_size, and arr. Write pseudocode for a method triple_capacity which triples the size of the array but keeps the same items inside the list.

• Here is code to reverse the elements in an ArrayStack with properties n, array_size, and arr. First, explain why the code actually works, perhaps drawing a diragram. Second, give the big-O time for the execution of this method.

void reverse() {
    for (int i = 0; i < n/2; i++) {
        T temp = arr[i];
        arr[i] = arr[n-1-i];
        arr[n-1-i] = temp;
    }
}

• Similar problems to the above, but using ArrayDeques, DualArrayDeques, or RootishArrayStacks instead of ArrayStacks.

• What are the steps to inserting a new item at the head of a singly linked list? Use one short English sentence for each step.

• Write pseudocode for the following method on singly linked lists of integers: count_equal is a method with one parameter needle and returns the number of occurrences needle appears as a value inside the linked list. The list itself is unchanged. What is the big-O running time of your method?

• Compare the worst-case big-O time for these two methods: The remove method for the ArrayStack and the remove method for the DoublyLinkedList. What about the amortized big-O time for the two methods?