View Assessment Result: Multiple Choice Quiz 11



Your performance was as follows:

1.
Suppose hash() is a hash function. The main idea behind hashing is to use a key k to store a value v in which position of a table?

(a) hash(k)
(b) hash() (a random position computed by the hash function using k)
(c) hash(k,v)
(d) hash(v)

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



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

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

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 never output a prime number.
(b) It should produce apparently random values for given items.
(c) It should only output prime numbers.
(d) It should produce small outputs for small inputs.

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

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



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

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

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



6.
What is the purpose of using memoizing?

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

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



7.

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

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.
Which of the following correctly indicates where keys and associated values are stored in hash tables when open addressing is used?

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

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.
The appropriate return type for a search function on a chaining hash table is

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

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



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

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



Go to top of assessment.

Total score: 90.00