COSC 2415 Exam 3 Review

COSC 2415 - Data Structures

Bob Comer, Professor of Computer Studies

Exam 3 Review Exercises

I recommend that you do the following exercises as you study the chapters in the textbook. Answers to the Quick Quiz exercises are in Appendix F at the back of your textbook. Click here to review answers to questions.

The exam will emphasize both C++ coding and concepts. Be sure to review the Summary (Chapter Notes, Programming Pointers, and ADT Tips) at the end of each chapter. Following is a sample question over concepts.

Give a brief description of pass-by-value and pass-by-reference. In what situations should pass-by-value be used? In what situations should pass-by-reference be used?

Chapter 10 - ADT Implementations: Recursion, Algorithm Analysis, and Standard Algorithms

Quick Quiz 10.1: 1-7.

Section 10.2 Examples of Recursion - this section will not be covered on the exam.

Quick Quiz 10.4: 1-5, 8-11.

Quick Quiz 10.5: 1-5.

Section 10.6 Proving Algorithms - this section will not be covered on the exam.

Other Questions

1. Write a recursive function that returns the number of digits in a nonnegative integer. Hint: you can use the integer division and integer remainder (mod) operators (/ and %) to pick apart an integer.

2. Write a recursive function called printReverse( ) that displays a nonnegative integer's digits in reverse order.

Chapter 11 - More Linking Up with Linked Lists

Quick Quiz 11.1: 1-5.

Section 11.2 Linked Implementations of Sparse Polynomials - this section will not be covered on the exam.

Section 11.3 Doubly-linked Lists and the Standard C++ List - you only need to read pages 602-611.

Section 11.4 Case Study Large Integer - this section will not be covered on the exam.

Section 11.5 Other Multiply-Linked Lists - this section will not be covered on the exam.

Other Questions

1. What advantage do doubly-linked lists (as discussed in section 11.3) have over singly-linked lists?

Chapter 12 - Searching: Binary Search Trees and Hash Tables

Quick Quiz 12.2: 1-11.

Quick Quiz 12.3: 1-6.

Quick Quiz 12.4: 1-6.

Section 12.5 Case Study Validating Logins - this section will not be covered on the exam.

Section 12.6 Threaded BSTs - this section will not be covered on the exam.

Quick Quiz 12.7: 1-3, 6, 7, 9.

Other Questions

Questions 1-4 use the following array.

      +--------------------------------------------+
      |  3 |  7 | 13 | 17 | 23 | 29 | 31 | 37 | 43 |
      +--------------------------------------------+
        [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]

For Questions 1-4, give the indicies of the elements of the array in the order that they are examined during a binary search for the listed value.

1. 31

2. 17

3. 25

4. 2

5. Rewrite the array-based linear search from the textbook to make it more efficient for ordered lists.

Be sure to review the Hash Table code in the Example Programs section of the class web site.

Chapter 13 - Sorting

You should be familiar with and ready to discuss the following array-based sort algorithms:

Selection sort (called simple Selction sort in the book)
Insertion sort (called linear insertion sort in the book)
Heapsort
Quicksort
Mergesort (called binary mergesort in the book)

Quick Quiz 13.1: 1-7.

Quick Quiz 13.2: 1-4.

Quick Quiz 13.3: 1-7.

Quick Quiz 13.4: 1-4.

Section 13.5 Radix Sort - this section will not be covered on the exam.

Other Questions

1. Interpret the array below as a binary tree as described in Section 13.2.

      +-------------------------------------------------+
      |  5 | 10 |  3 |  1 |  6 |  2 |  4 |  8 |  7 |  9 |
      +-------------------------------------------------+
        [1]  [2]  3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]

Does this array represent a binary tree that is a heap? If not, use the heapify algorithm to convert it to a heap and show the resulting array.

2. The following values are inserted into an empty heap in the order listed. Draw the array that represents the resulting heap.
7, 1, 6, 5, 4, 2, 3

3. Describe how quicksort works in a few sentences.

4. Given that the array below is to be sorted using quicksort, show what the array looks like after a call to function split( ) where the element at index 1 is used as the pivot value.

      +-------------------------------------------------+
      | 45 | 20 | 50 | 30 | 80 | 10 | 60 | 70 | 40 | 90 |
      +-------------------------------------------------+
        [1]  [2]  3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]

5. Describe how binary mergesort works in a few sentences.

Chapter 14 - OOP and ADTs

Quick Quiz 14.1: 1-5.

Sections 14.2 - 14.6 will not be covered on the exam.

Chapter 15 - Trees - not covered on the exam

Return to Data Structures Home Page