Deck 10: Sets and Maps

Question 1

Searching for a particular value in a sequential container is generally an O(__________) process.

Answer 1

n

Question 2

You retrieve an object from a map by specifying its __________.

Answer 2

key

Question 3

What mathematicians call a(n) __________ can be thought of as a collection of objects.

Answer 3

set

Question 4

What is the result of performing the following operation?
{1, 3, 5, 7} - {2, 3, 4, 5}

A) {-1, 0, 1, 2}
B) {1, 7}
C) {2, 4}
D) {1, 0, -1, -2}

Question 5

There are no set union, set intersection, or set difference member functions in the C++ set class.

Question 6

Suppose you are given two sets:
Set1 = {Apples, Peaches, Pineapples}
Set2 = {Apples, Grapes, Peaches}
The result of set1* set2 is __________.

A) {Peaches}
B) {Apples}
C) {Apples, Peaches}
D) {Apples, Grapes, Peaches, Pineapples}

Question 7

The vector and set both implement the common requirements of the container classes.

Question 8

The __________ is the same as the set except that it does not impose the requirement that the items be unique.

Question 9

If the set fruits is
{"Apples", "Grapes", "Oranges", "Peaches", "Pears", "Pineapples", "Tomatoes"},
Then
Lower_bound("Oranges")
Would return an iterator to "__________", and
Upper_bound("Pineapples")
Would return an iterator to "Tomatoes".

A) Apples
B) Grapes
C) Oranges
D) Peaches

Question 10

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

Question 11

Items are stored in a map as ordered by their __________ function.

Question 12

Because the map class overloads the subscript operator such that the key is used as an index, a map is also known as a(n) __________ array.

A) random
B) relational
C) sequential
D) associative

Question 13

Which of the following lines corrects the error in the Map class function?

A) Value_Type operator[ ](const Key_Type& key)
B) Value_Type& operator( )(const Key_Type& key)
C) std::pair<iterator, bool> ret =
the_set.insert(Entry_Type(key, Value_Type()));
D) std::pair<iterator, bool> ret =
the_set.insert(Entry_Type(key, ()));

Question 14

The default value for the Compare template parameter is the Key_Type's __________ operator.

A) less-than-or-equal-to
B) less-than
C) greater-than
D) greater-than-or-equal-to

Question 15

The subscript operator is defined for the multimap.

Question 16

The goal of the hash table is to access an entry based on its __________ value, not its location.

Question 17

Using a hash table enables us to retrieve an item in __________.

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

Question 18

The statement
int index = uni_char % __________;
computes an array index between 0 and 499 for a Unicode character.

Question 19

To reduce the clustering of indexes in hash tables, __________ probing uses increments that form the series:
(1 + 2²+ 3²; + · · ·).

A) constant
B) linear
C) quadratic
D) exponential

Question 20

An alternative to open addressing is a technique called __________, in which each table element references a linked list that contains all the items that hash to the same table index.

Question 21

__________ hashing grows linked lists to store key values associated with a particular index.

Question 22

Consider the formula for evaluating the number of hash table comparisons:
$c=1 / 2^{(1+1 /(1-L))}$ , where c = the number of comparisons and L = the load factor.
Given that a hash table of size 100,000 contains 20,000 items, how many comparisons are expected in a linear probe for an item?

A) .5
B) .625
C) 1.125
D) 3

Question 23

Worst-case performance for a hash table or a binary search tree is O(__________).

A) 1
B) log n
C) n
D) n log n

Question 24

Static data members must be initialized inside the class declaration.

Question 25

A hash function that evaluates indexes based on an original int value modulo the size of the hash table tends to uniformly distribute keys.