Berkeley COMPSCI 61B - CS 61B - Final Exam (10 pages)

Previewing pages 1, 2, 3 of 10 page document View the full content.
View Full Document

CS 61B - Final Exam



Previewing pages 1, 2, 3 of actual document.

View the full content.
View Full Document
View Full Document

CS 61B - Final Exam

122 views

Exam


Pages:
10
School:
University of California, Berkeley
Course:
Compsci 61b - Data Structures
Data Structures Documents

Unformatted text preview:

University of California at Berkeley Department of Electrical Engineering and Computer Sciences Computer Science Division Spring 2005 Jonathan Shewchuk CS 61B Final Exam This is an open book open notes exam Electronic devices are forbidden on your person including cell phones and laptops Please put them on the desk at the front of the room and turn your cell phone off or risk losing a point Do not open your exam until you are told to do so Name Login Lab TA Lab time Do not write in these boxes Problem Possible Score 1 Miscellany 8 2 Data structures 6 3 Sorting 12 4 Augmented trees 5 5 Asymptotic analysis 6 6 Amortized analysis 6 7 Index sort 7 Total 50 1 Name Login Problem 1 2 8 points A Miscellany a 2 points Consider the following method to make all the nodes in a doubly linked list circularly linked with sentinel available for garbage collection Recall that head references the sentinel Assume that listnodes are referenced only by other listnodes in the same list public void garbageList if size 0 head next prev null head prev next null head next null head prev null head null Erase references to sentinel Erase references to other nodes Are the lines marked with question marks necessary to ensure that all the listnodes are available to be garbage collected Explain b 1 point Recall that a SimpleBoard object stores an 8 8 array grid in which each cell has value 0 1 or 2 Suppose you want to store lots of SimpleBoards in a hash table Can you think of a reason why the following hash code will not distribute SimpleBoard objects evenly among the buckets Assume the compression function is good public class SimpleBoard private int grid public int hashCode int code 0 for int i 0 i 8 i for int j 0 j 8 j code code i j grid i j return code Name Login 3 c 2 points Every word falls into one of eight categories nouns verbs pronouns adjectives adverbs prepositions conjunctions and interjections Suppose you want to be able to look up the category of any English word in O 1 time You



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view CS 61B - Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 61B - Final Exam and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?