CS61B Fall 2009
UNIVERSITY OF CALIFORNIA Department of Electrical Engineering and Computer Sciences Computer Science Division
Test #2 (revised)
P. N. Hilfinger
Copyright By PowCoder代写 加微信 powcoder
READ THIS PAGE FIRST. Please do not discuss this exam with people who haven¡¯t taken it. Your exam should contain 4 problems on 7 pages. Officially, it is worth 20 points (out of a total of 200).
This is an open-book test. You have fifty minutes to complete it. You may consult any books, notes, or other inanimate objects available to you. You may use any program text supplied in lectures, problem sets, or solutions. Please write your answers in the spaces provided in the test. Make sure to put your name, login, and lab section in the space provided below. Put your login and initials clearly on each page of this test and on any additional sheets of paper you use for your answers.
Be warned: my tests are known to cause panic. Fortunately, this reputation is entirely unjus- tified. Just read all the questions carefully to begin with, and first try to answer those parts about which you feel most confident. Do not be alarmed if some of the answers are obvious. Should you feel an attack of anxiety coming on, feel free to jump up and run around the outside of the building once or twice.
Your name:
Login: Login of person to your Left: Right:
Discussion section number or time:
Discussion TA:
Lab section number or time:
Test #2 Login: Initials: 2
1. [8 points] Please give short answers to the following, being sure to answer all parts of each question. Time estimates refer to asymptotic bounds (O(¡¤¡¤¡¤), ¦¸(¡¤¡¤¡¤), ¦¨(¡¤¡¤¡¤)). Always give the simplest bounds possible (O(f(x)) is ¡°simpler¡± than O(f(x) + g(x)) and O(Kf(x))).
a. Consider a QuadTree, as represented in Project 2, in which each leaf node happens to contain at most one point. What is the worst-case time for determining whether a point with coordinates (x, y) is in the tree? Your answer may depend on the number of points in the QuadTree or the parameters to the QuadTree¡¯s constructor (or both).
b. A certain application receives and stores many timestamped records from a large number of satellites. Because the satellites are constantly moving and sometimes have to relay their data in various ways, the transit times of these messages can vary by several seconds and therefore the data records may get stored out of sequence. Occasionally, therefore, the data are sorted. A new programmer is horrified to discover that whoever wrote this application used insertion sort, an O(N2) algorithm. He decides to improve matters by switching to quicksort. However, this turns out to slow down the sorting process. Why? (Be specific; use the information given in the problem.)
Test #2 Login: Initials: 3
c. We wish to find all the values in a binary search tree with N nodes that are between two given values L and U, assuming that the value at the root of the tree is itself between L and U. If there are K such values in the tree, how long does it take to find them all, and would this answer change if the root¡¯s value need not be between L and U?
d. A binary search tree with N nodes has parent links¡ªthat is, from any node, one can reach either child of a node or the node¡¯s parent in one step. Show a worst-case situation for finding the node with next-larger value starting at an arbitrary node in the tree. Also, what is the worst-case time?
Test #2 Login: Initials: 4
[1 point] From Earth, what star has the largest known proper motion?
[8 points] Given the following class definition:
class IntTree {
public IntTree (int data, IntTree left, IntTree right) {
this.data = data; this.left = left; this.right = right; }
public final int data;
public IntTree left, right; }
we want to define a destructive mergeRight routine that combines the values in two search trees. The trees here are binary search trees with a sentinel node (whose data field is irrelevant) at their root. The sentinel¡¯s left child is the tree containing the data in each case. One of the trees is right-leaning¡ªessentially an ordered list. For example, if T and L contain the trees below the resulting tree is shown on the right. Fill in the method on the next page to fulfill its comment. Feel free to add any auxiliary methods you need. IMPORTANT WARNING: To get the running time specified in the comment, you cannot simply call the standard insertion method on T for each value in L. You need to take advantage of the fact that L is a right-leaning binary search tree.
T: L: mergeRight(T,L): 121 12
3 16 11 3 16
10 14 27 26 1 10 14 27
Test #2 Login: Initials: 5
/** Assuming that T and L are binary search trees each with a single * sentinel tree node, and that all left children in L aside from
* the sentinel are empty (L is “right-leaning”), returns (the
* sentinel of) a binary search tree containing the original elements * of T and L. The operation is destructive, and creates no
* new nodes. In the worst case, it takes time linear in the
* total number of items in T and L. */
public static IntTree mergeRight (IntTree T, IntTree L) {
// ADD ANY ADDITIONAL METHODS HERE, IF NEEDED
Test #2 Login: Initials: 6
4. [4 points] Give short answers to the following questions. As before, time estimates refer to asymptotic bounds (O(¡¤ ¡¤ ¡¤), ¦¸(¡¤ ¡¤ ¡¤), ¦¨(¡¤ ¡¤ ¡¤)). Always give the simplest bounds possible (O(f (x)) is ¡°simpler¡± than O(f(x) + g(x)) and O(Kf(x))).
a. A certain hash table on strings uses a very fast hash function: it simply takes the first and last characters in a string and interprets them as a two-digit number¡ªspecifically (assuming that all characters are lower-case letters) a two-digit base-26 number, so that ¡°algebra¡± hashes to 0, ¡°add¡± hashes to 3, ¡°bad¡± to 29, and so forth. Each hash bucket is represented by a linked list. Assuming that keys are distributed evenly by this hash function, what is the worst-case time (including the time required to compute the hash function) for inserting one new key, as a function of N, the maximum number of keys in the table?
b. How does your answer to (a) change if we change the hash function so that it considers up to the first log26 N characters (or the length of the key, whichever is smaller), keeping other assumptions the same? (Ignore the time to compute log26 N.)
Test #2 Login: Initials: 7
c. A heap data structure containing integers is represented as an array. Assuming that the heap is initially empty, show that for any N, there is a sequence of distinct N values that can be added to the heap in total time O(N).
d. For Java int variable x, what is (~x) – ((-1) ^ x)?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com