1
What is the time complexity of the Brute Force Pattern Matching algorithm in the worst-case scenario?
Correct Answer
O(nm)
☑ MCQ PRACTICE
Data Structures Unit 5
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Data Structures - Unit-5
2
In the context of Brute Force Pattern Matching, what does 'n' represent?
Correct Answer
The length of the text
3
Which of the following best describes the Brute Force Pattern Matching algorithm?
Correct Answer
It matches the pattern against the text by checking for a match starting at each position in the text.
4
In Brute Force Pattern Matching, what happens if a mismatch is found?
Correct Answer
The pattern is shifted by one position in the text and the matching process starts again.
5
What is a major disadvantage of the Brute Force Pattern Matching algorithm?
Correct Answer
It has a high time complexity in the worst-case scenario.
6
When is the Brute Force Pattern Matching algorithm considered efficient?
Correct Answer
When the pattern is short and the alphabet size is large.
7
Which of the following is true about the Brute Force Pattern Matching algorithm?
Correct Answer
It does not require any additional memory.
8
What is the space complexity of the Brute Force Pattern Matching algorithm?
Correct Answer
O(1)
9
What aspect of the Boyer-Moore algorithm makes it perform faster than the Brute Force Pattern Matching algorithm in many cases?
Correct Answer
The use of Bad Character and Good Suffix heuristics
10
What is the best-case time complexity of the Boyer-Moore Pattern Matching algorithm?
Correct Answer
O(n/m)
11
What does the Bad Character Heuristic in the Boyer-Moore algorithm do?
Correct Answer
It shifts the pattern to align the last occurrence of the mismatched character in the pattern with the text.
12
What does the Good Suffix Heuristic in the Boyer-Moore algorithm do?
Correct Answer
It shifts the pattern based on the information gathered from the matched part of the pattern.
13
Which of the following is true about the preprocessing phase of the Boyer-Moore algorithm?
Correct Answer
It computes both the bad character and good suffix tables.
14
In the context of the Boyer-Moore algorithm, what is the significance of the rightmost occurrence of a character?
Correct Answer
It determines how the pattern should be aligned upon a mismatch.
15
What is the worst-case time complexity of the Boyer-Moore Pattern Matching algorithm?
Correct Answer
O(n + m)
16
Why is the Boyer-Moore algorithm generally faster than other pattern matching algorithms for long patterns?
Correct Answer
Because it does not process every character of the text in the worst case.
17
What is the key concept behind the KMP algorithm that improves its efficiency compared to brute force pattern matching?
Correct Answer
Skipping comparisons based on partial matches
18
What does the prefix table (also known as the failure function or LPS array) in the KMP algorithm store?
Correct Answer
The length of the longest prefix which is also a suffix for each substring of the pattern
19
What is the time complexity of the preprocessing phase (building the prefix table) in the KMP algorithm?
Correct Answer
O(m)
20
During the pattern matching phase, if a mismatch occurs at position m in the pattern and position n in the text, how does the KMP algorithm proceed?
Correct Answer
It uses the prefix table to determine the next position in the pattern to compare.
21
What is the worst-case time complexity of the KMP Pattern Matching algorithm?
Correct Answer
O(n + m)
22
In the KMP algorithm, if the prefix table at a position i has a value k, what does it imply?
Correct Answer
The length of the longest proper prefix which is also a suffix up to position i is k.
23
How does the KMP algorithm handle the occurrence of a mismatch?
Correct Answer
By using the prefix table to skip unnecessary comparisons in the pattern
24
Why is the KMP algorithm considered efficient for pattern matching in strings?
Correct Answer
It never reexamines a character in the text that has already been examined.
25
What is the primary advantage of using a standard trie for storing strings?
Correct Answer
Fast search times for prefixes
26
In a standard trie, each node typically represents what?
Correct Answer
A single character
27
What is the main difference between a standard trie and a compressed trie (also known as a radix tree)?
Correct Answer
Compressed tries combine a sequence of nodes with only one child into a single node.
28
How does a compressed trie (radix tree) improve upon the space efficiency of a standard trie?
Correct Answer
By merging nodes with single children into one node
29
What does a suffix trie of a string S represent?
Correct Answer
All suffixes of S
30
Which of the following operations can be performed efficiently using a suffix trie?
Correct Answer
Finding the longest repeated substring in a string
31
What is a potential drawback of using suffix tries?
Correct Answer
They can be space-inefficient due to storing all suffixes.
32
In the context of suffix tries, how is the substring search operation performed?
Correct Answer
By traversing the path that corresponds to the characters of the substring
Fill in the Blanks
33
The ________ algorithm is the simplest method where the pattern is slid over the text one character at a time.
Correct Answer
Brute Force
34
The Brute Force algorithm can be inefficient because it does not ________ any information from the text characters.
Correct Answer
reuse
35
The ________ algorithm uses the bad character rule and the good suffix rule to improve the efficiency of pattern matching.
Correct Answer
Boyer-Moore
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 ________.
Correct Answer
text
37
The ________ algorithm preprocesses the pattern to create an LPS (longest proper prefix which is also suffix) array to avoid unnecessary comparisons.
Correct Answer
Knuth-Morris-Pratt (KMP)
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 ________.
Correct Answer
pattern
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.
Correct Answer
large
40
The KMP algorithm improves the time complexity to O(n + m) by not re-comparing characters that are already known to ________.
Correct Answer
match
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.
Correct Answer
text
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.
Correct Answer
character
43
In a Trie, all the descendants of a node have a common ________.
Correct Answer
prefix
44
The root node in a Trie represents an ________ string.
Correct Answer
empty
45
In a Trie, a node that represents the end of a string or a word is often marked with a special ________ marker.
Correct Answer
end-of-word
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 ________.
Correct Answer
arrays, linked lists
47
Tries are particularly efficient for ________ operations, allowing for rapid re-traversal of shared key parts.
Correct Answer
prefix-based search
48
In a Trie, nodes may have as many children as there are characters in the ________, making it different from a binary search tree.
Correct Answer
alphabet
49
Tries are commonly used in applications like auto-complete, spell checking, and IP routing, where quick retrieval of ________ is crucial.
Correct Answer
strings
50
To save space, a common variation of Trie is ________ Trie, which merges nodes with a single child.
Correct Answer
compressed
51
Unlike regular Tries, ________ Tries store all the suffixes of a given string and are used in various string-searching algorithms.
Correct Answer
suffix