CMSC 256 Final Exam ACTUAL UPDATED QUESTIONS AND CORRECT ANSWERS
- Addition (ALL) O(n) Sorted Array Based Implementations Worst Case Graphs
- Removal (Rats) O(n) - Addition
- Retrieval (Run) O(log n) - Removal
- Traversal (There) O(n) - Retrieval
- Traversal
A hash code and a compression function What parts does hashing consist of
Hashing is a technique in comp sci to efficiently store and What is hashing
retrieve data from memory using a unique identifier
called a hash code
- Unique Identifier generated from the input data Hash codes
- Used to store and retrieve data from memory
- Good Hash code should produce a unique code for
each input and be easy to compute
- A technique used to generate a hash code for a string What is Polynomial Accumulation
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]*31^0 Polynomial accumulation formula for strings
where s = string and n is the length of string
Technique used to handle cases where two different Collision Resolution
inputs produce the same hash code code
Chaining, Linear probing, quadratic probing, double Different collision strategies include :
hashing
Creates a linked list to store multiple values with the same What does the collision resolution strategy chaining do?
hash code
If there's a collision for the position of the key value then What does the collision resolution strategy Linear Probing do?
the linear probing technique assigns the next free space
to the value
Collision is resolved by finding the new position of the What does the collision resolution strategy Quadratic Probing do?
element to be inserted in hash table with the help of
quadratic probing hash function
it works by using two hash functions to compute two What does the collision resolution strategy Double hashing do?
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
, Used to map the hash code to a specific index in.the hash compression function
table, should distribute the hash codes evenly across the
hash table to minimize collisions
A graph is a collection of vertices and edges, they What is a graph?
represent relationships between objects
are the objects represented in the graph (nodes) Vertices
are the connections between vertices (lines) edges
Directed and undirected graphs What are the different edge types?
have a value assigned to them Weighted edges
Have no value assigned to them Unweighted Edges
Vertices that are not connected to any other vertices Disconnected graphs
All vertices connected by at least one edge Connected Graphs
All vertices connected by an edge Complete Graphs
A closed path in the graph Cycle
A cycle with no repeated vertices Simple Cycle
A sequence of vertices connected by edges Path
A path with no repeated vertices Simple path
number of edges a vertex contains Degree
max number of edges in a graph with n vertices is n*(n- Maximum number of edges
1)/2.
Contain fewer edges than the maximum Sparse Graphs
close to the maximum number of edges Dense graphs
- Addition (ALL) O(n) Sorted Array Based Implementations Worst Case Graphs
- Removal (Rats) O(n) - Addition
- Retrieval (Run) O(log n) - Removal
- Traversal (There) O(n) - Retrieval
- Traversal
A hash code and a compression function What parts does hashing consist of
Hashing is a technique in comp sci to efficiently store and What is hashing
retrieve data from memory using a unique identifier
called a hash code
- Unique Identifier generated from the input data Hash codes
- Used to store and retrieve data from memory
- Good Hash code should produce a unique code for
each input and be easy to compute
- A technique used to generate a hash code for a string What is Polynomial Accumulation
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]*31^0 Polynomial accumulation formula for strings
where s = string and n is the length of string
Technique used to handle cases where two different Collision Resolution
inputs produce the same hash code code
Chaining, Linear probing, quadratic probing, double Different collision strategies include :
hashing
Creates a linked list to store multiple values with the same What does the collision resolution strategy chaining do?
hash code
If there's a collision for the position of the key value then What does the collision resolution strategy Linear Probing do?
the linear probing technique assigns the next free space
to the value
Collision is resolved by finding the new position of the What does the collision resolution strategy Quadratic Probing do?
element to be inserted in hash table with the help of
quadratic probing hash function
it works by using two hash functions to compute two What does the collision resolution strategy Double hashing do?
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
, Used to map the hash code to a specific index in.the hash compression function
table, should distribute the hash codes evenly across the
hash table to minimize collisions
A graph is a collection of vertices and edges, they What is a graph?
represent relationships between objects
are the objects represented in the graph (nodes) Vertices
are the connections between vertices (lines) edges
Directed and undirected graphs What are the different edge types?
have a value assigned to them Weighted edges
Have no value assigned to them Unweighted Edges
Vertices that are not connected to any other vertices Disconnected graphs
All vertices connected by at least one edge Connected Graphs
All vertices connected by an edge Complete Graphs
A closed path in the graph Cycle
A cycle with no repeated vertices Simple Cycle
A sequence of vertices connected by edges Path
A path with no repeated vertices Simple path
number of edges a vertex contains Degree
max number of edges in a graph with n vertices is n*(n- Maximum number of edges
1)/2.
Contain fewer edges than the maximum Sparse Graphs
close to the maximum number of edges Dense graphs
