CSE 310 COMPREHENSIVE PAPER 2026
COMPLETE SOLUTIONS GUARANTEED
⫸ Consider the hashing function h(k) = k mod m.
What is a good value for m? Answer: A prime number.
⫸ Which of the following statements are true regarding direct
address tables?
Statement 1: If the universe U is large, storing a table of size |U| may
be impractical.
Statement 2: Often, most of the space allocated to table T is wasted as
the set K of keys actually stored is small. Answer: Both of the
statements are true.
Storing a large table is impractical because one will be allocating a
large table, where here may be collisions or often times, unused space.
If for example, the set is [1 8 10 12 20], one may allocate memory of
size 20 and store each at value - 1, there will be 20 spaces allocated
for only 5 elements, leaving 15 spaces unused.
⫸ What is a hash table? Answer: A generalization of an ordinary
array where a function of key is used as the index instead of using key
as index directly.
,⫸ Keys 5, 4, 6, 1, 2 are mapped to a hash table of size 3 with hash
function h(k) = k mod 3. If collisions are resolved by separate
chaining, what are the values of a, b, c, d, e respectively as shown
below?
T
0 -> a -> /
1 -> b -> c -> /
2 -> d -> e -> / Answer: 6, 4, 1, 5, 2
⫸ Insert keys 7, 10, 25, 12, 17, 34 into a hash table of size 7 using
open addressing, with the hash function h(k, i) = (k + i) mod 7 and
linear probing to resolve collisions. What does the final array look
like? Answer: [7, 34, EMPTY, 10, 25, 12, 17]
⫸ What is true about hash tables? Answer: Collisions can happen
even when |K| <= m where K is the number of keys and m is the size
of hash table.
Deleting a key from hash table is O(1) if collisions are resolved by
chaining and if the lists are doubly linked.
⫸ Which of the following statements are true?
, Statement 1: With a different interpretation, hash functions can be
used even when the keys are strings.
Statement 2: Hash functions should be fast, i.e, O(1) to compute.
Answer: Both statements are true.
⫸ What is a collision? Answer: When two keys hash to the same
value?
⫸ Considering the case of separate chaining in hashing. Which of the
following are true?
Statement 1: Performance of the dictionary operations is not good
because of the use of a linked list.
Statement 2: The chain is not maintained in sorted order. Answer:
Both statements are true.
The use of a linked list has little effect towards the performance of
dictionary operations.
The element is simply inserted at the end of the chain, regardless of
order.
COMPLETE SOLUTIONS GUARANTEED
⫸ Consider the hashing function h(k) = k mod m.
What is a good value for m? Answer: A prime number.
⫸ Which of the following statements are true regarding direct
address tables?
Statement 1: If the universe U is large, storing a table of size |U| may
be impractical.
Statement 2: Often, most of the space allocated to table T is wasted as
the set K of keys actually stored is small. Answer: Both of the
statements are true.
Storing a large table is impractical because one will be allocating a
large table, where here may be collisions or often times, unused space.
If for example, the set is [1 8 10 12 20], one may allocate memory of
size 20 and store each at value - 1, there will be 20 spaces allocated
for only 5 elements, leaving 15 spaces unused.
⫸ What is a hash table? Answer: A generalization of an ordinary
array where a function of key is used as the index instead of using key
as index directly.
,⫸ Keys 5, 4, 6, 1, 2 are mapped to a hash table of size 3 with hash
function h(k) = k mod 3. If collisions are resolved by separate
chaining, what are the values of a, b, c, d, e respectively as shown
below?
T
0 -> a -> /
1 -> b -> c -> /
2 -> d -> e -> / Answer: 6, 4, 1, 5, 2
⫸ Insert keys 7, 10, 25, 12, 17, 34 into a hash table of size 7 using
open addressing, with the hash function h(k, i) = (k + i) mod 7 and
linear probing to resolve collisions. What does the final array look
like? Answer: [7, 34, EMPTY, 10, 25, 12, 17]
⫸ What is true about hash tables? Answer: Collisions can happen
even when |K| <= m where K is the number of keys and m is the size
of hash table.
Deleting a key from hash table is O(1) if collisions are resolved by
chaining and if the lists are doubly linked.
⫸ Which of the following statements are true?
, Statement 1: With a different interpretation, hash functions can be
used even when the keys are strings.
Statement 2: Hash functions should be fast, i.e, O(1) to compute.
Answer: Both statements are true.
⫸ What is a collision? Answer: When two keys hash to the same
value?
⫸ Considering the case of separate chaining in hashing. Which of the
following are true?
Statement 1: Performance of the dictionary operations is not good
because of the use of a linked list.
Statement 2: The chain is not maintained in sorted order. Answer:
Both statements are true.
The use of a linked list has little effect towards the performance of
dictionary operations.
The element is simply inserted at the end of the chain, regardless of
order.
