Exam (elaborations)
DSA Quiz 5 Questions with Solutions
- Module
- Institution
Exam of 15 pages for the course DSA at DSA (DSA Quiz 5)
[Show more]
Seller
Follow
Dreamer252
Reviews received
Content preview
DSA Quiz 5You have just written a class for your new program, for a type of object that will be
stored in a Set. What method must you override for this to work correctly?
A both .equals() and .toString() must be overridden
B .toString() - to be able to print
C .equals() - to be able to check
D equality
E .compareTo() - to be able to compare - answerD
The Java doc for the Object class specifies one must make sure that "If two objects are
equal according to the equals(Object) method, then calling the hashCode method on
each of the two objects must produce the same integer result." Which of the following
best describes why this is necessary?
A If hashCode() returns diff values, then HashMap won't work bc one of the Objects is
likely to run off the end of the table causing an IndexOutOfBounds.
B Not recommended to make this mistake, but Java will fix automatically by converting
one Object instance into the other to ensure Java's HashMap works.
C If equals() returns true, the objects are the same. They need to hash to the same val
so they can be correctly ins/del in the table using either object.
D If hashCode() returns diff values for equal objects, Java's HashMap will still work, but
the performance dec significantly bc the whole table is scanned for dup - answerC
Suppose you have a hash table with a capacity of 10, and you are inserting integers into
this table. The hash function and second hash
function that will be used are:
hash(int key) = key % 10
hash2(int key) = 1 + (key % 3)
Insert the following elements into the table: 5, 15, 8, 18, 11, 35.
What index in the table does the 35 end up being inserted into?
For your collision resolution strategy, you should use Double Hashing where hash1(k)+
n * hash2(k) as n increments by 1, starting at 0.
A index 0
B index 1
, C index 2
D index 3
E index 4
F index 5
G index 6
H index 7
I index 8
J index 9 - answerE
Suppose you have a hash table with a capacity of 10, and you are
inserting integers into this table. The hash function that will be used is:
hash(int key) = key % 10;
Insert the following elements into the table: 5, 25, 8, 65, 18, 11, 35. What index in the
table does the 35 end up being inserted into? For your collision resolution strategy, you
should use the following: Use linear probing, except you should offset by 3 indices on
every collision instead of 1. For example, if the key hashes to index 5 and there is a
collision, the next place to look is index 8, and so on.
A index 0
B index 1
C index 2
D index 3
E index 4
F index 5
G index 6
H index 7
I index 8
J index 9 - answerD
In a hash table using linear probing, there is a difference between those spots which
have never been used and those spots which have previously been used but no longer
contain an item. Which function(s) could not work without this difference?
A remove
B insert
C retrieve
D size - answerC
When storing key/value pairs in a hash table, what properties
are DESIRABLE in a hash function? (Do not select the properties that a
hash function *must* have, select those beyond the minimum properties.)
Select from these options:
A. Deterministic
B. Fast
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Dreamer252. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £9.74. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
77858 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now