Fall 2025 Final Exam Practice Problems

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

Author

Adriana Picoral

1 Array-based lists

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

2 Linked-list

Draw an empty linked list with a head and a tail references
Draw the linked list from part (a) with the following values added in this order: 32, 15, 6, 50
Draw the linked list from part (b) with the node of value 15 deleted

3 Binary Search Tree

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
Draw the binary search tree from part (a) with value 25 deleted, and the value 44 inserted
Draw the binary search tree from part (b) with value 43 deleted, and the value 29 inserted

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.

5 Big-O

Consider the following python code.

def loreum(n):
  lst1 = []
  for i in range(n):
    j = 1
    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

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

6 Sorting

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

7 Java Writing

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 the value in one and two. If argument is not equal to one than it returns the comparison of argument and one, and if they are equal returns the comparison of two.

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()
  { /* to be implemented */ }
  
  public void add(T obj)
  { /* to be implemented */ }
  
  public void remove(T obj)
  { /* to be implemented */ }

Node.java

class Node <T extends Comparable<T>> implements Comparable<Node<T>>{
  private T data;
  private Node<T> next; 

  public Node(T data) {
    this.data = data;
    this.next = null;
  }

  public Node(T data, Node next) {
    this.data = data;
    this.next = next;
  }

  public Node(){
    this.data = null;
    this.next = null;
  }

  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }

  public Node<T> getNext() {
    return next;
  }

  public void setNext(Node<T> next) {
    this.next = next;
  }

  public int compareTo(Node<T> other) {
    if (other == null) {
      throw new NullPointerException("The other node is null.");
    }
    return this.data.compareTo(other.getData());
  }

  @Override
  public String toString() {
    return "Node{" +
      "data=" + data +
      '}';
  }
}

8 Key

Submit your answers to the gradescope assignment titled “Final Exam Practice (extra credit)”, using the template found on gradescope. Once you do, I’ll send you the key by email.