Tutorials
PPTs
Lecture Notes
Objective Questions
Lab ProgramsObjective Type Questions & Answers
Data Structures Objective Type Question Bank-Unit-5
1. What is the time complexity of the Brute Force Pattern Matching algorithm in the worst-case scenario?
A . O(n)
B . O(m)
C . O(n + m)
D . O(nm)
2. In the context of Brute Force Pattern Matching, what does `n` represent?
A . The length of the pattern
B . The length of the text
C . The number of matches found
D . The number of comparisons made
3. Which of the following best describes the Brute Force Pattern Matching algorithm?
A . It pre-processes the pattern to improve matching efficiency.
B . It matches the pattern against the text by checking for a match starting at each position in the text.
C . It uses a hash function to match the pattern with the text.
D . It requires additional memory proportional to the size of the pattern.
4. In Brute Force Pattern Matching, what happens if a mismatch is found?
A . The algorithm tries to match the next character of the pattern.
B . The pattern is shifted by one position in the text and the matching process starts again.
C . The text is pre-processed again.
D . The algorithm terminates immediately.
5. What is a major disadvantage of the Brute Force Pattern Matching algorithm?
A . It cannot handle large patterns.
B . It is too complex to implement.
C . It has a high time complexity in the worst-case scenario.
D . It requires additional space equal to the size of the text.
6. When is the Brute Force Pattern Matching algorithm considered efficient?
A . When the pattern is significantly longer than the text.
B . When the pattern and the text are of similar length.
C . When the pattern is short and the alphabet size is large.
D . When multiple patterns need to be matched in the same text.
7. Which of the following is true about the Brute Force Pattern Matching algorithm?
A . It requires pre-processing of the text.
B . It is the most efficient pattern matching algorithm in all cases.
C . It does not require any additional memory.
D . It can be optimized to skip some comparisons.
8. What is the space complexity of the Brute Force Pattern Matching algorithm?
A . O(1)
B . O(n)
C . O(m)
D . O(nm)
9. What aspect of the Boyer-Moore algorithm makes it perform faster than the Brute Force Pattern Matching algorithm in many cases?
A . The use of a prefix table
B . The use of hash functions
C . The use of Bad Character and Good Suffix heuristics
D . The use of dynamic programming
10. What is the best-case time complexity of the Boyer-Moore Pattern Matching algorithm?
A . O(n/m)
B . O(n + m)
C . O(n)
D . O(m)
11. What does the Bad Character Heuristic in the Boyer-Moore algorithm do?
A . It shifts the pattern by one position when a mismatch occurs.
B . It shifts the pattern to align the last occurrence of the mismatched character in the pattern with the text.
C . It skips alignments that would result in a mismatch.
D . It pre-processes the pattern to find all bad characters.
12. What does the Good Suffix Heuristic in the Boyer-Moore algorithm do?
A . It shifts the pattern based on the information gathered from the matched part of the pattern.
B . It compares the characters from the start of the pattern.
C . It ignores the suffix of the pattern.
D . It shifts the pattern by the length of the good suffix.
13. Which of the following is true about the preprocessing phase of the Boyer-Moore algorithm?
A . It only computes the bad character table.
B . It only computes the good suffix table.
C . It computes both the bad character and good suffix tables.
D . No preprocessing is done in Boyer-Moore algorithm.
14. In the context of the Boyer-Moore algorithm, what is the significance of the rightmost occurrence of a character?
A . It determines how the pattern should be aligned upon a mismatch.
B . It is used to compute the good suffix table.
C . It indicates the end of the pattern.
D . It is used to start the search from the right end of the pattern.
15. What is the worst-case time complexity of the Boyer-Moore Pattern Matching algorithm?
A . O(n/m)
B . O(n + m)
C . O(n)
D . O(mn)
16. Why is the Boyer-Moore algorithm generally faster than other pattern matching algorithms for long patterns?
A . Because it always processes every character of the text.
B . Because it does not process every character of the text in the worst case.
C . Because it uses extra memory to store the pattern.
D . Because it uses a hash function to match the pattern with the text.
17. What is the key concept behind the KMP algorithm that improves its efficiency compared to brute force pattern matching?
A . Skipping comparisons based on partial matches
B . Using a hash function to match the pattern
C . Shifting the pattern by the length of the mismatch
D . Recursively dividing the text into smaller parts
18. What does the prefix table (also known as the failure function or LPS array) in the KMP algorithm store?
A . The length of the longest prefix which is also a suffix for each substring of the pattern
B . The index of the next character to be compared in the text
C . The number of characters to be skipped for each mismatch
D . The hash values of all the prefixes of the pattern
19. What is the time complexity of the preprocessing phase (building the prefix table) in the KMP algorithm?
A . O(n)
B . O(m)
C . O(n + m)
D . O(m^2)
20. During the pattern matching phase, if a mismatch occurs at position mm in the pattern and position nn in the text, how does the KMP algorithm proceed?
A . It starts matching again from the beginning of the pattern.
B . It shifts the pattern by mm positions and continues matching.
C . It uses the prefix table to determine the next position in the pattern to compare.
D . It reverses the pattern and starts matching again.
21. What is the worst-case time complexity of the KMP Pattern Matching algorithm?
A . O(n/m)
B . O(n + m)
C . O(n)
D . O(mn)
22. In the KMP algorithm, if the prefix table at a position ii has a value kk, what does it imply?
A . The next character to match in the text is at position kk.
B . The next character to match in the pattern is at position kk.
C . The length of the longest proper prefix which is also a suffix up to position ii is kk.
D . kk characters should be skipped in the text.
23. How does the KMP algorithm handle the occurrence of a mismatch?
A . By backtracking in the text
B . By backtracking in the pattern
C . By using the prefix table to skip unnecessary comparisons in the pattern
D . By restarting the search from the next character in the text
24. Why is the KMP algorithm considered efficient for pattern matching in strings?
A . It never reexamines a character in the text that has already been examined.
B . It uses a binary search mechanism.
C . It sorts the pattern and the text before matching.
D . It compares the pattern and text character by character without skipping.
25. What is the primary advantage of using a standard trie for storing strings?
A . Efficient memory usage
B . Fast search times for prefixes
C . In-order traversal of strings
D . Quick sort of strings
26. In a standard trie, each node typically represents what?
A . A full string from the root to the node
B . A single character
C . The end of a string
D . A hash value of the string
27. What is the main difference between a standard trie and a compressed trie (also known as a radix tree)?
A . Compressed tries store entire strings at each node.
B . Compressed tries combine a sequence of nodes with only one child into a single node.
C . Compressed tries do not allow for the insertion of new strings.
D . Compressed tries require more memory than standard tries.
28. How does a compressed trie (radix tree) improve upon the space efficiency of a standard trie?
A . By eliminating all leaf nodes
B . By using a linked list instead of tree nodes
C . By merging nodes with single children into one node
D . By storing characters as bits instead of full characters
29. What does a suffix trie of a string SS represent?
A . All prefixes of SS
B . All suffixes of SS
C . All substrings of SS
D . All anagrams of SS
30. Which of the following operations can be performed efficiently using a suffix trie?
A . Finding the longest repeated substring in a string
B . Sorting a list of unrelated strings
C . Finding the minimum element in a numeric array
D . Balancing a binary search tree
31. What is a potential drawback of using suffix tries?
A . They cannot store certain types of strings.
B . They can be space-inefficient due to storing all suffixes.
C . They do not support search operations.
D . They only work with binary alphabets.
32. In the context of suffix tries, how is the substring search operation performed?
A . By checking each node for the substring
B . By traversing the path that corresponds to the characters of the substring
C . By reversing the trie and searching from the end
D . By converting the trie into a suffix array and searching
Fill in the Blanks
33. The ________ algorithm is the simplest method where the pattern is slid over the text one character at a time.
34. The Brute Force algorithm can be inefficient because it does not ________ any information from the text characters.
35. The ________ algorithm uses the bad character rule and the good suffix rule to improve the efficiency of pattern matching.
36. In the Boyer-Moore algorithm, the bad character rule shifts the pattern by aligning the last occurrence of a mismatched character in the pattern with its occurrence in the ________.
37. The ________ algorithm preprocesses the pattern to create an LPS (longest proper prefix which is also suffix) array to avoid unnecessary comparisons.
38. The time complexity of the Brute Force algorithm is generally O(nm) where n is the length of the text and m is the length of the ________.
39. The Boyer-Moore algorithm performs best when the alphabet size is ________, as it reduces the chance of a match with the bad character rule.
40. The KMP algorithm improves the time complexity to O(n + m) by not re-comparing characters that are already known to ________.
41. In the Boyer-Moore algorithm, the good suffix rule shifts the pattern such that the best matching prefix aligns with the suffix in the ________ that has been matched so far.
42. A Trie is a tree-like data structure that stores a dynamic set of strings. Each node in a Trie represents a single ________ of a string.
43. In a Trie, all the descendants of a node have a common ________.
44. The root node in a Trie represents an ________ string.
45. In a Trie, a node that represents the end of a string or a word is often marked with a special ________ marker.
46. The time complexity of searching for a key in a Trie is O(m), where m is the length of the key, making it very efficient compared to other data structures like ________ or ________.
47. Tries are particularly efficient for ________ operations, allowing for rapid re-traversal of shared key parts.
48. In a Trie, nodes may have as many children as there are characters in the ________, making it different from a binary search tree.
49. Tries are commonly used in applications like auto-complete, spell checking, and IP routing, where quick retrieval of ________ is crucial.
50. To save space, a common variation of Trie is ________ Trie, which merges nodes with a single child.
51. Unlike regular Tries, ________ Tries store all the suffixes of a given string and are used in various string-searching algorithms.
Relevant Materials :
☞ Data Structures Objective Type Question Bank-Unit-1 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-2 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-3 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-4 - [ DS ]
☞ Data Structures Objective Type Question Bank-Unit-5 - [ DS ]
Similar Materials :
☞ R - Programming MCQs - Unit-1 - [ R-Programming ]
☞ R - Programming MCQs - Unit-2 - [ R-Programming ]
☞ R - Programming MCQs - Unit-3 - [ R-Programming ]
☞ R - Programming MCQs - Unit-4 - [ R-Programming ]
☞ R - Programming MCQs - Unit-5 - [ R-Programming ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-1 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-2 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-3 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-4 - [ FLAT ]
☞ Formal Languages and Automata Theory (FLAT) MCQs - Unit-5 - [ FLAT ]
☞ PPS MCQs - Unit-1 - [ PPS ]
☞ PPS MCQs - Unit-2 - [ PPS ]
☞ PPS MCQs - Unit-3 - [ PPS ]
☞ PPS MCQs - Unit-4 - [ PPS ]
☞ PPS MCQs - Unit-5 - [ PPS ]
☞ Object Oriented Programming through Java MCQs - Unit-1 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-2 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-3 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-4 - [ OOP_JAVA ]
☞ Object Oriented Programming through Java MCQs - Unit-5 - [ OOP_JAVA ]
☞ Design and Analysis of Algorithms MCQs - Unit-1 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-2 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-3 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-4 - [ DAA ]
☞ Design and Analysis of Algorithms MCQs - Unit-5 - [ DAA ]
☞ Software Engineering MCQs - Unit-1 - [ SE ]
☞ Software Engineering MCQs - Unit-2 - [ SE ]
☞ Software Engineering MCQs - Unit-3 - [ SE ]
☞ Software Engineering MCQs - Unit-4 - [ SE ]
☞ Software Engineering MCQs - Unit-5 - [ SE ]
☞ Data Mining MCQs - Unit-1 - [ DM ]
☞ Data Mining MCQs - Unit-2 - [ DM ]
☞ Data Mining MCQs - Unit-3 - [ DM ]
☞ Data Mining MCQs - Unit-4 - [ DM ]
☞ Data Mining MCQs - Unit-5 - [ DM ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-1 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-2 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-3 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-4 - [ COA ]
☞ Computer Organization and Architecture (COA) Objective Question Bank-Unit-5 - [ COA ]
☞ Database Management System Objective Type Question Bank-Unit-1 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-2 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-3 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-4 - [ DBMS ]
☞ Database Management System Objective Type Question Bank-Unit-5 - [ DBMS ]
☞ Cyber Forensics Objective Type Question Bank-Part-2 - [ Cyber Forensics ]
☞ Cyber Forensics Objective Type Question Bank-Part-1 - [ Cyber Forensics ]
☞ Java Programming Objective Type Question Bank - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-1 - [ Java Programming ]
☞ Java Programming Objective Type Questions-Part-2 - [ Java Programming ]