DSA Quiz 5 Questions with Solutions

DSA Quiz 5


You 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