Java程序辅导

CS 3114 Data Structures & Algorithms  Homework 1:  Trees 
 
You are permitted to work in pairs for this assignment! 1 
You may work in pairs for each part of this assignment.  If you choose to work with a partner, you must work with the same 
partner on both parts of this assignment, and make sure only one of you submits a solution for each part, and you paste a copy 
of the Partners Template that contains the names and PIDs of both students at the beginning of the file you submit. For part 2, 
be sure the template is formatted as a comment. 
  
 
Part 1:  Short-answer Questions 
 
You will submit your solution to this part of the assignment to the Curator System (as HW01P1).  Your solution must be either a 
plain text file (e.g., NotePad++); submissions in other formats will not be graded. 
 
Partial credit will only be given if you show relevant work. 
 
1. [20 points] Suppose that a PR quadtree, with bucket size 1, represents a region in the xy-plane bounded between (0, 0) 
and (2^12, 2^12).  Suppose further that we insert two data objects A and B, corresponding to locations that are 
separated by a distance of 5 units.  Given only that much information, give the most precise statement you can 
regarding how many region splits will be required in order to separate A and B?  Justify your answer carefully. 
 
 
2. The diagram below shows a partitioned world, which can be represented by a PR quadtree, with bucket size 1.  Since 
the tree is implemented sensibly, a leaf node will be created only if it contains a data point, and an internal node will be 
created only when a partitioning operation is performed. 
 
  A              
   I             
M                
 R               
 C         B   F   
                
O         N       
         K       
                
                
                
    L         P   
          H      
          S G     
          E     Q 
         D       
 
a) [10 points]  How many leaf nodes (nonempty) would the quadtree have? 
 
b) [10 points]  How many internal nodes would the quadtree have?   
 
c) [10 points]  How many levels would the PR quadtree have? 
 
d) [10 points]  Assuming the same world size as in question 1, what are the dimensions of the smallest leaf region?  
CS 3114 Data Structures & Algorithms  Homework 1:  Trees 
 
You are permitted to work in pairs for this assignment! 2 
Part 2:  BST coding questions 
 
You will submit your completed BSTUtils.java file to the Curator System (as HW01P2).  Your score for this part will be 
entirely determined by testing your solution with the supplied testing code. 
 
Download the posted zip file, which contains the following files: 
 
testDriver.java Java driver for the grading code; see embedded comments 
BST.java partial BST generic 
BSTUtils.java shell file for your solution 
UtilsChecker.class Java grading functions 
 
Unpack these files in a folder on your machine.  You may work Windows or MacOS or Linux, as you prefer.  If you have 
installed the JDK, you can compile the given code with the command: 
 
prompt> javac testDriver.java BST.java BSTUtils.java 
 
The test driver can be invoked with the command: 
 
prompt> java testDriver 
 
This displays invocation instructions: 
 
Invocation: java testDriver testSelector [-repeat] logName 
    testSelector is either –lub or -range 
    -repeat is optional; a seed file must already exist from a previous test run 
 
Of course, this will not pass testing until you complete the following generic functions in BSTUtils.java: 
 
 
/**  Returns a reference to the unique object Y in the BST such that 
 *  
 *      Y = min { Z in tree | X.compareTo(Z) <= 0 } 
 *  
 *   or null if no such element exists in the BST. 
 *  
 *   Pre:  tree is a proper BST containing zero or more nodes 
 *         X is a proper object of type T 
 */ 
public static > T LUB(BST tree, T X) {. . .} 
 
 
 
/**  Returns an ArrayList containing all the values in the given BST 
 *   that fall between lower and upper, inclusive, according to the 
 *   compareTo() method supplied by the user's data type. 
 *  
 *   Pre:  tree is a proper BST holding zero or more data objects 
 *         lower and upper are valid data objects 
 */ 
public static > 
              ArrayList rangeSearch(BST tree, T lower, T upper) {. . .} 
 
  
CS 3114 Data Structures & Algorithms  Homework 1:  Trees 
 
You are permitted to work in pairs for this assignment! 3 
If you find the syntax confusing, review the posted course note on Java generics.  For a generic function in Java, we must 
specify the generic type (including any type bound) between the access controls and the return type for the function: 
 
 
public static > T LUB(BST tree) {. . .} 
 
 
The requirements for the generic type bound are explained in the BST course notes. 
 
The functions are static so that they may be called without creating an object of the class BSTUtils.   If you want to write 
your own testing code (not a bad idea at all), you would call the BSTUtils functions using syntax like this: 
 
BST myBST = new BST(); 
 
// code to add data to the tree 
Integer N = new Integer(42); 
 
Integer LUB = BSTUtils.LUB(tree, N); 
 
Of course, each of your functions will need one or more helper functions, also implemented in BSTutils.java.  Those 
functions must be declared as private static.  The interfaces of any helper function is entirely up to you; the testing code 
will be unaware of those functions, and so will never call them directly. 
 
The testing code, in UtilChecker, will create BSTs holding Integer objects from the given BST implementation, and then 
call the functions you have written, in BSTutils.java, the test those functions, writing information about the tests that were 
run, and the results into a log file.   
 
Aside from the top-level test functions called from testDriver, UtilChecker provides the following function for your 
convenience: 
 
/**  Inserts randomly-selected Integer values in to a BST, and also initializes 
 *   an ArrayList with the same values, in sorted order. 
 * 
 *   Pre:  setupUtilChecking() has been called to initialize the random generation 
 *         tree is a valid, empty BST 
 *         data is a valid, empty ArrayList 
 * 
 *   Post: tree contains Size different Integer values 
 *         data contains the same values, but in sorted order 
 */ 
public static void UCfillBST(BST tree, ArrayList data, int Size) {. . .} 
 
 
Grading 
 
Part 1 will be graded manually by the GTAs.  Part 2 will be auto-graded using the supplied testing code.  Your solution to 
each function will be scored out of a possible xx points.  Your final score for this assignment will be the sum of your scores 
from Part 1 and Part 2.