Deck 7: Sets and Maps

Question 1

Using a hash table enables us to retrieve an item in O(n²) time.

Answer 1

False

Question 2

Collections implementing the Set interface must contain unique elements.

Answer 2

True

Question 3

Sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

Answer 3

True

Question 4

With respect to hash tables, if there are no collisions, the performance for search and retrieval is O(n), regardless of table size.

Question 5

Although you cannot reference a specific element of a Set, you can iterate through all its elements using an Iterator object.

Question 6

The basis of ____________________ is to transform the item's key value to an integer value which will then be transformed into a table index.

Question 7

In ____________________ addressing, each hash table element (type Object) references a single key-value pair.

Question 8

The Java API implements the Set using a(n) ____________________.

Question 9

The problem with ____________________ probing is that it tends to form clusters of keys in the table, causing longer search chains.

Question 10

Mathematically, a(n) ___________________ is a set of ordered pairs whose elements are known as the key and the value.

Question 11

An alternative to open addressing is a technique called _____________________.

Question 12

An addressing technique in which each table element references a linked list that contains all the items that hash to the the same table index is referred to as _________________________.

Question 13

In ____________________ addressing, search chains can overlap, so a search chain may include items in the table that have different starting values.

Question 14

An advantage of ____________________ is that you can store more elements in the table than the number of table slots (indexes).

Question 15

One requirement on the key-value pair for a Map object is to implement the interface ____________________, which is an inner interface of interface Map.

Question 16

Method ____ creates a set view of the entries in a Map.

A) setIterator
B) getValue
C) getKey
D) entrySet

Question 17

____ occur(s) because you can only store one key-value pair in a given array element.

A) Quadratic probing
B) Hashing
C) Collisions
D) Backtracking

Question 18

If we compare hash table performance with binary search of a sorted array, the number of comparisons required by binary search is ____.

A) O(1)
B) O(n)
C) O(log₂n)
D) O(log n)

Question 19

The intersection of sets A, B is a set ____.

A) whose elements belong to A but not to B
B) whose elements belong to both A and B
C) whose elements belong either to A or B or to both A and B
D) set where every element of A is also an element of B

Question 20

Which of the following is a commonly used method of the Set interface?

A) boolean ContainsAll(Collection<E> coll)
B) boolean retain<E>(E obj)
C) boolean remove(Collection coll)
D) boolean Empty()

Question 21

With respect to the Map interface, the ____ method returns the current value associated with a given key.

A) isEmpty
B) insert
C) put
D) get

Question 22

With respect to the Map interface, the ____ method either inserts a new mapping or changes the value associated with an existing mapping.

A) get
B) isEmpty
C) put
D) insert

Question 23

Which of the following is an example of a map?

A) { (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B, Bill) }
B) { (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill) }
C) { (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (J, Jane) }
D) { (S, Sam), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill) }

Question 24

The union of two sets A, B is a(n) ____.

A) set whose elements belong to both A and B
B) set whose elements belong to A but not to B
C) set where every element of A is also an element of B
D) set whose elements belong either to A or B or to both A and B

Question 25

The following is an algorithm for ____.
Compute the index by taking the item's hashCode() % table.length.
If table[index] is null
The item is not in the table.
Else if table[index] is equal to the item
The item is in the table.
Else
Continue to search the table by incrementing the index until either the item is found or a null entry is found.

A) rehashing
B) accessing an item in a hash table
C) deleting an item in a hash table
D) inserting an item in a hash table

Question 26

A NavigableSet (NavigableMap) allows the programmer to create _____________ of a Set (Map).

Question 27

A NavigableSet (NavigableMap) can be traversed in reverse order.