联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> javajava

日期:2018-12-19 11:01

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 2

CS 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<K,V> {

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<K> preOrderKeys(){

// TODO Student Code

}

/**

* Helper function for public recursive method

*/

private List<K> preOrderKeys(Node start){

// TODO Student Code

}

}

}

Page 3

CS 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


版权所有:留学生程序网 2020 All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。