- | Page
CMSC 256 FINAL EXAM TERMS
Question : Sorted Array Based Implementations Worst
Case Graphs
Addition (ALL) O(n)
Removal (Rats) O(n)
Retrieval (Run) O(log n)
Traversal (There) O(n)
CORRECT ANSWER : - Addition - Removal - Retrieval
- Traversal
Question : What parts does hashing consist of
CORRECT ANSWER : A hash code and a compression
function
Question : What is hashing
- | Page
CORRECT ANSWER : Hashing is a technique in comp
sci to efficiently store and retrieve data from memory using a unique identifier called a hash code
Question : Hash codes
CORRECT ANSWER : - Unique Identifier generated
from the input data - Used to store and retrieve data from memory - Good Hash code should produce a unique code for each input and be easy to compute
Question : What is Polynomial Accumulation
CORRECT ANSWER : - A technique used to generate a
hash code for a string
Question : Polynomial accumulation formula for strings
CORRECT ANSWER : hash = s[0]*31^(n-1) +
s[1]*31^(n-2) + ... + s[n-1]*31^0 where s = string and n is the length of string
Question : Collision Resolution
- | Page
CORRECT ANSWER : Technique used to handle cases
where two different inputs produce the same hash code code
Question : Different collision strategies include :
CORRECT ANSWER : Chaining, Linear probing,
quadratic probing, double hashing
Question : What does the collision resolution strategy
chaining do?
CORRECT ANSWER : Creates a linked list to store
multiple values with the same hash code
Question : What does the collision resolution strategy
Linear Probing do?
CORRECT ANSWER : If there's a collision for the
position of the key value then the linear probing technique assigns the next free space to the value
- | Page
Question : What does the collision resolution strategy
Quadratic Probing do?
CORRECT ANSWER : Collision is resolved by finding
the new position of the element to be inserted in hash table with the help of quadratic probing hash function
Question : What does the collision resolution strategy
Double hashing do?
CORRECT ANSWER : it works by using two hash
functions to compute two different hash values for a given key, The first hash function is used to compute the initial hash value, and the second hash func is used to compute the step size for the probing sequence
Question : compression function
CORRECT ANSWER : Used to map the hash code to a
specific index in.the hash table, should distribute the hash codes evenly across the hash table to minimize collisions