View Assessment Result: Multiple Choice Quiz 11



Your performance was as follows:

1.
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 will be almost instantaneous.
(b) It may fail to find an element that is present.
(c) It will be noticeably slow.
(d) It may "find" an element that is no longer there.

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.
What is the purpose of using memoizing?

(a) To improve the memory requirements of hash tables
(b) To store return values of functions, in order to avoid recomputation
(c) To speed up access in a hash table
(d) To eliminate recursion in computing function values

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



3.

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

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.
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) Ascending order
(b) Blocks of items in ascending order
(c) Descending order
(d) Random order

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



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

(a) a prime
(b) anything but a prime
(c) a perfect square
(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



6.
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 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).
(c) They go into the slots that result from recomputing all the hash values.
(d) The resize command for the underlying array will take care of everything.

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



7.
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



8.
The appropriate return type for a search function on a chaining hash table is

(a) a Boolean
(b) a pair consisting of a Boolean and an iterator
(c) a list node
(d) an iterator

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



9.
For a templated hash table to cope with some user-defined key type Thing, the user has to specify

(a) the type Thing and a hash function for Thing.
(b) just the type Thing.
(c) just the size of the table, templates take care of the rest.
(d) the type Thing, a hash function for Thing, and equality testing for Thing.

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



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

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



Go to top of assessment.

Total score: 100.00