Summer 2015 CSC 161 Final Exam Study Guide

Quicksort

Suppose that you have a method

int partition(int [] arr, int lower, int uppper)

which when called on a segment of an array arr whose elements are in positions lower through upper, rearranges the elements of the array in that segment and returns an integer p such that all elements in the segment arr[lower...p-1] are less than arr[p], and all elements in the segment arr[p+1..upper] are greater or equal to arr[p].

Show how to write a recursive method that uses the partition method based on the Quicksort method.

void Quicksort(int [] arr, int lower, int upper)

Partition

Write the partition method used in the Quicksort algorithm.

Collections

Explain the difference between lists and sets.

Define the concept of an iterator for a collection, and list, with descriptions, the key methods in the Iterator interface.

Describe the two different approaches to implementing lists and point out the tradeoffs in the two approaches. Name the two Java classes that are used to implement the List interface.

Describe the two different approaches to implementing sets and point out the tradeoffs in the two approaches. Name the two Java classes that are used to implement the Set interface.

Explain the concept of a map, and explain how maps differ from lists and sets. Give at least three methods that are in the Java Map< K, V > interface.

Binary Trees

Assume we have a class

class Node 
{
   int value;
   Node left;
   Node right;
   Node(int v, int left1, int right1)
   {
      value = v;  left = left1; right = right1;
   }
   Node(int v)
   {
     this(v, null, null);
   }
}

Write recursive methods for traversing a binary tree, where a reference to the root node of the binary tree is passed as parameter:

void preorder(Node t)
{


}

void inorder(Node t)
{


}

void postorder(Node t)
{


}

Write a method int treeSize(Node t) that returns the number of nodes in a binary tree t.

Write a method boolean contains(Node t, int value) that returns true if the given value is stored in one of the nodes of the tree rooted at t, and false otherwise.

Write a method int numberOfLeaves(Node t) that returns the number of leaves in the binary tree rooted at t.

Define the concept of a binary search tree.

Write a method Node add(Node t, int value) that adds a value to the binary search tree rooted at t and returns a reference to the root of the resulting binary search tree.