View Assessment Result: Multiple Choice Quiz 11



Your performance was as follows:

1.
In the context of hashing, what is meant by a collision?

(a) Two key/value pairs have the same value.
(b) Two different keys hash to the same slot.
(c) The hash function returns a value larger than the table size.
(d) The insertion algorithm cannot find an empty slot in the table.

Correct answer is (b)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (b) No Feedback



2.
Which of the following is true about a good hash function?

(a) It should produce apparently random values for given items.
(b) It should never output a prime number.
(c) It should produce small outputs for small inputs.
(d) It should only output prime numbers.

Correct answer is (a)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (a) No Feedback



3.

Suppose a user-defined hash function has the following prototype.

      size_t  hash( const Thing& x );

Suppose further that it produces values of size up to 32 bits. To use this function with a hash table of size m, the user should



(a) compute hash( x ) / m
(b) compute hash( x ) % m
(c) modify x until a value less than m appears
(d) call the function repeatedly until a value less than m appears

Correct answer is (b)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (b) No Feedback



4.
Which of the following indicates the reaction time, in general, for searching in an open addressing hash table of size 1,000,000 with a load factor of 0.9?

(a) It may "find" an element that is no longer there.
(b) It will be almost instantaneous.
(c) It will be noticeably slow.
(d) It may fail to find an element that is present.

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (c) No Feedback



5.

Consider the following outline of a memoized function.

      int  f( int x ) { ... }

How many steps does it take to make 10000 calls to f on input x = 1000?



(a) About 10000 steps, plus computing f(1000)
(b) About 10000 times the number of steps used in computing f(1000)
(c) A small, constant number of steps
(d) About 10000 steps

Correct answer is (a)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (a) No Feedback



6.
In order for the division method to work in the context of hashing, the table size should be

(a) anything but a prime
(b) a power of two
(c) a perfect square
(d) a prime

Correct answer is (d)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (d) No Feedback



7.
When the load factor in a hash table becomes too high, the table must be resized. What should happen with the old entries?

(a) All the old entries should go into the same positions they occupied in the old table.
(b) The resize command for the underlying array will take care of everything.
(c) They go into the slots that result from recomputing all the hash values.
(d) The old entries should be spread out in the new table (e.g., if the new table is twice as large, an old entry at slot p should be moved to slot 2*p).

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (c) No Feedback



8.
Which of the following correctly indicates where keys and associated values are stored in hash tables when chaining is used?

(a) Each key is stored in the table, and the associated value is stored in a linked list.
(b) The keys are stored in the table, and the associated values are stored in the list header.
(c) Each key/value pair is stored in a node of a linked list.
(d) The keys are stored in the list header, and the associated values are stored in the linked lists.

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (c) No Feedback



9.
Which of the following correctly indicates where keys and associated values are stored in hash tables when open addressing is used?

(a) Each key is stored in a slot in the table, and the associated value is stored in one of the slots that follow.
(b) The keys are stored in the list header, and the associated values are stored in linked lists.
(c) Each key/value pair is stored in the table.
(d) The values are stored in a slot in the table, and keys are stored in the slots that follow.

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (c) No Feedback



10.

Consider the following definition of a function hash.

   size_t  hash( const char *str )
      {
          size_t  h = 0;
          for( ; *str != '0'; str++ )
               h = h*256 + *str;
      }

What, if anything, is wrong with hash as a hash function for null-terminated strings?



(a) It is very slow to compute.
(b) If the string is very long, there will be overflow.
(c) It only takes into account the last few characters long strings.
(d) Nothing

Correct answer is (c)

Your score on this question is: 10.00

Feedback:
   See section 2.4.1 of the course notes.
   (c) No Feedback



Go to top of assessment.

Total score: 100.00