Computer Science 153

Introduction to Data Structures

Question Pool for Final Exam

Up to 25% of the questions on the Final Exam will come from exams 1, 2 and 3

One-third of the exam will involve writing the C++ member functions listed at the end of the pool

Chapter 11

A heap is a binary tree where the entries can be compared using the usual six comparison operations (that form a total order semantics). Write the two rules that the binary tree must follow in order for the structure to actually be a heap.

Give two different reasons to explain why the following binary tree is not a heap: 
                91
               /  \
             77    46
            /  \     \
          68    81    11

Draw a new heap that is created by inserting 82 into the following heap:

           910
          /  \
        77    66
       /  \  /  \
     68    1 3  11

Draw a new heap that is created by removing 77 from the following heap:

         910
         /  \
        77   66
       /  \  / \
      68  1  3 11

Suppose that you are performing a reheapification downward. Write a precise condition that describes the situation that causes the reheapification to stop.
Suppose that you are performing a reheapification upward. Write a precise condition that describes the situation that causes the reheapification to stop.
What feature of heaps allows them to be efficiently implemented using a partially filled array?

If a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?

Select the true statement about the worst-case time for operations on heaps.

Suppose that we have implemented a priority queue by storing the items in a heap (using an array for the heap items). We are now executing a reheapification upward and the out-of-place node is at data[i] with priority given by data[i].priority. Which of the following boolean expressions is true to indicate that the reheapification is not yet done.

Suppose that we have implemented a priority queue by storing the items in a heap. We are now executing a reheapification downward and the out-of-place node has priority of 42. The node's parent has a priority of 72, the left child has priority 52 and the node's right child has priority 62. Which statement best describes the status of the reheapification.

Which formula is the best approximation for the depth of a heap with n nodes?

₂

₁₀

Suppose you run a O(log n) algorithm with an input size of 1000 and the algorithm requires 110 operations. When you double the input size to 2000, the algorithm now requires 120 operations. What is your best guess for the number of operations required when you again double the input size to 4000?

Tree algorithms typically run in time O(d) . What is d?

Chapter 12
Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15. Suppose that we are doing a serial search for an element.

Circle any elements that will be found by examining two or fewer numbers from the array.

Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose that we are doing a binary search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.
Implement the body of the following function using a binary search of the array. You do not need to check the precondition. All your local variables must be size_t variables.

    bool has_42(const int data[ ], size_t n) 
    // Precondition: The elements data[0]...data[n-1] are sorted from smallest 
    // to largest. The value of n might be zero (indicating an empty array). 
    // Postcondition: A true return value indicates that the number 42 appears in 
    // data[0]...data[n-1]. A false return value indicates that 42 doesn't appear.

Draw a hash table with open addressing and a size of 9. Use the hash function "k % 9". Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order).
Suppose you are building an open address hash table with double hashing. The hash table capacity is n, so that the valid hash table indexes range from 0 to n-1. Fill in the blanks:
- In order to ensure that every array position is examined, the value returned by the second hash function must be ________________________ with respect to n.
- One way to ensure this good behavior is to make n be _______________,
- and have the return value of the second hash function range from _________ to _________ (including the end points)

You are writing code for the remove member function of a chained hash table. Fill in the blanks in this pseudocode with the two missing statements. You may use pseudocode yourself, or write actual C++ code:

    void Table::remove(int key) 
    { 
        Node * cursor; 
        size_t i; 
        1. i = hash(key); 
        2. Make cursor point to the node that contains an item with the given key 
           (or set it to NULL if there is no such node). 
        3. if (cursor != NULL) 
           { 
              3a. _____________________________________________________________ 
              3b. _____________________________________________________________ 
           }
    }

Draw a hash table with chaining and a size of 9. Use the hash function "k % 9" to insert the keys 5, 29, 20, 0, and 18 into your table.

struct RecordType      
{          
  int key;
  ... other stuff may also appear here
  ...
};

    size_t hash(int key) 
    { 
        return (key % CAPACITY); 
    }

Complete the implementation of the following function. There is no need to check the precondition, but your code must be as efficient as possible.

    bool key_occurs(const RecordType data[ ], int search_key) 
    // Precondition: data[0]...data[CAPACITY-1] is an open address hash table 
    // as described above. 
    // Postcondition: If search_key occurs as a key of a record in the table, 
    // then the function returns true; otherwise the function returns false.

Suppose that an open-address hash table has a capacity of 811 and it contains 81 elements. What is the table's load factor? (An approximation is fine.)

I plan to put 1000 items in a hash table, and I want the average number of accesses in a successful search to be about 2.0.
About how big should the array be if I use open addressing with linear probing? NOTE: For a load factor of A, the average number of accesses is generally ½(1+1/(1-A)).
About how big should the array be if I use chained hashing? NOTE: For a load factor of A, the average number of accesses is generally (1+A/2).
What is the worst-case time for serial search finding a single item in an array?

What is the worst-case time for binary search finding a single item in an array?

What additional requirement is placed on an array, so that binary search may be used to locate an entry?

What is the best definition of a collision in a hash table?

In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference?

What kind of initialization needs to be done for an open-address hash table?

What kind of initialization needs to be done for a chained hash table?

A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

Chapter 13

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Draw this array after the FIRST iteration of the large loop in a selection sort (sorting from smallest to largest).

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!
Suppose that you are writing a program that has the usual selectionsort function available:

void selectionsort(int data[ ], size_t n);

Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses selectionsort to sort all of x; the second call uses selectionsort to sort x[3]..x[9].
Describe a case where quicksort will result in quadratic behavior.

Here is an array which has just been partitioned by the first step of quicksort 3, 0, 2, 4, 5, 8, 7, 6, 9

Which of these elements could be the pivot? (There may be more than one possibility!)

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4. Suppose we partition this array using quicksort's partition function and using 5 for the pivot.

Draw the resulting array after the partition finishes.

Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Draw this array after the TWO recursive calls of merge sort are completed, and before the final merge step has occurred.
Fill in the following table for the times to sort an array of n items. Use only big-O notation, and do not have any extraneous constants in your expressions.

	Average Case	Worst Case
Binary Search of a sorted array
Insertion sort
Merge sort
Quick sort without "median of three" pivot selection
Quick sort with "median of three" pivot selection
Selection sort
Heap sort

Suppose that you are writing a program that has these two functions available:

    int compare_ints(const void * p1, const void * p2); 
    // Precondition: p1 and p2 are really pointers to integers. 
    // Postcondition: The return value is: 
    //   (a) negative if *p1 < *p2 
    //   (b) zero if *p1 == *p2 
    //   (c) positive if *p1 > *p2 

    void qsort( 
        void * base, 
        size_t n, 
        size_t bytes, 
        int compar(const void *, const void *) 
    ); 
    // Same specification as the standard library qsort function.

Your program also has an integer array called x, with 10 elements. Write two function calls: The first call uses qsort to sort all of x; the second call uses qsort to sort x[3]..x[9].
In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?

Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

         1  2  3  4  5  0  6  7  8  9

Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

         2  4  5  7  8  1  3  6

Which statement is correct? (Note: Our selectionsort picks largest items first.)

When is insertionsort a good choice for sorting an array?

What is the worst-case time for mergesort to sort an array of n elements?

What is the worst-case time for quicksort to sort an array of n elements?

Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

What is the worst-case time for heapsort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
E. None of these.

Chapter 14
Describe one purpose of a member initialization list for a derived class.
Describe the difference between a public base class and a private base class.
Suppose that a derived class has a private base class. How is it possible to to make some of the inherited members become public?

Throughout this section A is a class and B is a new class derived from A. Also, we have these variables

    A a; 
    B b; 
    B b1; 
    B b2;

What C++ syntax is used to declare that a class B is derived from class A?

If a class B is derived from A, then which of the following terms describes A?

Consider the assignment statement a=b; (with the variable declarations at the top of this section). Which answer is true?

Consider the assignment statement b=a; (with the variable declarations at the top of this section). Which answer is true?

What is the term used to describe the situation when a derived class provides a function already provided in the base class?

Consider the declarations at the top of this section. Suppose there are two functions: f has an argument of type A and g has an argument of type B. Which statement is correct?

Consider the declarations at the top of this section. Suppose there are two functions: f has an argument of type A and g has an argument of type B. Which statement is correct?

Suppose you were going to quickly implement a Stack class. What class would be the best base class?

Suppose you were going to quickly implement a Stack class as a derived class. Why would it be likely that the base class would be a private base class?

You will be given all of the following class definitions on the exam. Be prepared to write any of the member functions defined within the classes. In the case of class Stack, write the requested member function without using inheritance.

struct Node
{    Node * Next;
      Node * Prev;
      int Data;
};

class Stack
{public:
    Stack();
    ~Stack();
    void Push(int);
    int Pop();
    int Peek();
    bool Empty();
    bool Full();
private:
    Node * Top;
};

class List   //Forward-Backward List
{public:
    List();
    ~List();
    InsertHead(int);
    InsertTail(int);
    int RemoveHead(); //and return the value of
    int RemoveTail();     //and return the value of
    int GetCurrent(); //return the value pointed to by Current
    bool Find(int);   //if successful, leave Current pointing to the
                            // Node found
private:
    Node * Head;
    Node * Tail;
    Node * Current;
};

class BST    //Binary Search Tree 
  { 
     public: 
     BST(); 
     ~BST(); 
     void Insert(BNode *); 
     bool Find(BNode *);
     void PrintInOrder();
    private:
     void HelpPrintInOrder(BNode *);            
     BNode * Root; 
             };

struct BNode // An abstract Node
{
    virtual bool operator<(const BNode &)=0;
    virtual bool operator==(const BNode &)=0;
    BNode * LC;
    BNode * RC;
};

struct MyData : public BNode
{
    virtual bool operator<(const BNode & arg);
    virtual bool operator==(const BNode & arg);
    int Data;

};