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

Postorder: A,B,C,J,K,I,D,E,F,G,H,L.

#### Question 2

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

Answer: There is more than one way to do the deletes, so the final answer is not unique, but here is one:

#### 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?

Answer: If every internal node of T has 2 children then there is one node at the root, 2 at depth 1, 4 at depth 2, 8 at depth 3, for a total of 15 nodes. If every internal node of T has 1 child, then there is a total of 4 nodes.

#### 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?

Answer: The first three levels (including the root) must be fully filled out, giving a total of 7 nodes. The 4th level has between 1 node and 8 nodes. So the total number of nodes in the heap is between 8 and 15.

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

Answer: False. The first node printed out in a preorder traversal is the root, which is greater than the nodes in the left subtree. For example, in the tree of question 2, the first node printed out is 15.

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

Answer: True. In a breadth-first traversal, the first node printed out is the root, which is the smallest element in a min-heap.

#### Question 7

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

Answer: The implementation of a heap as an array follows the breadth-first order: [2,3,5,10,8,7,22,11,13,20,24,16].

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]

Answer: [6,2,7,11,17,23,49,34,22,23]. The value returned is 4 (the index of 17).

#### 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]

Answer: Step 1. Go through the numbers and put each one into the corresponding bucket in order.

```   Bucket 0.0-0.1: 0.03
Bucket 0.1-0.2: 0.15, 0.12, 0.19
Bucket 0.2-0.3:
Bucket 0.3-0.4:
Bucket 0.4-0.5: 0.43
Bucket 0.5-0.6: 0.52
Bucket 0.6-0.7: 0.69
Bucket 0.7-0.8: 0.71
Bucket 0.8-0.9:
Bucket 0.9-1.0: 0.92, 0.95
```

Step 2: Sort the non-empty buckets. The only one that changes is

```   Bucket 0.1-0.2: 0.12, 0.15, 0.19
```

Step 3: String the buckets together.

```     [0.03, 0.12, 0.15, 0.19, 0.43, 0.52, 0.69, 0.71, 0.92, 0.95]
```

#### Question 10

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

Answer: N2 / N log(N) = N/log(N) = 1,000,000/20 = 50,000 times faster.

#### 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

```A = array of size M, initialized to 0;
MODE = 1;      // Most frequent value seen so far
for (X in L) {
A[X]++;
if (A[X] > A[MODE]) MODE = X;
}
return MODE;
```

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

 --- 1 4 --- 2 3 --- --- ---
Here --- is a null value; in practice, this is implemented as a number which is known not to be a possible value.

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

```public void addEdge(Vertex v, in l) {
Edge e = new Edge();
e.tag = l;
e.tail = this;
e.nextEdge = firstOutarc;
firstOutarc = e;
}
```

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

Answer: Graph 1: Acyclic. Topological sort: A, B, D, C.
Graph 2: Cyclic. Cycle: F,H,G,F
Graph 3: Acyclic. There are several different topological sorts. I,J,K,L,M is one.

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

Answer: There are four different possibilities. These are two:

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

```