### Sample questions from the second half of the course

Note: this is not a sample final exam. For one thing, there are too many questions. For another thing, there are no questions from the first half of the course.

You should be particularly sure to do problems 15 and 16, since these deal with topics that were not on any of the homework assignments.

#### Question 1

List the nodes of the tree below in preorder, postorder, and breadth-first order.

#### Question 2

In the binary search tree below, carry out the following operations in sequence: Add 5, add 17, delete 23, delete 9.

#### Question 3

T is a binary tree of height 3. What is the largest number of nodes that T can have? What is the smallest number?

#### Question 4

T is a min heap of height 3. What is the largest number of nodes that T can have? What is the smallest number?

#### Question 5

True or false: In a preorder traversal of a binary search tree, the first item printed out is always the smallest one. If true, explain why; if false, give an example where it is false.

#### Question 6

True or false: In a breadth-first traversal of a min heap, the first item printed out is always the smallest one. If true, explain why; if false, give an example where it is false.

#### Question 7

A. Show how the min heap below would be implemented in an array.

B. Show the result of executing deleteMin() and add(4) in sequence starting with the min heap below. (You may give your answer either in the form of a tree or in the form of an array.)

#### Question 8

Show the result of running the partition subroutine of quicksort on the following array, assuming that the index of the pivot is chosen to be 0 (the pivot is A[0]=17). What value does partition return?
A=[17, 2, 34, 23, 6, 11, 49, 7, 22, 33]

#### Question 9

Explain how bucket sort can be used to sort the numerical values below. Assume that the range 0.0 - 1.0 is divided into 10 buckets, each of size 0.1
[0.92, 0.15, 0.03, 0.71, 0.95, 0.43, 0.12, 0.69, 0.19, 0.52]

#### Question 10

If you are sorting a million items, roughly how much faster is heapsort than insertion sort? (Note: log(1,0000,000) = 20.)

#### Question 11

Given a list of integers, you wish to find the mode; that is, the value that appears most often in the list. Let N be the length of the list. For instance, in the list [1, 5, 2, 5, 2, 5, 5, 1], N=9 and the mode is 5, which appears four times.

Assume that the values are all between 1 and M, that you have enough memory to construct an array of size M, and that you can create an array initialized to 0 in unit time. Given an algorithm to find the mode in time O(N). Note: This time bound should be valid even if M is much bigger than N

#### Question 12

Suppose that a graph is implemented using an adjacency-list representation using the following Java class definitions: (For this question, we are only interested in the data fields, so the methods are omitted.)
```class Vertex {
public String tag;
public Edge firstOutarc;
}

class Edge {
public Integer tag;
public Vertex tail;
public Edge nextEdge;
}
```
Assume that the nextEdge fields are used to organize the outarcs from a given vertex into a singly-linked list with no header.

Draw the objects with links that would be an implementation of the following directed graph:

Note: there are many more than 3 objects and 4 links.

#### Question 13

Show how the graph in question 12 would be represented as an adjacency array.

#### Question 14

For the class definition in question 12, write a method U.addEdge(V,L) which adds an edge from U to V labelled L.

#### Question 15

For each of the directed graphs shown below:
• If it is acyclic, give a topological sort.
• If it not acyclic, find a cycle.

#### Question 16

A. Construct a 2-3 tree with the following elements: 2,5,8,11,14,17,21,24,28. Do not do successive adds; just build the tree left to right, bottom up.

B. Show the results of doing the following operations in sequence: Add 18, add 19, delete 8, delete 5, delete 11.