CSE310 Exam 2 2025 Questions and
Answers
Minimum and Maximum - ANSWER-Requires Θ(n) in all cases. Faster to run
both simultaneously rather than separately.
Selecting iᵗʰ Smallest - ANSWER-Average-case of Θ(n).
Worst-case of Θ(n²).
Binary Search Tree - ANSWER-Worst Case:
Θ(lg n) to add
ΘIlg n) to retrieve
Direct Address Table - ANSWER-A table that has a single location for every
possible value to be stored.
Pros of Direct Address Table - ANSWER-Searching and retrieving takes a
constant amount of time.
Only look in one location.
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 1
, Requires Θ(1) to store or retrieve.
Cons of Direct Address Table - ANSWER-Requires storage for every possible
value, not just the actual number of values needed.
Storage has to be initialized, which takes Θ(n) due to the fact that n is the number
of possible values.
Hash Table - ANSWER-A data structure that stores values similar to a direct
addressing table with fewer options for where elements can go which keeps storage
requirements down, but still needs to have enough memory to store all of the
values. A hash function 𝘩 is used to determine which location in the table an
element goes in.
Independent Uniform Hashing - ANSWER-An ideal hash will appear to randomly
assign each element to any given hash table location with equal probability (has to
be deterministic so that the location is the same for an element every time).
Pros of Independent Uniform Hashing - ANSWER-Requires less storage than a
direct addressing table.
Don't need to come up with a different hash function for each data set.
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 2
Answers
Minimum and Maximum - ANSWER-Requires Θ(n) in all cases. Faster to run
both simultaneously rather than separately.
Selecting iᵗʰ Smallest - ANSWER-Average-case of Θ(n).
Worst-case of Θ(n²).
Binary Search Tree - ANSWER-Worst Case:
Θ(lg n) to add
ΘIlg n) to retrieve
Direct Address Table - ANSWER-A table that has a single location for every
possible value to be stored.
Pros of Direct Address Table - ANSWER-Searching and retrieving takes a
constant amount of time.
Only look in one location.
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 1
, Requires Θ(1) to store or retrieve.
Cons of Direct Address Table - ANSWER-Requires storage for every possible
value, not just the actual number of values needed.
Storage has to be initialized, which takes Θ(n) due to the fact that n is the number
of possible values.
Hash Table - ANSWER-A data structure that stores values similar to a direct
addressing table with fewer options for where elements can go which keeps storage
requirements down, but still needs to have enough memory to store all of the
values. A hash function 𝘩 is used to determine which location in the table an
element goes in.
Independent Uniform Hashing - ANSWER-An ideal hash will appear to randomly
assign each element to any given hash table location with equal probability (has to
be deterministic so that the location is the same for an element every time).
Pros of Independent Uniform Hashing - ANSWER-Requires less storage than a
direct addressing table.
Don't need to come up with a different hash function for each data set.
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 2
