CS 1332 Exam 1 - Version A

Spring Semester 2021- February 17, 2022

1) E fficiency - Multiple Choice [15 points]

For each of the operations listed below, determine the time complexity of the operation as it pertains to the data structure. Select the bubble corresponding to your choice in the space provided, and completely fill in the bubble. Unless otherwise stated, assume the worst-case time complexity.

However, make sure you choose the tightest Big-O upper bound possible for the operation. Do not use an amortized analysis for these operations unless otherwise specified.

A) What is the worst-case cost of removing an element from an array-backed stack?

⃝ O(1)           ⃝ O(n)       ⃝ O(log n)        ⃝ O(nlog n)        ⃝ O(n2)

B) What is the worst-case cost of adding an element to an array-backed stack?

⃝ O(n)            ⃝ O(1)       ⃝ O(log n)        ⃝ O(nlog n)        ⃝ O(n2)

C) What is the worst-case cost of adding an element to an array-backed queue?

⃝ O(n)            ⃝ O(log 1)       ⃝ O(log n)        ⃝ O(nlog n)        ⃝ O(n2)

D) What is the worst-case cost of removing from the front of a Circular Singly Linked List without a tail pointer?

⃝ O(1)           ⃝ O(log n)       ⃝ O(n)        ⃝ O(nlog n)        ⃝ O(n2)

E) What is the worst-case cost of removing the last element in an ArrayList that does not have a size variable?

⃝ O(n)            ⃝ O(1)       ⃝ O(n2)        ⃝ O(nlog n)        ⃝ O(log n)

2) Data Structure Properties - Multiple Choice [10 points]

For each of the scenarios listed below, determine the most appropriate choice data structure. Answer choices for different scenario matching questions may be used once, multiple times, or not at all.

A) On the way to Hamburger Queen, you have gotten horribly lost. But don't worry, a series of signs have been erected to help you reach that sweet burger-y goodness. Strangely, instead of giving you directions straight to Hamburger Queen, each sign only tells you how to reach the next sign, but eventually, by following the signs, you will reach Hamburger Queen. What structure best represents these signs?

⃝ ArrayList           ⃝ Singly Linked List       ⃝ SLL-backed Stack         ⃝ Binary Heap

B) Many car salespeople are only paid based on how many vehicles they can sell. At the end of each month, the salesperson with the highest number of sales is rewarded with an extra bonus. What structure is best suited to identify the salesperson who made the most sales in constant time (assuming all the sales data has already been added to the structure)?

⃝ Binary Tree           ⃝ Priority Queue       ⃝ Deque        ⃝ Array-backed Stack

C) A developer is working on a creative file explorer that visualizes files as papers on a desk. Instead of organizing files into folders like a regular file explorer, users put their papers into piles. In these piles, users can only access the most recently added file (the one represented by the paper at the top of the pile). For example, if they want to see a paper deeper in the pile, they must first remove all the   ones on top of it. What structure is best suited to represent a paper pile?

⃝ Stack           ⃝ Queue       ⃝ Heap        ⃝ ArrayList

D) Biologists are creating a program to model the lifecycle of a single celled organism. To reproduce, the organism simply splits in half to create two new organisms. Then, each of these organisms either reproduces (produces two more children) or dies before reproduction (produces no more children).     What structure is best suited to represent the hierarchy of organism generations?

⃝ Binary Tree           ⃝ Deque      ⃝ Singly Linked List with tail        ⃝ Queue

E) Tomorrow is your town's beloved Rubber Duck Festival, and to contribute to the festivities, you have decided to curate a playlist of your favorite duck songs to share with the festival-goers. Since some of the townsfolk don't share your taste in duck music, you have provided the option to skip to the next song in the playlist. Once the end of the playlist has been reached, the first song will automatically begin playing again. What structure best represents the playlist?

⃝ Array         ⃝ SLL-backed Queue       ⃝ Circular Linked List         ⃝ ArrayList

3) Trees - Multiple Select [3 points]

Given the following tree, select all properties that apply to the tree. If you believe none of the properties apply, select ONLY that answer.

4) Binary Search Trees - Diagramming [12 points]

Given the following initial BSTs in the left column below. Perform. the stated operation, add or remove, for each tree. Draw the resulting BST in the right column. If you want, you can draw multiple steps (circle the final step if you do so). If necessary for any operation, use the successor node.

5) Binary Search Trees - Diagramming [12 points]

Given the following initial BSTs in the left column below. Perform. the stated operation, add or remove, for each tree. Draw the resulting BST in the right column. If you want, you can draw multiple steps (circle the final step if you do so). If necessary for any operation, use the successor node.

6) MinHeap - Diagramming [10 points]

Given the MinHeap below backed by an array of length 13, perform. the listed operation and enter the  updated values of the backing array at the correct indices. Follow the implementation taught in class.

Requirements: Rewrite the array each time a swap is necessary on a new row and write and circle the swapped elements only on the line directly

add(1);

7) Binary Tree Traversals - Diagramming [8 points]

Given the following Binary Search Tree, perform. a pre-order traversaland enter the resulting list in the box below as a comma separated list of values.

8) Array-Backed Stacks- Coding [10 points]

Goal: Given the following ArrayStack class, which is an array-backed Stack, implement the pop() method. As per the javadocs, you should not attempt to resize the array at any point. You may    assume all data is not null.

Requirements: Since Node is an inner class, you should access its fields directly (e.g. node.data)    instead of using getters/setters. Your code should be as efficient as possible. You may not assume any other method in the CircularSinglyLinkedList class is implemented. You may assume that

everything from java.util is imported.

public class ArrayStack<T> {

private T[] backingArray;

private int size;

/**

* Removes and returns the element on top of the stack

*

* Do not grow or shrink the backing array.

*

* Replace any spots that you remove from with null.

*

* @return the data formerly located at the top of the stack

* @throws java.lang.NoSuchElmentExcpetion if the stack is empty

*/

public T pop(T data) {

// YOUR CODE HERE, USE THE NEXT PAGE IF NEEDED

} // END OF METHOD

} // END OF CLASS

9) Circular Singly-Linked List - Coding [10 points]

Given the following Circularly Singly-Linked List class (CSLL), implement the addToFront() method. Reference the Javadocs for specific requirements.

Requirements: Feel free to write any helper methods you consider to be necessary, but you may NOT call any CSLL methods you do not write out in full. You may NOT create additional instance variables for the CSLL class. Since CSLLNode is a private inner class, you should access its fields directly (e.g. node.data) instead of using getters/setters. Notice that neither CSLL nor CSLLNode are generic; you  should reflect this in the declaration and instantiation of nodes by not including generic types. Your code should be as efficient as possible.  You may assume all data is not null, including data that is passed into the method..

public class CSLL {

private class Node {

public int data;

public Node next;

public Node(int data, Node next) { ... }

public Node(int data) { this(data, null); }

}

private Node head;

int size;

/**

* Adds the data to the front of the list.

*

* @param data the data to add to the front of the list

*/

public void addToFront(int data) {

// YOUR CODE HERE, USE THE NEXT PAGE IF NEEDED

} // END OF METHOD

} // END OF CLASS