Data Structure Exam Quiz!

27 Questions | By Bakhtiarhasan | Last updated: Mar 22, 2022 | Total Attempts: 243

Questions

Settings

Create your own Quiz

Questions and Answers

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

More Data Structure Quizzes

Insertion Sort Quiz Questions And Answers

Do you know what an insertion sort is? Here's an interesting Insertion Sort Quiz to test your knowledge. It is a simple sorting algorithm that builds the final sorted array one item at a time. This...

Questions: 10 | Attempts: 9134 | Last updated: Apr 24, 2022

Sample Question
What are the correct intermediate steps of the following data set when it is being sorted with theInsertionsort? 15,20,10,18

15,20,10,18 -- 10,15,20,18 -- 10,15,18,20 -- 10,15,18,20

15,18,10,20 -- 10,18,15,20 -- 10,15,18,20 -- 10,15,18,20

15,10,20,18 -- 15,10,18,20 -- 10,15,18,20

10, 20,15,18 -- 10,15,20,18 -- 10,15,18,20

Linked List Data Structure Quiz

Have you studied linked lists in data structure? Take this linked list quiz to check your knowledge of this section of data structure. A linked list is basically a linear collection of data elements whose order is not provided by...

Questions: 20 | Attempts: 7640 | Last updated: Mar 27, 2022

Sample Question
What are the basic components of a linked list?

Head and tail are the only important components

Data members for the information to be stored and a link to the next item

Generic class because without this linked list is not possible

None of the above

The Data Structure Trivia Exam: Quiz!

Do you have any idea what the data structure is? Data structure is a method that applies the appropriate structure and syntax to store and organize information. This quiz asks you what an array is, how to delete an item from an...

Questions: 20 | Attempts: 5030 | Last updated: Mar 22, 2022