Exam 1

810:052

Data Structures

Fall Semester 1997

Tuesday, October 7, 1997

Instructions

• The exam consists of eight questions and two pages of C++ code. Be sure that you have all of these items and that they are all legible.

• Read all questions and their instructions thoroughly before you begin. It is always worth your time to plan ahead!

• You have also been given three blank pages. Use these sheets for your exam answers. Be sure to write your name on each sheet.

• The exam is worth 100 points. Questions 1-2 and 4-7 are worth twelve points each; Questions 3 and 8 are worth 14 points each.

• Keep the exam questions when you are done, for future reference.

• Points will be awarded based on your explicit answers. Partial credit will be given where possible, so show all of your work.

• The exam lasts sixty (60) minutes. It is due one hour after you receive it.

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).

   • Explain two significant similarities between TDD and OOD.

   • Explain two significant differences between TDD and 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"

   • Rewrite this specification as a precondition and a postcondition.

   • Specify an invariant for the primary loop in removeBlanks, either symbolically or with a picture.

   • Using your assertions as a guide, write the function removeBlanks.

   ---

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?"

   • Specify a set of messages to which a useful Time object would respond. Your list should include at least half a dozen, probably more.

   • What private member data might a Time object contain? Your answer may be in English; you do not have to write C++ code.

   ---

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.

   • What is the critical operation in these search operations?

   • What is the run-time efficiency for each in terms of order of magnitude (big-oh notation)?

   • In the lab, timing experiments indicated that one of these algorithms was much faster than the other. Explain the difference.

   ---

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:

   • a recursive procedure that splits the array in half, makes recursive calls to merge-sort the halves, and then calls a merge procedure to put the sorted halves back together, and

   • a merge procedure that takes two sorted sub-arrays as input and modifies the array so it that it is sorted across the full range.

   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:

   • Interface: int merge_sort(int a[], int first, int last)

   • Precondition: a is an array beginning in slot first and ending in slot last

   • Postcondition: a is sorted in ascending order from slot first to slot last

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