Exam 1


Data Structures

Fall Semester 1997

Tuesday, October 7, 1997


  1. List the steps of the software lifecycle and give a one to two sentence description of each.

  2. In class, we discussed approaches to software design: Top-Down Design (TDD) and Object-Oriented Design (OOD).

  3. The function void removeBlanks(char word[]) takes as input a C++ string and compresses any whitespace characters out of it. For example:

    input: word[] = "Hi Bob good to see you"

    output: word[] = "HiBobgoodtoseeyou"

  4. The function void computeParity(int sequence[], int n) takes as input an integer array of length n and computes the parity of each entry in the array. The element in position k is replaced by 0 if sequence[k] is even and by 1 if sequence[k] is odd. For example, if sequence[] = {1 2 4 7 -1} before calling computeParity, then afterwards sequence[] = {1 0 0 1 1}.

    Write a short test plan for computeParity. Group your tests according to the kind of situation that they address.

  5. Many applications require the ability to work with times. Suppose that we need a Time class for a piece of scheduling software. Clients of Time would want to be able to ask questions such as "If Aldi closes at 7:00 PM, then how much time left do I have to do my shopping?"

  6. Answer the following questions about the linearSearch and unknownSearch algorithms from Laboratory Exercise 15 in Roberge. Explain your answers with references to the code wherever possible.

  7. What is the output of the mystery program? For partial credit in the case of an incorrect answer, be sure to show as much of your work, such as the changing values of variables, as you can.

  8. MergeSort is an algorithm that sorts an array with O(nlogn) worst case performance. Like QuickSort, it consists of two procedures:

    For now, let's assume that someone else has written the merge procedure for us and that its specification is:

    void merge(int a[], int first, int middle, int last)

    middle is the index of the last integer in the left sub-array, and middle + 1 is the first integer in the right sub-array.

    Write a recursive function named merge_sort that satisfies the following specification:

    As with QuickSort, the base case in MergeSort will be an array of size 0 or 1, that is,
    when first >= last.

Eugene Wallingford ==== wallingf@cs.uni.edu ==== November 19, 1997