Deck 11: Sets and Dictionaries

Question 1

Two keys that hash to the same index is called a collision.

Answer 1

True

Question 2

The AbstractSet class is a subclass of AbstractBag .

Answer 2

False

Question 3

A set is similar to a bag, but it contains unique data items and additional methods.

Answer 3

True

Question 4

Much like a list, a set contains items that are in a particular order.

Question 5

The __sub__ method of the set class returns a set containing items in s1 that are not in s2.

Question 6

A hashing function acts on a given key by returning its absolute position in an array.

Question 7

In the Entry class for a dictionary, comparisons are done using the value item in each entry.

Question 8

Python supports multiple inheritance, so a class can have more than one parent class.

Question 9

The dictionary constructor has two optional collection arguments: a collection of keys and a collection of corresponding values.

Question 10

If a hashing function runs in constant time, insertions, accesses, and removals of the associated keys are O(1).

Question 11

The AbstractSet class is a subclass of AbstractCollection because AbstractSet introduces new instance variables for data.

Question 12

If S1 and s2 are sets, the expression s1.issubset(s2) returns True if s2 is a subset of s1 .

Question 13

As the density, or number of keys relative to the length of an array decreases, so does the probability of hashing collisions.

Question 14

In Python's dict type, values are inserted or replaced at a given location using the index operator {} .

Question 15

The entries in a dictionary consist of a key, a value, and an index.

Question 16

Array-based implementations of sets and dictionaries do not perform well.

Question 17

Two strings that are anagrams will return a unique integer value when the sum of the ASCII values is calculated.

Question 18

A small load factor and an array length that is a prime number increases the chances for a hashing collision.

Question 19

To reduce the probability of collisions with hashes, you can decrease the array length.

Question 20

With a set, the difference and subset operations are not symmetric.

Question 21

The standard Python hash function always returns a unique positive integer.

Question 22

The data in sets and dictionaries are ordered by position by default.

Question 23

Which method in the interface for a dictionary collection returns an iterator on the key/value pairs in the dictionary?

A) keys()
B) entries()
C) pairs()
D) values()

Question 24

In the hashing implementation of a set, self.index refers to the index of the chain in which the node was just located, or is -1 otherwise.

Question 25

Which method is specific to a set compared to a bag?

A) remove
B) __str__
C) add
D) __sub__

Question 26

In the hashing implementation of a set, the Bag class is used to represent an item and a pointer to the next item in a chain.

Question 27

The simplest implementations of sets are subclasses of which other class?

A) bags
B) queues
C) stacks
D) lists

Question 28

In the hashing implementation of a dictionary, the data field of each node in a chain contains an Entry object.

Question 29

What is the value of set S after the following operations?
S = set([ 3, 9, 6 ])
S.add(6)
S.add(4)
S.remove(6)

A) {3 9 6 4}
B) {3 9 4}
C) {3 9 6}
D) {3 4 6 9}

Question 30

What strategy for implementing sets attempts to approximate random access into an array for insertions, removals, and searches?

A) indexing
B) linking
C) hashing
D) keying

Question 31

Which of the following is true about sets?

A) the items in a set are arranged in order
B) the difference and subset operations on a set are symmetric
C) there are no duplicate items in a set
D) there is no standard set class in Python

Question 32

For a key value of 93 and a hashing function of key % 46 , what is the index into the array?

A) 1
B) 2
C) 46
D) 47

Question 33

For a given set s , which method returns True if item is in s , or False otherwise.

A) s.__contains__(item)
B) s.__iter__(item)
C) s = set()
D) S1.__sub__(s2)

Question 34

In the code for the __sub__ method for the AbstractSet class, what is the missing code? def __sub__(self, other):
Difference = type(self)()
For item in self:
If not item in other:
< missing code >
Return difference

A) difference.remove(item)
B) intersection.add(item)
C) difference.add(item)
D) return(item)

Question 35

In the implementation of the AbstractDict class, which four methods have the same implementation for all dictionaries?

A) keys, values, __add__, __eq__
B) entries, values, __init__, __str__
C) keys, values, entries, get
D) get, __add__, keys, __init__

Question 36

In the code for the __iter__ method for the ArrayDict class, what is the missing code? def __iter__(self):
Cursor = 0
While cursor < len(self):
Yield self.items[cursor].key
< missing code >

A) return(self.items[ cursor ])
B) cursor -= 1
C) return(self.items[ key ])
D) cursor += 1

Question 37

For key values of 84 and 108 and a hashing function of key % 12 , what is the result?

A) indexes of 7 and 9
B) indexes of 0 and 1
C) a collision
D) indexes of 12 and 14

Question 38

In the code for the __init__ method in the Entry class or a dictionary, what is the missing code? def __init__(self, key, value):
< missing code >
Self.value = value

A) key = self.key
B) self.key = key
C) value = self.key
D) self.key = value

Question 39

What is the performance value of the array-based implementations of sets and dictionaries?

A) O( n ²)
B) O( n )
C) O ⁿ
D) O(1)

Question 40

Which of the following is a subset of Set A if Set A is {19 4 26 8}?

A) None of the choices are subsets of Set A
B) {19 4 26 8 0}
C) {4 8 19 26 44}
D) {}

Question 41

What happens when two keys map to the same index after a hashing function has been applied?

A) the array is lengthened
B) a collision occurs
C) the second item is mapped to the next cell
D) the hash is reapplied with a random value

Question 42

What strategy does the hashing implementation of a dictionary use?

A) a binary search tree
B) quadratic probing
C) linear probing/bucket
D) bucket/chaining

Question 43

Which of the following is the best array length to reduce the probability of collisions given the set [ 8, 6, 18, 9, 14, 23 ]?

A) 9
B) 8
C) 11
D) 12

Question 44

Referring to the keysToIndexes function, what is the result of the following statement? keysToIndexes([ 39, 18, 4, 51, 6, 28 ], 9)

A) [ 4, 1, 5, 7, 6, 2 ]
B) [ 3, 0, 4, 6, 6, 1 ]
C) [ 2, 0, 3, 5, 5, 0 ]
D) [ 8, 3, 6, 0, 1, 4 ]

Question 45

When considering an insertion into a set using a hash function and linear probing, which of the following is defined as the position where the item should go if the has function works perfectly?

A) absolute index
B) probe index
C) zero index
D) home index

Question 46

In the algorithm for the __contains method of the hashing implementation of sets, what is the first step in the algorithm?

A) set foundNode to table[ index ]
B) set priorNode to foundNode
C) set index to the home index of the item
D) set foundNode to foundNode.next

Question 47

Referring to the keysToIndexes function, what is the result of the following statement? keysToIndexes([ 39, 18, 4, 51, 6, 28 ], 17)

A) [ 6, 2, 5, 1, 7, 12 ]
B) [ 7, 3, 6, 2, 8, 13 ]
C) [ 4, 2, 3, 1, 5, 10 ]
D) [ 5, 1, 4, 0, 6, 11 ]

Question 48

In which collision-avoidance hashing strategy are the items stored in an array of linked lists in which each item's key locates the bucket where the item is to be inserted?

A) clustering
B) chaining
C) quadratic probing
D) linear probing

Question 49

Which statement is true when considering a hashing strategy and the density of the keys/array length relationship?

A) as the density decreases, the probability of collisions decreases
B) as the density increases, the probability of collisions decreases
C) as the density decreases, the probability of collisions increases
D) as the density increases, the probability of collisions stays the same

Question 50

In the code for the keysToIndexes function, what is the missing code? def keysToIndexes(keys, n):
Return < missing code >

A) list(map(lambda key: key % n, keys))
B) list(map(lambda key: keys, key % n ))
C) map(list(lambda key: key % n, keys))
D) map(list(lambda key % n: keys, key))