Data Structure Exam Quiz!

27 Questions | Total Attempts: 243

SettingsSettingsSettings
Data Structure Exam Quiz! - 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.
Back to Top Back to top