[理工] [資結]-台大97-電機
Suppose that we have a hash table with 19 buckets, where each
bucket holds only one key-element pair. The hash function is
h(key) = (key % 19). Consider the quadratic probing scheme.
(關於quadratic probing的敘述就省略了,不然好多字 囧)
A. This scheme will check every bucket eventually with t<=9
B. If the hash table contains 14 elements, an unsuccessful
look-up checks less than 3 buckets on average.
C. A successful look-up takes theta(1) time on average when the
hash table is half-full.
D. A successful look-up takes theta(logn) time in the worst case
when the hash table is half-full with n pairs.
E. Deleting an element given its key can be done in theta(1) time
in the worst case.
不好意思, 題目有點長= =
主要想問(C)選項怎麼算, 有請強者(_ _)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.189.59