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

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



2.
If a hash table of size m contains n items, what is the load factor of the table?

(a) m - n
(b) m/n
(c) n/m
(d) n + m

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



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

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

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 a chaining hash table of size 1,000,000 with a load factor of 0.9?

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

Correct answer is (d)

Your score on this question is: 0.00

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



5.
In searching for an entry with key k in an open addressing hash table, the slot p = hash(k) is computed, after which it is necessary to

(a) check only if the entry in slot p has key k
(b) traverse a linked list to check if any entry there has key k
(c) compute p + k to find the right position for the entry
(d) check if the entry in slot p has key k, then p+1 if necessary, then p+2, and so forth.

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



6.

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 steps
(c) About 10000 times the number of steps used in computing f(1000)
(d) A small, constant number of steps

Correct answer is (a)

Your score on this question is: 0.00

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



7.
What order should be expected when the occupied slots in an open addressing hash table with load factor 0.9 are printed in the order in which they appear in the table?

(a) Random order
(b) Ascending order
(c) Descending order
(d) Blocks of items in ascending order

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



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

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

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



9.
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: 0.00

Feedback:
   See section 2.4.1 of the course notes.
   (a) 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 += *str;
      }

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



(a) If the string is very long, there will be overflow.
(b) All permutations of a word hash to the same slot.
(c) It makes no sense to add characters.
(d) Nothing

Correct answer is (b)

Your score on this question is: 0.00

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



Go to top of assessment.

Total score: 60.00