Fall 2025 Final Exam Practice Key

CSCI 1913 – Introduction to Algorithms, Data Structures, and Program Development

Author

Adriana Picoral

1 Array-based lists

  1. Draw an array of size 5, which has the following values appended in the following order: 32, 15, 6, 50
32 15 6  50   
  1. Draw the array from part (a) with value 15 deleted
32 6  50      
  1. Draw the array from part (b) with the value 44 inserted at index 1
32 44 6  50   

2 Linked-list

  1. Draw an empty linked list with a head and a tail references

G head head null null head->null tail tail tail->null

  1. Draw the linked list from part (a) with the following values added in this order: 32, 15, 6, 50

G head head 32 32 head->32 tail tail 50 50 tail->50 15 15 32->15 6 6 15->6 6->50

  1. Draw the linked list from part (b) with the node of value 15 deleted

G head head 32 32 head->32 tail tail 50 50 tail->50 6 6 32->6 6->50

3 Binary Search Tree

  1. Draw a binary search tree which has the following values inserted in the following order: 32, 15, 6, 50, 25, 21, 43, 73, 36, 37, 68, 23, 75, 34

BST 32 32 15 15 32--15 50 50 32--50 6 6 15--6 25 25 15--25 43 43 50--43 73 73 50--73 21 21 25--21 null1 25--null1 null4 21--null4 23 23 21--23 36 36 43--36 null2 43--null2 68 68 73--68 75 75 73--75 34 34 36--34 37 37 36--37

  1. Draw the binary search tree from part (a) with value 25 deleted, and the value 44 inserted

BST 32 32 15 15 32--15 50 50 32--50 6 6 15--6 21 21 15--21 43 43 50--43 73 73 50--73 null4 21--null4 23 23 21--23 36 36 43--36 44 44 43--44 68 68 73--68 75 75 73--75 34 34 36--34 37 37 36--37

  1. Draw the binary search tree from part (b) with value 43 deleted, and the value 29 inserted

BST 32 32 15 15 32--15 50 50 32--50 6 6 15--6 21 21 15--21 44 44 50--44 73 73 50--73 null4 21--null4 23 23 21--23 36 36 44--36 null 44--null 68 68 73--68 75 75 73--75 34 34 36--34 37 37 36--37 null1 23--null1 29 29 23--29

4 Hash Table

Consider an initially empty hash table \(H\) of size 6, designed to store integer keys with linear probing. The hash function is defined as:

\(hash(k) = k \mod length(H)\)

When the load factor (λ) exceeds 0.7, the table size is doubled.

Insert the following sequence of keys in the given order: 12, 18, 21, 2, 26, 17, 34 and show the final hash table configuration.

12       2  26      17 18           21 34     

5 Big-O

Consider the following python code.

def loreum(n):
  lst1 = []
  for i in range(n):
    j = 0
    while j < n:
      lst1.append(i)
      lst1.append(j)
      j *= 2
  set2 = set() # A python set, add is O(1)
  for val in lst1:
    set2.add(val)
  return set2

  1. Identify the Big O notation for this function:

    ▢ a) \(O(1)\)

    ▢ b) \(O(\log n)\)

    ▢ c) \(O(n)\)

    ✅ d) \(O(n \log n)\)

    ▢ e) \(O(n^2)\)

    ▢ f) \(O(n^3)\)

    ▢ g) \(O(n^4)\)

    ▢ h) \(O(2^n)\)

  2. Write a function which given the same argument as loreum will result in the same return result but has a better runtime. (You may use either python or java to solve this problem, the python set is set the java set you can assume is Set with a generic).

A possible answer (remove the nested loops, make them happen one after the other, adding to set instead of a list first) – \(O(n)\)

def loreum(n):
  set2 = set() 
  for i in range(n):
    set2.add(i)
    
  j = 1
  while j < n:
    set2.add(j)
    j *= 2
  return val

It can be simplified as so because the while loop is adding repeated elements anyway:

def loreum(n):
  set2 = set()
  for i in range(n):
    set2.add(i)
    
  return set2

Simpler yet:

def loreum(n):
  return set(range(n))

6 Sorting

  1. Given the array [8, 3, 5, 11, 2, 9], show what the array would be after each pass of insertion sort. (insertion sort has two nested loops, a pass in this case is one iteration of the outer loop).
[3, 8, 5, 11, 2, 9]
[3, 5, 8, 11, 2, 9]
[3, 5, 8, 11, 2, 9]
[2, 3, 5, 8, 11, 9]
[2, 3, 5, 8, 9, 11]
  1. Given the array [8, 3, 5, 11, 2, 9], show what the array would be after each pass of bubble sort. (bubble sort has two nested loops, a pass in this case is one iteration of the outer loop).
[3, 5, 8, 2, 9, 11]
[3, 5, 2, 8, 9, 11]
[3, 2, 5, 8, 9, 11]
[3, 2, 5, 8, 9, 11]

Bubble sort always have a repeated last pass to make sure everything is sorted.

  1. Given the array [8, 3, 5, 11, 2, 9], show what the array would be after each pass of selection sort. (selection sort has two nested loops, a pass in this case is one iteration of the outer loop).
[2, 3, 5, 11, 8, 9]
[2, 3, 5, 11, 8, 9]
[2, 3, 5, 11, 8, 9]
[2, 3, 5, 8, 11, 9]
[2, 3, 5, 8, 9, 11]

7 Java Writing

  1. Write a java class named Shelf. The class must implement the Comparable interface to allow comparison between Shelf objects based on the items they contain. Follow these requirements:

The class should have two instance variables which are generics of the same type that are comparable. The Shelf class should also be comparable.

  • a constructor that accepts two arguments to be assigned to instance variables one and two.
  • a compareTo method which returns the compareTo of the argument with either the value in one and two. If argument is not equal to one than it returns the comparison of argument and one, otherwise it returns the comparison of argument and two.
public class Shelf<T extends Comparable> implements Comparable<Node<T>>{
    private T one;
    private T two;

    public Shelf(T one, T two) {
        this.one = one;
        this.two = two;
    }

    public int compareTo(T argument) {
        if (!argument.equals(one)) return one.compareTo(argument);
        return two.compareTo(argument);
    }
}
  1. The LinkedSet class represents a set of distinct elements (no duplicates) implemented using a linked data structure (the code for Node.java can be found below). These elements are stored as the data values of a linked list, arranged in increasing order. Implement the size, add, and remove methods.
public LinkedSet<T extends Comparable<T>>{
  private Node<T> head;
  
  public int size() { 
    int size = 0;
    Node<T> current = head;
    while (current != null) {
      size++;
      current = current.getNext();
    }
    return size;
    }
  
  public void add(T obj) {
    if (head == null) head = new Node(obj);
    else {
      Node<T> current = head;
      Node<T> previous = null;
      while (current != null && current.compareTo(obj) != 0) {
        previous = current;
        current = current.getNext();
      }
    
      if (current == null) previous.setNext(new Node(obj));
    }
  }
  
  public void remove(T obj) { 
    if (head.getData().compareTo(obj) == 0) head = head.getNext();
    else {
      Node<T> current = head;
      Node<T> previous = null;
      while (current != null && current.compareTo(obj) != 0) {
        previous = current;
        current = current.getNext();
      }
    
      if (current != null) previous.setNext(current.getNext());
      
    }
    
  }