COSC 2415 Exam 3 Review

COSC 2415 - Data Structures

Bob Comer, Professor of Computer Studies

Exam 3 Review Exercises

Points on the exam will be distributed roughly as follows:

Ch. 10 - Recursion, Algorithm Analysis, and Standard Algorithms	15%
Ch. 11 - More Linking Up with Linked Lists	5%
Ch. 12 - Searching: Binary Search Trees and Hash Tables	40%
Ch. 13 - Sorting	35%
Ch. 14 - OOP and ADTs	5%

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.

3. Write a function to return the sum of the elements in an array. The function parameters should be the array and the number of elements in the array. Your function must be recursive (no loops).

4. Write a function to return the sum of the integers stored in a linked-list given:

     class Node
     {
     public:
        int data;
        Node *next;
     };

The function should have one parameter - a pointer to the first node in the linked list (NULL if the list is empty). Your function must be recursive (no loops).

5. Give the best-case and worst-case execution times for the following searches in Big-O notation.

a. Linear search

b. Binary search

6. What is the worst-case execution time in Big-O notation for the simple selection sort? Explain your answer.

7. The worst-case execution time for algorithm A is O(log n). The worst-case execution time for algorithm B is O(n). If algorithm A and algorithm B are run on the same input, will the execution time for algorithm A always be faster than algorithm B?

8. For the following code segment, what is the worst-case computing time as a function of n (the problem size): O(1), O(log n), O(n), O(n²) or O(n³)?

    // Matrix addition
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            c[i][j] = a[i][j] + b[i][j];

9. For the following code segment, what is the worst-case computing time as a function of n (the problem size): O(1), O(log n), O(n), O(n²) or O(n³)?

    for (int i=0; i < n; i++)
        for (int j = 0; j < 12; j++)
            a[i] *= (1 + 0.01);

10. For the following code segment, what is the worst-case computing time as a function of n (the problem size): O(1), O(log n), O(n), O(n²) or O(n³)?

    //Matrix multiplication
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < n; k++)
                c[i][j] += a[i][k] * b[k][j]
        }
    }

11. For the following code segment, what is the worst-case computing time as a function of n (the problem size): O(1), O(log n), O(n), O(n²) or O(n³)?

    k = n;
    while (k >= 1)
    {
        k /= 2;
    }

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.

6. What is the worst-case time (in Big-O notation) to insert a value in a binary search tree (BST)? What is the worst-case time (in Big-O notation) to insert a value in a balanced BST?

7. What is the worst-case time (in Big-O notation) to find a value in a binary search tree (BST)?

What is the worst-case time (in Big-O notation) to find an item in a balanced BST?

8. Be sure to review how hash tables work. You may want to review the hash table code from programming assignment 7.

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.

6. What are the worst-case execution times (in Big-O notation) for each of the following search algorithms:

a. bubble sort

b. linear insertion sort

c. heap sort

d. binary merge sort

7. What are the average-case and worst-case execution times (in Big-O notation) for the quick sort algorithm given in the textbook (using the first element as the pivot).

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