1 Data Structures

You need to repeatedly find and remove the minimum element from a collection of integers. Which data structure is most efficient for this operation?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You are implementing a spell checker that needs to quickly determine whether a word exists in a dictionary of 100,000 words. Which data structure supports the fastest lookup?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

A hospital triage system assigns patients a priority score upon arrival. The doctor always treats the highest-priority patient next, and new patients can arrive at any time. Which data structure best supports this workflow?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to store a collection of integers and frequently need to find all values within a given range (e.g., all values between 50 and 100). Which data structure makes range queries most efficient?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to store exactly 200 integers and will access them frequently by index (e.g., “give me the element at position 42”). Insertion and deletion never take place. Which data structure is most appropriate?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You are implementing a task scheduler that always executes the task that was first added to the scheduler. Tasks are added and removed continuously. Which data structure best supports this?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to maintain a dynamic sorted collection where you frequently need to find the predecessor and successor of a given value. Which data structure is most efficient?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to repeatedly extract the largest element from a dynamic collection of integers, while also supporting efficient insertion of new elements. Which data structure is most appropriate?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to store a collection of student GPAs and frequently search for whether a specific GPA exists, insert new GPAs, and delete old ones — all efficiently. Which data structure is best?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

An emergency room assigns each patient a severity score. Doctors always treat the most severe patient next, and new patients arrive continuously. Which data structure best supports this system?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to store 500 sensor readings and frequently access them by index (e.g., “get reading number 200”). The data does not change after it is stored. Which data structure is most efficient?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

A CPU scheduler processes tasks in the order they arrive, but tasks can also be added to the front of the line when re-queued after a time slice. Which data structure best supports efficient insertion at both ends?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

You need to maintain a sorted collection of words and frequently need to retrieve all words that fall alphabetically between “mango” and “peach”. Which data structure makes this most efficient?

▢ A) Array-based list

▢ B) Linked-list

▢ C) Binary search tree

▢ D) Heap

▢ E) Hash Table

2 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

3 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

4 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

5 Heap

For the questions below, you are to draw the max-heap tree and the corresponding array.

Draw a max-heap (tree and array) which has the following values inserted in the following order: 32, 15, 6, 25, 21, 31, 7, 18, 35
What would the max-heap from part (a) look like after pop()?
What would the max-heap from part (b) look like after pop()?
What would the max-heap from part (c) look like after value 29 is inserted?

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

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

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

9 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 comparable type. 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 +
      '}';
  }
}

10 Key

Access the answers on this other page.