# Data Structure Exam Quiz!

27 Questions | Total Attempts: 243  Settings  .

• 1.
In the case of Union by Rank, the rank is increased based on the rank of the tree with:
• A.

Higher rank

• B.

Lower rank

• C.

None of the above

• 2.
Which of the following are true for the amortized time complexity of DSU having N nodes after applying path compression and union by size?
• A.
• B.

Proportional to Ackermann Function

• C.
• D.
• E.

None of the above

• 3.
You are given a list of N elements. You will be asked Q queries. Each query will ask you to print the minimum value in a range [L, R]. Which of the following data structures can be used to provide the fastest query answers (Here, N, and M both are in the range of 10^5)?
• A.

Segment Tree

• B.

Fenwick Tree

• C.

Disjoint Set Union

• 4.
Consider that you are participating in a programming contest. It’s almost the end of the contest. You have one last problem to solve. The problem involves performing an efficient range sum query in a 1D array. The queries contain both range updates and printing the range sum. You only have enough time to implement and debug one of the following algorithms. Which one do you choose?
• A.

Segment Tree

• B.

Fenwick Tree

• C.

Disjoint Set Union

• 5.
Which of the following range queries does a single Fenwick Tree support?
• A.

Multiplication

• B.

GCD

• C.

Matrix Sum

• D.

Minimum

• E.

None of the above

• 6.
In practice, the implementation of Fenwick Tree is similar to that of:
• A.

Segment Tree

• B.

Binary Heap

• C.

Binary Search Tree

• D.

AVL Tree

• E.

None of the above

• 7.
Each integer can be represented as the sum of the integer power of:
• A.

0

• B.

1

• C.

2

• D.

3

• 8.
Consider that we have 10^6 strings. We want to find out the number of unique strings using the polynomial hash function with m = 10^9 + 9. In that case, there will definitely be a collision. To avoid the problem without increasing much time complexity, we can:
• A.

Use a larger m

• B.

Compare the strings if two hash values match

• C.

Use the same hash function twice, each time with different p

• D.

None of the above

• 9.
Given a string of length N, and a pattern of length M to look for, what is the time for pre-processing in the Rabin-Karp Algorithm?
• A.
• B.
• C.
• D.
• E.
• F.
• G.
• H.
• I.
• 10.
Given a string of length N, and a pattern of length M to look for, the time complexity of Rabin-Karp in the worst case:
• A.
• B.
• C.
• D.
• E.
• 11.
Why is it best to use a prime number as a mod in a hashing function?
• A.

Minimize collisions

• B.

Have more common factors with the hash value

• C.

Higher Number of Slots in Hash Table

• D.

Higher chance of existence of inverse

• 12.
Which of the following can be considered as a collision in the Hash table?
• A.

Two key-value pairs that have equal keys but different values

• B.

Two key-value pairs that have different keys and hash to different indices

• C.

Two key-value pairs that have different keys but hash to the same index

• D.

Two key-value pairs that have equal keys but hash to different indices

• 13.
Consider that, you have a hash function that converts each character of a string using a formula, f(x), and then concatenates them to find the hash value. Which of the following formulae will you use to convert each character to ensure no collision (Here, x denotes the ASCII value of the character)?
• A.

F(x) = (3x%5)+3

• B.

F(x) = 5x+12

• C.

F(x) = x/3+1

• 14.
String hashing performs worse than the brute force algorithm when doing a single comparison.
• A.

True

• B.

False

• 15.
While calculating the hash of a string using Polynomial Hash Function, we map each character to 0, 1, 2, … and so on.
• A.

True

• B.

False

• 16.
To reduce collision, the hash function should derive a hash value depending on the pattern that might exist in the strings.
• A.

True

• B.

False

• 17.
We can use the polynomial hash function for calculating the rolling hash given modulo is prime.
• A.

True

• B.

False

• 18.
Since Fenwick Tree stores prefix sum, we cannot get the sum for a specific range that doesn’t involve prefix.
• A.

True

• B.

False

• 19.
Fenwick Tree is slower than the prefix array in answering range sum queries.
• A.

True

• B.

False

• 20.
We can use Fenwick Tree to keep track of prefix GCDs.
• A.

True

• B.

False

• 21.
In DSU, two elements having the same representatives might belong to different sets.
• A.

True

• B.

False

• 22.
In Kruskal’s Algorithm, DSU is used to find the edge with the lowest weight.
• A.

True

• B.

False

• 23.
Path compression in a tree with N nodes transforms find_set() operation from having time complexity [Blank] to [Blank]
• 24.
The depth of any tree with N nodes if we use union by rank is [Blank]
• 25.
Consider that in a rolling hash, we have a window of size 23. We shift the window by removing the first character and adding a new character at the end. The old and the window have [Blank] characters in common.
Related Topics Back to top