The Versions Differ in Exam Structure Only

CIS 265506

Summer 2008

Exam #3

Name: ______

Score ______/ 100

Exam Version A B C

The versions differ in exam structure only

For multiple choice & true/false questions, circle the correct letter (or answer). You will need to choose the most correct answer from the list. Don’t “read into” the question – answer what is asked. For short answer, essays, and code completion, completely answer the question. When writing code, use plenty of comments so your work can be followed. There is no partial credit for the multiple choice or true/false questions.

Exams are closed notes, closed book. No electronic devices of any kind are permitted. All papers, books, book bags, beverages/food (and containers), computer bags, electronic devices, coats/jackets, and hats must be under your desk (on the floor). Do your own work. The people sitting around you will have a different version of this exam.

Objective Section (50 points)

Choose 25 of the following questions. If you answer more than twenty-five, only the first twenty-five answered questions will be graded.

1. True or False: A preorder traversal of a tree visits the root, the left child, and then the right child. ______

1. The maximum number of nodes in a binary tree is ______(formula)

1. A balanced binary search tree is desirable because it avoids slow performance when data is inserted
2. randomly
3. out of order
4. in order
5. none of the above

1. The goal of hashing is to reduce the number of comparisons to ______

1. A ______is the event that occurs when a hashing algorithm produces an address for insertion that is already occupied.

1. A hashed list should never be more than ______% full

1. Which of the following is not a red-black rule?
2. Every path from a root to a leaf, or to a null child, must contain the same number of black nodes
3. If a node is black, its children must be red
4. The root is always black
5. All three are valid rules

1. True or False: Not all trees are binary trees.

1. An unbalanced tree is one
2. in which most of the keys have values much greater than the average
3. whose behavior is unpredictable
4. in which the root or some other node has many more left children than right children, or vice versa
5. that is shaped like an umbrella

1. True or False: Deletion in a red-black tree may require some readjustment of the tree’s structure.

1. A ______transforms a range of key values into a range of index values.

1. A B – Tree grows from ______

1. True or False: Deleting a node with one child from a binary search tree involves finding that node’s successor.

1. A 2-3-4 tree is so named because a node can have
2. three children and four data items
3. two, three, or four children
4. two parents, three children, and four items
5. two parents, three items, and four children

1. Open addressing generally refers to
2. keeping many of the cells in the array unoccupied
3. keeping an open mind about which address to use
4. probing at cell x+1, x+2, … and so on until an empty cell is found
5. looking for another location in the array when the one you want is occupied

1. In external storage, indexing means keeping a file of
2. keys and their corresponding blocks
3. records and their corresponding blocks
4. keys and their corresponding records
5. last names and their corresponding keys

1. Separate chaining involves the use of a ______at each location.

1. In external hashing, all records with keys that hash to the same value are located in ______

1. The best technique when the amount of data is not well know is
2. linear probing
3. quadratic probing
4. double hashing
5. linear chaining

1. The worstcase running time to search a red-black tree or insert an item is ______

1. All leaves in a B-Tree:
2. have to be at the same level
3. can not be at the same level
4. can be anywhere – level does not matter

1. Which tree type has leaf nodes that contain a pointer to the next leaf?
2. B
3. B+
4. B*
5. B-

1. ______involves storing and retrieving objects from an external file.

1. Which of the following methods is used to reduce/eliminate collisions in a hash table?
2. Double hashing
3. Key Offset
4. Pseudorandom collision resolution
5. Linked list/chaining

1. Define “load factor”.

1. A ______algorithm is an algorithm that accepts an argument a and tries to find a record who key is a. If this algorithm does not find a, it will be added. This is called a ______algorithm.

1. True or False: If dynamic structures are used in a program, the maximum size must be pre-set at compile time. ____

1. True or False: Linear lists are efficient to search for and retrieve information. ______

1. True or False: A preorder traversal of a tree visits the root, the left child, and then the right child. ______

1. The maximum number of nodes in a tree is ______
   
2. Identify the type of the following equations (Circle One, for each item)

A+B*C+D-E*FPrefixPostfixInfix

-++A*BCD*EFPrefixPostfixInfix

ABC*+D+EF*-PrefixPostfixInfix

Java Data Structures Programming (50 points)

Answer two of the following questions. Be complete, specific, and accurate. Use proper Java syntax. If you answer all three, only the first two questions will be graded.

1. The code below is a non-recursive method to display the elements in a tree. It can be easily modified to copy a tree (and still remain non-recursive). That method will return an S_Tree. Please modify the method below to non-recursively copy a tree, and return the new tree to the calling program. The next page is blank to provide space for your answer

publicvoid displayTree()

{

Stack<S_Node> globalStack = new Stack<S_Node>();

globalStack.push(root);

int nBlanks = 32;

boolean isRowEmpty = false;

System.out.println("...... ");

while(isRowEmpty==false)

{

Stack<S_Node> localStack = new Stack<S_Node>();

isRowEmpty = true;

for(int j=0; j<nBlanks; j++)

System.out.print(' ');

while(globalStack.isEmpty()==false)

{

S_Node temp = (S_Node)globalStack.pop();

if(temp != null)

{

System.out.print(temp.iData);

localStack.push(temp.leftChild);

localStack.push(temp.rightChild);

if(temp.leftChild != null ||

temp.rightChild != null)

isRowEmpty = false;

}

else

{

System.out.print("--");

localStack.push(null);

localStack.push(null);

}

for(int j=0; j<nBlanks*2-2; j++)

System.out.print(' ');

} // end while globalStack not empty

System.out.println();

nBlanks /= 2;

while(localStack.isEmpty()==false)

globalStack.push( localStack.pop() );

} // end while isRowEmpty is false

System.out.println("...... ");

} // end displayTree()

1) continues…

2. Given the following tree, what are the pre-, in-, and post-order traversals?

This code will help with the last question

publicclass S_Tree {

private S_Node root; // first node of tree

// ------

public S_Tree() // constructor

{ root = null; } // no nodes in tree yet

// ------

public S_Node find(String key) // find node with given key

{ // (assumes non-empty tree)

S_Node current = root; // start at root

while(!current.iData.equals(key)) // while no match,

{

if(key.compareTo(current.iData) < 0) // go left?

current = current.leftChild;

else // or go right?

current = current.rightChild;

if(current == null) // if no child,

returnnull; // didn't find it

}

return current; // found it

} // end find()

// ------

publicvoid insert(String id)

{

S_Node newNode = new S_Node(); // make new node

newNode.iData = id; // insert data

if(root==null) // no node in root

root = newNode;

else // root occupied

{

S_Node current = root; // start at root

S_Node parent;

while(true) // (exits internally)

{

parent = current;

if(id.compareTo(current.iData) < 0) // go left?

{

current = current.leftChild;

if(current == null) // if end of the line,

{ // insert on left

parent.leftChild = newNode;

return;

}

} // end if go left

else // or go right?

{

current = current.rightChild;

if(current == null) // if end of the line

{ // insert on right

parent.rightChild = newNode;

return;

}

} // end else go right

} // end while

} // end else not root

} // end insert()

// ------

publicboolean delete(String key)

// delete node with given key

{ // (assumes non-empty list)

S_Node current = root;

S_Node parent = root;

boolean isLeftChild = true;

while(!current.iData.equals(key)) // search for node

{

parent = current;

if(key.compareTo(current.iData) < 0) // go left?

{

isLeftChild = true;

current = current.leftChild;

}

else // or go right?

{

isLeftChild = false;

current = current.rightChild;

}

if(current == null) // end of the line,

returnfalse; // didn't find it

} // end while

// found node to delete

// if no children, simply delete it

if(current.leftChild==null

current.rightChild==null)

{

if(current == root) // if root,

root = null; // tree is empty

elseif(isLeftChild)

parent.leftChild = null; // disconnect

else // from parent

parent.rightChild = null;

}

// if no right child, replace with left subtree

elseif(current.rightChild==null)

if(current == root)

root = current.leftChild;

elseif(isLeftChild)

parent.leftChild = current.leftChild;

else

parent.rightChild = current.leftChild;

// if no left child, replace with right subtree

elseif(current.leftChild==null)

if(current == root)

root = current.rightChild;

elseif(isLeftChild)

parent.leftChild = current.rightChild;

else

parent.rightChild = current.rightChild;

else // two children, so replace with inorder successor

{

// get successor of node to delete (current)

S_Node successor = getSuccessor(current);

// connect parent of current to successor instead

if(current == root)

root = successor;

elseif(isLeftChild)

parent.leftChild = successor;

else

parent.rightChild = successor;

// connect successor to current's left child

successor.leftChild = current.leftChild;

} // end else two children

// (successor cannot have a left child)

returntrue; // success

} // end delete()

// ------

// returns node with next-highest value after delNode

// goes to right child, then right child's left descendents

private S_Node getSuccessor(S_Node delNode)

{

S_Node successorParent = delNode;

S_Node successor = delNode;

S_Node current = delNode.rightChild; // go to right child

while(current != null) // until no more

{ // left children,

successorParent = successor;

successor = current;

current = current.leftChild; // go to left child

}

// if successor not

if(successor != delNode.rightChild) // right child,

{ // make connections

successorParent.leftChild = successor.rightChild;

successor.rightChild = delNode.rightChild;

}

return successor;

}

// ------

publicvoid traverse(int traverseType)

{

switch(traverseType)

{

case 1: System.out.print("\nPreorder traversal: ");

preOrder(root);

break;

case 2: System.out.print("\nInorder traversal: ");

inOrder(root);

break;

case 3: System.out.print("\nPostorder traversal: ");

postOrder(root);

break;

}

System.out.println();

}

// ------

privatevoid preOrder(S_Node localRoot)

{

if(localRoot != null)

{

System.out.print(localRoot.iData + " ");

preOrder(localRoot.leftChild);

preOrder(localRoot.rightChild);

}

}

// ------

privatevoid inOrder(S_Node localRoot)

{

if(localRoot != null)

{

inOrder(localRoot.leftChild);

System.out.print(localRoot.iData + " ");

inOrder(localRoot.rightChild);

}

}

// ------

privatevoid postOrder(S_Node localRoot)

{

if(localRoot != null)

{

postOrder(localRoot.leftChild);

postOrder(localRoot.rightChild);

System.out.print(localRoot.iData + " ");

}

}

}
Using the tree class presented, create a method (that will be part of the tree class) that will – for the current tree – delete all occurrences of a user supplied string. You may assume the string is valid

CIS 265/506

Exam Number 3

Exam3_A.doc

Page 1 of 10