讲解CS 310、辅导Java编程语言、辅导data structure留学生、Java程序设计讲解 辅导Python编程|辅导R语言程序
CS 310: Worksheet 04 San Diego State University
Name: Section:
Due Date: 2018-OCT-16/17 Score:
Answer the questions in the spaces provided on the question sheets. If you run out
of room for an answer, continue on the back of the page.
Complexity
1. (2 points) In a complete binary search tree, what is the worst case complexity for finding a
single key within the data structure? Select the tightest bound.
A. O(n
2
)
B. O(1)
C. O(log(n))
D. O(n)
E. O(n log(n))
2. (2 points) In an unbalanced binary search tree, after inserting the keys in increasing order,
what is the worst case complexity for finding a single key within the data structure? Select the
tightest bound.
A. O(n
2
)
B. O(1)
C. O(log(n))
D. O(n)
E. O(n log(n))
3. (2 points) Removing a single arbitrary key from the map, in an unbalanced binary search tree,
requires time in the worst case.
A. O(n
2
)
B. O(1)
C. O(log(n))
D. O(n)
E. O(n log(n))
Trees
4. (2 points) A post-order tree traversal produces keys .
A. With the largest key in the tree last in the list.
B. Only from the right subtree.
C. With all the tree’s leaves first.
D. With values first.CS 310: Worksheet 04 San Diego State University
5. (2 points) Given the following number sequence, draw the resultant tree: 3, 49, 0, -34,
121, 122, 10, 13, 37, -5, 12, 9
Page 2CS 310: Worksheet 04 San Diego State University
Tree Software
6. Given the following Java code fragment, implement the requested methods. You may not
introduce any new class level variables. Assume no syntax errors.
public class BasicTree {
private class Node {
K key;
V value;
public Node(K key, V value){
this.key = key;
this.value = value;
}
}
Node root;
int curSize;
...
/**
* Produces the key sequence resulting from a pre-order tree
* traversal.
*
* @return A List of the keys in the tree in pre-order
*/
public List preOrderKeys(){
// TODO Student Code
}
/**
* Helper function for public recursive method
*/
private List preOrderKeys(Node start){
// TODO Student Code
}
}
}
Page 3CS 310: Worksheet 04 San Diego State University
(a) (4 points) Complete the public inOrderKeys() method using a recursive algorithm. To do
so, students must also implement the private version which takes a single parameter.
(b) (6 points) Complete the public inOrderKeys() method using a non-recursive algorithm.
This method may use a java.util.Stack.
END