### 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 Vertex head;
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.